메뉴 건너뛰기

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.

번호 제목 글쓴이 날짜 조회 수
46 데이터베이스및실습 101분반 11월 19일(월) 수업 9시 시작합니다. 관리자 2018.11.18 959
45 데이터베이스 중간고사 시간 및 장소 관리자 2018.10.10 1011
44 UML 참고자료 file 관리자 2018.10.08 351
43 '데이터베이스및실습101분반' 10월 8일(월) 수업 오전 9시부터 시작합니다 관리자 2018.10.05 686
42 102분반 게시판입니다. 누리관(A13) 2226 관리자 2018.09.04 333
41 101분반 게시판입니다. 웅비관(A12) 1320 관리자 2018.09.04 315
40 인터넷DB응용 중간고사 안내 관리자 2018.04.17 2484
39 2017-2학기 캡스톤디자인 결과물 제출 file 관리자 2017.12.15 351
38 데이터베이스및실습 기말고사 안내 관리자 2017.12.07 1254
37 JDBCExample.java file 관리자 2017.11.06 328
36 데이터베이스및실습 중간고사 안내 관리자 2017.09.29 961
35 데이터베이스및실습 9월 12일(화) 수업 오후 4:00부터 시작합니다 관리자 2017.09.12 584
34 UML 소개 file 관리자 2017.09.11 376
33 인터넷 DB 5월 18일(목) 수업 오후 2:30부터 시작합니다 관리자 2017.05.18 610
32 UpBit: Scalable In-Memory Updatable Bitmap Indexing [1] file 관리자 2017.04.25 524
» The shortest path is not always a straight line [1] file 관리자 2017.04.25 392
30 Specification을 볼때 알아야할 의미 관리자 2009.01.21 905
29 바이너리트리 file 관리자 2006.06.05 1092
28 BinaryTree file 관리자 2006.06.01 1010
27 LSTAFF (Flash Memeory) file 관리자 2006.05.29 887