{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/118077"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/118077","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Sketching distances in graphs","abstract":"Often in computer science, graphs are used to represent metrics: the nodes represent \"locations,\" and the edges represent connectivity between locations. The salient properties of such a graph are the shortest path distances between its nodes - that is, the minimum length of a path from each point A to each point B, capturing the time or resource cost of travelling from one place to another in the space represented by the graph. There are plenty of nice algorithms and structure theorems that are used to understand or analyze shortest path distances. However, in the modern computing, we sometimes have to handle spaces that are too enormous to be efficiently handled by these classic methods. When this happens, it is often useful to \"sketch\" these enormous spaces, designing a graph or data structure that approximately encodes the distances of the original network, but in much smaller space. This dissertation is about the design of these graph sketches that encode distances. Some of the content will cover upper bounds: we will demonstrate some new ways to make sketches, and we will prove things about the tradeoff between the size of these sketches and their approximation error. Some of the content will cover lower bounds: we will design some very particular graphs, and we will prove that a certain size vs error tradeoff can't be achieved any sketch on these graphs. We will do this for a few different reasonable notions of \"approximation\" of distances. We will also consider some of these settings in the fault-tolerant model, where we imagine that nodes or edges of the graph can spontaneously \"fail,\" and we want our sketches to be strongly robust to these failures.","abstract_html":"Often in computer science, graphs are used to represent metrics: the nodes represent "locations," and the edges represent connectivity between locations. The salient properties of such a graph are the shortest path distances between its nodes - that is, the minimum length of a path from each point A to each point B, capturing the time or resource cost of travelling from one place to another in the space represented by the graph. There are plenty of nice algorithms and structure theorems that are used to understand or analyze shortest path distances. However, in the modern computing, we sometimes have to handle spaces that are too enormous to be efficiently handled by these classic methods. When this happens, it is often useful to "sketch" these enormous spaces, designing a graph or data structure that approximately encodes the distances of the original network, but in much smaller space. This dissertation is about the design of these graph sketches that encode distances. Some of the content will cover upper bounds: we will demonstrate some new ways to make sketches, and we will prove things about the tradeoff between the size of these sketches and their approximation error. Some of the content will cover lower bounds: we will design some very particular graphs, and we will prove that a certain size vs error tradeoff can't be achieved any sketch on these graphs. We will do this for a few different reasonable notions of "approximation" of distances. We will also consider some of these settings in the fault-tolerant model, where we imagine that nodes or edges of the graph can spontaneously "fail," and we want our sketches to be strongly robust to these failures.","abstract_has_math":false,"creators":["Bodwin, Greg (Gregory MIchael)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Virginia Vassilevska Williams."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-07-22T22:22:17Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/118077","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Virginia Vassilevska Williams."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Bodwin, Greg (Gregory MIchael)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-09-17T15:56:29Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-09-17T15:56:29Z"]},{"key":"dc:date.issued","label":"Date","values":["2018"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/118077"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D. in Computer Science, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 131-144)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Often in computer science, graphs are used to represent metrics: the nodes represent \"locations,\" and the edges represent connectivity between locations. The salient properties of such a graph are the shortest path distances between its nodes - that is, the minimum length of a path from each point A to each point B, capturing the time or resource cost of travelling from one place to another in the space represented by the graph. There are plenty of nice algorithms and structure theorems that are used to understand or analyze shortest path distances. However, in the modern computing, we sometimes have to handle spaces that are too enormous to be efficiently handled by these classic methods. When this happens, it is often useful to \"sketch\" these enormous spaces, designing a graph or data structure that approximately encodes the distances of the original network, but in much smaller space. This dissertation is about the design of these graph sketches that encode distances. Some of the content will cover upper bounds: we will demonstrate some new ways to make sketches, and we will prove things about the tradeoff between the size of these sketches and their approximation error. Some of the content will cover lower bounds: we will design some very particular graphs, and we will prove that a certain size vs error tradeoff can't be achieved any sketch on these graphs. We will do this for a few different reasonable notions of \"approximation\" of distances. We will also consider some of these settings in the fault-tolerant model, where we imagine that nodes or edges of the graph can spontaneously \"fail,\" and we want our sketches to be strongly robust to these failures."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D. in Computer Science"]},{"key":"dc:title","label":"Title","values":["Sketching distances in graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Virginia Vassilevska Williams."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Bodwin, Greg (Gregory MIchael)"],"dc:date.accessioned":["2018-09-17T15:56:29Z"],"dc:date.available":["2018-09-17T15:56:29Z"],"dc:date.issued":["2018"],"dc:description":["Thesis: Ph. D. in Computer Science, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 131-144)."],"dc:description.abstract":["Often in computer science, graphs are used to represent metrics: the nodes represent \"locations,\" and the edges represent connectivity between locations. The salient properties of such a graph are the shortest path distances between its nodes - that is, the minimum length of a path from each point A to each point B, capturing the time or resource cost of travelling from one place to another in the space represented by the graph. There are plenty of nice algorithms and structure theorems that are used to understand or analyze shortest path distances. However, in the modern computing, we sometimes have to handle spaces that are too enormous to be efficiently handled by these classic methods. When this happens, it is often useful to \"sketch\" these enormous spaces, designing a graph or data structure that approximately encodes the distances of the original network, but in much smaller space. This dissertation is about the design of these graph sketches that encode distances. Some of the content will cover upper bounds: we will demonstrate some new ways to make sketches, and we will prove things about the tradeoff between the size of these sketches and their approximation error. Some of the content will cover lower bounds: we will design some very particular graphs, and we will prove that a certain size vs error tradeoff can't be achieved any sketch on these graphs. We will do this for a few different reasonable notions of \"approximation\" of distances. We will also consider some of these settings in the fault-tolerant model, where we imagine that nodes or edges of the graph can spontaneously \"fail,\" and we want our sketches to be strongly robust to these failures."],"dc:description.degree":["Ph. D. in Computer Science"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/118077"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Sketching distances in graphs"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:17Z"}