In:
ACM Transactions on Database Systems, Association for Computing Machinery (ACM), Vol. 39, No. 2 ( 2014-05), p. 1-46
Abstract:
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 (RSK k NN) query, which finds those objects that have the query as one of their k -nearest spatial-textual objects. The RSK k NN queries have numerous applications in online maps and GIS decision support systems. To answer RSK k NN 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 2 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.
Type of Medium:
Online Resource
ISSN:
0362-5915
,
1557-4644
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2014
detail.hit.zdb_id:
196155-X
detail.hit.zdb_id:
2006335-0
