de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Pay-as-you-go Maintenance of Precomputed Nearest Neighbors in Large Graphs

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44267

Crecelius,  Tom
Databases and Information Systems, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45380

Schenkel,  Ralf
Databases and Information Systems, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Crecelius, T., & Schenkel, R. (2012). Pay-as-you-go Maintenance of Precomputed Nearest Neighbors in Large Graphs. In X.-W. Chen, G. Lebanon, H. Wang, & M. J. Zaki (Eds.), CIKM'12 (pp. 952-961). New York, NY: ACM.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-58C0-B
Abstract
An important building block of many graph applications such as searching in social networks, keyword search in graphs, and retrieval of linked documents is retrieving the transitive neighbors of a node in ascending order of their distances. Since large graphs cannot be kept in memory and graph traversals at query time would be prohibitively expensive, the list of neighbors for each node is usually precomputed and stored in a compact form. While the problem of precomputing all-pairs shortest distances has been well studied for decades, efficiently maintaining this information when the graph changes is not as well understood. This paper presents an algorithm for maintaining nearest neighbor lists in weighted graphs under node insertions and decreasing edge weights. It considers the important case where queries are a lot more frequent than updates, and presents two approaches for transparently performing necessary index updates while executing queries. Extensive experiments with large graphs, including a subset of Twitter’s user graph, demonstrate that the overhead for this maintenance is small.