Diversifying Top-κ Routes with Spatial Constraints

来源 :计算机科学技术学报(英文版) | 被引量 : 0次 | 上传用户:luohz09
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Trip recommendation has become increasingly popular with the rapid growth of check-in data in location-based social networks. Most existing studies focused only on the popularity of trips. In this paper, we consider further the usability of trip recommendation results through spatial diversification. We thereby formulate a new type of queries named spatial diversified top-κ routes (SDκR) query. This type of queries finds k trip routes with the highest popularity, each of which starts at a given starting point, consumes travel time within a given time budget, and passes through points of interest (POIs) of given categories. Any two trip routes reted are diversified to a certain degree defined by the spatial distance between the two routes. We show that the SDkR problem is NP-hard. We propose two precise algorithms to solve the problem. The first algorithm starts with identifying all candidate routes that satisfy the query constraints, and then searches for the κ-route combination with the highest popularity. The second algorithm identifies the candidate routes and builds up the optimal κ-route combination progressively at the same time. Further, we propose an approximate algorithm to obtain even higher query efficiency with precision bounds. We demonstrate the effectiveness and efficiency of the proposed algorithms on real datasets. Our experimental results show that our algorithms find popular routes with diversified POI locations. Our approximate algorithm saves up to 90%of query time compared with the baseline algorithms.
其他文献
现已查明核桃溃疡病是由小穴壳菌危害引起。经两年间多点最佳组合药剂的防治试验及推广应用,取得了很好成效。 Has been identified walnut ulcer disease is caused by the
期刊
期刊
采用问卷和实地抽样调查等方法,对河北省沽源县退耕还林工程的实施情况进行了调查。结果表明:退耕还林工程政策执行情况良好,工程区森林资源及生态状况改善,工程区经济与社会
据了解,随着我国城市化建设进程快速发展,各领域高科技信息化建设突飞猛进,人工免疫服务远远不能满足人民群众日益增长的高质量个性化服务需求,“互联网+”免疫规划信息化水平滞后成为严重影响宁夏预防接种服务质量提升的瓶颈,手工登记差错多速度慢、儿童异地接种不便、儿童个案信息无法掌握和疫苗冷链温度监测不规范等问题凸显。  从2016年起,宁夏卫生健康委打造了贯穿预防接种服务、疫苗流通电子监管、冷链温湿度预警
期刊
期刊
为了使头颅CT片的质量评价工作由经验型向科学型发展迈进一步 ,从而推动QA和QC活动的开展 ,我们探讨将正常头颅CT片的空气区、脑室前角区、半卵圆中心区、丘脑区、及颅骨区的
这次会议的主要任务是认真贯彻落实省委、省政府关于加强新农村建设的有关部署,突出推进农村环境综合整治工作,进一步提高认识、强化措施、加强领导,全面提升全省新农村建设
在红早酥梨园杂草优势种草高10~20cm时期,应用100~150mL/667m2百草枯(20%克无踪水剂)对杂草进行茎叶喷雾处理,处理后15d,对1年生、多年生杂草除草效果达92.4%~98.3%,处理后30
子宫腔以外存在有功能的子宫内膜腺体和基质,即相对于在位内膜存在的异位内膜称为子宫内膜异位症(EMs).盆腔是绝大多数EMs发生的主要部位,且直接影响女性患者不孕情况.黄海波