受限网络模糊对象最近邻查询.pdf

《受限网络模糊对象最近邻查询.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第3期计算机工程2014年3月v0l_40No．3ComputerEngineeringMarch2014·先进计算与数据处理·文章编号：1000-3428(2014)03—0039—07文献标识码：A中圈分类号：TP311．13受限网络模糊对象最近邻查询高峻，郝忠孝，(1．哈尔滨理工大学计算机科学与技术学院，哈尔滨150080；2．哈尔滨工业大学计算机科学与技术学院，哈尔滨150001)摘要：针对网络空间中有范围约束、不确定对象的最近邻查询问题，提出范围受限的网络空间模糊对象最近邻查询概念，并根据查询顺序

2、的不同，给出NN—R查询算法和R】N查询算法。两种算法均采用网络位置信息与连接信息分别存储的方式，使用聚类文件进行组织，减少UO操作。NN—R算法在近邻查询过程中利用查询对象与受限范围的a一距离作为约束，缩小搜索范围。R-NN算法将受限范围内查询对象的欧氏近邻作为候选对象，利用欧氏距离的下界性与易求性降低时问复杂度。两种算法时间复杂度分别为O((1ogIIEI+([~Im3+1)log21~q+IEVllog}+(1g+1))和O(1og4n+(k+1)logIIEI+IEl+lY]loglV1)。实验结果表明，在

3、各自适用条件下，两种算法均有较好的性能。关健诃：确定网络；范围约束；模糊最近邻；0【一距离；邻接表；R树NearestNeighborQueryforFuzzyobjectinConstraintNetworkGAoJun．HAOZhong．xiao，一(1．CollegeofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080，China；2．CollegeofComputerScienceandTechn

4、ology,HarbinInstituteofTechnology,Harbin150001，China)[Abstract]Aimingatnearestneighborqueryforuncertainobjectwithrangeconstraintinnetwork,theconceptofnearestneighborqueryforfuzzyobjectinconstraintnetworkisputforward．Accordingtothequerysequence，twoqueryalgorith

5、msareproposed：NN—RandR—NN．Inthewayofstorage．thetwoalgorithmsallusetheindexstructurethatspatiallocationinformationseparatedfromnetwo~spaceconnectioninformation，andtheyuseclusteringfileorganizationtoreduceI／Ooperation．NN—Ralgorithmreducesthesearchareabyusingmini

6、mumandm~imum旺一distancebetweenfuzzyobjectandrangeconstraint．R—NNalgorithmusesEuclideannearestneighborsasthecandidates．ItdeclinesthecomplexitybyusingthatEuclideandistanceCanbecomputedeasilyandisthebottomboundaryofthenetworkdistance．Thecomplexityofthealgorithmsis

7、respectivelyO((1ogIIEI+(IV*lm3+1)log2lVI+IEl+j／]loglel+n(1gn+1))andO(1Ogm4n+(k+1)logIIEI+IEl+l／]logl)．Experimentalresultsshowthatthetwoalgorithmsallhavebetterperformanceintheconditionoftheirownappliedarea．[Keywordslcertainnetwork；rangeconstraint；fuzzynearestne

8、ighbor；a—distance；adjacenttable；RtreeD0I：10．3969／j．issn．1000—3428．2014．03．008法的研究往往局限在单一空间环境下，在现实需求中覆盖1概述还不够全面。现实中存在自由空间的位置信息和网络空间随着地理信息系统、空间数据库、物联网、交通控制、的连接信息相结合的需求，如在路网中行驶的汽车要找到多