Low latency queries on big graph data

The availability of large datasets and on-demand system capacity to analyze these datasets has led to exciting new applications in the context of big graph data. Many big graph data applications --- social search and ranking, personalized and socially-sensitive search, social network analysis, online advertising, to name a few --- require computing distances and paths between vertices in the graph. Systems for these applications need to meet three performance goals: (1) low memory footprint; (2) low latency; and (3) small stretch --- the ratio of the cost of path returned by the system to the actual shortest path. The theory community has established that meeting these goals is impossible for extremely dense graphs. The central theme of this dissertation is to show that these goals can, in fact, be achieved by exploiting {\em graph sparsity}, a property almost always encountered in big graph data. This dissertation formally establishes a separation between the sparse and the dense cases for the problem of computing distances on graphs. For the realistic case of sparse graphs, our algorithms exhibit a smooth three-way trade-off between space, stretch and query time --- a phenomenon that does not occur in dense graphs. Specific operating points on this trade-off space give us linear-space data structures for computing paths of stretch 2, 3 and larger, and the first data structure for computing paths of stretch less than 2 on general weighted undirected graphs. We then apply our techniques and algorithms to build systems that enable efficient path computations for various big graph data applications. We first present ASAP, a system that almost always computes the exact shortest distance in tens of microseconds on graphs with millions of vertices and edges. We then present ShapeShifter, a system that enables efficient computation of short paths on dynamic graphs; ShapeShifter can update, upon an edge insertion and/or deletion, the underlying data structure within tens of microseconds and answers each user query in less than a millisecond.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Agarwal, Rachit

Contributors dc:contributor

• Vaidya, Nitin H.
• Godfrey, Philip B.
• Caesar, Matthew C.
• Hajek, Bruce
• Rexford, Jennifer

• Big Data
• Graphs
• Social networks
• Distance Oracles
• Sparse Graphs
• Internet
• Social search and recommendation

Statement dc:rights

• Copyright 2013 Rachit Agarwal

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/46810

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/46810