English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Fast and Accurate Estimation of Shortest Paths in Large Networks

Gubichev, A., Bedathur, S., Seufert, S., & Weikum, G. (2010). Fast and Accurate Estimation of Shortest Paths in Large Networks. In X. J. Huang, G. Jones, N. Koudas, X. Wu, & K. Collins-Thompson (Eds.), Proceedings of the 19th ACM Conference on Information and Knowledge Management (pp. 499-508). New York, NY: ACM. doi:10.1145/1871437.1871503.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-14EF-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-33FE-3
Genre: Conference Paper

Files

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

Locators

show

Creators

show
hide
 Creators:
Gubichev, Andrey1, Author           
Bedathur, Srikanta1, Author           
Seufert, Stephan1, Author           
Weikum, Gerhard1, Author           
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Content

show
hide
Free keywords: -
 Abstract: Computing shortest paths between two given nodes is a fundamental operation over graphs, but known to be nontrivial over large disk-resident instances of graph data. While a number of techniques exist for answering reachability queries and approximating node distances efficiently, determining actual shortest paths (i. e. the sequence of nodes involved) is often neglected. However, in applications arising in massive online social networks, biological networks, and knowledge graphs it is often essential to find out many, if not all, shortest paths between two given nodes. In this paper, we address this problem and present a scalable sketch-based index structure that not only supports estimation of node distances, but also computes corresponding shortest paths themselves. Generating the actual path information allows for further improvements to the estimation accuracy of distances (and paths), leading to near-exact shortest-path approximations in real world graphs. We evaluate our techniques – implemented within a fully functional RDF graph database system – over large real-world social and biological networks of sizes ranging from tens of thousand to millions of nodes and edges. Experiments on several datasets show that we can achieve query response times providing several orders of magnitude speedup over traditional path computations while keeping the estimation errors between 0% and 1% on average.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536375
DOI: 10.1145/1871437.1871503
URI: http://www.mpi-inf.mpg.de/~sseufert/papers/aspsn.pdf
Other: Local-ID: C1256DBF005F876D-044882A73F4E922EC125777A00722D9F-Gubichev2010
 Degree: -

Event

show
hide
Title: 19th ACM Conference on Information and Knowledge Management
Place of Event: Toronto, Canada
Start-/End Date: 2010-10-26 - 2010-10-30

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 19th ACM Conference on Information and Knowledge Management
  Abbreviation : CIKM 2010
Source Genre: Proceedings
 Creator(s):
Huang, Xiangji Jimmy1, Editor
Jones, Gareth1, Editor
Koudas, Nick1, Editor
Wu, Xindong1, Editor
Collins-Thompson, Kevyn1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 499 - 508 Identifier: ISBN: 978-1-4503-0099-5