Estimating pairwise distances in large graphs

Maria Christoforaki, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Point-to-point distance estimation in large scale graphs is a fundamental and well studied problem with applications in many areas such as Social Search. Previous work has focused on selecting an appropriate subset of vertices as landmarks, aiming to derive distance upper or lower bounds that are as tight as possible. In order to compute a distance bound between two vertices, the proposed methods apply triangle inequalities on top of the precomputed distances between each of these vertices and the landmarks, and then use the tightest one. In this work we take a fresh look at this setting and approach it as a learning problem. As features, we use structural attributes of the vertices involved as well as the bounds described above, and we learn a function that predicts the distance between a source and a destination vertex. We conduct an extensive experimental evaluation on a variety of real-world graphs and show that the average relative prediction error of our proposed methods significantly outperforms state-of-the-art landmark-based estimates. Our method is particularily efficient when the available space is very limited.

    Original languageEnglish (US)
    Title of host publicationProceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014
    EditorsWo Chang, Jun Huan, Nick Cercone, Saumyadipta Pyne, Vasant Honavar, Jimmy Lin, Xiaohua Tony Hu, Charu Aggarwal, Bamshad Mobasher, Jian Pei, Raghunath Nambiar
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages335-344
    Number of pages10
    ISBN (Electronic)9781479956654
    DOIs
    StatePublished - Jan 7 2015
    Event2nd IEEE International Conference on Big Data, IEEE Big Data 2014 - Washington, United States
    Duration: Oct 27 2014Oct 30 2014

    Publication series

    NameProceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

    Other

    Other2nd IEEE International Conference on Big Data, IEEE Big Data 2014
    CountryUnited States
    CityWashington
    Period10/27/1410/30/14

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Information Systems

    Cite this