University of Illinois Urbana-Champaign

Low latency queries on big graph data

Agarwal, Rachit

Content Files
Rachit_Agarwal.pdf

Permalink

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

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
Date of Ingest
2014-01-16T18:16:48Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering