A Survey on Nearest Neighbor Search with Keywords

Many applications require finding objects closest to a specified location that contains a set of s. 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. The problems of nearest neighbor search on spatial data and search on text data have been extensively studied separately. In this work, we present an efficient method to answer top-k spatial queries. To do so, we introduce an indexing structure called IR2-Tree (Information Retrieval R-Tree) which combines an R-Tree with superimposed text signatures. To increase the efficiency of nearest neighbor search 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 s in real time. To answer mCK m-closest s queries efficiently, we introduce a new index called the bR*-tree, which is an extension of the R*-tree.