We present Teseo, a new system for the storage and analysis of dynamic structural graphs in main-memory and the addition of transactional support. Teseo introduces a novel design based on sparse arrays, large arrays interleaved with gaps, and a fat tree, where the graph is ultimately stored. Our design contrasts with early systems for the analysis of dynamic graphs, which often lack transactional support and are anchored to a vertex table as a primary index. We claim that the vertex table implies several constraints, often neglected, that can actually impair the generality, the robustness and extension opportunities of these systems. We compare Teseo with other dynamic graph systems, showing a high resilience to workload and input changes, while achieving comparable, if not superior, throughputs in updates and latencies in raw scans.

In our paper [4], we experimentally evaluated our work, Teseo, together with five other systems under the LDBC Graphalytics benchmark [6]. We developed and publicly released [2] an ad-hoc driver for the purpose. Since the time the paper was published, a bug [1] in the driver has been found. Due to this bug, we discovered that the completion times for Graphalytics have been incorrectly measured by 1 second or slightly more than their actual values. This issue involves the results of Table 2, Figure 8 and Table 3 reported in our paper [4]. Still, because the bug equally affected all systems evaluated and it is only related to the measurements, most of the comparisons and the general conclusions in the paper still hold.

The physical memory layout of a tree-based index structure deteriorates over time as it sustains more updates; such that sequential scans on the physical level become non-sequential, and therefore slower. Packed Memory Arrays (PMAs) prevent this by managing all data in a sequential sparse array. PMAs have been studied mostly theoretically but suffer from practical problems, as we show in this paper. We study and fix these problems, resulting in an improved data structure: the Rewired Memory Array (RMA). We compare RMA with the main previous PMA implementations as well as state-of-the-art tree index structures and show on a wide variety of data and query distributions that RMA can reach competitive update and point lookup performance, while always providing superior scan performance - close to dense column scans.