博士论文 | 通过多维运输网络处理轮廓线路径查询 170页

多维数据保存数据对象的多个特征的信息。例如，兴趣点（POI）是多维数据，其中每个POI的信息可以是POI类型、位置、价格和评分。对多维数据的Skyline查询用于查找Pareto最优解，其中答案集中的点不互相支配。近年来，越来越多的应用程序致力于多成本网络/图（MCN），其边与不同特征的多个权重相关联。Skyline查询作为Skyline路径查询 (SPQ) 扩展到 MCN。SPQ 用 MCN 内外的两个给定图节点表示。MCN 上的 SPQ 的答案是连接两个给定节点的路径，并且其在多个维度上的路径权重不互相支配。大多数评估 MCN 上的Skyline查询的现有工作都会发现位于网络边的有趣对象。

本文提出了评估多成本交通网络（MCTN）（MCTN 的一种特殊类型）上的Skyline路径查询的方法。本论文包含两个主要部分。第一个主要组件是处理一种新型的Skyline路径查询，称为 CSQ，其评估受到 MCTN 的约束，并且其答案不在网络中。为了评估 CSQ，我们提出了一种精确搜索算法及其通过实现多个属性的改进版本。精确的Skyline解决方案的空间很大，很容易达到数千的量级，并且评估时间很长。我们进一步设计更有效的启发式方法来寻找近似解。我们提出了一种优度测量来评估近似结果的质量。我们创建了一个评估CSQ的原型，通过添加新的实用参数并接受任意查询点，使系统更加友好和实用。

本文的第二个主要组成部分创建了处理通用 SPQ 的新策略，因为我们观察到在解决 CSQ 问题时不存在解决通用 SPQ 的有效解决方案。我们提出了两种方法：一种是由新提出的索引结构支持，另一种是通过整合从机器学习（ML）模型中学到的知识来增强。(i)在基于索引的方法中，我们设计了一种新颖的索引结构——Backbone索引，并提出了相应的索引构建和查询处理方法，以提高寻找SPQ近似路径的效率。与从其他最先进的方法改编来处理路径查询的方法相比，主干索引可以显着改善 SPQ 的查询处理。然而，大图上的近似解的误差仍然很高。(ii) 为了特别解决这个问题，我们提出了一种基于图神经网络（GNN）的模型，称为 Skyline Path-GNN（SP-GNN），以及使用迁移学习的改进版本（TSP-GNN 模型）。这些模型可以将整体搜索空间缩小到更小但更准确。搜索空间的改进有助于在大型 MCTN 上找到更高质量的近似解。

对于这两个论文部分，我们通过进行广泛的实验展示了我们提出的方法的优越性。我们利用多个大型真实道路网络将我们的方法与其他最先进的基线进行比较。实验分析表明，我们提出的方法显着改进了其他基线：（1）改进了 CSQ 的基线方法，查询性能加快了两倍，需要检查的候选数量减少了 20 倍，（ 2）基于主干索引的方法可以在具有100万个节点的路网上在0.5秒内返回近似SPQ解决方案，而其他基线甚至在几天内也无法完成。（3）基于机器学习模型的方法可以为 SPQ 找到更准确的搜索空间，并且可以获得比基于索引的方法更好的近似值。

论文题目：Processing Skyline Path Queries over Multi-Dimensional Transportation Networks

作者：Qixu Gong

类型：2022年博士论文

学校：New Mexico State University （美国新墨西哥州立大学）

下载链接：

链接: https://pan.baidu.com/s/1L4Hlaj1iqoAWm0XmBSr_AA?pwd=y9fx

硕博论文汇总：

链接: https://pan.baidu.com/s/1Gv3R58pgUfHPu4PYFhCSJw?pwd=svp5

微信群                  公众号