Approximating geographical queries

This article proposes a graph-theoretic methodology for query approximation in Geographic Information Systems, enabling the relaxation of three kinds of query constraints: topological, semantic and structural. An approximate query is associated with a value corresponding to the degree of similarity with the original query. Such a value is computed for topological constraints on the basis of the topological distance between configurations, for semantic constraints using the information content approach, and for structural constraints revisiting the maximum weighted matching problem in bipartite graphs. Finally, the high correlation of our proposal with human judgment is demonstrated by an experiment.