Influence zone: Efficiently processing reverse k nearest neighbors queries

Publisher:
IEEE
Publication Type:
Conference Proceeding
Citation:
2011 IEEE 27th International Conference on Data Engineering, 2011, pp. 577 - 588
Issue Date:
2011-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005462OK.pdf307.77 kB
Adobe PDF
Given a set of objects and a query q, a point p is called the reverse k nearest neighbor (RkNN) of q if q is one of the k closest objects of p. In this paper, we introduce the concept of influence zone which is the area such that every point inside this area is the RkNN of q and every point outside this area is not the RkNN. The influence zone has several applications in location based services, marketing and decision support systems. It can also be used to efficiently process RkNN queries. First, we present efficient algorithm to compute the influence zone. Then, based on the influence zone, we present efficient algorithms to process RkNN queries that significantly outperform existing best known techniques for both the snapshot and continuous RkNN queries. We also present a detailed theoretical analysis to analyse the area of the influence zone and IO costs of our RkNN processing algorithms. Our experiments demonstrate the accuracy of our theoretical analysis.
Please use this identifier to cite or link to this item: