Fast concurrent reads and updates with PMAs
Presented at the GRADES-NDA, co-located at ACM SIGMOD/PODS (June 2019), Amsterdam, the Netherlands
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.
|Conference||GRADES-NDA, co-located at ACM SIGMOD/PODS|
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