International Workshop on Collaborative Big Data

Research Article

Towards Efficient Query Processing on Massive Time-Evolving Graphs

Download516 downloads
  • @INPROCEEDINGS{10.4108/icst.collaboratecom.2012.250532,
        author={Arash Fard and Amir Abdolrashidi and Lakshmish Ramaswamy and John Miller},
        title={Towards Efficient Query Processing on Massive Time-Evolving Graphs},
        proceedings={International Workshop on Collaborative Big Data},
        keywords={time-evolving graphs big-data partitioning reachability pattern matching},
  • Arash Fard
    Amir Abdolrashidi
    Lakshmish Ramaswamy
    John Miller
    Year: 2012
    Towards Efficient Query Processing on Massive Time-Evolving Graphs
    DOI: 10.4108/icst.collaboratecom.2012.250532
Arash Fard1,*, Amir Abdolrashidi1, Lakshmish Ramaswamy1, John Miller1
  • 1: UGA
*Contact email:


Time evolving graph (TEG) is increasingly being used as a paradigm for modeling and analyzing dynamic relationships in many emerging domains such as online social networks, World Wide Web and evolutionary genomics. A time-evolving graph consists of a sequence of snapshots of the graph as it evolves over time. The ability to scalably process various types of queries on massive TEGs is central to building powerful analytic applications for these domains. Unfortunately, indexing techniques and cluster computing schemes that have been designed for static graphs are not very effective for processing massive TEGs. Towards designing scalable mechanisms for answering TEG queries, this paper studies three important problems. The first is the distribution of TEG data on the nodes of a cluster computing framework such as Pregel or Giraph so that the computing and communication resources of the cluster are effectively harnessed. The second is the answering of reachability queries on any snapshot of a TEG and the third is that of processing pattern matching queries in TEGs. For each problem, we provide a brief literature survey and explain why trivial extensions of static graph techniques are not adequate for TEGs. We also present our preliminary ideas towards addressing these problems and discuss their benefits.