Files in this item



application/pdfRachit_Agarwal.pdf (1MB)
(no description provided)PDF


Title:Low latency queries on big graph data
Author(s):Agarwal, Rachit
Director of Research:Godfrey, Philip B.
Doctoral Committee Chair(s):Godfrey, Philip B.
Doctoral Committee Member(s):Caesar, Matthew C.; Hajek, Bruce; Rexford, Jennifer; Vaidya, Nitin H.
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Big Data
Social networks
Distance Oracles
Sparse Graphs
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.
Issue Date:2014-01-16
Rights Information:Copyright 2013 Rachit Agarwal
Date Available in IDEALS:2014-01-16
Date Deposited:2013-12

This item appears in the following Collection(s)

Item Statistics