公开(公告)号：CN108388579A

公开(公告)日：2018-08-10

申请号：CN201810054924.8

申请日：2018-01-19

Applicant: 复旦大学

Inventor： 阚海斌 ,  唐渊 ,  张新鹏 ,  陆尧 ,  任艳丽 ,  李雪峰

IPC: G06F17/30

CPC classification number: G06F17/30333 ,  G06F17/30973

Abstract: 本发明属于计算几何的技术领域，具体涉及一种多维正交区域上基于属性的范围查询方法。问题的定义为：给定一个d维空间，d为一个常数，空间上任意的点对某属性可能为真或为假，对于该d维空间上任意的一个正交区域，判断该区域内某属性是否为真，即是否包含某属性为真的点。本发明在对给定的d维空间进行预处理的情况下，在接近常数的时间复杂度内，解决多维正交区域上基于属性的范围查询问题。相比现阶段存在的传统方法，本发明具有普适性强，占据空间少，查询时间短的优点。本方法适用所有正交形状上基于属性的范围查询，占用至多线性空间，并且可以在常数时间内得到查询结果。

公开(公告)号：CN108388578A

公开(公告)日：2018-08-10

申请号：CN201810054922.9

申请日：2018-01-19

Applicant: 复旦大学

Inventor： 阚海斌 ,  唐渊 ,  张新鹏 ,  陆尧 ,  任艳丽 ,  吴小川

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30979

Abstract: 本发明属于计算几何的应用领域，具体为一种多维特定非正交区域上基于属性的范围查询方法。问题的定义为：给定一个维空间，空间上任意的点对某属性可能为真或为假，对于该维空间上任意的一个非正交区域，判断该区域内某属性是否为真，即是否包含某属性为真的点。本发明在对给定的维空间进行预处理后，在接近常数的时间复杂度内，解决多维特定非正交区域上的基于属性的范围查询问题。相比现在的传统方法，本发明具有普适性强，占据空间少，查询时间短的优点。本方法适用于多维直角边与坐标轴平行的直角三角形，圆形、球形，以及可以分解为周平行直角三角形和多维正交矩形的简单多维多边形。