利索能及
我要发布
收藏
专利号: 2023109421128
申请人: 哈尔滨理工大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-10-22
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种路网环境下广义近似聚集Skyline查询处理方法,其特征在于,设定路网近似距离dε,若两个对象之间路网距离小于dε,则两个对象路网距离近似;定义一组非空间维度阈值ε1、ε2、…、εn,如果两个对象在各个非空间维度上差值均小于非空间维度阈值,则这两个对象非空间维度近似;不属于任何近似点集的点称为独立点;对于给定的道路网G和查询数据集D,其具体操作步骤包括:步骤一:通过变体的DBSCAN算法对查询数据集D进行近似聚集处理,聚集那些dε内非空间维度近似的对象,聚集那些dε内非空间维度近似的对象,将数据集D中对象划分为近似集和独立点,将近似集中对象统合为一个整体进行处理,形成具有近似点集和独立点的数据集D’;

步骤二:基于步骤一生成的数据集D’中的近似集与独立点对道路网进行划分,构建SSR‑tree索引,将近似集当做一个整体加入到SSR‑tree索引中同一处理;

步骤三:基于SSR‑tree索引结构,将近似集放入到Skyline查询中进行近似集与数据集中独立点的道路网广义聚集支配处理,输出具有二层近似索引结构的结果集合;

所述的变体DBSCAN算法具体步骤为:

步骤一:给定一个道路网G和查询数据集D,D中所有点标记为unvisited,输入半径dε,密度阈值≡1;

步骤二:随机选择一个unvisited点p并标记为visited;

步骤三:若p点路网半径dε领域内至少有一个点,创建新簇C将p加入C,否则标记p为独立点;

步骤四:若p点路网半径dε领域内至少有一个点,将p领域内所有点加入集合N,循环判断N中每一个unvisited点p’;

步骤五:标记p’为visited,判断p’与p是否非空间近似,如果是且p’尚未加入簇且未被标记为独立点,则将p’领域内所有点加入集合N且将p’加入C,若p’与p不存在非空间近似,则标记p’为独立点;

步骤六:当集合N为空时,输出簇C;

步骤七:当数据集D中不存在unvisited点时,运行结束,生成近似数据集D’;

所述的道路网广义聚集支配处理这一步骤,其具体包括:对于生成的数据集D’以及SSR‑tree索引,快速查询D’中的支配集合,道路网广义聚集支配处理就是处理近似集与近似集、近似集与独立点以及独立点与独立点之间的支配关系,最终生成带有近似集的二层索引结构的查询结果集合,近似集与近似集之间支配判断:若近似集A中存在一个点在所有维度上均支配近似集B中所有点,则近似集A路网支配近似集B;近似集与独立点之间支配判断:若独立点p在所有维度上均支配近似集A中所有点,则该点p路网支配近似集A,反之,若近似集A中存在一个点在所有维度上支配独立点p,则近似集A支配独立点p。

2.根据权利要求1所述的一种路网环境下广义近似聚集Skyline查询处理方法,其特征在于,所述的SSR‑tree索引这一步骤,其具体包括:将传统R树叶子节点连接二维List列表,将数据集D’中的近似集视为空间中的一个对象存储在二维List列表中,以此来构建SSR‑tree索引,保证近似集在索引中同一判断。