Investigations on path indexing for graph databases

Jonathan M. Sumrall, George H.L. Fletcher, Alexandra Poulovassilis, Johan Svensson, Magnus Vejlstrup, Chris Vest, Jim Webber

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


Graph databases have become an increasingly popular choice for the management of the massive network data sets arising in many contemporary applications. We investigate the effectiveness of path indexing for accelerating query processing in graph database systems, using as an exemplar the widely used open-source Neo4j graph database. We present a novel path index design which supports efficient ordered access to paths in a graph dataset. Our index is fully persistent and designed for external memory storage and retrieval. We also describe a compression scheme that exploits the limited differences between consecutive keys in the index, as well as a workload-driven approach to indexing. We demonstrate empirically the speed-ups achieved by our implementation, showing that the path index yields query run-times from 2x up to 8000x faster than Neo4j. Empirical evaluation also shows that our scheme leads to smaller indexes than using general-purpose LZ4 compression. The complete stand-alone implementation of our index, as well as supporting tooling such as a bulk-loader, are provided as open source for further research and development.

Originele taal-2Engels
TitelEuro-Par 2016
SubtitelParallel Processing Workshops - Euro-Par 2016 International Workshops, Revised Selected Papers
RedacteurenPierre-Francois Dutot, Frederic Desprez
Plaats van productieCham
Aantal pagina's13
ISBN van elektronische versie978-3-319-58943-5
ISBN van geprinte versie978-3-319-58942-8
StatusGepubliceerd - 1 jan 2017
Evenement22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016 - Grenoble, Frankrijk
Duur: 24 aug 201626 aug 2016

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10104 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016

Vingerafdruk Duik in de onderzoeksthema's van 'Investigations on path indexing for graph databases'. Samen vormen ze een unieke vingerafdruk.

Citeer dit