File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.is.2017.05.004
- Scopus: eid_2-s2.0-85020737359
- WOS: WOS:000412618100003
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Efficient Processing of Shortest Path Queries in Evolving Graph Sequences
Title | Efficient Processing of Shortest Path Queries in Evolving Graph Sequences |
---|---|
Authors | |
Keywords | Evolving graph sequeces Shortest paths Social networking |
Issue Date | 2017 |
Publisher | Pergamon. 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? |
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. © 2017 Elsevier Ltd |
Persistent Identifier | http://hdl.handle.net/10722/243523 |
ISSN | 2023 Impact Factor: 3.0 2023 SCImago Journal Rankings: 1.201 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ren, C | - |
dc.contributor.author | Lo, E | - |
dc.contributor.author | Kao, CM | - |
dc.contributor.author | Zhu, X | - |
dc.contributor.author | Cheng, CK | - |
dc.contributor.author | Cheung, DWL | - |
dc.date.accessioned | 2017-08-25T02:55:57Z | - |
dc.date.available | 2017-08-25T02:55:57Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Information Systems, 2017, v. 70, p. 18-31 | - |
dc.identifier.issn | 0306-4379 | - |
dc.identifier.uri | http://hdl.handle.net/10722/243523 | - |
dc.description.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. © 2017 Elsevier Ltd | - |
dc.language | eng | - |
dc.publisher | Pergamon. The Journal's web site is located at http://www.elsevier.com/locate/is | - |
dc.relation.ispartof | Information Systems | - |
dc.rights | Posting 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.subject | Evolving graph sequeces | - |
dc.subject | Shortest paths | - |
dc.subject | Social networking | - |
dc.title | Efficient Processing of Shortest Path Queries in Evolving Graph Sequences | - |
dc.type | Article | - |
dc.identifier.email | Kao, CM: kao@cs.hku.hk | - |
dc.identifier.email | Cheng, CK: ckcheng@cs.hku.hk | - |
dc.identifier.email | Cheung, DWL: dcheung@cs.hku.hk | - |
dc.identifier.authority | Kao, CM=rp00123 | - |
dc.identifier.authority | Cheng, CK=rp00074 | - |
dc.identifier.authority | Cheung, DWL=rp00101 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.is.2017.05.004 | - |
dc.identifier.scopus | eid_2-s2.0-85020737359 | - |
dc.identifier.hkuros | 275446 | - |
dc.identifier.volume | 70 | - |
dc.identifier.spage | 18 | - |
dc.identifier.epage | 31 | - |
dc.identifier.isi | WOS:000412618100003 | - |
dc.publisher.place | United Kingdom | - |
dc.identifier.issnl | 0306-4379 | - |