基于Voronoi图的最近邻查询的索引结构的研究

第２２卷第６期　２ＯＯ６年１１月　齐齐哈尔大学学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｑｉｑｉｈａｒ　Ｕｎ￣ｅｍ｝ｂ，　Ｖｏ１．２２，Ｎｏ．６　ＮＯＷ，，２００６　基于．Ｖｏｍｎｏｉ图的最近邻查询的索引结构的研究　王淼　。　（齐齐哈尔大学计算机与控制工程学院。黑龙江齐齐哈尔１６１００６）　摘耍：基于ｖ啪Ｉｍｉ图的最近邻查询在计算几何中已被研究了相当长一段时间　但在以往的研究中，基于Ｖｏｒｏｎｏｉｌ￣　的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的。却很少被提及。本文把传统的Ｒ树和　Ｖｏｍｎｏｉ图在解决最近邻查询问题中的优越性相结合，提出了一种新的索引结构：ＶＲ树。进而提出了基于ＶＲ树索引　结构的Ｎ　喳询算法并对这该算法进行分析，在理论上证明了这个算法较基于Ｒ树索引结构的最近邻查询算法优。　关键词：Ｖｏｒｏｎｏｉ［￣；最近邻查询；ｖＲ树　中图分类号：ＴＰ３　１　１．１３　１　文献标识码：Ａ　文章编号：１００７－９８４Ｘ（２００６）０６－００５６－ｏ３　ｌ预备知识．　，　’　时，Ｐｉ锄。其中　，　ｔ　’　定义１（Ｖｏｒｏｎｏｉ图）Ⅲ给定一组生成点尸＝　・・　）ＣＲ　，其中２＜ｎ＜ｏｏ，且当　ｆ、　厶＝｛１，…，疗）。Ｖｏｒｏｎｏｉ区域由以下公式给出：　ｖＰ＋Ａ＝　Ｉ　『Ｊ≤ｄ（ｐ妨））　其中ｊ＃ｉ，　厶，　为Ｐ与Ｐ　之间的最小距离（欧氏空间里点Ｐ　和Ｐ　之间的直线距离）０由Ｐ　所决定的区域称为Ｖｏｒｏｎｏｉ多边形。而由　砑ＩＰ）＝｛　），…，　）所定义的图形被称为Ｖｏｒｏｎｏｉ图。共享相同的棱的　，　圈１　Ｖｏｍｎｏｌ圈　ＶｏＴＯｎｏｉ多边形被称为邻接多边形，它们的生成点被称为邻接生成点。图１　展示了部分Ｖｏｍｎｏｉ图。　性质１【ＩＩ　Ｖｏｒｏｎｏｉ边由“相邻”两母点间的垂直平分线或该直线上的线段、射线构成。　性质２ｌ玎帅『）（／＝１，２，…，疗）是对平面的一个分割，即将平面分成互不重叠的，价部分。　２　ＶＲ树　定义３（Ｖｏｒｏｎｏｉ边缘多边形）设Ｐ＝｛Ｐｔ　，－．．，ｆ　ｌ为二维欧氏空间（平面）上的点集，点集口　ｐ。ｖｂｐ（ｇ）＝　｛ｖｐ／ｐ，）￣，∈ｑ（ｉ＝ｌ，２，…，疗））称为点集ｇ的Ｖｏｒｏｎｏｉ边缘多边形ｖｂｐ。　鉴于在以往基于Ｖｏｍｎｏｉ图的近邻查询的研究中大　多仅限于在计算几何的层面上对近邻查询进行方法进　行理论探讨，而对那些基于Ｖｏｒｏｎｏｉ图的近邻查询算法究　竞是采取何种索引结构避而不谈。本文提出了一种基于　Ｒ树思想的新的索引树：ＶＲ树，用于基于Ｖｏｒｏｎｏｉ图的近　邻查询。ｖＲ树最显著的特征就是把聆个数据点的集合　一　，　一　、　Ｒ２．　Ｆ　生成Ｖｏｒｏｎｏｉ图的信息加入到存储结构中。与Ｒ树的本质　图２图ｌ的ＶＲ树中外包Ｖｏｍｎ￣边缘多边形ｖｂｐ的组织形式　区别是：在ＶＲ树中不是用最小外包矩形（ＭＢＲ）组织空间点而是用最小外包Ｖｏｍｎｏｉ边缘多边形　（Ｖｏ　ｄｉ　Ｂｏｌｓｔｅｒ　Ｐｏｌｙｇｏｎ）组织空间对象。ＶＲ树中最小外包Ｖｏｒｏｎｏｉ￣缘多边形　组织形式如　２。从图２可以看到，　最小外包Ｖｏｍｎｏｉ边缘多边形　组织空间对象时，不像最小外包矩形（ＭＢＲ）那样有缝隙和重叠，它们之　收稿日期：２００６－１０－１９　作者简介：王森（１９８１一）．男，河南光山人，在读硕士研究生，主要研究方向为时宅数据库。　维普资讯 http://www.cqvip.com

第６期　基于Ｖｏｒｏｎｏｉ图的最近邻查询的索引结构的研究　问是完全紧邻的。所以在查询，点口属：ｔ：￣Ｗｏｒｏｎｏｉ单元的过程中，不会产生任何不必要的搜索路径和重　复搜索。因此基于最小外包Ｖｏｒｏｎｏｉ边缘多边形ｖｂｐ组织空间对象的　树的近邻查询算法是基于用最小外包　矩形（ＭＢＲ）组织空问物体的Ｒ树系列的近邻查询算法的理想上界。　树的叶子节点结构如下：￡：　，…　Ｌ≤刀≤　，Ｅｉ：（ｆ７，ｖｐ，ｖａｐ　叶子￡包含　个记：录蜀，…　，　Ｌ≤刀≤＾　其中ｍＬ和舰表示叶子节点中记录数目的最小值和最大值；每个　记录跑含的数据点　，点　生成的Ｖｏｒｏｎｏｉ多边形　，指向存储该点邻接生成点的信息的ｈａｓｈ表单元的指针　ｖａｐｔｒｏ　中间节点的结构如下：Ⅳ．（Ｃｌ，…，Ｃ　，　≤刀≤＾　，Ｃ，（ｖｂｐ，ｃｈｉｌｄｐｔｒ）　一个中问节点胞含刀个记录Ⅳ．（Ｃｌ，…，　≤刀≤＾　，其中　和螈是中间节点的最小和最大的记录数　目；每个记录　应一个孩子节点，包括两项：该节点所包含实体的Ｖｏｍｎｏｉ边缘多边形　，指向其孩子的　指针ｃｈｉｌｄｐｔｒ。ＶＲ树还使用了一个二级索引结构（图２中的ｈａｓｈ表，表单元包括各点的邻接生成点及邻接生　成点的个数）点。去存储各点的邻接生成其建立规则与Ｒ树相似不再介绍。一个基于图１中Ｖｏｒｏｎｏｉ图的　树结构表示的例子如图３。　非叶结点结掩　ＶｏｒｏｎｏＪ关系ｈａｓｈ表单元结构　图３图１的ＶＲ树表示　３静态环境下基于Ｖｏｒｏｎｏｉ图的ＮＮ查询算法　３．１最近邻查询的定义　定义４Ｉ４１在刀维空间里，给定一个移动对象点集合　和移动查询点ｇ，时空最近邻搜索就是找到一个　集合　的子集ＮＮＳ（ｑ），使得如下等式成立：　ＮＮＳ（ｑ）＝｛ｒＥ　Ｓ　ＩＶｐｅ　；Ｄ（ｑ，，’≤Ｄ（ｇ　Ｊ　３＿２基于Ｖｏｒｏｎｏｉ图的ＮＮ查询算法　由定义１知：对于查询点ｇ的ＭＶ查询只需要确定ｇ在哪个生成点生成Ｖ０ｒ０ｎｏｉ单元即可，那么那个点即为ｇ　的最近邻。再者　树索引结构中包含了Ｖ０ｍｎ０ｉ图的信息，故能迅速确定口在哪个生成点生成的Ｖｏｒｏｎｏｉ单元。　由以上论述可得出基于　树索引结构的ＭＶ查询算法如下　ＮＮ＿ＳＥＣ（ｎ，ｑ）　输入：ＶＲ树节点类型数据ｎ，查询点ｑ　输出：ｑ的最近邻　１）ｅｇｉｎ　ｉｆ　ｎＥ　Ｌｅａｌ１　ｅ（、，　ｔｈｅｎ，，８是Ⅵ树的叶子节点　Ｉ：ｆｏｒｅｎｔｒｙ（Ｐ，ｖｐ，ｖａｐｔｒ）ｅ　ｎｄｏ　，　维普资讯 http://www.cqvip.com

・５８・　齐齐哈尔大学学报　ｉｆ（ｑＥ　ｖｐ）￣ｅｎ　断ｑ是否在实体的Ｖｏｅｒｎｏｉ单元中　ｒｅｔｕｒｎ　ｐ；，，返回ｑ的最近邻　ｅｌｓｅＧｏｔｏＩ：／　砖回攻￡，进入下一次判断‘　ｅｌｓｅｆｆ　ｎＥ　ＭｉｄＮｏｄｅ（ＶＴ）ｔｈｅｎ、／／ｓ是ｖ喇的中问节点　Ｊ：ｆｏｒｅｎｔｒｙｆｖｂｐ，ｃｈｉｌｄｐｔｒ）∈ｎｄｏ　２００６年　ｉｆ（ｑｅ　ｖｂｐ）ｈｔｅｎ　０断ｑ是否在实体的ｖｂｐ中　ＮＮ＿ＳＥＣ（ｃｈｉｌｄｐｔｒ，ｑ）；，，进行递规查询　ｅｌｓｅＧｏｔｏＪ；臌网Ｊ处，进入下一次判断　ｅＭ　‘　。　。　：　　．虽然本算法与基于脚对的ｌＮＮ算法都在同一时间复杂度级别上，但由于　树的　之间没有间隙和重叠，　故不会产生任何不必要的搜索路径和重复搜索，于是大大提高了查询的效率。　　’４结论　在以往基于Ｖｏｍｎｏｉ图的近邻查询研究中，大多仅限于在计算几何的层面上对近邻企询方法进行理论探　讨，而对那些基于Ｖｏｌ－ｏｎ０ｉ图的近邻查询算法究竟是采取何种具体的索引结构避而不谈。而本文就以上问题　进行了大胆的探索和尝试，提出了一种新的索引结构ＶＲ树，‘从而解决了基于Ｖｏｒｏｎｏｉ图的近邻查询中索引结　构的问题并提高了近邻查询的效率。　参考文献　［１ｌＪ．Ｒ．Ｓａｃｋ，Ｊ．Ｕｒｍｔｉａ．ＶｏｒｅｎｏｉｄｉａｇｒａｍｓＨａｎｄｂｏｏｋ　ｏｎＣｏｍｐｕｔａｔｉｏｎａｌＧｅｏｍｅｔｒｙ［Ｊ］．Ｏｔｔａｗａ：ＥｌｓｅｖｉｅｒＳｃｉｅｎｃｅ，２０００．２０１￣２９０．　【２】Ｇｕｔｔｍａｎ　Ａ．Ｒ－ｔｒｅｅｓ：ａ　Ｄｙｎａｍｉｃ　Ｉｎｄｅｘ　Ｓｔｒｕｃｔｕｒｅ　ｆｏｒ　Ｓｐａｔｉａｌ　ｅａＳｒｃｈｉｎｓｉＪ］，ＡＣＭＳＩＧＭＯＤ，１９８４．４７－５７．　［３１　Ｓ．Ｂｅｓｐａｍｙａｔｎｉｋｈ，Ｊ．Ｓｎｏｅｙｉｎｋ．，Ｑｕｅｒｉｅｓ　ｗｉｈ　ｔＳｅｇｍｅｎｔｓ　ｉｎ　Ｖｏｒｏｎｏｉ　ｄｉａｇｒａｍｓ［Ｊ］．ＳＯＤＡ，１９９９．１２２－１２９．　【４】Ｂｏｕｓｓｏｐｏｕｌｏｓ　Ｎ．，Ｋｅｌｌｅｙ　Ｓ．ａｎｄ　Ｖｉｎｃｅｎｔ　Ｆ．Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ　Ｑｕｅｒｉｅｓ［Ｊ］．ＡＣＭＳＩＧＭＯＤ，１９９５．７１－７９．　［５１　Ｓｏｎｇ　Ｚ．ｎｄ　ａＲｏｕｓｓｏｐｏｕｌｏｓ　Ｎ．Ｋ－ＮＮ　ｅａＳｒｃｈ　ｏｆｒ　Ｍｏｖｉｎｇ　Ｑｕｅｒｙ　Ｐｏｉｎｔ［］．ＳＳＴＤ，２００１．７９－９５．Ｊ　‘　【６】Ａ．Ｐａｐａｄｏｕｌｏａ，Ｙ．Ｍａｎｏｌｏｐｏｕｌｏｓ．ＰｅｒｆｏｒｍａｎｃｅｏｆＮｅａｒｅｓｔ　ＮｅｉｇｈｂｏｒＱｕｅｒｉｅｓｉｎＲ－ｔｒｅｅｓ［Ｃ］．ＩｎＰｒｏｃｅｅｄｉｎｇｓｏｆＩｎｔｅｎａｔｒｉｏｎａｌＣｏｎｆｅｅｎｃｅｒ　ｏｎ　Ｄａ￣ｂａｓｅ　Ｔｈｅｏｒｙ，．Ｄｅｌｐｈｉ，Ｇｒｅｅｃｅ，１９９７．３９４－４０８．　【７１　Ｍ．Ｋｏｌａｈｄｏｕｚａｎ　ｎｄ　ａＣ．Ｓｈａｈａｂｉ．Ｖｏｒｅｎｏｉ－Ｂａｓｅｄ　Ｋ　Ｎｅａｒｅｓｔ　Ｎｅｉ￣ｂｏｒ　Ｓｅａｒｃｈ　ｆｏｒ　Ｓｐａｔｉａｌ　Ｎｅｔｗｏｒｋ　Ｄａｓｔｌ，ａｓｓ［ｅＣ］．ＩｎＶＬＤＢ　２００４，Ｔｏｒｏｎｔｏ．　Ｃａｎａｄａ．１－１２．　　’：　Ｒｅｓｅａｒｃｈ　ｏｎ　ｉｎｄｅｘ　ｏｆ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ　ｑｕｅｒｉｅｓ　ｂａｓｅｄ　ｏｎ　Ｖｏｒｏｎｏｉ　ｄｉａｇｒａｍｓ　ＷＡＮＧ　Ｍｉａｏ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｎｔｒｏｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｑｉｑｉｈａｒ　Ｕｔｉｆｖｅｒｓｉｔｙ，Ｈｅｆｌｏｎｇｊｉａｎｇ　Ｑｉｑｉｈａｒ　１　６　１　００６．Ｃｈｉｎａ）　ＡｂｓｔｒａＣｌ：Ｔｈｅ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｉｎｑｕｉｒｙ　ｉｓ　ｆｏｕｎｄａｔｉｏｎａｌ　ａｎｄ　ｉｍｐｏｒｔａｎｔ　ｉｎ　ｂｏｔｈ　ｍｏｂｉｌｅ　ｃｏｍｐｕｔｉｎｇ　ｍｓｅａｍｈ　ａｎｄ　ｅａｌｒ　ｌｌｆｅ　ａｐｐｌｉｃａｔｉｏｎｓ．Ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｉｎｑｕｉｙ　ｒｂａｓｅｄ　ｏｎ　Ｖｏｒｏｎｏｉ　ｄｉａｇｒａｍｓ　ｈａｓ　ｂｅｅｎ　ｓｔｕｄｉｅｄ　ｆｏｒ　ｑｕｋｅ　ａ　ｌｏｎｇ　ｉｔｍｅ　ｉｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｇｅｏｍｅｔｙ．Ｗｈｉｒｃｈ　ｃｏｎｃｒｅｔｅ　ｉｎｄｅｘ　ｓｔｒｕｃｔｕｒｅ　ｔｏ　ｉｎｑｕｉｒｅ　ｔｈｅ　ｓｐａｔｉａｌ　ｓｅａｒｃｈ　ｕｓｅｄ　ｉｎ　ｔｈｅ　ｎｅａ　ｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｉｎｑｕｉｅｒ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　Ｖｏｍｎｏｉ　ｄｉａｇｒｍ　ａｉｎ　ｈｔｅ　ｐａｓｔｒｅｓｅａｗｈ　ｉｓ　ｒａｍｌｙ　ｍｅｎｔｉｏｎｅｄ．Ｉｎ　ｈｔｉｓ　ｐａｐｅｒ　ａ　ｎｅｗ　ｉｎｄｅｘ　Ｓｍｒｅｔｕｒｅ　ＶＲ—ｔｅｅ　ｒｉｓ　ｐｒｅ￣ｎｔｅｄ；ｗｈｉｃｈ　ｃｏｍｂｉｎｅｓ　ｈｅ　ｔａｄｖａｎｔａｇｅ　ｏｆ　Ｖｏｒｏｎｏｉ　ｄｉａｇｒａｍ　ｉｎ　ｈｅ　ｔｉｆｅｌｄ　ｏｆ　ｅｓｏｌｒｖｉｎｇ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｉｎｑｕｉｒｙ　ｗｉｈ　ｔｈｅ　ｔｔｒａｄｉｉｔｏｎａｌ　Ｒ－ｔｒｅｅ．Ｔｈｅｎ　ｐｒｏｐｏｓｅｄ　ａ　ＮＮ　ｉｎｑｕｉｙ　ｒａｌｇｏｒｉｔｈｍ　ｗｈｉｃｈ　ｉｓ　ｂａｓｅｄ　０ｎ　ＶＲ—ｔｒｅｅ　ｉｎｄ　ｘ　ｓｔｒｕｃｔｕｒｅ．Ｉｔｈａｓｂｅｅｎｐｒｏｖｅｄｉｎｔｈｅｏｒｙｔｈａｔｉｔｉｓ　ｓｕｐｅｒｉｏｒｔｏｔｈｅａｌｇｏｒｉｔｈｍｏｆｎｅｉｇｈｂｏｒｉｎｑｕｉｙｗｈｉｒｃｈｂａｓｅｄ　ｏｎＲ－ｔｒｅｅ　ｎｄｅｘ　ｉｓｔｒｕｃｔｕｒｅ．　。　Ｋｅｙ　ｗｏｒｄｓ：Ｖｏｒｏｎｏｉ　ｄｉａｇｒａｍｓ；ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ　ｉｎｑｕｉｙ；ｒＶＲ－ｔｒｅｅ．　．