Scalable Nearest Neighbors with Guarantees in Large and Composite Networks
The authors address the problem of k Nearest Neighbor (kNN) search in networks, according to a random walk proximity measure called Effective Importance. Their approach retrieves the exact top neighbors at query time without relying on off-line indexing or summaries of the entire network. This makes it suitable for very large dynamic networks, as well as for composite network overlays mixed at query time. They provide scalability and flexibility without compromising the quality of results due to theoretical bound guarantees that they develop and incorporate in their search procedure. They incrementally construct a subgraph of the underlying network, sufficient to obtain the exact top k neighbors.