动态受限区域内的单纯型连续近邻链查询方法.pdf

《动态受限区域内的单纯型连续近邻链查询方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第41卷第6期计算机科学Vo1．41No．62014年6月ComputerScienceJune2014动态受限区域内的单纯型连续近邻链查询方法李松张丽平朱德龙郝晓红。(哈尔滨理工大学计算机科学与技术学院哈尔滨150080)(哈尔滨理工大学计算中心哈尔滨150080)。摘要受限区域内的单纯型连续近邻链查询在空间数据挖掘、数据的相似分析和推理、空间数据库等方面具有重要的作用。为了弥补已有方法的不足，详细研究了动态受限区域内的单纯型连续近邻链查询方法。基于计算几何中的Voronoi图给出了V0R—IN—CRSCNNC算法

2、、VOR_Ex—CRC算法和V0IDE_CRSCNNC算法。进一步进行了实验比较和分析。理论研究和实验分析表明，所提出的算法在查询过程中减少了数据逐一筛选和判断的冗余计算，在处理空间数据量较大、初始受限区域数据量较多、受限区域形状较为复杂的单纯型连续近邻链查询方面具有较大的优势。关键词空间数据库，Voronoi图，最近邻查询，单纯型连续近邻链，受限区域中图法分类号TP311文献标识码ASimpleContinuesNearNeighborChainQueryinDynamicConstrainedRegionsLIS

3、ongZHANGLi-pingZHUDe-longHAOXiao-hongz(SchoolofComputerScienceandTechnology，HarbinUniversityofScienceandTechnology，Harbin150080，China)(ComputationCenter，Ha~inUniversityofScienceandTechnology，Harbin150080，China)AbstractThesimplecontinuesnearneighborchainqueryint

4、heconstrainedregions(CRSCNNC-Query)hasimportantsignificanceinthespatialdatamining，similarityanalysisandreasoningofdata，spatialdatabaseetc．Toremedythedefbciencyoftheexistingwork，thesimplecontinuesnearneighborchainqueryinthedynamicconstrainedregionswasstu-diedres

5、pectively．TheVOR一CRSCNNCalgorithm，VOREX—CRSCNNCandtheVOR_DE_CRSCNNCalgorithm—werepresentedbasedontheVoronoidiagram．Furthermore，theperformanceofthemethodswereanalyzedandcorn—paredbyexperiment．Thetheatricalstudyandtheexperimentalresultsshowthattheredundantcalcula

6、tionisreducedandthealgorithmsholdlargeadvantageatthebigdatasetsandtheregionswithcomplexshapes．KeywordsSpatialdatabase，Voronoidiagram，Nearneighborquery，Simplecontinuesnearneighborchain，Constrainedregion进行了研究，提出了一些较为典型的方法，但没有涉及单纯型1引言连续近邻链(SimpleContinuesNearNeigh

7、borChain，SC—数据信息的近邻关系查询在空间数据库、地理信息系统、NNC)查询问题，所提出的方法不适合处理单纯型连续近邻空间定位与查询、数据挖掘、图像处理与分析、网络智能查询、链的查询与分析。文献1,133研究了处理理想二维空间中的单智能交通控制等领域具有重要的作用D,z3。国内外学者对数纯型连续近邻链的查询方法，给出了SCNNC_V—SEARCH据集中的近邻关系查询进行了较为广泛的研究，在简单近邻算法。为了处理预定数据链规模的单纯型连续近邻链问题，查询、最近对查询、邻近对查询、组最近邻查询、反向最近邻查文献

8、[143基于空间索引结构R树给出了动态数据集中的单询等方面取得了一些重要的研究成果E。纯型连续近邻链查询的算法：SCNNCR_ST算法、SCNNC_R近年来，由于数据信息的复杂性和查询需求的不断提高，—SD算法和SCNNC_R_XZ算法。文献[15]基于空间Hilbert查询条件变得日益复杂，有关近邻关系的查询进一步扩展到曲线给出了预定数据链规