Efficient Algorithms and Cost Models for Reverse Spatial-Keyword k-Nearest Neighbor Search

Geographic objects associated with descriptive texts are becoming prevalent, justifying the need for spatial keyword queries that consider both locations and textual descriptions of the objects. Specifically, the relevance of an object to a query is measured by spatial-textual similarity that is based on both spatial proximity and textual similarity. In this article, we introduce the Reverse Spatial-Keyword k-Nearest Neighbor (RSKkNN) query, which finds those objects that have the query as one of their k nearest spatial-textual objects. The RSKkNN queries have numerous applications in online maps and GIS decision support systems. To answer RSKkNN queries efficiently, we propose a hybrid index tree, called IUR-tree (Intersection-Union R-Tree) that effectively combines location proximity with textual similarity. Subsequently, we design a branch-and-bound search algorithm based on the IUR-tree. To accelerate the query processing, we improve IUR-tree by leveraging the distribution of textual description, leading to some variants of the IUR-tree called clustered IUR-tree (CIUR-tree) and combined clustered IUR-tree (C²IUR-tree), for each of which we develop optimized algorithms. We also provide a theoretical cost model to analyze the efficiency of our algorithms. Our empirical studies show that the proposed algorithms are efficient and scalable