一种路网环境下广义近似聚集Skyline查询处理方法

一种路网环境下广义近似聚集skyline查询处理方法
技术领域
1.本发明涉及数据查询技术领域，具体是一种路网环境下广义近似聚集skyline查询处理方法。


背景技术：

2.skyline查询，面向推荐系统，用于解决多目标决策问题。skyline查询是一种在多属性数据集中查找最优解的查询方法。它的目标是找到一组数据对象（也称为记录或数据点），这些对象在多个属性上都优于其他对象，即它们在某些属性上具有最佳的性能或价值。在实际应用中，skyline查询可以用于各种领域，如数据挖掘、决策支持、多目标优化等。它能够帮助用户从大量的数据中筛选出最有价值或最有潜力的选择，提供决策的参考和洞察。
3.路网中的skyline查询不仅考虑已有的非空间属性，同时加入了路网距离属性，使得skyline查询变得更加复杂，已有的路网skyline算法仅仅是将距离当做一个属性，如果路网中两个对象距离很近的话，可以近似认为他们的距离属性上的值是相同的；同时路网中可能存在大量相似点重复判断的问题，以及skyline结果集过少的问题。


技术实现要素：

4.为了解决上述问题，本发明的目的是提供一种路网环境下广义近似聚集skyline查询处理方法，丰富skyline查询结果集，并且减少近似对象间的判断，提高效率，解决传统skyline查询结果集过少的问题。
5.本发明技术方案是：一种路网环境下广义近似聚集skyline查询处理方法，包括以下步骤：
6.步骤一：对于给定的道路网g和查询数据集d，通过变体的dbscan算法对查询数据集d进行近似聚集处理，形成具有近似点集的数据集d’。
7.步骤二：基于数据集d’对道路网进行划分，构建ssr-tree索引。
8.步骤三：基于ssr-tree索引结构，进行近似集与数据集中独立点的道路网广义聚集支配判断，输出具有二层近似索引结构的结果集合。
9.所述的通过变体的dbscan算法对查询数据集d进行近似聚集处理这一步骤，其具体包括：
10.设定路网近似距离d
ε
，若两个对象之间路网距离小于d
ε
，则两个对象路网距离近似；定义一组非空间维度阈值ε1、ε2、
…
、εn。如果两个对象在各个非空间维度上差值均小于非空间维度阈值，则这两个对象非空间维度近似；遍历数据集d中点进行变体dbscan计算，聚类半径为d
ε
，聚集那些d
ε
内非空间维度近似的对象，形成近似集，不属于任何近似点集的点称为独立点。
11.所述的ssr-tree索引这一步骤，其具体包括：
12.将传统r树叶子节点连接二维list列表，将数据集d’中的近似集视为空间中的一
个对象存储在二维list列表中，以此来构建ssr-tree索引，保证近似集可以在索引中同一判断。
13.所述的道路网广义聚集支配处理这一步骤，其具体包括：
14.给定包含近似集和独立点的数据集d’，确定近似集与近似集、近似集与独立点以及独立点与独立点之间的支配关系。近似集与近似集之间支配判断：若近似集a中存在一个点在所有维度上（包括路网距离维度）均支配近似集b中所有点，则近似集a路网支配近似集b；近似集与独立点之间支配判断：若独立点p在所有维度上（包括路网距离维度）均支配近似集a中所有点，则该点p路网支配近似集a，反之，若近似集a中存在一个点在所有维度上（包括路网距离维度）支配独立点p，则近似集a支配独立点p，路网环境下广义近似聚集skyline查询处理方法具体步骤包括：
15.步骤一：创建一个空的结果集，用于存储找到的skyline数据点。
16.步骤二：逐个处理数据点：通过ssr-tree索引快速确定距离维度上各个对象（近似集和独立点）之间的支配关系。
17.步骤三：支配判断：判断当前对象（近似集和独立点）是否被结果集中的任何对象所支配。如果当前对象被支配，则不加入结果集。
18.步骤四：非支配判断：如果当前对象不被任何结果集中的对象所支配，则执行下一步。
19.步骤五：支配结果集中的对象：判断结果集中的对象是否被当前对象所支配。如果结果集中的某个对象被当前对象支配，则将该对象从结果集中移除。
20.步骤六：加入结果集：将当前对象加入结果集。
21.本发明方法的有益效果：本发明通过寻找合并路网中近似对象。并建立有效的ssr-tree索引结构，加快近似集的计算效率，通过提出的广义聚集支配方法减少近似数据之间的判断，丰富skyline查询结果集，增加skyline查询结果。使查询结果更加符合用户的需要。
附图说明
22.图1是本发明一种路网环境下广义近似聚集skyline查询处理方法的步骤流程图。
23.图2是本发明具体实施例变体dbscan近似聚类算法流程图。
24.图3是本发明具体实施例ssr-tree索引示例图。
实施方式
25.下面结合附图和具体实施例对本发明做进一步的详细说明。对于以下实施例中的步骤编号，其仅为了便于阐述说明而设置，对步骤之间的顺序不做任何限定，实施例中的各步骤的执行顺序均可根据本领域技术人员的理解来进行适应性调整。
26.参照图1和图2 ，本发明提供了一种路网环境下广义近似聚集skyline查询处理方法，该方法包括以下步骤：
27.步骤一：对于给定的道路网g和查询数据集d，通过变体的dbscan算法对查询数据集d进行近似聚集处理，形成具有近似点集的数据集d’；设定路网近似距离d
ε
，若两个对象之间路网距离小于d
ε
，则两个对象路网距离近似；定义一组非空间维度阈值ε1、ε2、
…
、εn。如
果两个对象在各个非空间维度上差值均小于非空间维度阈值，则这两个对象非空间维度近似；遍历数据集d中点进行变体dbscan计算，聚类半径为d
ε
，聚集那些非空间维度近似的对象，形成近似集，不属于任何近似点集的点称为独立点。
28.变体的dbscan算法具体步骤如图3所示：
29.输入：道路网g和查询数据集d，密度半径d
ɛ
。
30.输出：带有近似集的数据集d’。
31.1、给定一个道路网g和查询数据集d，d中所有点标记为unvisited，输入半径d
ɛ
，密度阈值≡1。
32.2、随机选择一个unvisited点p并标记为visited。
33.3、若p点路网半径d
ɛ
领域内至少有一个点，创建新簇c将p加入c，否则标记p为独立点。
34.4、若p点路网半径d
ɛ
领域内至少有一个点，将p领域内所有点加入集合n，循环判断n中每一个unvisited点p’。
35.5、标记p’为visited，判断p’与p是否非空间近似，如果是且p’尚未加入簇且未被标记为独立点，则将p’领域内所有点加入集合n且将p’加入c，若p’与p不存在非空间近似，则标记p’为独立点。
36.6、当集合n为空时，输出簇c。
37.7、当数据集d中不存在unvisited点时，运行结束，生成近似数据集d’。
38.步骤二：ssr-tree索引如图3所示，将传统r树叶子节点连接二维list列表，将数据集d’中的近似集视为空间中的一个对象存储在二维list列表中，以此来构建ssr-tree索引，保证近似集可以在索引中同一判断。
39.1、我们将近似集抽象为数据集中一个对象来进行r树索引的构建，我们用一个二维list列表替换r树索引的根节点。
40.2、二维list列表用于存储在该r树分支下的近似集或者独立点。
41.3、通过索引快速剪枝数据集，通过我们提出的广义聚集skyline查询进行近似集同独立点之间的支配判断。
42.步骤三：所述的道路网广义聚集支配处理这一步骤，其具体包括：确定近似集与近似集、近似集与独立点以及独立点与独立点之间的支配关系。近似集与近似集之间支配判断：若近似集a中存在一个点在所有维度上（包括路网距离维度）均支配近似集b中所有点，则近似集a路网支配近似集b；近似集与独立点之间支配判断：若独立点p在所有维度上（包括路网距离维度）均支配近似集a中所有点，则该点p路网支配近似集a，反之，若近似集a中存在一个点在所有维度上（包括路网距离维度）支配独立点p，则近似集a支配独立点p；独立点与独立点之间的支配同传统skyline支配。
43.道路网广义聚集skyline算法具体步骤如下：
44.输入：道路网g和查询数据集d’，ssr-tree索引。
45.输出：道路网广义聚集skyline查询的结果，包含近似集和独立点的二层近似索引结构。
46.1、创建一个空的结果集，用于存储找到的skyline数据点。
47.2、逐个处理数据点：通过ssr-tree索引快速确定距离维度上各个对象（近似集和
独立点）之间的支配关系。
48.2.a、支配判断：判断当前对象（近似集和独立点）是否被结果集中的任何对象所支配。如果当前对象被支配，则不加入结果集。
49.2.b、非支配判断：如果当前对象不被任何结果集中的对象所支配，则执行下一步。
50.2.c、支配结果集中的对象：判断结果集中的对象是否被当前对象所支配。如果结果集中的某个对象被当前对象支配，则将该对象从结果集中移除。
51.3、加入结果集：将当前对象加入结果集。
52.以上是对本发明的较佳实施进行了具体说明，但本发明创造并不限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做作出种种的等同变形或替换，这些等同的变形或替换均包含在本技术权利要求所限定的范围内。

技术特征：
1.一种路网环境下广义近似聚集skyline查询处理方法，其特征在于，设定路网近似距离d
ε
，若两个对象之间路网距离小于d
ε
，则两个对象路网距离近似；定义一组非空间维度阈值ε1、ε2、
…
、ε
n
。如果两个对象在各个非空间维度上差值均小于非空间维度阈值，则这两个对象非空间维度近似；不属于任何近似点集的点称为独立点；对于给定的道路网g和查询数据集d，其具体操作步骤包括：步骤一：通过变体的dbscan算法对查询数据集d进行近似聚集处理，聚集那些d
ε
内非空间维度近似的对象，聚集那些d
ε
内非空间维度近似的对象，将数据集d中对象划分为近似集和独立点，将近似集中对象统合为一个整体进行处理，形成具有近似点集和独立点的数据集d’；步骤二：基于步骤一生成的数据集d’中的近似集与独立点对道路网进行划分，构建ssr-tree索引，将近似集当做一个整体加入到ssr-tree索引中同一处理；步骤三：基于ssr-tree索引结构，将近似集放入到skyline查询中进行近似集与数据集中独立点的道路网广义聚集支配判断，输出具有二层近似索引结构的结果集合。2.根据权利要求1所述的一种路网环境下广义近似聚集skyline查询处理方法，其特征在于，所述的通过变体的dbscan算法对查询数据集d进行近似聚集处理这一步骤，其具体包括：根据道路网g，遍历数据集d中点进行变体dbscan计算，路网聚类半径为d
ε
，聚类密度≡1，聚集那些d
ε
内非空间维度近似的对象，形成近似集，不属于任何近似点集的点称为独立点，生成包含近似集和独立点的数据集d’。3.根据权利要求1所述的一种路网环境下广义近似聚集skyline查询处理方法，其特征在于，所述的ssr-tree索引这一步骤，其具体包括：将传统r树叶子节点连接二维list列表，将数据集d’中的近似集视为空间中的一个对象存储在二维list列表中，以此来构建ssr-tree索引，保证近似集可以在索引中同一判断。4.根据权利要求1所述的一种路网环境下广义近似聚集skyline查询处理方法，其特征在于，所述的道路网广义聚集支配处理这一步骤，其具体包括：对于我们生成的数据集d’以及ssr-tree索引，快速查询d’中的支配集合，确定近似集与近似集、近似集与独立点以及独立点与独立点之间的支配关系。最终生成带有近似集的二层索引结构的查询结果集合。

技术总结
本发明公开了一种路网环境下广义近似聚集Skyline查询处理方法，本发明将路网中大量距离相近且非空间维度相似的点聚集在一起形成近似点集融入Skyline查询。本方法包括：对于给定的道路网G和查询数据集D，通过变体的DBSCAN算法对查询数据集D进行近似聚集处理，形成具有近似点集的数据集D’；基于数据集D’对道路网划分构建SSR-tree索引；基于SSR-tree索引结构进行近似集与独立点的道路网广义聚集支配判断，输出具有二层近似索引结构的结果集合。通过本发明，能够减少大量近似数据点的判断，提高效率，并且丰富Skyline查询结果集，解决传统Skyline查询结果集过少的问题。本发明作为一种路网环境下广义近似聚集Skyline查询处理方法，可广泛应用于数据查询技术领域。可广泛应用于数据查询技术领域。可广泛应用于数据查询技术领域。


技术研发人员：李松 杨晓龙 李春红
受保护的技术使用者：哈尔滨理工大学
技术研发日：2023.07.29
技术公布日：2023/10/11