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

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

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

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

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

收稿日期:2014-06-10 修回日期:2014-07-30 出版日期:2014-12-01 发布日期:2014-12-31
通讯作者: 张丽平
作者简介:张丽平(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-01 Published:2014-12-31
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]. 计算机应用, 2021, 41(8): 2396-2405.
[2]	冯钧王秉发陆佳民. 分布式资源描述框架数据管理系统查询性能评价[J]. 计算机应用, 0, (): 0-0.
[3]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[4]	林定康颜嘉麒巴·楠登符朕皓姜皓晨. 门罗币匿名及追踪技术综述[J]. 计算机应用, 0, (): 0-0.
[5]	沈忱, 邰凌翔, 彭煜玮. 面向自动参数调优的动态负载匹配方法[J]. 计算机应用, 2021, 41(3): 657-661.
[6]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[7]	兰海, 韩珂, 申砾, 崔秋, 彭煜玮. TiDB的多索引访问优化[J]. 计算机应用, 2020, 40(2): 410-415.
[8]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[9]	万静, 郑龙君, 何云斌, 李松. 高维不确定数据的子空间聚类算法[J]. 计算机应用, 2019, 39(11): 3280-3287.
[10]	李博, 张晓, 颜靖艺, 李可威, 李恒, 凌玉龙, 张勇. 基于值差度量和聚类优化的K最近邻算法在银行客户行为预测中的应用[J]. 计算机应用, 2019, 39(9): 2784-2788.
[11]	李耘书, 滕飞, 李天瑞. 基于微操作的Hadoop参数自动调优方法[J]. 计算机应用, 2019, 39(6): 1589-1594.
[12]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[13]	朱跃龙, 朱晓晓, 王继民. 基于子序列全连接和最大团的时间序列模体发现算法[J]. 计算机应用, 2019, 39(2): 414-420.
[14]	尹远, 张昌, 文凯, 郑云俊. 基于DiffNodeset结构的最大频繁项集挖掘算法[J]. 计算机应用, 2018, 38(12): 3438-3443.
[15]	曲立平, 吴家喜. 基于评分可靠性的跨域个性化推荐方法[J]. 计算机应用, 2018, 38(11): 3081-3083.