Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2017) | last year (2016) | two years ago (2015) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Crecelius, Tom
Schenkel, Ralf

dblp
dblp



Editor(s):

Chen, Xue-Wen
Lebanon, Guy
Wang, Haixun
Zaki, Mohammed J.

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Chen, Xue-Wen
Lebanon, Guy
Wang, Haixun
Zaki, Mohammed J.

BibTeX cite key*:

CreceliusS2012

Title, Booktitle

Title*:

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


fp118-crecelius.pdf (850.46 KB)

Booktitle*:

CIKM'12 : The Proceedings of the 21st ACM International Conference on
Information and Knowledge Management

Event, URLs

URL of the conference:

http://www.cikm2012.org/

URL for downloading the paper:

http://doi.acm.org/10.1145/2396761.2396881

Event Address*:

Maui, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

29 October 2012

Event End Date:

2 November 2012

Publisher

Name*:

ACM

URL:


Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

952-961

Year*:

2012

VG Wort Pages:


ISBN/ISSN:

978-1-4503-1156-4

Sequence Number:


DOI:

10.1145/2396761.2396881



Note, Abstract, ©


(LaTeX) 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.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{CreceliusS2012,
AUTHOR = {Crecelius, Tom and Schenkel, Ralf},
EDITOR = {Chen, Xue-Wen and Lebanon, Guy and Wang, Haixun and Zaki, Mohammed J.},
TITLE = {Pay-as-you-go Maintenance of Precomputed Nearest Neighbors in Large Graphs},
BOOKTITLE = {CIKM'12 : The Proceedings of the 21st ACM International Conference on
Information and Knowledge Management},
PUBLISHER = {ACM},
YEAR = {2012},
PAGES = {952--961},
ADDRESS = {Maui, USA},
ISBN = {978-1-4503-1156-4},
DOI = {10.1145/2396761.2396881},
}


Entry last modified by Klaus Berberich, 02/22/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
07/17/2012 07:01:22 AM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Klaus Berberich
Anja Becker
Ralf Schenkel
Ralf Schenkel
Ralf Schenkel
Edit Dates
02/22/2013 08:25:51 AM
20.02.2013 14:52:52
08.01.2013 11:50:15
08.08.2012 15:20:09
17.07.2012 13:58:48
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
fp118-crecelius.pdf