Efficient Algorithms to Monitor Continuous Constrained k Nearest Neighbor Queries (摘要粗译)

Abstract. Continuous monitoring of spatial queries has received significant research attention in the past few years. In this paper, we propose two efficient algorithms for the continuous monitoring of the constrained k nearest neighbor (kNN) queries. In contrast to the conventional k nearest neighbors (kNN) queries, a constrained kNN query considers only the objects that lie within a region specified by some user defined constraints (e.g., a polygon). Similar to the previous works, we also use grid-based data structure and propose two novel grid access methods. Our proposed algorithms are based on these access methods and guarantee that the number of cells that are accessed to compute the constrained kNNs is minimal. Extensive experiments demonstrate that our algorithms are
several times faster than the previous algorithm and use considerably less memory.

监测持续约束k最近邻查询的有效算法.

摘要:空间查询的持续监测在过去几年中已经有很多优秀的研究成果.本文中,我们设计了两个有效的约束k最近邻(knn)查询持续监测算法.为了和常见的k最近邻(knn)查询相对照,一个约束knn查询只包括处于由用户定义的固定区域(比如说多边形)的对象.类似以前的工作,我们同样使用了基于网格的数据结构,并并且设计两个新的网格存取方法.我们设计的算法基于这些存取方法,并且保证了存取与计算约束knn的单元格数据最小.大量的实验表明我们的算法比以前的算法更快,而且使用相当少的内存空间.

=========

以上为论文简单粗译,请大家指正与交流.