动态创建局部Voronoi图的连续近邻查询优化方法

"这篇论文探讨了如何利用动态创建局部Voronoi图来高效解决连续近邻查询的问题，特别是在时空数据库的背景下。作者王淼和郝忠孝提出了一个基于分支限界思想的方法，以减少k阶Voronoi图的构建成本。他们通过限制Voronoi图的生成范围，仅在查询段内所有点的k个近邻上界内构建局部的k阶Voronoi图，从而显著降低了查询复杂性。" 在计算机科学领域，尤其是在地理信息系统和时空数据库中，连续近邻查询是一项重要的任务，它要求找到一系列查询点的最近邻。传统的k阶Voronoi图是解决此类问题的有效工具，因为它能直观地表示出空间中的点与其最近邻之间的关系。然而，对于连续的查询，全量的k阶Voronoi图构建可能会带来巨大的计算和存储开销，这在实际应用中是不切实际的。 Voronoi图是一种分割空间的方式，每个点的区域（Voronoi细胞）包含了所有距离该点比其他任何点更近的点。k阶Voronoi图则扩展了这一概念，考虑了每个点的前k个最近邻。在本文中，作者意识到k阶Voronoi图在连续近邻查询中的优势，但同时也指出其实施的困难。 为了解决这个问题，论文引入了分支限界的思想。分支限界是一种搜索算法，常用于优化问题，通过设定上限来避免无效的搜索分支。在这里，作者使用分支限界来确定预创建Voronoi图时所需生成点的范围上界，有效地减少了计算的范围。 具体来说，论文提出的方法是在查询序列的每个时刻，仅构建当前查询点及其k个近邻的局部Voronoi图。这种方法不仅降低了计算量，还能适应查询的变化，使得在连续近邻查询中保持高效性能。通过这种方式，他们成功地降低了基于Voronoi图的连续k近邻查询的代价，提高了系统的响应速度和效率。 总结起来，这篇论文的研究成果对于时空数据库的查询优化具有重要意义，特别是对于那些需要频繁进行连续近邻查询的应用，如交通监控、环境监测或紧急响应系统等。通过动态创建局部Voronoi图，可以实现对大规模数据集的快速近邻检索，而无需预先构建完整的Voronoi图，从而在保证查询精度的同时，显著降低了计算资源的消耗。