Query Pre-Processing of Topological Constraints: Comparing a Composition-Based with a Neighborhood-Based Approach

Andrea Rodríguez, Max Egenhofer, and Andreas Blaser
SSTD '03 -- Eighth International Symposium on Spatial and Temporal Databases, Santorini, Greece, in: T. Hadzilacos, Y. Manolopoulos, J. Roddick, and Y. Theodoridis (eds.), Lecture Notes in Computer Science, Vol. 2750, Springer, pp. 362-379, July 2003.

Abstract

Checking query consistency and constraint redundancy plays an important role in pre-processing spatial queries, where the goal is to define a search space that leads to an efficient search process. This paper focuses on pre-processing of spatial similarity queries, where the query is given by a visual example, such as an example data set or a sketch. It derives and compares two strategies for minimizing topological constraints: (1) elimination of topological relations that are implied uniquely by composition and (2) restriction to topological relations that relate near-neighbor objects, as determined by a Delaunay triangulation. In both cases, the query processing approach is to solve a constraint satisfaction problem over a graph of binary topological relations. Individuals and the combination of the composition- and neighborhood-based strategies were implemented and compared with respect to their ability to reduce topological constraints, and with respect to the quality of the results obtained by a similarity-based searching that uses these pre-processing strategies. The main conclusion of this work is that similarity queries that are formulated in a visual language should exploit the metric characteristics of the configuration, even if only topological constraints are considered for making matches.

PDF