Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports of the Computer Science Department
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports of the Computer Science Department
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Playing Vivaldi in Hyperbolic Space

    Thumbnail
    View/Open
    cs-tr-4843.pdf (557.6Kb)
    No. of downloads: 1186

    Date
    2006-11-17
    Author
    Lumezanu, Cristian
    Spring, Neil
    Metadata
    Show full item record
    Abstract
    Internet coordinate systems have emerged as an efficient method to estimate the latency between pairs of nodes without any communication between them. They avoid the cost of explicit measurements by placing each node in a finite coordinate space and estimating the latency between two nodes as the distance between their positions in the space. In this paper, we adapt the Vivaldi algorithm to use the Hyperbolic space for embedding. Researchers have found promise in Hyperbolic space due to its mathematical elegance and its ability to model the structure of the Internet. We attempt to combine the elegance of the Hyperbolic space with the practical, decentralized Vivaldi algorithm. We evaluate both Euclidean and Hyperbolic Vivaldi on three sets of real-world latencies. Contrary to what we expected, we find that the performance of the two versions of Vivaldi varies with each data set. Furthermore, we show that the Hyperbolic coordinates have the tendency to underestimate large latencies (> 100 ms) but behave better when estimating short distances. Finally, we propose two distributed heuristics that help nodes decide whether to choose Euclidean or Hyperbolic coordinates when estimating distances to their peers. This is the first comparison of Euclidean and Hyperbolic embeddings using the same distributed solver and using a data set with more than 200 nodes.
    URI
    http://hdl.handle.net/1903/4007
    Collections
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility