Indexing large moving objects from past to future with PCFI

In moving object database, the moving objects' current position must be kept in memory, also to the trajectory, in some case, as same as the future. But the current existing indexes such as SEB-tree, SETI-tree, 2+3R-tree, 2-3RT-tree and etc. can only provide the capability for past and current query, and the TPR-Tree, TPR*-Tree and etc.can only provide the capability for current and future query. None of them can provide a strategy for indexing the past, current and also the future information of moving objects.In this paper, we propose the past-current-future Index (PCFI-Index) to index the past,current & future information of the moving objects. It is the combination of SETI-tree and TPR*-tree, the SETI liking index is used for indexing the historical trajectory segments except the front line structure, and the moving objects' current positions, velocities are indexed via the in-memory frontline structure which mainly implemented with TPR*-tree.Considering the large update operations on TPR-tree of large population, a hash table considering cache sensitivity is also introduced. It works with the frontline part, leading a bottom-up update of the tree. The performance analysis proves that the PCFI-index can handle most of the query efficiently and provides a uniform solution for the trajectory query, time-slice query, internal query and moving query.     

基于双树双索引结构的移动查询方法

为实现对有限范围内海量移动对象的有效索引,构建通用的移动查询解决方案,针对移动对象在道路网格中的运动特点,提出了预测实时运动速度的速度积累模型和预测未来聚集位置的基于双树双索引结构的移动对象查询方法.双树双索引结构利用网格划分思想构建空间分割树,实现对现有GG TPR-tree查询结构的拓展,并结合GG TPR-tree索引及建立于内存中的Hash索引以满足各种类型的移动查询请求.仿真实验表明,在回答受限范围内海量移动对象的确定性查询和统计性查询时,与传统方法相比,双树双索引结构在查询结果准确率方面有明显的改善.     

基于固定网络的移动对象轨迹查询

在基于固定网络的移动对象轨迹查询方面.现有的索引模型只能管理移动对象当前和过去或将来轨迹的查询,它们都不能同时实现移动对象的现在,过去和将来轨迹查询.本文在IMORS的索引结构基础上进行改进并提出了一种新的索引结构.它能实现基于固定网络的移动对象的全时态索引.     

移动对象数据库中的索引机制

无线通信技术和定位技术以其显著的实用性和先进性成为近年来的热门研究课题 ,同时各种应用中对移动对象的定位和跟踪能力的要求也越来越高。在 R*树的基础上提出一种多维空间索引结构 TPR树 ,以实现对活动在 (或可能活动在 )某区域内的移动对象的快速查询。分析和解决了 TPR树在查询、插入、删除和适时更新等处理中存在的问题。最后通过综合实验测试对所提方案进行性能评价     

路网中基于RQOP树的移动对象索引技术研究

基于位置的信息服务需要高效的索引方法来管理移动对象.针对PMR QUAD树索引路网空间时不平衡、部分路段重复存储且索引结构可调整性差的问题,用RQOP树对路网空间按照路段的空间分布进行划分,使树的高度尽可能低,改进基于路网的动态组合索引结构.对照实验表明,基于RQOP树的索引结构提高了查询效率.     

移动对象数据库将来查询方法研究

首先提出一个移动对象的轨迹模型,能建模低维和高维运动轨迹,并在此基础上提出一个具体的移动对象将来查询方法,该方法能应用于多种索引结构。本文基于R树结构,给出了对于不同查询形式的具体实现过程。     

一种改进的基于交通网络的移动对象索引方法

通过对基于交通网络(简称网络)移动对象索引方法FNR-Tree的分析，提出了一种改进的TNR-Tree方法。该方法充分利用网络信息，增大空间索引粒度，使用更合理的时间间隔，加强对轨迹的索引。性能分析说明了TNR-Tree方法较大程度地减少数据存储量和索引尺寸，提高了插入性能，并能有效地进行轨迹索引。     

一种改进的基于交通网络的移动对象索引方法

通过对基于交通网络（简称网络）移动对象索引方法FNRTree的分析,提出了一种改进的TNRTree方法。该方法充分利用网络信息,增大空间索引粒度,使用更合理的时间间隔,加强对轨迹的索引。性能分析说明了TNRTree方法较大程度地减少数据存储量和索引尺寸,提高了插入性能,并能有效地进行轨迹索引。     

QGrid:一种空间移动对象并行索引结构

为提高空间移动对象数据更新效率和查询准确率,提出了一种空间移动对象并行索引结构.利用主索引和辅助索引支持对空间对象进行基于范围的查询和基于对象标识的查询,还通过查询索引将更新操作和可能受其影响的查询操作相连接,在满足并行操作时间片语义的同时,避免了传统方法进行范围查询时对查询范围内相关对象及相关索引结构全部进行锁定的需求.实验结果表明:高负载环境下,该索引结构不但能保证查询准确率,其处理能力也明显优于传统索引结构.该索引通过提高系统并行度,使同一范围内的更新和查询操作可以并行执行,提升了系统整体运行效率.     

面向移动对象范围的混合索引结构

许多时空应用(如火灾模拟等)需要高效地查询移动对象的变化范围,针对此需求提出了基于TPR-tree和GF索引方法的两种混合索引结构,以支持对移动对象当前和未来范围的预测时空查询.在代价模型分析的基础上,基于模拟数据集的实验结果表明,这种混合索引方法能够有效地支持对移动对象变化范围的预测查询.     

不同维数下空间对象的反最近邻查询

反最近邻查询是在最近邻查询基础上提出的一种新的查询类型,是空间数据库的应用拓展,在不同维数下,根据不同的索引结构,反映出空间对象的反最近邻查询差异性较大,从不同索引结构的特性出发,分析了低维环境下基于R*-树的反最近邻查询优势,提出高维环境下一种新的基于SRdnn-树索引结构的空间对象反最近查询方法,优化了不同维数下空间对象的反最近查询性能,提高了查询效率.     

MC-Tree: Dynamic Index Structure for Partially Clustered Multi-Dimensional Database

Index structure that enables efficient similarity queries in high-dimensional space is crucial for many applications. This paper discusses the indexing problem in dataset composed of partially clustered data, which exists in many applications. Current index methods are inefficient with partially clustered datasets. The dynamic and adaptive index structure presented here, called a multi-cluster tree (MC-tree), consists of a set of height-balanced trees for indexing. This index structure improves the querying efficiency in three ways: 1) Most bounding regions achieve uniform distributions, which results in fewer splits and less overlap compared with a single indexing tree. 2) The clusters in the dataset are dynamically detected when the index is updated. 3) The query process does not involve a sequential scan. The MC-tree was shown to be better than hierarchical and cluster-based indexes for the partially clustered datasets.     

基于网格分组移动对象的索引方法

针对目前使用广泛的移动对象索引技术对受限范围内的海量数据索引管理问题.引入了网格技术实现移动对象的分组管理,提出了基于网格分组的移动对象GG TPR树索引方法.该方法利用网格分组的方式,将位置与运动行为接近的移动对象进行整体维护和批量管理,从而减少索引维护的中间环节,提高移动对象的索引效率.模拟实验结果表明,利用GG TPR树索引受限范围内的海量数据较已有的移动对象索引方法性能更优.     

分布式网络中 CKNN 查询的 BORA 优化汇聚

针对时空数据库中,移动对象轨迹的连续K近邻查询(continuous K nearest neighbor query,CKNN)的查询效率较低的问题,以及在分布式的移动对象数据库(moving objects databases,MOD)环境下,提升对应查询结果的数据汇聚效率问题进行了研究.在CKNN查询中,设计优化了查询海滩线的更新算法,通过在轨迹数据结构中增加更新标志位,减少了轨迹线段参与的判定运算;同时在假设的类网格覆盖的分布式空间环境下,利用基于Bresenham覆盖的路由汇聚(Bresenham-based overlay for routing and aggregation,BORA)方法,进行查询结果的汇聚;并针对不同近邻参数、轨迹数目、移动对象速度、汇聚方式等对查询时间的影响进行了仿真实验;仿真结果表明,不同参数数值的增加延长了处理时间,基于BORA的汇聚方式比一般的汇聚方式节省了更多的处理时间,提高了系统查询及处理的效率.     

An index method for continuous moving objects

There are current, historical and future information about continuously moving spatio-temporal objects. And there are correspondingly spatio-temporal indexes for current, past and future querying. Among the various types of spatio-temporal access methods, no one can support historical and future information querying. The Time Parameterized R-tree(TPR-tree) employs the idea of parametric bounding rectangles in the R-tree. It can effectively support predictive querying to continuously moving objects.Unfortunately, TPR-tree can not used to historical querying. This paper presents a partial-persistence method in order to extend TPR-tree for querying past information of moving objects. In this method, several TPR-trees will be created for more effectively predictive querying, because TPR-tree has a time horizon limit for predictive querying.Further more, a B-tree will be used to index time dimension. Since the partial-persistence method brings about huge storage space using, this paper also discusses some methods on how to reduce storage space. Finally, this paper presents an extensive experimental study for the proposed method and gives some interesting directions for future work.     

考虑运动对象位置不确定性的位置管理策略

以传统轨道模型为基础,观测构造运动对象历史信息统计样本并分析其特征,设计了基于样本统计的位置预测模型,更好地考虑了运动对象运动随机性的特点,提高了位置预测的准确性;然后在该模型的基础上设计了一种为管理运动对象位置不确定性而设定最佳阈值的方法,这种方法相对于传统的静态阈值策略减少了位置更新的信息代价开销;最后,采用一种基于时间和空间划分的Grid模型构造索引结构,给出了管理运动对象位置信息进行区域查询和kNN（k-Nearest Neighbor）查询的实现过程和算法,是一种进行运动对象位置相关查询的可行性方案.     

LDCQ的距离更新策略

提出了在LDCQ中保证满足误差限制的距离更新策略．移动对象和查询边界的距离远近不同，它们相交的可能性也不同，因而对查询结果的影响也不一样．依据它们之间距离的不同，给予移动对象不同的偏差限：使得越靠近查询边界，移动对象的偏差限越小；反之亦然．其好处是减少了大量的不必要的更新，减轻了系统负荷．     

基于B+树的XML数据查询处理

基于B 树,并借鉴XB树的特点设计一种XM L文档的索引方法.索引关键字分为元素关键值和XM L编码的范围.利用元素编码的范围查询,不必在整XM L文档中搜索,提高了查询效率.对于复杂分支查询,提出了拆分成简单查询路径的规则.在结构化连接问题上,提出了不仅要进行祖孙(父子)关系的连接,还要进行兄弟关系的判断,以得到正确的匹配结果.     

分布式时态索引DTindex

研究基于线序划分（LOP）分布式时态索引技术DTindex．首先,建立DTindex所需数据结构和算法,并讨论分布式时态数据索引DTindex;其次,针对时间数据LOP结构提出基于查询期望的数据分布算,依据DTindex两层索引架构提出P2P部署以减少系统的通信开销．另外,完成仿真以表明索引可行性和有效性．     

An index method for continuous moving objects

There are current, historical and future information about continuously moving spatio-temporal objects. And there are correspondingly spatio-temporal indexes for current, past and future querying. Among the various types of spatio-temporal access methods, no one can support historical and future information querying. The Time Parameterized R-tree(TPR-tree) employs the idea of parametric bounding rectangles in the R-tree. It can effectively support predictive querying to continuously moving objects. Unfortunately, TPR-tree can not used to historical querying. This paper presents a partial-persistence method in order to extend TPR-tree for querying past information of moving objects. In this method, several TPR-trees will be created for more effectively predictive querying, because TPR-tree has a time horizon limit for predictive querying. Further more, a B-tree will be used to index time dimension. Since the partial-persistence method brings about huge storage space using, this paper also discusses some methods on how to reduce storage space. Finally, this paper presents an extensive experimental study for the proposed method and gives some interesting directions for future work.