Publication Type

Journal Article

Version

acceptedVersion

Publication Date

5-2015

Abstract

Reverse k nearest neighbor (RkNN) queries have a broad application base such as decision support, profile-based marketing, and resource allocation. Previous work on RkNN search does not take textual information into consideration or limits to the Euclidean space. In the real world, however, most spatial objects are associated with textual information and lie on road networks. In this paper, we introduce a new type of queries, namely, reverse top-k Boolean spatial keyword (RkBSK) retrieval, which assumes objects are on the road network and considers both spatial and textual information. Given a data set P on a road network and a query point q with a set of keywords, an RkBSK query retrieves the points in P that have q as one of answer points for their top-k Boolean spatial keyword queries. We formalize the RkBSK query and then propose filter-and-refinement framework based algorithms for answering RkBSK search with arbitrary k and no any pre-computation. To accelerate the query process, several novel pruning heuristics that utilize both spatial and textual information are employed to shrink the search space efficiently. In addition, a new data structure called count tree has been developed to further improve query performance. A comprehensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness of our presented pruning heuristics and the performance of our proposed algorithms.

Keywords

Boolean Spatial Keyword Query, Reverse Top-k Boolean Spatial Keyword Query, Road Network, Query Processing.

Discipline

Computer Sciences | Databases and Information Systems | Numerical Analysis and Scientific Computing | Transportation

Publication

IEEE Transactions on Knowledge and Data Engineering (TKDE)

Volume

27

Issue

5

First Page

1205

Last Page

1218

ISSN

1041-4347

Identifier

10.1109/TKDE.2014.2365820

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/TKDE.2014.2365820

Download

Share

COinS