检索结果-南通市图书馆

计算机应用 2024年第8期44卷 2455-2465页

作者：赵浩宇于自强陈晓萌陈国祥朱慧李博涵烟台大学计算机与控制工程学院山东烟台264005 南京航空航天大学计算机科学与技术学院南京211106

支持关键词搜索的top-K条最优路线查询问题是针对给定的道路网络、兴趣点集合、起点和多个关键词的路线查询。查询旨在找到途经与查询关键词匹配的多个兴趣点的k条最优路线。然而,一些现有研究为降低算法的复杂度,将用户输入关键词的顺... 详细信息

支持关键词搜索的top-K条最优路线查询问题是针对给定的道路网络、兴趣点集合、起点和多个关键词的路线查询。查询旨在找到途经与查询关键词匹配的多个兴趣点的k条最优路线。然而,一些现有研究为降低算法的复杂度,将用户输入关键词的顺序作为到达兴趣点顺序,不适用于对兴趣点到达顺序没有要求的场景,降低了实用性;另一些研究为提高查询效率,设定距离阈值对不符合要求的兴趣点剪枝,然而这类算法无法保证被剪枝的兴趣点一定不能组成最优路线。针对上述问题,提出一种关键词感知的top-K最优路线搜索(KKRS)算法。首先,将整个道路网络划分为多个子网络。然后,采用启发式搜索策略从查询起点所在的子网络开始逐步扩展搜索范围,直至找到top-K条最优路线或遍历完整个道路网络。在扩展过程中,引入子图剪枝策略,用于剪去不包含top-K最优路线的子网络,缩小搜索范围。此外,为避免对每个可能构成最优路线的兴趣点集合依次计算,设计兴趣点序列的剪枝策略,以快速过滤不可能构成最优路线的兴趣点序列,降低计算代价。最后,在真实数据集和合成数据集上对提出的两种剪枝算法进行实验,实验结果表明这两种算法在所有数据集上的子图剪枝上都能达到70%以上的剪枝率,在兴趣点序列剪枝上则能保证60%以上的剪枝率。与目前已有的先进算法大规模路网图下关键词覆盖最优路径查询(KORL)、ROSE-GM(Recurrent Optimal Subroute Expansion Using Greedy Merge Strategy)、OSSCaling和StarKOSR(finding Top-K Optional Sequenced Routes with A*)相比,KKRS算法比对比算法中查询效率较高的StarKOSR算法提高了40%。

关键词：道路网络路线剪枝兴趣点关键词搜索个性化旅游路线

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

支持关键词搜索的top-k最优路线查询问题研究

支持关键词搜索的top-k最优路线查询问题研究

引用

作者：赵浩宇烟台大学

学位级别：硕士

支持关键词搜索的top-k最优路线查询研究的一个典型的应用场景是旅游路线规划。给定一个具有不同兴趣点（Point of Interest,简称POI）、关键字标签和受欢迎程度的道路网络,支持关键词搜索的top-k最优路线查询返回k最优路线。这k条路线... 详细信息

支持关键词搜索的top-k最优路线查询研究的一个典型的应用场景是旅游路线规划。给定一个具有不同兴趣点（Point of Interest,简称POI）、关键字标签和受欢迎程度的道路网络,支持关键词搜索的top-k最优路线查询返回k最优路线。这k条路线依次经过多个POI,这些POI的关键词标签包含所有查询关键词。“最优”是指平衡路线距离和包含POI的累计受欢迎程度的分数后得分最高的k条路线。目前,支持关键词搜索的top-k最优路线查询研究分为两类:限制POI到达顺序的top-k最优顺序路线查询（top-k Optimal Sequenced Route,简称KOSR）和不限制POI到达顺序的top-k行程规划查询（top-k Optimal Trip Planning,简称KOTP）。目前,该领域的研究面临两个重要的挑战:（1）如何对搜索范围进行有效剪枝。由于最优路线考虑其中POI受欢迎程度的得分,因此该领域研究的搜索范围不能简单的划定一个最远距离,然后将距离查询点超过这个最远距离的区域全部剪枝。这是因为距离查询点较远区域中的POI可能会因为高得分而构成分数更高的路线。（2）如何快速对不可能构成top-k最优路线的POI集合进行批量剪枝。对于一个包含n个关键词的查询,若每个关键词对应m个POI,则KOSR需要考虑8))个POI集合,由于每个POI集合对应一条路线,KOSR需要考虑8))条候选路线。对于KOTP来说,每个POI集合对应n!个POI到达顺序不同的路线,因此KOTP需要考虑9)!8))条候选路线。庞大的计算量使得解决该问题的算法需要快速对不可能构成top-k最优路线的POI集合进行批量剪枝。为了对搜索范围进行有效剪枝,本文提出的两种算法将道路网络划分为若干子网络,当查询到达时,估计一个查询点与搜索到达的子网络内的POI所能组成路线的得分上界,对该得分上界判断该子网络中的POI是否有可能构成top-k最优路线。对于得分上界不满足条件的子网络进行剪枝,从而避免对其内部POI进行不必要的搜索。为了快速对不可能构成top-k最优路线的POI集合进行批量剪枝,KOTP-Search在搜索过程中使用POI序列剪枝在不计算序列评分的前提下对不可能代表该集合的序列进行剪枝。POI序列剪枝算法通过使用序列中POI之间的欧式距离评估一个距离的下界,若该下界都不能使该序列被选择代表该集合,则该序列被剪枝。最后,使用加州和北京的真实数据集以及纽约和科罗拉多州的合成数据集进行实验。实验结果表明,所提出的子图剪枝算法和POI序列剪枝算法在不同参数环境下都表现出较高的剪枝效率。接着,引入了已有的先进算法作为基准算法,与提出的KOSR-Search算法和KOTP-Search算法进行了充分的对比和验证。实验证明,提出的两种算法具有较好的查询效率,提出的剪枝算法能够高效的对不可能成为最优路线的候选路线进行剪枝。

关键词：道路网络路线剪枝 POI 关键词搜索个性化旅游路线

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：