The shortest path is not always a straight line
2017.04.25 14:26
ABSTRACT
In this paper, we leverage the concept of the metric backbone
to improve the efficiency of large-scale graph analytics. The
metric backbone is the minimum subgraph that preserves
the shortest paths of a weighted graph. We use the metric
backbone in place of the original graph to compute vari-
ous graph metrics exactly or with good approximation. By
computing on a smaller graph, we improve the performance
of graph analytics applications on two di erent systems, a
batch graph processing system and a graph database.
Further, we provide an algorithm for the computation of
the metric backbone on large graphs. While one can com-
pute the metric backbone by solving the all-pairs-shortest-
paths problem, this approach incurs prohibitive time and
space complexity for big graphs. Instead, we propose a
heuristic that makes computing the metric backbone prac-
tical even for large graphs. Additionally, we analyze several
real datasets of di erent sizes and domains and we show
that we can approximate the metric backbone by removing
only rst-order semi-metric edges; edges for which a shorter
two-hop path exists.
We provide a distributed implementation of our algorithm
and apply it in large scale scenarios. We evaluate our algo-
rithm using a variety of real graphs, including a Facebook
social network subgraph of 50 billion edges. We measure
the impact of using the metric backbone on runtime per-
formance in two graph management systems. We achieve
query speedups of up to 6.7x in the Neo4j commercial graph
database and job speedups of up to 6x in the Giraph graph
processing system.
댓글 1
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
66 | 연구실원 모집 | 관리자 | 2024.10.14 | 110 |
65 | 101분반 게시판입니다. 웅비관(A12) 1320 | 관리자 | 2018.09.04 | 315 |
64 | JDBCExample.java | 관리자 | 2017.11.06 | 328 |
63 | 102분반 게시판입니다. 누리관(A13) 2226 | 관리자 | 2018.09.04 | 333 |
62 | 2017-2학기 캡스톤디자인 결과물 제출 | 관리자 | 2017.12.15 | 351 |
61 | UML 참고자료 | 관리자 | 2018.10.08 | 351 |
60 | UML 소개 | 관리자 | 2017.09.11 | 376 |
» | The shortest path is not always a straight line [1] | 관리자 | 2017.04.25 | 392 |
58 | 연구실원 모집 | DBADMIN | 2023.08.03 | 491 |
57 | 최종보고서 양식 | 관리자 | 2020.09.07 | 491 |
56 | UpBit: Scalable In-Memory Updatable Bitmap Indexing [1] | 관리자 | 2017.04.25 | 524 |
55 | 정보 및 데이터 베이스 연구실 연구생 모집 | 관리자 | 2023.08.04 | 582 |
54 | 데이터베이스및실습 9월 12일(화) 수업 오후 4:00부터 시작합니다 | 관리자 | 2017.09.12 | 584 |
53 | 인터넷 DB 5월 18일(목) 수업 오후 2:30부터 시작합니다 | 관리자 | 2017.05.18 | 610 |
52 | '데이터베이스및실습101분반' 10월 8일(월) 수업 오전 9시부터 시작합니다 | 관리자 | 2018.10.05 | 686 |
51 | 객체지향프로그래밍 7장 강의노트 | 관리자 | 2005.12.14 | 694 |
50 | 분산객체시스템 5장 강의노트 | 관리자 | 2005.12.14 | 707 |
49 | RAID 발표자료(옥충기) | 관리자 | 2005.12.14 | 714 |
48 | 분산객체시스템 8장 강의노트 | 관리자 | 2005.12.14 | 715 |
47 | odbc | 관리자 | 2005.12.14 | 725 |