Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of
\nresearch in the networking community has studied the distance matrix defined by node-to-node latencies
\nin the Internet, resulting in a number of recent approaches that approximately embed this distance
\nmatrix into low-dimensional Euclidean space. There is a fundamental distinction, however, between
\nthe theoretical approaches to the embedding problem and this recent Internet-related work: in addition
\nto computational limitations, Internet measurement algorithms operate under the constraint that it is
\nonly feasible to measure distances for a linear (or near-linear) number of node pairs, and typically in a
\nhighly structured way. Indeed, the most common framework for Internet measurements of this type is a
\nbeacon-based approach: one chooses uniformly at random a constant number of nodes (\u2018beacons\u2019) in the
\nnetwork, each node measures its distance to all beacons, and one then has access to only these measurements
\nfor the remainder of the algorithm. Moreover, beacon-based algorithms are often designed not for
\nembedding but for the more basic problem of triangulation, in which one uses the triangle inequality to
\ninfer the distances that have not been measured.
\nHere we give algorithms with provable performance guarantees for beacon-based triangulation and
\nembedding. We show that in addition to multiplicative error in the distances, performance guarantees
\nfor beacon-based algorithms typically must include a notion of slack \u2014 a certain fraction of all distances
\nmay be arbitrarily distorted. For metric spaces of bounded doubling dimension (which have been
\nproposed as a reasonable abstraction of Internet latencies), we show that triangulation-based distance
\nreconstruction with a constant number of beacons can achieve multiplicative error 1 + \u00b1 on a 1 \u00a1 \u00b2 fraction
\nof distances, for arbitrarily small constants \u00b1 and \u00b2. For this same class of metric spaces, we give
\na beacon-based embedding algorithm that achieves constant distortion on a 1 \u00a1 \u00b2 fraction of distances;
\nthis provides some theoretical justification for the success of the recent Global Network Positioning algorithm
\nof Ng and Zhang, and it forms an interesting contrast with lower bounds showing that it is not
\npossible to embed all distances in a doubling metric space with constant distortion. We also give results
\nfor other classes of metric spaces, as well as distributed algorithms that require only a sparse set of
\ndistances but do not place too much measurement load on any one node.<\/p>\n","protected":false},"excerpt":{"rendered":"
Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of recent approaches that approximately embed this distance matrix into low-dimensional Euclidean space. There is a fundamental distinction, however, […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"Institute of Electrical and Electronics Engineers, Inc.","msr_publisher_other":"","msr_booktitle":"45th IEEE Symp. on Foundations of Computer Science (FOCS)","msr_chapter":"","msr_edition":"45th IEEE Symp. on Foundations of Computer Science (FOCS)","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"444-453","msr_page_range_start":"444","msr_page_range_end":"453","msr_series":"","msr_volume":"","msr_copyright":"\u00a9 2007 IEEE. Personal use of this material is permitted. However, permission to reprint\/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.","msr_conference_name":"45th IEEE Symp. on Foundations of Computer Science (FOCS)","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"Jon Kleinberg, Aleksandrs Slivkins, Tom Wexler","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2004-10-01","msr_highlight_text":"","msr_notes":"This is the journal version, to appear in JACM in 2009. This version includes portions of [Slivkins SODA'05]","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2004,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-154097","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_publishername":"Institute of Electrical and Electronics Engineers, Inc.","msr_edition":"45th IEEE Symp. on Foundations of Computer Science (FOCS)","msr_affiliation":"","msr_published_date":"2004-10-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"45th IEEE Symp. on Foundations of Computer Science (FOCS)","msr_pages_string":"444-453","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"This is the journal version, to appear in JACM in 2009. This version includes portions of [Slivkins SODA'05]","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"209801","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"focs04_jv.pdf","viewUrl":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-content\/uploads\/2016\/02\/focs04_jv.pdf","id":209801,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":209801,"url":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-content\/uploads\/2016\/02\/focs04_jv.pdf"}],"msr-author-ordering":[{"type":"text","value":"Jon Kleinberg","user_id":0,"rest_url":false},{"type":"text","value":"Aleksandrs Slivkins","user_id":0,"rest_url":false},{"type":"text","value":"Tom Wexler","user_id":0,"rest_url":false},{"type":"user_nicename","value":"slivkins","user_id":33685,"rest_url":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=slivkins"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/154097","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/154097\/revisions"}],"predecessor-version":[{"id":526868,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/154097\/revisions\/526868"}],"wp:attachment":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/media?parent=154097"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=154097"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=154097"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=154097"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=154097"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=154097"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=154097"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=154097"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=154097"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=154097"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=154097"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=154097"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=154097"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}