tutorial

GRATIN: Accelerating Graph Traversals in Main-Memory Column Stores

Authors:

Marcus Paradies,

Michael Rudolf,

Christof Bornhövd,

Wolfgang LehnerAuthors Info & Claims

GRADES'14: Proceedings of Workshop on GRAph Data management Experiences and Systems

Pages 1 - 6

https://doi.org/10.1145/2621934.2621941

Published: 22 June 2014 Publication History

Abstract

Native graph query and processing capabilities have become indispensable for modern business applications in enterprise-critical operations on data that is stored in relational database management systems. Traversal operations are a basic ingredient of graph algorithms and graph queries. As a consequence, they are fundamental for querying graph data in a relational database management system.

In this paper we present gratin, a concise secondary index structure to speedup graph traversals in main-memory column stores. Conventional approaches for graph traversals rely on repeated full column scans, making it an inefficient approach for deep traversals on very large graphs. To tackle this challenge, we devise a novel and adaptive block-based index to handle graphs efficiently. Most importantly, gratin is updateable in constant time and allows supporting evolving graphs with frequent updates to the graph topology.

We conducted an extensive evaluation on real-world data sets from different domains for a large variety of traversal queries. Our experiments show improvements of up to an order of magnitude compared to a scan-based traversal algorithm.

References

[1]

P. Bohannon, P. Mcllroy, and R. Rastogi. Main-memory index structures with fixed-size partial keys. In SIGMOD Record, volume 30, pages 163--174, 2001.

Digital Library

[2]

A. Buluç and K. Madduri. Parallel breadth-first search on distributed memory systems. In Proc. SC'11, pages 65--77, 2011.

Digital Library

[3]

J. Chhugani, N. Satish, C. Kim, J. Sewall, and P. Dubey. Fast and Efficient Graph Traversal Algorithm for CPUs: Maximizing Single-Node Efficiency. In Proc. IPDPS'12, pages 378--389, 2012.

Digital Library

[4]

N. Christofides. The optimum traversal of a graph. Omega, 1(6):719--732, 1973.

[5]

M. Ciglan, A. Averbuch, and L. Hluchy. Benchmarking traversal operations over graph databases. In Proc. ICDE Data Engineering Workshops, pages 186--189, 2012.

Digital Library

[6]

D. G. Corneil and R. Krueger. Simple vertex ordering characterizations for graph search. Electronic Notes in Discrete Mathematics, 22:445--449, 2005.

[7]

A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders. A parallelization of Dijkstra's shortest path algorithm. In Mathematical Foundations of Computer Science 1998, volume 1450 of LNCS, pages 722--731. 1998.

Digital Library

[8]

D. Dominguez-Sal, N. Martínez-Bazan, V. Muntés-Mulero, P. Baleta, and J. L. Larriba-Pey. A Discussion on the Design of Graph Database Benchmarks. In Proc. TPCTC'10, pages 25--40, 2011.

Digital Library

[9]

M. Faust, D. Schwalb, and J. Krueger. Fast column scans: Paged indices for in-memory column stores. In Proc. IMDM'13, 2013.

[10]

P.-A. Larson, C. Clinciu, C. Fraser, E. N. Hanson, M. Mokhtar, M. Nowakiewicz, V. Papadimos, S. L. Price, S. Rangarajan, R. Rusanu, and M. Saubhasik. Enhancements to SQL Server Column Stores. In Proc. SIGMOD'13, pages 1159--1168, 2013.

Digital Library

[11]

T. J. Lehman and M. J. Carey. A study of index structures for main memory database management systems. Proc. VLDB, pages 294--303, 1986.

Digital Library

[12]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. In Proc. KDD'05, pages 177--187, 2005.

Digital Library

[13]

H. Lu, Y. Y. Ng, and Z. Tian. T-tree or B-tree: Main memory database index structure revisited. In Proc. ADC'10, pages 65--73, 2000.

Digital Library

[14]

V. Prabhakaran, M. Wu, X. Weng, F. McSherry, L. Zhou, and M. Haridasan. Managing large graphs on multi-cores with graph awareness. In Proceedings of the USENIX Annual Technical Conference, volume 12, pages 41--52, 2012.

Digital Library

[15]

J. Rao and K. A. Ross. Making B+-Trees Cache Conscious in Main Memory. In Proc. SIGMOD'00, pages 475--486, 2000.

Digital Library

[16]

M. A. Rodriguez and P. Neubauer. Constructions from Dots and Lines. Bulletin of the American Society for Information Science and Technology, 36(6):35--41, 2010.

[17]

T. G. Rokicki. Main memory bank indexing scheme that optimizes consecutive page hits by linking main memory bank address organization to cache memory address organization. US Patent 6,070,227, 2000.

[18]

D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266--283, 1976.

[19]

S. Sakr and G. Al-Naymat. Graph indexing and querying: a review. International Journal of Web Information Systems, 6(2):101--120, 2010.

[20]

H. Shang and M. Kitsuregawa. Efficient Breadth-First Search on Large Graphs with Skewed Degree Distributions. In Proc. EDBT'13, pages 311--322, 2013.

Digital Library

[21]

V. Sikka, F. Färber, W. Lehner, S. K. Cha, T. Peh, and C. Bornhövd. Efficient Transaction Processing in SAP HANA Database: The End of a Column Store Myth. In Proc. SIGMOD'12, pages 731--742, 2012.

Digital Library

[22]

S. Trißl and U. Leser. Fast and practical indexing and querying of very large graphs. In Proc. SIGMOD'07, pages 845--856, 2007.

Digital Library

[23]

X. Wang, X. Ding, A. K. Tung, S. Ying, and H. Jin. An efficient graph indexing method. In Proc. ICDE'12, pages 210--221.

Digital Library

[24]

X. Yan, P. S. Yu, and J. Han. Graph indexing: a frequent structure-based approach. In Proc. SIGMOD'04, pages 335--346, 2004.

Digital Library

[25]

A. Yoo, E. Chow, K. Henderson, W. McLendon, B. Hendrickson, and U. Catalyurek. A scalable distributed parallel breadth-first search algorithm on BlueGene/L. In Proc. SC'05, pages 25--44, 2005.

Digital Library

[26]

S. Zhang, M. Hu, and J. Yang. Treepi: A novel graph indexing method. In Proc. ICDE'07, pages 966--975, 2007.

[27]

J. L. Zhao and H. K. Cheng. Graph indexing for spatial data traversal in road map databases. Computers & Operations Research, 28(3):223--241, 2001.

Digital Library

[28]

J. L. Zhao and A. Zaki. Spatial data traversal in road map databases: A graph indexing approach. In Proc. CIKM'94, pages 355--362, 1994.

Digital Library

[29]

P. Zhao, J. X. Yu, and P. S. Yu. Graph indexing: tree + delta <= graph. In Proc. VLDB'07, pages 938--949, 2007.

Digital Library

Cited By

Azriel LHumbel LAchermann RRichardson AHoffmann MMendelson ARoscoe TWatson RFaraboschi PMilojicic D(2019)Memory-Side Protection With a Capability Enforcement Co-ProcessorACM Transactions on Architecture and Code Optimization10.1145/330225716:1(1-26)Online publication date: 8-Mar-2019
https://dl.acm.org/doi/10.1145/3302257
Vasilyeva EThiele MMocan ALehner W(2015)Relaxation of subgraph queries delivering empty resultsProceedings of the 27th International Conference on Scientific and Statistical Database Management10.1145/2791347.2791382(1-12)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1145/2791347.2791382
Faerber FDees JWeidner MBaeuerle SLehner W(2015)Towards a web-scale data management ecosystem demonstrated by SAP HANA2015 IEEE 31st International Conference on Data Engineering10.1109/ICDE.2015.7113374(1259-1267)Online publication date: Apr-2015
https://doi.org/10.1109/ICDE.2015.7113374

Index Terms

GRATIN: Accelerating Graph Traversals in Main-Memory Column Stores

Recommendations

Sql: Learn Basics of Queries and Implement Easily (sql programming, SQL 2016, sql database programming, sql for beginners, sql beginners guide, sql ... sql workbook, sql guide, MSSQL) (Volume 1)
On the Multichromatic Number of s-Stable Kneser Graphs

For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GRADES'14: Proceedings of Workshop on GRAph Data management Experiences and Systems

June 2014

79 pages

ISBN:9781450329828

DOI:10.1145/2621934

Program Chairs:
Peter Boncz
CWI
,
Josep Lluis Larriba Pey
UPC Catalunya

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Tutorial
Research
Refereed limited

Conference

SIGMOD/PODS'14

Sponsor:

SIGMOD

SIGMOD/PODS'14: International Conference on Management of Data

June 22 - 27, 2014

UT, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 29 of 61 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
164
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Azriel LHumbel LAchermann RRichardson AHoffmann MMendelson ARoscoe TWatson RFaraboschi PMilojicic D(2019)Memory-Side Protection With a Capability Enforcement Co-ProcessorACM Transactions on Architecture and Code Optimization10.1145/330225716:1(1-26)Online publication date: 8-Mar-2019
https://dl.acm.org/doi/10.1145/3302257
Vasilyeva EThiele MMocan ALehner W(2015)Relaxation of subgraph queries delivering empty resultsProceedings of the 27th International Conference on Scientific and Statistical Database Management10.1145/2791347.2791382(1-12)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1145/2791347.2791382
Faerber FDees JWeidner MBaeuerle SLehner W(2015)Towards a web-scale data management ecosystem demonstrated by SAP HANA2015 IEEE 31st International Conference on Data Engineering10.1109/ICDE.2015.7113374(1259-1267)Online publication date: Apr-2015
https://doi.org/10.1109/ICDE.2015.7113374

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents