{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46810"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46810","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Low latency queries on big graph data","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Agarwal, Rachit"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Vaidya, Nitin H.","Godfrey, Philip B.","Caesar, Matthew C.","Hajek, Bruce","Rexford, Jennifer"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T18:16:48Z","date_published":"2014-01-16T18:16:48Z","updated_at":"2026-07-22T22:25:36Z","subjects":["Big Data","Graphs","Social networks","Distance Oracles","Sparse Graphs","Internet","Social search and recommendation"],"languages":["en"],"rights":["Copyright 2013 Rachit Agarwal"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46810","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vaidya, Nitin H.","Godfrey, Philip B.","Caesar, Matthew C.","Hajek, Bruce","Rexford, Jennifer"]},{"key":"dc:creator","label":"Author","values":["Agarwal, Rachit"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T18:16:48Z","2016-01-16T11:01:25Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Big Data","Graphs","Social networks","Distance Oracles","Sparse Graphs","Internet","Social search and recommendation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Rachit Agarwal"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46810"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-12-04T16:40:22Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Agarwal_Rachit.pdf: 1033420 bytes, checksum: e22f85f0a756d332b107cde7e69e0ba3 (MD5)","Made available in DSpace on 2014-01-16T18:16:48Z (GMT). No. of bitstreams: 2 Rachit_Agarwal.pdf: 1033420 bytes, checksum: e22f85f0a756d332b107cde7e69e0ba3 (MD5) license.txt: 4064 bytes, checksum: 2a94c2401d2b80861282a740c8b589f0 (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (robbins.sd@gmail.com) on 2014-01-16T18:19:39Z Item is restricted until 2016-01-16T18:19:34Z","Restriction data tranferred 2014-07-01T11:35:33-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2016-01-16 12:19:34 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 46829 on 2016-01-16T11:01:25Z."]},{"key":"dc:title","label":"Title","values":["Low latency queries on big graph data"]}]}],"canonical_facts":{"dc:contributor":["Vaidya, Nitin H.","Godfrey, Philip B.","Caesar, Matthew C.","Hajek, Bruce","Rexford, Jennifer"],"dc:creator":["Agarwal, Rachit"],"dc:date":["2014-01-16T18:16:48Z","2016-01-16T11:01:25Z","2013-12"],"dc:description":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-12-04T16:40:22Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Agarwal_Rachit.pdf: 1033420 bytes, checksum: e22f85f0a756d332b107cde7e69e0ba3 (MD5)","Made available in DSpace on 2014-01-16T18:16:48Z (GMT). No. of bitstreams: 2 Rachit_Agarwal.pdf: 1033420 bytes, checksum: e22f85f0a756d332b107cde7e69e0ba3 (MD5) license.txt: 4064 bytes, checksum: 2a94c2401d2b80861282a740c8b589f0 (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (robbins.sd@gmail.com) on 2014-01-16T18:19:39Z Item is restricted until 2016-01-16T18:19:34Z","Restriction data tranferred 2014-07-01T11:35:33-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2016-01-16 12:19:34 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 46829 on 2016-01-16T11:01:25Z."],"dc:identifier":["http://hdl.handle.net/2142/46810"],"dc:language":["en"],"dc:rights":["Copyright 2013 Rachit Agarwal"],"dc:subject":["Big Data","Graphs","Social networks","Distance Oracles","Sparse Graphs","Internet","Social search and recommendation"],"dc:title":["Low latency queries on big graph data"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}