DSE精选文章 | 具有POI首选项的Top k更优排序道路查询

文章介绍

更优次序途径(OSR)查询是智能城市道路规划中的一个热门问题，以觅觅从一个起始位置以特定的次序颠末多个兴致点（POI）的最小间隔道路。现实上，将POI停止评级摆列，有助于用户做出决策。现有的OSR查询漠视了一个事实，即统一类此外POI可能有差别的评分，那可能会影响用户的道路抉择。该文研究了OSR查询的一种新改编算法，即评分约束的更优次序路途径查询(RCOSR)，该办法中更优次序途径中的每个POI的评分都超越查询阈值。为了有效地处置RCOSR查询，该文起首扩展了现有的TD-OSR算法，提出名为MTDOSR的基线办法。针对MTDOSR算法的不敷，设想了一种新的RCOSR算法，即更优子途径扩展(OSE)算法。尝试成果表白，该算法的性能明显优于现有算法。图1展现了路网中OSR查询的一个例子。

图1. 具有评分的兴致点（POI）的路网

该文的奉献总结如下:

提出并处理评分约束更优次序途径查询问题

提出MTDOSR算法处理RCOSR查询和低效率问题

提出OSE算法, 摘用动态规划体例扩展更优子途径，并提出索引(RNII)用以加速OSE中POI对的间隔计算

在OSE和RNII的根底上，进一步提出ROSE算法，迭代计算更优评分约束序列途径做为引导途径来批示途径摸索

将ROSE扩展为kROSE，以处理前k个RCOSR查询

尝试效果

该文尝试摘用实在和合成数据集，此中CA数据集是加利福尼亚实在的道路收集，OL数据集是Oldenburg城市实在的道路收集。此外，文章生成的合成数据集中包罗100,000个节点，125,000个道路边沿，10,000个POI（随机设置从0到100的评级评分）属于50个类别。所有算法都利用C++实现。

如表1所示，该文对模子算法停止了性能评估，一方面，评估RCOSR算法的效率，比力了在各类参数下的查询时间和被拜候的节点数。另一方面，评判RNII的效率，利用RNII比力了参考节点战略的查询时间和笼盖率。

表1. 参数范畴和默认值

*Query size是指查询规模(即查询类此外数量)

**Network size (×1000)是指收集规模(即|V|)

该文还在查询规模、收集大小、POI数量、节点均匀度四个方面，比力了利用随机战略的ROSE(称为ROSE_RD)、利用贪婪合并战略的ROSE(称为ROSE_GM)和利用两个实在数据集的MTDOSR的效率。

如图2所示，跟着查询规模的增加，所有算法的查询时间和拜候节点数都在增加。关于OL数据集，ROSE的优势比CA数据集更明显。

图2. 在现实路网中的性能w.r.t查询大小

如图3所示，合成数据集中ROSE和MTDOSR针对差别收集大小的查询时间和拜候节点数。两种算法的查询时间跟着收集规模的增大而增大，而ROSE的性能明显优于MTDOSR。

图3. 时间w.r.t.收集大小

如图4所示，就POI数的影响而言，ROSE优于MTDOSR，特殊是在POI数较小时。跟着POI个数的增加，两种算法的查询时间都在增加，且ROSE对POI个数愈加灵敏。

图4. 时间w.r.t POI数量

如图5所示，比力了算法性能与节点均匀度的关系。两种算法跟着节点均匀度的增加，查询时间和拜候节点数都略有增加。MTDOSR中利用堆存储整个途径的节点，但摆列和搜刮堆十分耗时，而ROSE摘用A*算法计算两个POI之间的间隔，只需要庇护堆中的少量节点。

图5. 时间w.r.t节点均匀度

结语

该文研究评分约束的更优次序途径(RCOSR)查询，指的是更优次序途径所含POI的评级得分都应称心用户阈值。为有效处置查询，该文优化TD-OSR算法做为基线办法，称其为MTDOSR。针对该算法不敷之处，该文提出一种新的更优子路由扩展(OSE)算法。此外，该文还提出参考节点倒排索引(RNII)来加速OSE中的间隔计算。基于OSE和RNII，进一步提出新的轮回更优子途径扩展算法（ROSE）。之后，进一步研究RCOSR查询的改编办法，即RCkOSR查询。最初该文评估综合性能，验证所提目标和算法的有效性。

扫码免费阅读全文

做者简介

墨怀杰

墨怀杰，博士，于2018年获得东北大学计算机软件与理论专业博士学位。攻读博士学位期间，赴美国宾州州立大学结合培育提拔。担任CCF中国数据库专委会施行委员。现为中山大学副研究员，次要研究标的目的包罗：空间数据库，社交收集及隐私庇护。目前在数据库范畴颁发多篇高程度学术论文，此中包罗SIGMOD，TKDE,ICDE等多篇顶级学术论文。主持国度天然科学基金1项，广东面上基金1项。

黎文彬

黎文彬，硕士，于2021年获得中山大学计算机专业硕士学位。次要研究范畴为空间数据库,途径查询。

刘威

刘威， 博士，副研究员，2018年6月博士结业于中山大学计算机科学与手艺专业，并在中山大学数据科学与计算机学院担任副研究员。担任CCF中国数据库专委会通信委员。近三年，在人工智能、数据发掘等范畴的重要会议期刊颁发多篇文章，包罗IJCAI、 ACL、等。研究兴致包罗：个别行为阐发、时空数据发掘、选举系统等。

印鉴

印鉴，传授，于1989年获武汉大学学士学位，1994年硕博连读，获武汉大学博士学位。现任中山大学人工智能学院副院长。主持国度天然科学基金重点和面上项目、国度科技部严重专项方案项目子课题、广东省天然科学基金团队和重点项目、广东省重点研发方案项目等三十多个项目标研究工做。目前，次要处置人工智能、机器进修、大数据阐发与处置、数据库与数据发掘等方面的研究工做。

徐建良

徐建良，传授，现任香港浸会大学，于1998年获得浙江大学计算机科学与工程学士学位，2002年获得香港科技大学计算机科学博士学位后加进香港浸会大学计算机科学系，曾为宾夕法尼亚州立大学大学公园分校和复旦大学的拜候学者。现任香港浸会大学担任区块链和金融科技尝试室主任，并指导数据库研究小组。他的研究标的目的是大数据、区块链、挪动计算、数据平安和隐私。

期刊简介

Data Science and Engineering(DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格 天然（Springer Nature）出书的开放获取期刊。DSE努力于颁发所有和数据科学与工程范畴相关的关键科学问题与前沿研究热点，以大数据做为研究重点，征稿范围次要包罗：数据自己，数据信息提取办法，数据计算理论，以及用来阐发与治理数据的手艺和系统。

目前期刊已被EI、ESCI与SCOPUS收录，CiteScore 2021为6.4，在Computer Science Applications范畴排名# 157/747（位列前21%）。稿件处置费由赞助商中新赛克（Sinovatio）承担，欢送各人免费下载阅读期刊全文，并积极投稿。

欢送扫码进进期刊主页