Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 摘要粗译

ABSTRACT
In this paper, we study the problem of continuous monitoring of reverse k nearest neighbor queries. Existing continuous reverse nearest neighbor monitoring techniques are sensitive towards 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 queries by assigning each object and query with a rectangular 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 by-product, 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 to guide an effective selection of such rectangular safe regions. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.

摘要
本文中，我们研究了持继检测反最近邻查询问题。现存的持续反最近邻查询技术当对象或查询发生移动情况很敏感。比如说，当查询的位置发生变动时查询结果会被重新计算。我们提出一个持续反k最近邻查询的框架，通过设定每一个对象或查询的安全区域矩形，从而当查询和对象在他们的各自的安全区域中的时侯就不必进行重新计算了。这种方法极大节约了计算代价。作为副产品，我们的框架同时在C-S架构中，也压缩了通信代价，因为一个对象不向服务器报告他的位置，除非它离开了安排区域或服务器发出位置更新请求。我们同时也进行了严格的代价分析，产生了一个有效的安全矩形区域的选择。大量的实验表明，我们的技术在计算代价和通信代价方面，数量级地优于现存的技术。

＝＝＝＝＝＝＝＝

以上摘要为粗译，供仅参考，欢迎指正与讨论交流。