共享交通的时空轨迹检索与群体发现

为解决共享交通下的共乘用户群体发现效率低、准确率不高问题，依据R-树原理建立GeoOD-Tree索引，并在此基础上提出以最大化共乘率为目标的群体发现策略。首先，对原始时空轨迹数据进行特征提取与标定处理，挖掘有效出行起讫点（OD）轨迹；其次，针对用户起讫点轨迹的特征，建立GeoOD-Tree索引进行有效的存储管理；最后，给出以最大化共乘行程为目标的群体发现模型，并运用K最近邻（KNN）查询对搜索空间剪枝压缩，提高群体发现效率。采用西安市近12000辆出租车营运轨迹数据，选取动态时间规整（DTW）等典型算法与所提算法在查询效率与准确率上进行性能对比分析。与DTW算法相比，所提算法的准确率提高了10.12%，查询效率提高了约15倍。实验结果表明提出的群体发现策略能有效提高共乘用户群体发现的准确率和效率，可有效提升共乘出行方式的出行率。     

一种散乱分层点云的有序化精简方法

针对激光扫描仪所得点云散乱分层的特点,提出一种有序化的精简方法。首先基 于已知标记点建立三维R-tree 和八叉树集成的空间索引,快速准确地获取局部点云数据,保证 良好的数据检索效率。然后根据局部点云数据的参考平面法向量信息,选取工件坐标系中的一 个坐标轴作为参数化的方向,对局部点云数据进行参数化并拟合二次曲面。最后对R-tree 叶节 点内的二次曲面进行有序化采样,使散乱分层的点云变为单层,得到整个型面的有序参考点集。 应用实例表明,该方法适用于大规模的、具有复杂几何特征且存在一定程度散乱分层的点云, 可以有效地提高数据点的整体精确度,且不会丢失点云的细节特征,具有较强的实用性。     

基于R-树的连续最近邻查询算法优化研究

连续最近邻查询是空间数据库中一类重要的查询,在解决这个问题的已有方法中,最有效的是基于R-树的一次遍历算法,但这个算法中没有对R树的遍历顺序进行优化,没能最大程度地删剪结点,就磁盘存取而言是低效率的.对这个算法进行了改进,通过优化遍历顺序减少了磁盘存取数量,提高了I/O效率.     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

MOQ-QR:基于QR-树的连续K近邻查询算法研究*

综合分析了R-树和四叉树在处理移动对象的连续K近邻（简称CKNN）查询算法中的不足,提出了一种基于R树和四叉树索引结构,去解决移动对象连续K近邻查询算法。该算法通过对移动对象分配静态空间,并在研究区域内利用QR-树和hash表作为索引去存储移动对象以此计算查询点与移动对象之间的空间距离。实验证明,该算法与现有算法相比,不仅提高了数据的查询效率,而且降低了系统资源的消耗。     

eGiST:一种改进的通用搜索树

新型应用领域的出现,要求数据库系统提供支持数据类型和查询谓词可扩展的索引结构。该文首先介绍了具有这种可扩展性的通用搜索树结构(GiST),分析了GiST在结点溢出处理策略上的不足,并提出了一种改进的通用搜索树结构eGiST,提高了空间利用率和系统效率。     

多路R树连接的加权处理

空间连接运算是空间数据查询中最重要、最耗时的基本操作之一,其中基于R树的空间连接(RJ)被认为是一种高效的处理机制,但在空间连接的精化阶段处理复杂的空间数据时需要很大的系统开销。基于MBR及直接查询谓词,提出了一种加权处理方法,并扩展了R树结构及MRJ算法。从而优化了多路R树连接的筛选处理,能得到更加有效的候选集;同时,减少了磁盘访问次数,可节省CPU及I/O的时间开销。还通过应用实例验证了其在空间数据库查询优化方面的优势。     

基于主存R树的空间连接的实现

空间查询效率是衡量数据库性能的关键，而空间连接查询是最耗时、最重要的空间查询。对几种典型的空间连接方法作了简单回顾，并具体给出了基于R树的空间连接算法(RJ)在空间数据库管理系统SADBS中的实现。     

基于R-tree的高效异常轨迹检测算法

异常检测是一种流行的数据挖掘任务,但是轨迹数据的异常检测的研究比较少,而且存在的算法也较有局限性,因此J.-G Lee等人提出了TRAOD算法。该算法能够有效地检测出异常的轨迹,但是也存在着缺陷。它的复杂度和准确度比较难平衡,在参数的选取上也比较难,算法的运行时间较长。基于TRAOD的问题,提出一种基于R-tree的高效的异常轨迹检测算法R-TRAOD。该算法通过R-tree对轨迹点进行索引搜索其领域内的轨迹点,然后根据TRAOD算法对R-tree索引出来的轨迹点进行异常轨迹的检测,这样可以提高算法的运行速度。真实数据实验测试表明,该算法比最新的TRAOD异常轨迹挖掘算法效率要高。     

基于R树的空间查询连接处理优化与实现

空间索引作为空间数据库的关键技术,其性能的高低决定着整个空间数据库的效率。通过对现有的多种空间索引结构进行比较分析,基于开源数据库Ingres实现了广度优先R树连接算法(BFRJ),并对其进行了局部优化和全局优化。基于真实数据的实验结果分析,证实了采用适当的全局优化方法的BFRJ优于其他已知的空间连接算法方法。