一种矢量QR树并行索引方法

摘要

本专利公开了一种矢量QR树并行索引方法。在新型并行环境下，针对海量空间数据的高效索引尤为重要，且空间数据索引效率的高低是衡量空间数据库整体性能的关键。目前已有的并行索引方法不能突破方法主节点访问的瓶颈，难以解决进程间的负载均衡问题。针对以上问题，本发明设计了一种针对矢量的Q树和R树协同的并行索引方法，内容包括：1)基于空间对象最小包围矩形的中心点构建QR树，利用多通道法将相邻的空间数据集划分至不同进程，实现进程间任务的负载均衡，且优化索引路径；2)对QR树进行主从式存储，优化索引读取；3)对QR树进行协同检索，突破根节点访问瓶颈。基于空间对象集划分的QR树构建、QR树主从式存储、QR树协同检索共同组成了QR树并行索引方法。本发明所涉及的QR树并行索引可为单机多核、众核与高性能集群环境的海量数据空间索引软件的开发与服务提供一种高效的矢量空间检索方法。

主权项

一种矢量QR树并行索引方法，其特征在于：1)基于空间对象最小包围矩形中心点及空间对象真实范围的QR树构建步骤中，面向任务均衡的多通道空间数据划分通过各通道依据空间对象最小包围矩形的中心点将相邻的空间对象集划分至不同进程，实现进程间空间数据集的负载均衡及检索的任务均衡；基于空间对象最小包围矩形中心点及空间对象真实范围的QR树构建，每个Q树叶子节点都包含两个范围：逻辑范围、实际范围，Q树叶子节点的逻辑范围与对应R树范围合并，得到的新范围为叶子节点的实际范围；遍历Q树叶子节点，计算每个叶子节点的实际范围与逻辑范围比值的最大值，获取所有叶子节点中该比值最大值mev；2)QR树主从式存储步骤中，各进程存储各自创建的QR树，R树集的存储依赖于Q树的存储；3)QR树协同检索步骤中，各进程通过Q树协助检索到R树集，再通过R树集检索空间数据本身。