Low latency queries on big graph data

Agarwal, Rachit

Permalink

https://hdl.handle.net/2142/46810 Copy

Description

Title

Low latency queries on big graph data

Author(s)

Agarwal, Rachit

Issue Date

2014-01-16T18:16:48Z

Director of Research (if dissertation) or Advisor (if thesis)

Godfrey, Philip B.

Doctoral Committee Chair(s)

Godfrey, Philip B.

Committee Member(s)

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

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2013-12

Permalink

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

Copyright and License Information

Copyright 2013 Rachit Agarwal

Owning Collections