Guoliang Li
ABSTRACT
With the ever-increasing number of spatio-textual objects, many applications require to find objects close to a given query point in spatial databases. In this paper, we study the problem of keyword-based k-nearest neighbor search in spatial databases, which, given a query point and a set of keywords, finds k-nearest neighbors of the query point that contain all query keywords. To efficiently answer such queries, we propose a new indexing framework by integrating a spatial component and a textual component, which can efficiently prune search space in terms of both spatial information and textual descriptions. We develop effective index structures and pruning techniques to improve query performance. Experimental results show that our approach significantly outperforms state-of-the-art methods.
- A. Cary, O. Wolfson, and N. Rishe. Efficient and scalable method for processing top-k spatial boolean queries. In SSDBM, pages 87--95, 2010. Google Scholar
Digital Library
- G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB, 2009. Google ScholarDigital Library
- J. Fan, G. Li, L. Zhou, S. Chen, and J. Hu. Seal: Spatio-textual similarity search. PVLDB, 5(9):824--835, 2012. Google ScholarDigital Library
- I. D. Felipe, V. Hristidis, and N. Rishe. Keyword search on spatial databases. In ICDE, 2008. Google ScholarDigital Library
- R. Hariharan, B. Hore, C. Li, and S. Mehrotra. Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems. In SSDBM, 2007. Google ScholarDigital Library
- G. Li, J. Xu, and J. Feng. Desks: Direction-aware spatial keyword search. In ICDE, 2012. Google ScholarDigital Library
- D. Wu, M. L. Yiu, G. Cong, and C. S. Jensen. Joint top-k spatial keyword query processing. In IEEE TKDE, 2012.Google ScholarDigital Library
- B. Yao, F. Li, M. Hadjieleftheriou, and K. Hou. Approximate string search in spatial databases. In ICDE, 2010.Google ScholarCross Ref
- D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa. Keyword search in spatial databases: Towards searching by document. In ICDE, 2009. Google ScholarDigital Library
- Y. Zhou, X. Xie, C. Wang, Y. Gong, and W.-Y. Ma. Hybrid index structures for location-based web search. In CIKM, 2005. Google ScholarDigital Library
Index Terms
- Keyword-based k-nearest neighbor search in spatial databases
Recommendations
K-Nearest Neighbor Finding Using MaxNearestDist
Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...
Fast k-Nearest Neighbor Searching in Static Objects
The k-nearest neighbor searching is a classical problem that has been seriously studied, due to its many important applications. The paper proposes an efficient algorithm to search the k-nearest neighbors for static objects. Since locations of static ...
Ranked Reverse Nearest Neighbor Search
Given a set of data points P and a query point q in a multidimensional space, Reverse Nearest Neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-Nearest Neighbor (RkNN) query (where k ≥ 1) generalizes RNN query to find ...
Comments