资源描述：
《基于voronoi图的组最近邻查询》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、计算机研究与发展ISSN1000-1239PCN11-1777PTPJournalofComputerResearchandDevelopment47(7):1244-1251,2010基于Voronoi图的组最近邻查询11,2孙冬璞郝忠孝1(哈尔滨理工大学计算机科学与技术学院哈尔滨150080)2(哈尔滨工业大学计算机科学与技术学院哈尔滨150001)(sundongpu@sina.com)GroupNearestNeighborQueriesBasedonVoronoiDiagrams11,2SunDongpuand
2、HaoZhongxiao1(CollegeofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080)2(CollegeofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)AbstractGroupnearestneighborqueryismorecomplexthanthetraditionalnearestneighbo
3、rquerybecauseitcontainsonemorequerypoints.Itsobjectiveistofindadatapointthathasthesmallestsumofdistancestoallquerypoints.Theconditionsthatgroupnearestneighborshouldbesatisfiedandthetheoriesthatvaluatethegroupnearestneighborareputforward,whichareobtainedbyconsider
4、ingthedistributioncharacteristicsofquerypointsandthequalitiesofgeometricfiguresthattheyform.TheVGNNalgorithmispresentedtodealwithgroupnearestneighborquerybasedonVoronoidiagrams.ItcangetthequerypointspnearestneighborexactlybyusingtheVGNNalgorithm.Whenthequerypoint
5、sarenon-collinear,thequerywayoftheVGNNalgorithmisfirstlytoestimateonedatapointthatisthequerypointspnearestneighborpossible,andthentooutspreadaroundthedatapointtofindthefinalresult.Anditalsoconcludesthesearchregionwhenthequerypointsarecollineartolimitthequantityof
6、datapointswhichareincludedinthecomputation.TheVTreeindexgroundedonVoronoidiagramsisbroughtforward.ExperimentalresultsshowthattheVGNNalgorithmbasedontheVTreeindexhasbetterperformance,anditismorestablewhenthequerypointsarenon-collinear.Keywordsgroupnearestneighbor;
7、Voronoidiagrams;adjacentgenerator;VGNNalgorithm;VTreeindex摘要组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出
8、基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性.关键词组最近邻;Voronoi图;邻接生成点;VGNN算法;VTree索引中图法分类号TP311.13收稿日期:2009-03-19;修回日期:2009-09-30基金项目
