Paper Info
Title
Efficient processing of shortest path queries in evolving graph sequences.
Abstract
In many applications, information is best represented as graphs. In a dynamic world, information changes and so the graphs representing the information evolve with time. We propose that historical graph-structured data be maintained for analytical processing. We call a historical evolving graph sequence an EGS. We observe that in many applications, graphs of an EGS are large and numerous, and they often exhibit much redundancy among them. We study the problem of efficient shortest path query processing on an EGS and put forward a solution framework called FVF. Two algorithms, namely, FVF-F and FVF-H, are proposed. While the FVF-F algorithm works on a sequence of flat graph clusters, the FVF-H algorithm works on a hierarchy of such clusters. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in shortest query processing on EGSs. Comparing FVF-F and FVF-H, the latter gives a larger speedup, is more flexible in terms of memory requirements, and is far less sensitive to parameter values.
Year
DOI
Venue
2017
10.1016/j.is.2017.05.004
Information Systems
Keywords
Field
DocType
Evolving graph sequeces,Shortest paths,Social networking
Data mining,Cluster (physics),Shortest path problem,Computer science,Theoretical computer science,Redundancy (engineering),Shortest Path Faster Algorithm,Hierarchy,Longest path problem,Database,K shortest path routing,Speedup
Journal
Volume
ISSN
Citations 
70
0306-4379
1
PageRank 
References 
Authors
0.37
23
6
Name
Order
Citations
PageRank
Chenghui Ren1653.30
Eric Lo281351.50
Ben Kao32358194.98
Xinjie Zhu4532.42
Reynold Cheng53069154.13
David W. Cheung61511156.71