Title: Nearest-neighbor Queries in Probabilistic Graphs
Authors: Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios
Date: July 14, 2009
Abstract:
Large probabilistic graphs arise in various domains spanning from
social networks to biological and communication networks. An important
query in these graphs is the k nearest-neighbor query, which involves
finding and reporting the k closest nodes to a specific node. This
query assumes the existence of a measure of the -Y´proximity¡ or the
´distance¡ between any two nodes in the graph. To that end, we propose
various novel distance functions that extend well known notions of
classical graph theory, such as shortest paths and random walks. We
argue that many meaningful distance functions are computationally
intractable to compute exactly. Thus, in order to process
nearest-neighbor queries, we resort to Monte Carlo sampling and
exploit novel graph-transformation ideas and pruning opportunities. In
our extensive experimental analysis, we explore the trade-offs of our
approximation algorithms and demonstrate that they scale well on
real-world probabilistic graphs with tens of millions of edges.