一种基于固定网络的移动对象运动轨迹索引模型

实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化.IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作.IMTFN由一个管理固定网络的2D R^＊-Tree、一组管理移动对象运动轨迹的1D R^＊-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.     

支持固定网络中频繁更新的移动对象混合索引模型

IMOFN是一种支持固定网络中频繁更新的移动对象混合索引模型,它由一棵描述固定道路网络的2D R*-Tree、一组对时间进行索引的1D R*-Tree和一个存储移动对象实时数据的Hash数组组成.IMOFN既管理了移动对象实时位置,支持位置的频繁更新;又保存了历史轨迹,提供了范围查询、拓扑查询以及轨迹查询等多种有效的实时和历史查询功能.通过实验与FNR-Tree和MON-Tree进行性能比较,证实了IMOFN模型高效的查询能力.     

基于LRS与GDF的移动对象轨迹建模及索引*

针对当前基于受限网络的移动对象管理研究中道路网模型简单,以及以空间平面坐标表达移动对象位置的方法不适合于道路网应用的问题,采用交通应用中流行的GDF路网模型并结合线性参考系统设计了一种针对道路网络的移动对象索引模型。与FNRtree及相关改进的索引方法相比,该方法在移动对象位置更新及添加上有更高的效率,在相关查询上结果更加合理。     

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

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

一种新的分布式并行索引树——DPB^＋-Tree

随着数据规模的增大,查询越来越复杂,分布式并行索引以其高性能而逐渐成为解决复杂查询问题的有效手段。本文提出一种适合于分布式并行的新索引树结构——DPB~ -Tree,该索引树以B~ 树和 hash结构为基础,其叶子结点被组织为有n个散列表元的hash表链,从树的根结点到叶子结点,结点副本数量逐渐减少,并且其数量的变化是动态的。对DPB~ -Tree响应时间的仿真结果表明 DPB~ -Tree系统提高了系统的查询效率,与其它相关策略,如CPB方法比较具有较明显优势。     

一种基于城市交通网络的移动对象全时态索引

高效地管理移动对象以支持查询是一个重要课题.为了支持在城市交通网络上的移动对象过去、现在和将来位置查询,提出了一种新的索引技术.首先提出基于模拟预测的位置表示模型来改进对移动对象将来运动轨迹的预测精度;其次根据城市交通网的特征,设计了一种全新的动态结构自适应单元(AU),将其开发为一个基于R树的索引结构(current-Au);最后在AU的基础上进行扩展(past-AU)使其支持移动对象历史轨迹查询并且避免了大量的死空间.实验证明,AU索引优于传统的TPR树和TB树索引.     

B~+-Tree的改进算法在可复用软构件库中的应用

文章通过对B+-Tree索引算法的改进,将其应用到可复用软构件库中。该改进算法继承了B+-Tree的优点,结合可复用软构件库的特点,将构件库多维数据索引转化为B+-Tree一维数据索引进行存储、查询。通过对比分析,证明了该构件库索引算法大大改进了构件库中构件的查找效率。     

障碍空间中的移动对象位置预测

移动对象的运动基本是在障碍空间里进行的。近几年,已有较多针对障碍空间中范围查询、近邻查询、聚类查询等的研究,但是目前尚没有对障碍空间中移动对象的位置预测进行研究。为此,研究了障碍空间中移动对象的位置预测;采用灰模型与线性模型相结合的办法,提出了一种基于R树的高效的剪枝算法;根据移动对象的运动规律性,提出了几条剪枝策略,从而大大减少了需要处理的障碍对象个数。最后,通过实验验证了算法的准确性和高效性。     

基于动态距离的近邻查询算法研究

移动对象轨迹数据的挖掘是移动对象数据库的一个重要研究方向,从轨迹数据中得到的信息可以应用到交通控制、气候预测以及生态研究等多个方面.基于轨迹数据形式化定义时态距离,用相对简单的近似距离替代精确距离来减少查询过程中的计算量.在关系模型和树结构模型上,实现基于动态距离的距离查询、时间点最近邻查询和时间段最近邻查询算法并对查询效率加以比较.实验结果表明,树模型的查询效率明显高于关系模型.最后在树结构模型中引入嵌入式索引进一步提高了查询效率.     

方向感知的路网移动对象范围查询算法

路网移动对象的范围查询作为空间查询处理中经典的查询类型之一,已经在很多领域中得到了广泛应用。但现有的路网移动对象范围查询方法仍然存在一些不足:一方面,大多数的路网移动对象范围查询方法仅考虑了路网距离,而很少关注范围内移动对象在路网中的运动方向;另一方面,为数不多的考虑了移动对象运动方向的查询方法,几乎都基于欧氏空间进行查询处理,不能应用到大规模的路网来判断范围内的移动对象是否朝向查询点运动。针对在大规模复杂路网下如何高效地查找附近范围内所有朝向查询点的移动对象的问题,提出了一种方向感知的路网移动对象范围查询算法。该算法使用R-tree和简单网格作为底层索引支撑,同时利用一种高效的朝向查询点的路网移动对象判定方法,来高效地查找范围内朝向查询点的移动对象。分别从查询范围、移动对象数量以及网格划分数量3个方面进行实验分析,结果表明方向感知的路网移动对象范围查询算法在合理的参数范围内具有较高的实用性和有效性。     

Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks

Recent research has focused on Continuous K Nearest Neighbor (CKNN) queries in road networks, where the queries and the data objects are moving. Most existing approaches assume the fixed velocity of moving objects. The release of fixed moving velocity makes the query process slowly due to the significant repetitive query cost. In this paper, we study CKNN queries over moving objects with uncertain velocity in road networks. A Distance Interval Model (DIM) is designed to calculate the minimal and maximal road network distances between moving objects and query point. Furthermore, we propose a novel Possibility-based Vague KNN (PVKNN) algorithm to process the query efficiently, which determines the CKNN query results with possibility within each division time subinterval of given time interval by applying the vague set theory. In the PVKNN algorithm, the query efficiency can be improved significantly with the pruning, distilling and possibility-ranking phases. With these phases, the objects candidates are scaled down and the given time interval is divided into subintervals to reduce the repetitive query cost. In addition, an index structure TPR^uv-Tree is designed to efficiently index moving objects with uncertain velocity in road network by involving edge connection and moving objects information. Experiments with simulation and comparison show that significant improvement in the performance of efficiency can be achieved with our proposed algorithms.     

道路网络中的移动对象索引方法研究

基于MON-Tree的思想提出了一种新的索引结构MON⁺-Tree。给出了MON⁺-Tree的数据结构、插入算法和查询算法。最后通过实验MON⁺-Tree、MON-Tree和MONC-Tree进行性能比较,证明MON⁺-Tree为效率更高的查询算法。     

道路网中基于RRN-Tree的CKNN查询

现有针对基于道路网络的CKNN查询研究,主要是将道路网络以路段和节点的形式进行建模,转化成基于内存的有向/无向图,该模型存在2个问题:一个是道路网络中路段数据量大,导致索引结构分支过多、移动对象更新频繁;另一个是图表示方法不能很好地处理十字路口转向、U型转弯等交通规则。针对此问题,提出道路网中基于RRN-Tree的移动对象CKNN查询算法,包括索引结构设计和移动对象查询算法设计,采用路线对道路网建模,基于网络边扩展方式,实现复杂条件下的道路网络CKNN查询。实验结果表明,在各种网络密度和兴趣点对象分布密度下,与经典的IMA/GMA算法相比,基于RRN-Tree索引方法的查询性能提高1.5倍~2.13倍。     

多核处理器中支持频繁访问的B+-Tree

针对传统B+-Tree自顶向下访问模式的缺点,提出了支持频繁访问的FAB+-Tree（Frequent Access B+-Tree）。在B+-Tree的基础上增加了Hash辅助索引,使得访问B+-Tree时直接定位到叶结点,并利用基于内存的直接访问表及位矢量列表提高更新性能。同时基于共享Cache多核处理器,提出了基于流水线的FAB+-Tree多线程访问模块,并优化了该模块的共享Cache访问性能。在实验中,基于开源数据库INGRES实现了FAB+-Tree和多线程访问模块,实验结果表明B+-Tree的访问性能得到显著提高。     

面向移动对象连续k近邻查询的双层索引结构

移动对象连续k近邻（CKNN）查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分.为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构（grid GMM index,GGI）,并设计了移动对象连续k近邻增量查询算法（incremental search for continuous k nearest neighbors,IS-CKNN）.GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能.     

多参数的城市时空热点查询

城市时空热点指城市居民来往次数较多且交通流量较大的时空区域。确定城市时空热点在城市基础设施建设、交通规划、商铺选址、打击犯罪等公共服务领域有大量的应用。目前的热点检测通常是在收集到的全部出租车轨迹上，采用Getis-Ord统计学方法，把轨迹按照时空立方单元进行划分，计算所有轨迹数据覆盖下的热点单元，作为城市时空热点。由于积累的轨迹数量庞大且计算复杂，现有检测算法的重点放在了如何应对海量的数据上。但随着实际应用的扩展，很多需求下的热点检测不需要用到全部数据，适当的数据组织可以使热点检测变得高效。针对实际应用的需要，时空热点查询可以按照用户指定参数（地理范围、日期范围、城市热点大小和时间组织方式），计算时空区域的热度，返回TOP-K热度单元作为时空热点。针对不同的查询参数，时空热点查询需要处理的数据不同，小粒度三维网格索引的轨迹数据组织方法能够快速提取需要处理的轨迹数据。用纽约市出租车轨迹数据集在Spark集群进行查询实验，结果证明这样的索引方法和存储策略能够满足指定参数，并大幅减少查询响应时间。     

基于ODMG Java绑定的面向对象数据库 存储管理①

针对面向对象数据库（OODB）的存储管理进行研究,依照ODMG3．0标准,并以Java绑定方式提供实现方案。通过对典型对象存储结构的研究,给出一种兼顾各种类型数据特点的分层对象存储结构。结合这里使用的体系结构,给出一种基于分槽页结构的改进文件存储结构,将存储单位由页面替换成数据库文件。分析OODB中引入的索引,给出一种基于B＋－Tree,结合继承层次和聚集层次的综合索引策略。     

学习索引:现状与研究展望

索引是数据库系统中用于提升数据存取性能的主要技术之一.在大数据时代，随着数据量的不断增长，传统索引（如B+树）的问题日益突出：（1）空间代价过高.例如，B+树索引需要借助O（n）规模的额外空间来索引原始的数据，这对于大数据环境而言是难以容忍的.（2）每次查询需要多次的间接搜索.例如，B+树中的每次查询都需要访问从树根到叶节点路径上的所有节点，这使得B+树的查找性能受限于数据规模.自2018年来，人工智能与数据库领域的结合催生了“学习索引”这一新的研究方向.学习索引利用机器学习技术学习数据分布和查询负载特征，并用基于数据分布拟合函数的直接式查找代替传统的间接式索引查找，从而降低索引的空间代价并提升查询性能.首先对学习索引技术的现有工作进行了系统梳理和分类;然后，介绍了各种学习索引技术的研究动机与关键技术，对比分析了各种索引结构的优劣;最后，对学习索引的未来研究方向进行了展望.     

基于路网的移动对象索引机制研究

本文基于FNR-Tree的思想提出了一种新的索引算法FNR-Tree，该算法可以实现基于轨迹的查询，而这正是FNR-Tree索引结构所欠缺的，接着给出了FNR-Tree的数据结构和插入算法，查询算法，最后给出了两种索引结构的试验对比结果。