Data Management

Efficient and Scalable Method for Processing Top-k Spatial Boolean Queries

Date Added: Apr 2010
Format: PDF

In this paper, the authors present a novel method to efficiently process top-k spatial queries with conjunctive Boolean constraints on textual content. Their method combines an R-tree with an inverted index by the inclusion of spatial references in posting lists. The result is a diskresident, dual-index data structure that is used to proactively prune the search space. R-tree nodes are visited in best-first order. A node entry is placed in the priority queue if there exists at least one object that satisfies the Boolean condition in the subtree pointed by the entry; otherwise, the subtree is not further explored. They show via extensive experimentation with real spatial databases that their method has increased performance over alternate techniques while scaling to large number of objects.