Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks

Publisher:
Springer
Publication Type:
Journal Article
Citation:
VLDB Journal, 2012, 21 (1), pp. 69 - 95
Issue Date:
2012-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005444OK.pdfPublished Version2.13 MB
Adobe PDF
In this paper, we study the problem of continuous monitoring of reverse k nearest neighbors queries in Euclidean space as well as in spatial networks. Existing techniques are sensitive toward objects and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor (RkNN) queries by assigning each object and query with a safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a byproduct, our framework also reduces the communication cost in client---server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis for our Euclidean space RkNN algorithm. We show that our techniques can also be applied to answer bichromatic RkNN queries in Euclidean space as well as in spatial networks. Furthermore, we show that our techniques can be extended for the spatial networks that are represented by directed graphs. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.
Please use this identifier to cite or link to this item: