(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221079457 7.9 (22)申请日 2022.07.07 (71)申请人 深圳计算科 学研究院 地址 518000 广东省深圳市龙华区民宝路 红山6979园区26座9-10层 (72)发明人 谢珉　王尧舒　 (74)专利代理 机构 深圳市智胜联合知识产权代 理有限公司 4 4368 专利代理师 袁斌 (51)Int.Cl. G06F 16/2455(2019.01) G06F 16/26(2019.01) G06F 16/2457(2019.01) G06F 16/22(2019.01) (54)发明名称 一种基于二维空间的数据查询方法 (57)摘要 本申请提供了一种基于二维空间的数据查 询方法， 通过获取数据库中的若干数据点， 并依 据预设规则和若干所述数据点生成凸包； 依据用 户输入的后悔指数确定缩小比例， 并依据所述缩 小比例确定若干所述数据点对应于所述凸包的 最大可视区域； 依据若干所述数据点的最大可视 区域确定结果集合， 其中， 所述结果集合的可视 区域包围所述凸包； 依据所述结果集合确定包含 最少所述数据点的最简集合。 通过预构建凸包， 使得用户每次在同一个数据集上调用不同的k ‑ regret查询时， 不需要重建凸包， 大大提高查询 效率。 通过 以链表的方式顺时针存储极点， 可 以 快速地计算每 个数据点的可视区域。 权利要求书2页 说明书11页 附图3页 CN 115292362 A 2022.11.04 CN 115292362 A 1.一种基于二维空间的数据查询方法， 其特征在于， 所述方法用于从满足用户给定的 后悔指数的若干结果 集合中查询出最简的集 合， 所述方法包括： 获取数据库中的若干数据点， 并依据预设规则和若干所述数据点 生成凸包； 依据用户输入的后悔指数确定缩小比例， 并依据 所述缩小比例确定若干所述数据点对 应于所述凸包的最大 可视区域； 依据若干所述数据点的最大可视区域确定结果集合， 其中， 所述结果集合的可视区域 包围所述凸包； 依据所述结果 集合确定包 含最少所述数据点的最简集 合。 2.根据权利要求1所述的方法， 其特征在于， 所述依据用户输入的后悔指数确定缩小比 例的步骤， 包括： 依据所述后悔指数确定缩小比例； 依据所述缩小比例对所述数据点进行缩小， 生成缩小数据点； 依据所述缩小比例对所述凸包进行缩小， 生成缩小凸包。 3.根据权利要求2所述的方法， 其特征在于， 所述依据所述缩小比例确定若干所述数据 点对应于所述凸包的最大 可视区域的步骤， 包括： 将所述缩小凸包的极点按顺时针方向进行存 储， 生成链 表； 确定所述链 表与所述缩小数据点形成的夹角最大的第一极点和第二极点； 依据所述第一极点和所述第二极点确定所述缩小数据点对应于所述缩小凸包的所述 最大可视区域。 4.根据权利要求3所述的方法， 其特征在于， 所述将所述缩小凸包的极点顺 时针进行存 储， 生成链 表的步骤之前， 还 包括： 当所述缩小数据点在所述缩小 凸包内部时， 则所述缩小数据点对应于所述缩小 凸包的 最大可视区域 为零； 或， 当所述缩小数据点在所述缩小凸包外部时， 则将所述缩小凸包的极点顺时针进行存 储， 生成链 表。 5.根据权利要求2所述的方法， 其特征在于， 所述依据若干所述数据点的最大可视区域 确定结果 集合， 其中， 所述结果 集合的可视区域包围所述凸包的步骤， 包括： 确定若干所述缩小数据点中的关键数据点， 其中， 所述关键数据点的集合的可视区域 包围所述缩小凸包； 依据所述关键数据点的集 合确定所述结果 集合。 6.根据权利要求5所述的方法， 其特征在于， 所述依据所述结果集合集确定包含最少所 述数据点的最简集 合的步骤， 包括： 确定若干所述结果 集合中包含最少所述关键数据点的所述 最简集合。 7.根据权利要求1所述的方法， 其特 征在于， 还 包括： 当所述用户更新所述后悔指数时， 则依据 更新后的后悔指数对所述凸包以及若干所述 数据点进行缩小。 8.一种基于二维空间的数据查询装置， 其特征在于， 所述装置用于从满足用户给定的 后悔指数的若干结果 集合中查询出最简的集 合， 所述装置包括：权　利　要　求　书 1/2 页 2 CN 115292362 A 2预处理模块， 用于获取数据库中的若干数据点， 并依据预设规则和若干所述数据点生 成凸包； 缩小模块， 用于依据用户输入的后悔指数确定缩小比例， 并依据所述缩小比例确定若 干所述数据点对应于所述凸包的最大 可视区域； 计算模块， 用于依据若干所述数据点的最大可视区域确定结果集合， 其中， 所述结果集 合的可视区域包围所述凸包； 输出模块， 用于依据所述结果 集合确定包 含最少所述数据点的最简集 合。 9.一种计算机设备， 其特征在于， 包括处理器、 存储器及存储在所述存储器上并能够在 所述处理器上运行 的计算机程序， 所述计算机程序被所述处理器执行时实现如权利要求1 至7中任一项所述的方法。 10.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质上存储计算机程 序， 所述计算机程序被处 理器执行时实现如权利要求1至7中任一项所述的方法。权　利　要　求　书 2/2 页 3 CN 115292362 A 3