[发明专利]一种基于网格划分的并行空间查询方法及其系统

摘要

本发明提供一种基于网格划分的并行空间查询方法及其系统，方法包括依据四叉树对查询空间对象以及目标空间对象集合所处的空间范围进行网格划分并编号；对各个空间对象构建空间分片索引，依据空间分片索引中的所述最小网格的编号，从目标空间对象集合中，获取与查询空间对象对应的所述最小网格存在相交关系的目标空间对象。本发明使用四叉树进行空间网格划分和网格编号，使每个空间对象都被包含在一个对应的四叉树网格中，从而消除边界对象处理问题；同时，依据四叉树编码中隐含的空间拓扑关系，筛除明显不符合查询条件的空间对象，实现对候选目标空间对象的预过滤，从而减少任务候选集，再次提高并行查询效率。

主权项

1.一种基于网格划分的并行空间查询方法，其特征在于，包括：获取查询空间对象以及目标空间对象；获取目标空间对象集合；依据四叉树对所述查询空间对象以及目标空间对象集合所处的空间范围进行网格划分；依据四叉树对网格进行编号；对查询空间对象以及目标空间对象集合内的各个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR；依据空间分片索引中的所述最小网格的编号，从目标空间对象集合中，获取与查询空间对象对应的所述最小网格存在相交关系的目标空间对象，构成第一目标空间对象集合。