English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Pay-as-you-go Maintenance of Precomputed Nearest Neighbors in Large Graphs

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.

Item is

Files

show Files
hide Files
:
fp118-crecelius.pdf (Any fulltext), 851KB
 
File Permalink:
-
Name:
fp118-crecelius.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Crecelius, Tom1, 2, Author           
Schenkel, Ralf1, Author           
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2012
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 647468
DOI: 10.1145/2396761.2396881
URI: http://doi.acm.org/10.1145/2396761.2396881
Other: Local-ID: C1256DBF005F876D-8D1B2527866B2B3CC1257A3E001B974A-CreceliusS2012
BibTex Citekey: CreceliusS2012
 Degree: -

Event

show
hide
Title: 21st ACM International Conference on Information and Knowledge Management
Place of Event: Maui, USA
Start-/End Date: 2012-10-29 - 2012-11-02

Legal Case

show

Project information

show

Source 1

show
hide
Title: CIKM'12
  Subtitle : The Proceedings of the 21st ACM International Conference on Information and Knowledge Management
  Abbreviation : CIKM 2012
Source Genre: Proceedings
 Creator(s):
Chen, Xue-Wen1, Editor
Lebanon, Guy1, Editor
Wang, Haixun1, Editor
Zaki, Mohammed J.1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 952 - 961 Identifier: ISBN: 978-1-4503-1156-4