SCIENCE@home

Scalable Evaluation of k-NN Queries on Large Uncertain Graphs

Xiaodong Li,Reynold Cheng,Yixiang Fang,Jiafeng Hu,Silviu Maniu

Published 2018 in International Conference on Extending Database Technology

ABSTRACT

Large graphs are prevalent in social networks, traffic networks, and biology. These graphs are often inexact. For example, in a friendship network, an edge between two nodesu andv indicates that users u and v have a close relationship. This edge may only exist with a probability. To model such information, the uncertain graph model has been proposed, in which each edge e is augmented with a probability that indicate the chance that e exists. Given a node q in an uncertain graph G, we study the k-NN query of q, which looks for k nodes in G whose distances from q are the shortest. The k-NN query can be used in friend-search, data mining, and pattern-recognition. Despite the importance of this query, it has not been well studied. In this paper, we develop a tree-based structure called the U-tree. Given a k-NN query, the U-tree produces a compact representation of G, based on which the query can be executed efficiently. Our results on real and synthetic datasets show that our algorithm can scale to large graphs, and is 75% faster than the state-of-the-art solutions.

PUBLICATION RECORD

  • Publication year

    2018

  • Venue

    International Conference on Extending Database Technology

  • Publication date

    Unknown publication date

  • Fields of study

    Computer Science

  • Identifiers
    DOI 10.5441/002/edbt.2018.17
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-40 of 40 references · Page 1 of 1

CITED BY

Showing 1-12 of 12 citing papers · Page 1 of 1