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架构下压缩了通信代价，因为一个目标不再向服务器报告位置，除非离开了它的安全区域或服务器发出了位置更新请求。我们同时也进行了严格的代价分析，从而有效地的选择了这样的一个安全区域。广泛的实验表明，我们技术在计算代价和通信代价方面以数量级的方式胜过现存技术。

------------

以上为个人研究时粗译，欢迎交流指正。