- Titel
- GRATIN
- Untertitel
- Accelerating Graph Traversals in Main-Memory Column Stores
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-805028
- Konferenz
- SIGMOD/PODS'14: International Conference on Management of Data. Snowbird Utah, 22. - 27. Juni 2014
- Quellenangabe
- GRADES'14: Proceedings of Workshop on GRAph Data management Experiences and Systems
Herausgeber: Peter Boncz
Herausgeber: Josep Lluis Larriba Pey
Erscheinungsort: New York
Verlag: ACM
Erscheinungsjahr: 2014
Seiten: 1-6
ISBN: 978-1-4503-2982-8 - Erstveröffentlichung
- 2014
- Abstract (EN)
- 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.
- Andere Ausgabe
- Link zum Artikel, der zuerst in der ACM Digital Library erschienen ist.
DOI: 10.1145/2621934.2621941 - Freie Schlagwörter (DE)
- Datenbankmanagementsystem, Graphenabfrage- und Verarbeitungsfunktionen, Gratin, Graphenüberquerungen
- Freie Schlagwörter (EN)
- database management system, graph query and processing capabilities, Gratin, graph traversals
- Klassifikation (DDC)
- 004
- Verlag
- ACM, New York
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-805028
- Veröffentlichungsdatum Qucosa
- 25.08.2022
- Dokumenttyp
- Konferenzbeitrag
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
