欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2025100261974
申请人: 昆明理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于HQuadTree的空间范围查询方法,其特征在于:

Step 1:在空间索引构建阶段,给定空间数据集D,构建Hilbert曲线与QuadTree结合的索引结构HQuadTree;

Step 2:在空间范围查询阶段,给定查询q,根据创建的索引结构HQuadTree,实现粗粒度的空间范围查询,在数据集D中查询所有与q相交的节点对应的ID范围,存于结果集RS中。

2.根据权利要求1所述的一种基于HQuadTree的空间范围查询方法,其特征在于,所述Step 1具体为:Step 1.1:构建Hilbert曲线状态视图,Hilbert曲线是一种将多维数据映射到一维整数域上的曲线,其一阶状态根据曲线开口方向的不同分为四种状态:0开口向下、1开口向左、2开口向上和3开口向右,给定1阶状态值,其对应的4种状态下的坐标值和下一阶状态如下:状态0:物理坐标为(0,0)、(0,1)、(1,1)、(1,0);下一阶状态:1、0、0、3;

状态1:物理坐标为(0,0)、(1,0)、(1,1)、(0,1);下一阶状态:0、1、1、2;

状态2:物理坐标为(1,1)、(1,0)、(0,0)、(0,1);下一阶状态:3、2、2、1;

状态3:物理坐标为(1,1)、(0,1)、(0,0)、(1,0);下一阶状态:2、3、3、0;

Step1.2:重分配对象ID,按照Hilbert编码值的顺序,将数据集D中的对象重新编号,分配的ID范围从0到|D|-1;

Step 1.3:构建Hilbert曲线与QuadTree结合的空间索引结构HQuadTree。

3.根据权利要求2所述的一种基于HQuadTree的空间范围查询方法,其特征在于,所述Step 1.3具体为:Step 1.3.1:HQuadTree的每个节点N包含以下属性:

N.IDR:表示当前节点包含的对象ID区间,N.IDR[0]和N.IDR[1]分别表示对应的ID区间的下界和上界;N.Leaf表示是否为叶子节点;

N.Region:为节点N所表示的区域,是一个由左下角坐标P1=(x1,y1)和右上角坐标P2=(x2,y2)表示的空间区域;

N.State:表示当前节点N的Hilbert状态;

Step 1.3.2:HQuadTree结构的根节点代表整个数据空间,每个非叶子节点N包含四个孩子,表示对N对应空间区域的四等分划分,在构建过程中,根据节点的N.State确定四个子节点的顺序和状态,使得节点N的第i个子节点N.Ni对应Hilbert空间中的第i个Quadrant。

4.根据权利要求1所述的空间范围查询方法,其特征在于,所述Step 2具体为:Step 2.1:查询包含q的最小节点,从HQuadTree的根节点N出发,判断q是否包含于N的某个子节点Ni中,若是,递归判断q是否包含于Ni的某个子节点中,否则Ni即为包含q的最小节点,记该节点为MCN,并令MCN对应的节点的深度d=0;

Step 2.2:对MCN节点进行有限的m层下钻,通过下钻返回与q相交的MCN的子节点的对象区间IDR,缩小IDR范围,用I存储下钻后存在的多个IDR区间,并合并相邻IDR以减少区间数量;

Step 2.3:下钻时,在深度优先搜索的基础上,进行有限的广度扩展;首先引入一个堆栈S,初始时将MCN节点N及其层次d=0压入栈后执行Step2.3.1至Step2.3.2;

Step 2.3.1:如果栈非空,则将栈顶节点N及其所在层次d出栈,如果N满足以下条件:1)d=m;2)N是叶节点;3)N包含在q中,则无需继续下钻,令maxID表示I中最后一个IDR的最大ID,若N.IDR[0]-maxID=1,则将其合并到I的最后一个IDR中,并更新maxID←N.IDR[1];否则,将N.IDR添加到I中,并更新maxID←N.IDR[1];

Step 2.3.2:如果栈顶节点N不满足上述条件,采用以下步骤检测N的孩子节点Ni(i∈{1,2,3,4})是否与q相交,从而将查询下钻到d=d+1层,根据当前节点N的层次,分别执行如下两个步骤减少相交判断次数:Step 2.3.2.1:当d=0时,当前栈顶节点为MCN节点N,采用FSFO策略进行相交判断:首先将q与N的孩子节点N1和N2进行相交判断,令fi表示节点Ni与q是否相交的标志,其中1为相交,0表示不相交,当f1和f2不全为1时,直接获得否则f4=f3=O(N.N3,q);

Step 2.3.2.2:当d>1时,当前栈顶节点N为非MCN节点,采用FSFO+的策略进行相交判断:首先将q与N1和N2进行相交判断,若f1f2=11,则继续对N3进行覆盖判断;若f1f2=00,则继续判断q和N3是否相交,若f3=1则进一步判断N4;若f1f2=10或f1f2=01时,则需增加N4或N3的覆盖判断;

Step 2.3.3:将fi=1的节点及其深度d压入S中;

Step 2.4:经过上述步骤,得到多个分段组成的对象区间I,随后,依次遍历I中的每个分段,检查其中每个对象O的坐标是否位于矩形查询框q内,如果位于,则将其加入到结果集RS中。