Spatial query processing for sketch-based query using heuristics

Sketching the spatial query is one of the leading spatial database query methods (Blaser (2000)) for searching similar configurations. However, when the sketched spatial scene is processed with ordinary query processing methods, it does not achieve the efficiency that is desired especially dealing with large datasets (N>1000). Therefore indexing and heuristics are proposed to be able to help in reducing the search space and enhance the search performance (Papadias and Mamoulis (1999)) for configuration similarity. The most prominent indexing method of spatial objects is the R-tree. With the indexed spatial objects, then heuristics can be applied to improve the searching efficiency i.e. reduce the searching cost and increase the number of solutions to the query. This paper aims to discuss the generic R-tree model, then discusses the heuristics that can be applied to utilize the data structure in the searching of configuration similarity in spatial query by sketch.