File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient Processing of Shortest Path Queries in Evolving Graph Sequences

TitleEfficient Processing of Shortest Path Queries in Evolving Graph Sequences
Authors
KeywordsEvolving graph sequeces
Shortest paths
Social networking
Issue Date2017
PublisherPergamon. The Journal's web site is located at http://www.elsevier.com/locate/is
Citation
Information Systems, 2017, v. 70, p. 18-31 How to Cite?
AbstractIn 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. © 2017 Elsevier Ltd
Persistent Identifierhttp://hdl.handle.net/10722/243523
ISSN
2017 Impact Factor: 2.551
2015 SCImago Journal Rankings: 1.202
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorRen, C-
dc.contributor.authorLo, E-
dc.contributor.authorKao, CM-
dc.contributor.authorZhu, X-
dc.contributor.authorCheng, CK-
dc.contributor.authorCheung, DWL-
dc.date.accessioned2017-08-25T02:55:57Z-
dc.date.available2017-08-25T02:55:57Z-
dc.date.issued2017-
dc.identifier.citationInformation Systems, 2017, v. 70, p. 18-31-
dc.identifier.issn0306-4379-
dc.identifier.urihttp://hdl.handle.net/10722/243523-
dc.description.abstractIn 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. © 2017 Elsevier Ltd-
dc.languageeng-
dc.publisherPergamon. The Journal's web site is located at http://www.elsevier.com/locate/is-
dc.relation.ispartofInformation Systems-
dc.rightsPosting accepted manuscript (postprint): © <year>. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/-
dc.subjectEvolving graph sequeces-
dc.subjectShortest paths-
dc.subjectSocial networking-
dc.titleEfficient Processing of Shortest Path Queries in Evolving Graph Sequences-
dc.typeArticle-
dc.identifier.emailKao, CM: kao@cs.hku.hk-
dc.identifier.emailCheng, CK: ckcheng@cs.hku.hk-
dc.identifier.emailCheung, DWL: dcheung@cs.hku.hk-
dc.identifier.authorityKao, CM=rp00123-
dc.identifier.authorityCheng, CK=rp00074-
dc.identifier.authorityCheung, DWL=rp00101-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.is.2017.05.004-
dc.identifier.scopuseid_2-s2.0-85020737359-
dc.identifier.hkuros275446-
dc.identifier.volume70-
dc.identifier.spage18-
dc.identifier.epage31-
dc.identifier.isiWOS:000412618100003-
dc.publisher.placeUnited Kingdom-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats