Fast navigation through graphs with O(1) cost relies on compact storage of graphs in dense arrays, but is not efficiently updatable. In this paper we propose storage of updatable graphs in Packed Memory Arrays (PMAs), and tackle the problem of supporting concurrent updates and reads. So far, there has been no work on concurrently updating PMAs. We propose two novel techniques to perform concurrent scans and updates in the data structure and evaluate our implementation against other existing alternatives, showing that PMAs can in some cases be on par with data structures optimised for writes, while providing at least one order of magnitude higher throughput for reads.
Additional Metadata
Persistent URL dx.doi.org/10.1145/3327964.3328497
Conference GRADES-NDA, co-located at ACM SIGMOD/PODS
Citation
De Leo, D, & Boncz, P.A. (2019). Fast concurrent reads and updates with PMAs. In Proceedings of the Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) 2019. doi:10.1145/3327964.3328497