日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
一時保存へ追加
 タグ情報を表示リリース履歴を表示詳細要約
  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

 

表示: 全項目 非表示: 全項目

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-14EF-6 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0024-33FE-3
資料種別: 会議論文

ファイル

表示: ファイル
非表示: ファイル
:
cikm579i-gubichev.pdf (全文テキスト（全般）), 238KB
 
ファイルのパーマリンク:
-
ファイル名:
cikm579i-gubichev.pdf
説明:
-
OA-Status:
閲覧制限:
非公開
MIMEタイプ / チェックサム:
application/pdf
技術的なメタデータ:
著作権日付:
-
著作権情報:
-
CCライセンス:
-

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Gubichev, Andrey1, 著者           
Bedathur, Srikanta1, 著者           
Seufert, Stephan1, 著者           
Weikum, Gerhard1, 著者           
所属:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

内容説明

表示:
非表示:
キーワード: -
 要旨: 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.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 20102010
 出版の状態: 出版
 ページ: -
 出版情報: -
 目次: -
 査読: -
 識別子（DOI, ISBNなど）: eDoc: 536375
DOI: 10.1145/1871437.1871503
URI: http://www.mpi-inf.mpg.de/~sseufert/papers/aspsn.pdf
その他: Local-ID: C1256DBF005F876D-044882A73F4E922EC125777A00722D9F-Gubichev2010
 学位: -

関連イベント

表示:
非表示:
イベント名: 19th ACM Conference on Information and Knowledge Management
開催地: Toronto, Canada
開始日・終了日: 2010-10-26 - 2010-10-30

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Proceedings of the 19th ACM Conference on Information and Knowledge Management
  省略形 : CIKM 2010
種別: 会議論文集
 著者・編者:
Huang, Xiangji Jimmy1, 編集者
Jones, Gareth1, 編集者
Koudas, Nick1, 編集者
Wu, Xindong1, 編集者
Collins-Thompson, Kevyn1, 編集者
所属:
1 External Organizations, ou_persistent22            
出版社, 出版地: New York, NY : ACM
ページ: - 巻号: - 通巻号: - 開始・終了ページ: 499 - 508 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-1-4503-0099-5