Fast Nearest Neighbor Search with Keywords
Authors:
- 29 April 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 26 (4) , 878-888
Abstract
Conventional spatial queries, such as range search and nearest neighbor retrieval, involve only conditions on objects' geometric properties. Today, many modern applications call for novel forms of queries that aim to find objects satisfying both a spatial predicate, and a predicate on their associated texts. For example, instead of considering all the restaurants, a nearest neighbor query would instead ask for the restaurant that is the closest among those whose menus contain “steak, spaghetti, brandy” all at the same time. Currently, the best solution to such queries is based on the IR 2 -tree, which, as shown in this paper, has a few deficiencies that seriously impact its efficiency. Motivated by this, we develop a new access method called the spatial inverted index that extends the conventional inverted index to cope with multidimensional data, and comes with algorithms that can answer nearest neighbor queries with keywords in real time. As verified by experiments, the proposed techniques outperform the IR 2 -tree in query response time significantly, often by a factor of orders of magnitude.Keywords
This publication has 19 references indexed in Scilit:
- Spatial Keyword Querying2012
- Reverse spatial and textual k nearest neighbor search2011
- Efficient retrieval of the top-k most relevant spatial web objectsProceedings of the VLDB Endowment, 2009
- Algorithms and Data Structures for External MemoryFoundations and Trends® in Theoretical Computer Science, 2008
- Keyword Search on Spatial Databases2008
- Processing Spatial-Keyword (SK) Queries in Geographic Information Retrieval (GIR) Systems19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), 2007
- Discover2002
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Signature filesACM Transactions on Information Systems, 1984
- Mathematical analysis of various superimposed coding methodsAmerican Documentation, 1960