Voronoi图的生成及近邻关系查询方法

计算机应用 ›› 2014, Vol. 34 ›› Issue (12): 3470-3474.

Voronoi图的生成及近邻关系查询方法

张丽平,李松,麻琳,唐远新,郝晓红

哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080

收稿日期:2014-06-10 修回日期:2014-07-30 发布日期:2014-12-31 出版日期:2014-12-01
通讯作者: 张丽平
作者简介:张丽平(1976-）,女,辽宁铁岭人, 副教授,硕士,主要研究方向:计算几何、数据库;李松(1977-),男,江苏沛县人,副教授,博士,主要研究方向:数据库、数据挖掘；麻琳(1981-),女,黑龙江哈尔滨人,助理研究员,硕士,主要研究方向:数据挖掘；唐远新(1972-),男,黑龙江哈尔滨人,副教授,硕士,主要研究方向:图像处理、计算几何；郝晓红(1969-）,女,黑龙江哈尔滨人, 高级实验师,硕士,主要研究方向:软件工程、数据库。
基金资助:
黑龙江省教育厅科学技术研究项目

Methods of Voronoi diagram construction and near neighbor relations query

ZHANG Liping,LI Song,MA Lin,TANG Yuanxin,HAO Xiaohong

School of Computer Science and Technology, Harbin University of Science and Technology, Harbin Heilongjiang 150080, China

Received:2014-06-10 Revised:2014-07-30 Online:2014-12-31 Published:2014-12-01
Contact: ZHANG Liping

摘要/Abstract

摘要：

针对构建Voronoi图的方法的生成效率较低,构建复杂度较高的问题,提出了利用多方法交叉融合进行Voronoi图的构建与更新的方法。为了提高空间数据最近邻查询的效率,提出了基于Voronoi图和Voronoi多边形最小内切圆的最近邻查询方法；针对查询点位置频繁变化的情况,提出了基于Voronoi图和Voronoi多边形最小外接矩形的最近邻查询方法；为了提高对偶近邻对和最近对的查询效率,利用Voronoi多边形和对应的最小内切圆进行过滤和查询,提出了统一查询对偶近邻对和最近对的新方法。实验结果表明,所提方法解决了因数据分布不均导致的额外计算量的开销问题,在数据集规模较大和查询频率较高时具有一定的优势。

Abstract:

The existing methods of constructing Voronoi diagram have low efficiency and high complexity, to remedy the disadvantages, a new method of constructing and updating Voronoi diagram based on the hybrid methods was given to query the nearest neighbor of the given spatial data effectively, and a new method of searching the nearest neighbor based on Voronoi diagram and the minimum inscribed circle was presented. To deal with the frequent, changes of the query point position, the method based on Voronoi diagram and the minimum bounding rectangle was proposed. To improve the efficiency of the dual nearest neighbor pair and closest pair query, a new method was given based on Voronoi polygons and their minimum inscribed circles. The experimental results show that the proposed methods reduce the additional computation caused by the uneven distribution of data and have a large advantage for the big dataset and the frequent query.

中图分类号:

TP311.13

张丽平李松麻琳唐远新郝晓红. Voronoi图的生成及近邻关系查询方法[J]. 计算机应用, 2014, 34(12): 3470-3474.

ZHANG Liping LI Song MA Lin TANG Yuanxin HAO Xiaohong. Methods of Voronoi diagram construction and near neighbor relations query[J]. Journal of Computer Applications, 2014, 34(12): 3470-3474.

参考文献

［1］LI S, ZHANG L, SUN D. Spatial relation query and analysis［M］. Harbin: Harbin Institute of Technology Press, 2011.(李松,张丽平,孙冬璞. 空间关系查询与分析［M］.哈尔滨:哈尔滨工业大学出版社,2011.)
［2］SACL J R, URRUTIA J. Voronoi diagrams. handbook on computational geometry［M］. Ottawa: Elsevier Science, 2006:201-290.
［3］DONG L, WU Y, ZHOU S. Constructing the Voronoi diagram of planar point set in parallel［C］// Proceedings of the 2009 International Conference on Computational Intelligence and Software Engineering. Piscataway: IEEE, 2009: 1-5.
［4］ZHANG J, DU Q. The generating algorithm of Voronoi after adding and deleting points［J］. Journal of Graphics, 2013, 34(1): 46-49.(张娟,杜全叶. 增删点后的Voronoi图生成算法［J］. 图学学报, 2013, 34(1): 46-49.)
［5］ZHOU T, PENG Z, MI X. An improved Delaunay triangle network growth algorithm and its implementation［J］. Journal of Graphics, 2013, 34(5):12-15.(周婷,彭正洪,密新武. Delaunay三角网生长算法改进与实现［J］. 图学学报, 2013, 34(5): 12-15.)
［6］XIE Z. Divide-and-conguer algorithm for constructing Delaunay triangulation of planar points［J］. Computer Engineering and Design,2012,33(7):2652-2658.(谢增广. 平面点集Delaunay三角剖分的分治算法［J］. 计算机工程与设计, 2012, 33(7):2652-2658.)
［7］LI S, HAO Z. Methods for handling nearest neighbor spatial relations on spherical surface［J］.Computer Engineering, 2010, 36(6): 91-93.(李松,郝忠孝. 球面上最近邻空间关系处理方法［J］. 计算机工程, 2010,36(6):91-93.)
［8］ZHANG L, LI S, LIU W. New methods of strong neighborhood pair query［J］. Computer Engineering and Applications, 2009, 45(27):123-126.(张丽平,李松,刘文强. 强邻近对查询的新方法［J］. 计算机工程与应用, 2009,45(27):123-126.)
［9］ZHANG L, LI S, LI L, et al. Simple continues near neighbor chain query of the datasets based on the R tree［J］. Journal of Computational Information Systems,2012,8(22): 915-916.
［10］LI S, ZHANG L, CAI Z. Query method of simple continus near neighbor chain in dataset［J］. Computer Engineering, 2012, 38(4): 82-84.(李松,张丽平,蔡志涛. 数据集中的单纯型连续近邻链查询方法［J］. 计算机工程,2012,38(4):82-84.)
［11］ZHANG L, LI S, ZHAO J, et al. Simple continues near neighbor chain query in constrained regions［J］. Journal of Computer Applications, 2014,34(2):406-410.(张丽平, 李松,赵纪桥,等. 受限区域内的单纯型连续近邻链查询方法［J］. 计算机应用,2014,34(2):406-410.)
［12］MIAO D, SHI S, LI J. An algorithm on probabilistic frequent nearest neighbor query over snapshots of uncertain database with locally correlation［J］. Journal of Computer Research and Development, 2011, 48(10):1812-1822.(苗东菁,石胜飞,李建中.一种局部相关不确定数据库快照集合上的概率频繁最近邻算法［J］.计算机研究与发展,2011,48(10):1812-1822.)
［13］HICHAM G E, MOHAMED F M. Continuous aggregate nearest neighbor queries［J］. GeoInformatica, 2013,17(1): 63-95.
［14］YUAN P, SHA C, WANG X, et al. c-approximate nearest neighbor query algorithm based on learning for high dimensional data［J］. Journal of Software, 2012,23(8):2018-2031.(袁培森,沙朝锋,王晓玲,等. 一种基于学习的高维数据c-近似最近邻查询算法［J］. 软件学报, 2012,23(8):2018-2031.)〖WW)〗〖HT〗〖HQK〗〖FL)〗

[1]	高威刘丽华和斌涛邓方安. 区块链共识机制与改进算法研究进展[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[3]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[4]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[5]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[6]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	蒋辉, 闫秋艳, 姜竹郡. 面向多元时间序列异常检测的对称正定自编码器方法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3294-3299.
[9]	宋洪涛, 于江生, 韩启龙. 工业多元时序数据质量评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1743-1750.
[10]	孟玉飞, 武优西, 王珍, 李艳. 对比保序模式挖掘算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3740-3746.
[11]	王佳鑫, 颜嘉麒, 毛谦昂. 加密数字货币监管技术研究综述[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 2983-2995.
[12]	黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.
[13]	金泳, 高扬华, 潘晓华, 沈诗婧, 朱心洲. 采用数据血缘的数据热度预测方法[J]. 《计算机应用》唯一官方网站, 2023, 43(S1): 119-125.
[14]	马志峰, 于俊洋, 王龙葛. 多样性表示的深度子空间聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 407-412.
[15]	王旭, 申玉民, 熊晓芸, 李鹏, 王金龙. 基于哈希图的建筑物联网数据管理方法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2471-2480.