基于kd-tree的移动对象索引研究

《基于kd-tree的移动对象索引研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文基于kd-tree的移动索引索引研究基于kd．tree的移动对象索引研究专业：计算机软件与理论硕士生：石敏指导老师：叶小平副教授摘要长期以来，时态数据库和空间数据库作为数据库中两个重要的研究领域是相互分离的，然而现实世界中许多实体都同时具有时问特性和空间特性，因此时空数据库在时态数据库和空间数据库的基础上发展起来了。时空数据库可以处理带有时间和空间特性的数据，相对于传统关系数据库的一个突出特点就是数据量大，数据更新频繁。而随着移动计算、全球定位系统等相关技术的发展，时空数据库

2、得到了进一步发展，出现了移动对象数据库。移动对象数据库需要存储和管理大量现实世界中的带有时空信息的对象，即形状和位置随时间变化而变化的空间对象信息。为了快速有效地对数据进行查询和更新，这就需要通过索引机制来管理数据，而这一技术已成为时空数据库研究的焦点。在现有的索引方法中很多方法都是将时间维看作空间维，以便利用比较成熟的空间数据库索引技术。但时间和空间有着不同的特性，进而可能对系统性能产生较大的影响。本文研究并总结了当前移动对象索引技术的优缺点，并在此基础上，研究基于时间和空间有效整合的移动对象

3、索引技术。即通过将时间和空间分别进行处理，然后将分别处理后得到的时态索引和空间索引进行有效的整合，进而实现对移动对象数据的索引。本文首先介绍了移动对象数据库的相关概念和理论，并对现有的主要的移动对象索引方法进行系统归类。其次在移动对象数据特点的基础上讨论并提出了有效时间的拟序关系概念，研究了时间线序分枝算法。在此基础上研究了基于kd-tree的移动对象索引模型KMOIM，同时，研究了基于KMOIM的数据查询以及索引更新算法；最后通过仿真实验和比较评估，检验了KMOIM的可行性和有效性。关键词：时

4、间拟序关系，空间平面划分，时空整合，移动对象索引中山大学硕士学位论文基于kd-trce的移动索引索引研究ResearchOilMovingObjectsIndexBasedonKD-·TreeMajor：Name：ComputerSoftwareandTheoryShiMillSupervisor：AssociateProfessorXiaopingYeAbstractForalongtime，temporaldatabaseandspatialdatabaseareseparatedfrome

5、achother弱twoimportantresearchareas，however,therearermnyentitiesbothhavingthetimecharacteristicandspatialcharacteristicintherealworld，thereforespatio·temporaldatabasedevelopsonthebasisoftemporaldatabaseandspatialdatabase．Spatio-temporaldatabasecanhand

6、lewithdatahavingtimeandspatialcharacteristics,asopposedtoatraditionalrelationdatabasewichaprominentfeatureoflargevolumesofdata,frequentlyupdating．Withthedevelopmentofmobilecomputing，globallocationsystemsandotherrelatedtechnobgies，spatio—temporaldatab

7、asehasbeenfurtherdevebpedandtherehavebeenmovingobjectsdatabase．Movingobjectsdatabaseneedstostoreandmanagealargenumberofreal-worldobjectswiththespatio-temporalinformation,namely,thespaceobjectinformationwiththeshapeandpositionchangingwithtime．Inordert

8、oqueryandupdatedataquicklyandefficiently,itneedstheindexmechanismstomanagedata,andthistechnologyhasbecomingthefocusoftheresearchofspatioqernpomldatabase．Amongtheexistingindexmethods，mostofthemethodstaketemporaldimensionasonehigherspatialdimemioninord