On querying historical evolving graph sequences
Authors:
Open Access
- 1 August 2011
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 4 (11) , 726-737
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 query processing on an EGS and put forward a solution framework called FVF. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in EGS query processing.Keywords
This publication has 15 references indexed in Scilit:
- On graph query optimization in large networksProceedings of the VLDB Endowment, 2010
- Goal-directed shortest-path queries using precomputed cluster distancesACM Journal of Experimental Algorithmics, 2009
- On the evolution of user interaction in Facebook2009
- 3-HOP2009
- Finding time-dependent shortest paths over large graphs2008
- Structure and evolution of online social networks2006
- Graph indexing based on discriminative frequent structure analysisACM Transactions on Database Systems, 2005
- Algorithmics and applications of tree and graph searching2002
- Emergence of Scaling in Random NetworksScience, 1999
- Social Network Analysis1994