基于Quadtree和Hash表的移动对象全时态索引

为解决大量移动对象位置频繁更新所带来的性能下降问题,提出一种基于改进的Quadtree和Hash表的QH全时态索引结构。这种新的索引结构可以支持移动对象全时态索引,在Hash表中通过存储移动对象指针来支持移动对象标识查询,并对Quadtree的叶子节点采用适时合并的方法来防范分支太深而造成的查询效率低下。实验证明,QH索引与TPR-tree相比,移动对象的更新效率更高、对象标识查询较优、范围查询性能相近。     

支持多种查询的室内移动对象索引

随着室内定位技术的广泛应用,室内位置服务快速发展.移动对象索引技术作为支撑位置服务的核心技术,大多数都基于室外环境,难以直接应用于室内空间.现有的室内移动对象索引,仅关注对移动对象历史数据的查询,且支持的查询类型单一.为此,提出MQII(multiple queries indoor index)索引结构,对移动对象历史和当前位置信息进行索引,能够同时支持对象位置查询、轨迹查询以及时空范围查询.索引采用对象链表和桶链表结构,实现从对象和时空范围2个方面对移动对象数据的管理;提出针对该索引结构的有效更新、查询算法;实验结果表明,与现有室内移动对象索引相比,索引不仅能够支持历史查询和当前查询,还能够同时高效支持对象位置查询、轨迹查询和范围查询.该方法可应用于办公楼、医院等多种室内空间.     

移动对象索引方法研究

传统空间索引结构因无法适应大量的更新操作而不能应用于移动对象的存储和检索。本文介绍了三种主要移动时象索引方法的基本思想，即R树及其变形树、四叉树及其变形树以及网格文件及其变形算法，并进行了分析时比，在此基础上提出了混合索引结构，比已知的索引结构效率更高。     

不确定移动对象的模糊时空范围查询

指出不确定性和模糊性在时空语义上的区别;提出不确定移动对象的模糊时空范围查询问题,即查询条件中时间、空间范围的外延是模糊的,无清晰的边界,而目标对象的位置不确定;用模糊集表示模糊查询条件,概率密度函数表示移动对象在各自不确定区域内的可能位置分布;给出了不确定对象关于模糊查询条件匹配度的计算方法;设计了基于α截集的无效对象排除和有效对象确认规则及查询算法.算法规则适用于任意概率密度分布.现有的确定或不确定范围查询可以看成是模糊时空范围查询的特例.通过实验验证了算法的效率,在各种参数设置下,约有30%~90%的查询结果可在不计算匹配度的情况下获得.     

基于HBase的路网移动对象时空索引方法

在处理路网移动对象时,由于HBase只能采用key查询,不适用于移动对象的多维查询,导致HBase存在存储索引与查询效率不高的问题。针对此问题,在HBase存储结构的基础上设计并实现了一种高效的路网移动对象HBase索引框架（RM-HBase）。首先,对原生HBase索引框架的上层HMaster和下层HRegionServer进行改进,解决分布式集群数据的热点分布问题,提高空间数据的查询效率;其次,提出路网移动索引——RN-tree,解决空间划分中的"死空间"问题,同时提高空间中路段的查询效率;然后,基于上述对HBase的索引改进,分别设计了时空范围查询、时空K最近邻（KNN）查询和移动对象轨迹查询的查询算法;最后,实验选用了同样是基于HBase分布式数据库而提出的时空HBase索引（STEHIX）框架作为对比对象,分别从索引框架的性能和算法的查询效率两个方面对RM-HBase的性能进行分析。实验结果表明,所提的RM-HBase在数据的均衡分布性能和时空查询算法的查询性能方面都优于STEHIX框架,有助于提升海量路网移动对象数据的时空索引效率。     

支持预测查询和部分历史查询的移动对象索引方法

针对TPR*-tree隐含移动对象部分最近历史信息但不能提供历史信息查询的问题,将移动对象创建或更新时间引入到索引树中,提出一种既支持预测查询又支持部分历史信息查询的索引树Basic HTPR*-tree,为全时态查询奠定了坚实的基础.同时,为了支持移动对象的频繁更新,在Basic HTPR*-tree索引树基础上引入内存概要结构和Hash辅助索引结构,提出支持自底向上更新策略的HTPR*-tree索引结构.实验结果表明,HTPR*-tree更新性能优于TPR*-tree和Basic HTPR*-tree(TD_HTPR*-tree),预测查询性能仅仅稍逊于TPR*-tree.     

基于路网的移动对象动态双层索引结构

为了支持对大规模不确定性移动对象当前及将来位置的查询,亟需设计更加有效和高效的索引结构.当前索引算法主要考虑索引建立和维护的效率问题或关注基于索引进行查询时的准确性,对索引建立维护以及查询时性能综合考虑的研究较少.针对已有方法的不足,提出基于路网的移动对象动态双层索引结构DISC-tree,对静态路网信息采用R~*-tree索引,对实时更新的移动对象运动轨迹采用结点更新代价较小的R-tree进行索引,设计哈希表和双向链表辅助结构对索引协同管理.成都市真实地图数据集上的实验结果表明:相比于经典的NDTRtree,DISC-tree在索引建立和维护方面时间代价平均减少39.1%,移动对象轨迹查询时间代价平均减少24.1%;相比于FNR-tree,DISC-tree的范围查询准确率平均提高约31.6%.     

移动对象查询研究进展

移动对象查询技术是目前数据库技术研究的热点。移动对象的查询处理技术不仅要追求高效率和高精确度,而且要充分考虑到现实可行性和不同维度空间的可拓展性。本文基于前人对移动对象查询的分类方法,根据移动对象查询的发展动态,将移动对象查询分为轨迹查询和坐标查询两大类;回顾了已有的各种查询处理方法,分析了各种方法的优缺点,并且基于方法间的继承性和互补性,为后续的查询研究提出了建议。     

频繁更新移动对象的索引方法

在时空数据库中,频繁更新会导致TPR树更新与查询性能下降。针对该问题,提出MAH—TPR索引方法,分别对预处理过程、索引结构及更新算法进行优化。在构建索引及更新操作时,通过使用空间聚类来减少节点间空间区域的交叠几率。引入基于磁盘的Hash辅助存储结构,在直接访问叶节点的基础上进一步减少磁盘I／O的操作。引入基于内存的移动对象辅助存储结构,用于存储发出频繁更新请求,以避免主索引结构节点的合并和分裂。实验结果表明,MAH—TPR索引方法的查询性能优于HTPR方法和LGU方法,更新性能优于HTPR索引方法。     

移动对象数据库的索引和查询

该文首先概述了移动对象数据库(Moving Objects Database,MOD)的特点;接着,针对移动对象数据库的索引方法展开,根据移动对象索引空间的不同,将移动对象索引分为无限制空间移动对象索引和网络空间移动对象索引,阐述了几种主要的移动对象索引技术的发展情况;然后,分析了一下移动对象数据库中的查询技术,指出对查询策略的评价应多方面,多角度考虑;最后简述了移动对象索引和查询的发展方向。     

一种移动对象增量组最近邻居查询方法

基于移动对象增量最近邻居查询(INCNN),提出一种移动对象增量组最近邻居查询方法(INCGNN)。该方法以较小的代价求出每次更新时刻的组最近邻居。针对组最近邻居查询的特点,给出了k+1组最近邻居查询改进算法,椭圆剪枝和延迟更新3种优化查询的策略。实验结果表明,INCGNN明显优于REEGNN,3种优化策略能较好地提高查询性能。     

基于更新日志的移动对象索引方法

在TPR-tree上增加一个基于内存的更新日志,实现一种支持频繁更新的移动对象索引ULTPR-tree,采用分组更新方法对移动对象记录进行批量删除,从而减少ULTPR-tree索引结构的删除维护代价。理论分析和实验结果表明,ULTPR-tree的动态更新性能优于TPR-tree和HTPR-tree。     

面向路网的移动对象全时态高效索引模型

针对现有索引模型的冗余搜索问题,考虑路网拓扑结构及交叉口转向约束条件,提出一种面向路网的移动对象全时态高效索引模型。采用添加临近路段信息的方法索引历史轨迹和实时位置信息,设计新型窗口查询算法,实现移动对象查找,并运用指数平滑法进行轨迹的预测。实验结果表明,该模型具有较好的更新及查询性能。     

利用覆盖区域设计与实现移动对象索引

对移动对象索引频繁更新问题进行了研究,提出了一种基于区域覆盖的空间索引结构虚拟网格四分树(virtual grid quadtree,VGQ);通过索引移动对象所在的区域而非移动对象本身来减少由于移动对象位置的改变而引起的索引结构的改变,并给出了近似连续范围查询算法及增量和自底向上优化策略。实验结果表明,VGQ在查询效率和空间使用上是一种有效的索引方法。     

Indexing Fast Moving Objects for kNN Queries Based on Nearest Landmarks

With the rapid advancements in positioning technologies such as the Global Positioning System (GPS) and wireless communications, the tracking of continuously moving objects has become more convenient. However, this development poses new challenges to database technology since maintaining up-to-date information regarding the location of moving objects incurs an enormous amount of updates. Existing indexes can no longer keep up with the high update rate while providing speedy retrieval at the same time. This study aims to improve k nearest neighbor (kNN) query performance while reducing update costs. Our approach is based on an important observation that queries usually occur around certain places or spatial landmarks of interest, called reference points. We propose the Reference-Point-based tree (RP-tree), which is a two-layer index structure that indexes moving objects according to reference points. Experimental results show that the RP-tree achieves significant improvement over the TPR-tree.

基于范围查询的移动对象快照KNN查询算法

提出一种基于范围查询的移动对象快照K最近邻(KNN)查询算法——SKNN。预估包含结果集的子空间,使用该子空间作为范围,计算查询点的KNN兴趣点,以降低I/O成本。引入移动数据库中的缓存技术,缩短查询的平均响应时间。实验结果表明,当移动对象的规模较大时,SKNN算法的性能较优。     

双流模式下高吞吐量移动对象范围查询算法

随着位置感知移动设备的出现及通信技术和GPS系统的不断发展,基于位置的查询在数据库领域得到了广泛的关注.研究了基于快照的空间范围查询,即,查询在某个时间段位于某个查询范围内的移动对象.范围查询是其他空间查询的基础,例如KNN查询和反KNN查询等,很容易在范围查询的基础上得到.国内外的研究者针对移动对象的范围查询问题提出了一系列的算法,然而这些算法要么关注于解决移动对象的快速更新问题,要么关注于解决范围查询的快速处理问题.在大数据的背景下,查询和更新大量涌入时,不仅要求查询算法有较快的响应速度,还要求它们能够实现较高的吞吐量,但已有算法不能很好地解决高吞吐量的问题.针对移动对象更新数据流和查询数据流,提出一种基于内存的高吞吐量移动对象范围查询算法——双向流连接(DSJ)算法.双向流连接算法采用基于快照的模式,通过在每个快照中重新构建索引的方式,以避免复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,增加了数据的局部性,提高了算法的效率;在执行过程中,通过使用SIMD技术以加速查询处理过程.基于以上几点,双向流连接算法能够确保整个系统具有很高的吞吐量.在基于德国路网生成的数据集上对算法进行了测试,实验结果表明,双向流连接算法具有很好的性能表现.     

受限网络移动对象不确定性轨迹的查询

针对移动对象轨迹的内在不确定性及其导致的查询精度较低的问题,将已有移动对象的空间轨迹不确定性模型应用于网络移动对象的轨迹表示中。在此基础上,将概率查询方法运用到受限网络移动对象的不确定轨迹查询中,提出移动对象轨迹的不确定性点查询和概率范围查询方法。实验结果表明,该方法具有较高的查询效率。