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.
doi.org/10.1145/3327964.3328497
GRADES-NDA, co-located at ACM SIGMOD/PODS
Database Architectures

De Leo, D., & Boncz, P. (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 (pp. 1–8). doi:10.1145/3327964.3328497