Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2020, Vol. 60 Issue (8): 656-663    DOI: 10.16511/j.cnki.qhdxxb.2020.22.007
  专题:数据库 本期目录 | 过刊浏览 | 高级检索 |
杜明1, 郑凯文1, 陈子阳2, 周军锋1
1. 东华大学 计算机科学与技术学院, 上海 201620;
2. 上海立信会计金融学院 信息管理学院, 上海 201620
TFP: Efficient algorithm for fastest path queries
DU Ming1, ZHENG Kaiwen1, CHEN Ziyang2, ZHOU Junfeng1
1. College of Computer Science and Technology, Dong Hua University, Shanghai 201620, China;
2. School of Information Management, Shanghai Lixin University of Accounting and Finance, Shanghai 201620, China
全文: PDF(1056 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 给定时态图,最快路径查询可以得到两点之间用时最短的路径对应的时间跨度。高效回答最快路径查询可有效提升系统的易用性,增强用户黏度。然而,现有方法在处理时态图上的最快路径查询时,因其处理策略造成大量冗余操作,查询处理效率不高。该文提出3个启发式规则用于减少冗余计算,并给出了合理性证明。基于3个启发式规则,提出了一种高效的最快路径通用查询算法。该方法在多个数据集上比原有方法减少了5~8倍的可达性查询调用,显著减少了冗余计算,具有更高的查询处理效率。
E-mail Alert
关键词 时态图可达性查询最快路径查询启发式规则    
Abstract:The fastest path query returns the time span of the shortest path between two vertices in a temporal graph. Efficient responses to a fastest path query effectively improve system use and enhance user desire to continue using the system. However, existing fastest path query methods on temporal graphs have many redundant operations in their processing strategies, so they are not very efficient. Three heuristic rules are presented here to reduce the number of redundant computations with verification of their effectiveness. These three heuristic rules are then integrated into an efficient universal query algorithm to find the fastest path. This method reduces the query invocation reachability 5-8 fold on various data sets compared with the original method by significantly reducing redundant computations for higher query processing efficiencies.
Key wordstemporal graph    reachability query    fastest path query    heuristic rules
收稿日期: 2019-10-25      出版日期: 2020-06-17
杜明, 郑凯文, 陈子阳, 周军锋. TFP:高效的最快路径查询处理方法[J]. 清华大学学报(自然科学版), 2020, 60(8): 656-663.
DU Ming, ZHENG Kaiwen, CHEN Ziyang, ZHOU Junfeng. TFP: Efficient algorithm for fastest path queries. Journal of Tsinghua University(Science and Technology), 2020, 60(8): 656-663.
链接本文:  或
[1] KOSSINETS G, KLEINBERG J, WATTS D. The structure of information pathways in a social communication network[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA, 2008:435-443.
[2] TANG J, SCELLATO S, MUSOLESI M, et al. Small-world behavior in time-varying graphs[J]. Physical Review E, 2010, 81(2):055101.
[3] WU H H, HUANG Y Z, CHENG J, et al. Reachability and time-based path queries in temporal graphs[C]//Proceedings of the 32nd International Conference on Data Engineering. Helsinki, Finland, 2016:145-156.
[4] WU H H, CHENG J, HUANG S L, et al. Path problems in temporal graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(9):721-732.
[5] XUAN B B, FERREIRA A, JARRY A. Computing shortest, fastest, and foremost journeys in dynamic networks[J]. International Journal of Foundations of Computer Science, 2003, 14(2):267-285.
[6] WANG S B, LIN W Q, YANG Y, et al. Efficient route planning on public transportation networks:A labelling approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia, 2015:967-982.
[7] YANO Y, AKIBA T, IWATA Y, et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. San Francisco, USA, 2013:1601-1606.
[8] CHENG J, HUANG S L, WU H H, et al. TF-Label:A topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York, USA, 2013:193-204.
[9] JIN R M, WANG G. Simple, fast, and scalable reachability oracle[J]. Proceedings of the VLDB Endowment, 2013, 6(14):1978-1989.
[10] YILDIRIM H, CHAOJI V, ZAKI M J. GRAIL:Scalable reachability index for large graphs[J]. Proceedings of the VLDB Endowment, 2010, 3(1-2):276-284.
[11] WEI H, YU J X, LU C, et al. Reachability querying:An independent permutation labeling approach[J]. The VLDB Journal, 2018, 27(1):1-26.
[12] VELOSO R R, CERF L, MEIRA W JR, et al. Reachability queries in very large graphs:A fast refined online search approach[C]//Proceedings of the 17th International Conference on Extending Database Technology (EDBT). Athens, Greece, 2014:511-522.
[13] SEUFERT S, ANAND A, BEDATHUR S, et al. FERRARI:Flexible and efficient reachability range assignment for graph indexing[C]//Proceedings of the 29th International Conference on Data Engineering. Brisbane, Australia, 2013:1009-1020.
No related articles found!
Full text



版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持