2010 FastNearestNeighborSearchinDisk

• (Sarkar et al., 2010) ⇒ Purnamrita Sarkar, and Andrew W. Moore. (2010). “Fast Nearest-neighbor Search in Disk-resident Graphs.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835871

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Fast+nearest-neighbor+search+in+disk-resident+graphs%22+2010
• http://portal.acm.org/citation.cfm?id=1835871&preflayout=flat#citedby

Quotes

Abstract

Link prediction, personalized graph search, fraud detection, and many such graph mining problems revolve around the computation of the most "similar" [math]\displaystyle{ k }[/math] nodes to a given query node. One widely used class of similarity measures is based on random walks on graphs, e.g., personalized pagerank, hitting and commute times, and simrank. There are two fundamental problems associated with these measures. First, existing online algorithms typically examine the local neighborhood of the query node which can become significantly slower whenever high-degree nodes are encountered (a common phenomenon in real-world graphs). We prove that turning high degree nodes into sinks results in only a small approximation error, while greatly improving running times. The second problem is that of computing similarities at query time when graph is too large to be memory-resident. The obvious solution is to split the graph into clusters of nodes and store each cluster on a disk page; ideally random walks will rarely cross cluster boundaries and cause page-faults. Our contributions here are twofold: (a) we present an efficient deterministic algorithm to find the [math]\displaystyle{ k }[/math] closest neighbors (in terms of personalized pagerank) of any query node in such a clustered graph, and (b) we develop a clustering algorithm (RWDISK) that uses only sequential sweeps over data files. Empirical results on several large publicly available graphs like DBLP, Citeseer and Live-Journal (~90 M edges) demonstrate that turning high degree nodes into sinks not only improves running time of RWDISK by a factor of 3 but also boosts link prediction accuracy by a factor of 4 on average. We also show that RWDISK returns more desirable (high conductance and small size) clusters than the popular clustering algorithm METIS, while requiring much less memory. Finally our deterministic algorithm for computing nearest neighbors incurs far fewer page-faults (factor of 5) than actually simulating random walks.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 FastNearestNeighborSearchinDisk	Purnamrita Sarkar Andrew W. Moore			Fast Nearest-neighbor Search in Disk-resident Graphs		KDD-2010 Proceedings		10.1145/1835804.1835871		2010