# CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers

Brian Wheatman and Randal Burns  Johns Hopkins University wheatman,
<EMAIL_ADDRESS>and  Aydın Buluç and Helen Xu  Lawrence Berkeley National
Laboratory abuluc<EMAIL_ADDRESS>
###### Abstract.

This paper introduces the batch-parallel Compressed Packed
Memory Array (CPMA), a compressed dynamic ordered batch-parallel set data
structure based on the Packed Memory Array (PMA). Traditionally, batch-
parallel sets are built on pointer-based data structures such as trees because
pointer-based structures enable fast parallel unions via pointer manipulation.
When compared to cache-optimized trees, PMAs were slower to update but faster
to scan.

The batch-parallel CPMA overcomes this tradeoff between updates and scans by
optimizing for cache-friendliness. On average, the CPMA is faster than
compressed PaC-trees, a state-of-the-art batch-parallel set library based on
cache-optimized trees, by $1.2\times$ on range queries and $3\times$ on batch
updates.

We further evaluate the CPMA compared to compressed PaC-trees on a real-world
application of dynamic graph processing. The CPMA is on average $1.2\times$
faster on a suite of graph algorithms and $2\times$ faster on batch inserts
for graphs when compared with compressed PaC-trees.

††copyright: none

##  1\. Introduction

The dynamic ordered set data type (also called a key store) is one of the most
fundamental collection types and appears in many programming languages (e.g.,
C++, Python, Java, etc.) as either a built-in basic type or in standard
libraries (Blelloch et al., 2016; Sun et al., 2018; Dhulipala et al., 2022).
Ordered sets store their data in sorted order, which enables efficient scan-
based operations (i.e., operations that use ordered iteration) such as range
queries and maps. This paper focuses on dynamic ordered sets which also
support updates (inserts and deletes).

Due to their role in large-scale data processing, dynamic ordered sets have
been targeted for efficient batch-parallel implementations (Frias and Singler,
2007; Barbuzzi et al., 2010; Dhulipala et al., 2022, 2019; Sun et al., 2018;
Erb et al., 2014; Tseng et al., 2019). Since point operations (e.g., insertion
and deletion of a single element) are often not worth parallelizing due to
their logarithmic complexity, modern libraries parallelize batch updates that
insert or delete many elements at the same time. Direct support for batch
updates simplifies update parallelism and reduces the overall work of updates
by combining multiple updates into one operation on the data structure.

Since the focus of this paper is on batch-parallel sets, we will use “sets” to
refer to dynamic ordered batch-parallel sets.

Existing set implementations demonstrate the importance of optimizing for the
memory subsystem to achieve full parallel scalability. Almost all fast batch-
parallel set implementations are built on pointer-based data structures such
as trees (or tree-like structures) (Dhulipala et al., 2022, 2019; Blelloch et
al., 2016; Frias and Singler, 2007; Barbuzzi et al., 2010; Sun et al., 2018;
Erb et al., 2014) and skip lists (Tseng et al., 2019). Unfortunately, the main
bottleneck in the scalability of these sets is memory bandwidth limitations
due to pointer chasing (Blelloch et al., 2016; Frias and Singler, 2007).
Dhulipala _et al._ (Dhulipala et al., 2019, 2022) mitigated these memory
bandwidth issues in trees by improving spatial locality of trees via blocking
and compression.

Although cache-optimized trees are less memory-bandwidth bound than
unoptimized trees, pointer-based data structures inherently leave performance
on the table because non-contiguous memory accesses are slower than contiguous
memory accesses (Bender et al., 2019; Pandey et al., 2021; Wheatman and Xu,
2021). In theory, cache-friendly trees such as B-trees (Bayer and McCreight,
1972) are asymptotically optimal in the classical Disk Access Model (DAM)
(Aggarwal and Vitter, 1988) for both updates and scans. However, in practice,
array-based data structures can be empirically over $2\times$ faster to scan
than tree-based data structures due to prefetching and the cost of pointer
chasing (Pandey et al., 2021; Wheatman et al., 2023).

#### Exploiting sequential access with Packed Memory Arrays

This paper introduces a work-efficient batch-parallel Compressed Packed Memory
Array (CPMA) based on the Packed Memory Array (PMA) (Itai et al., 1981; Bender
et al., 2000, 2005), a dynamic array-based data structure optimized for cache-
friendliness. In this paper, we will use cache-friendliness to refer to how
well a data structure takes advantage of spatial locality. The PMA is an ideal
candidate for taking advantage of contiguous memory access in sets because it
collocates all of its data in memory (Itai et al., 1981; Bender et al., 2000,
2005). Due to its cache-friendliness, the PMA appears in domains such as graph
processing (Sha et al., 2017a; Wheatman and Xu, 2018; De Leo and Boncz, 2019a;
Wheatman and Xu, 2021; De Leo and Boncz, 2021; Pandey et al., 2021; Wheatman
and Burns, 2021), particle simulations (Durand et al., 2012), and computer
graphics (Toss et al., 2018).

Existing parallel PMAs suffer from low update throughput compared to batch-
parallel trees because they lack direct algorithmic support for batch updates
(Wheatman and Xu, 2021). At a high level, batch update algorithms can be
implemented with unions/differences (Blelloch et al., 2016). Previous work (De
Leo and Boncz, 2019b) introduced a serial batch-update algorithm for PMAs
based on local merges to avoid unnecessary work from unions, but stopped short
of parallelization. As we shall see, supporting theoretically and practically
efficient parallel unions in a PMA requires novel algorithmic development
because existing parallel batch update algorithms rely heavily on pointer
adjustments, which do not easily translate to contiguous memory layouts.

As an additional optimization for cache-friendliness, this paper adds
compression to PMAs. Previous work on compressed blocked trees (Dhulipala et
al., 2022, 2019) demonstrates the potential for compression to alleviate
memory bandwidth limitations by reducing the number of bytes transferred. This
paper takes the first step in applying the same techniques to PMAs.

Workload | U-PaC | C-PaC | PMA | CPMA
---|---|---|---|---
L1 misses | 3.1E9 | 2.2E9 | 8.9E8 | 7.0E8
L3 misses | 3.1E8 | 7.6E7 | 9.6E7 | 1.1E7
Table 1. Cache misses incurred while building with batches. “U-PaC” and
“C-PaC” refer to uncompressed and compressed PaC-trees (Dhulipala et al.,
2022), respectively.

#### Cache miss analysis

Array-based sets are more cache-friendly than tree-based sets because
contiguous data structures take advantage of optimizations for sequential
access such as prefetching. To verify this hypothesis, we measured111We added
100 million elements serially in batches of 1 million and measured the cache
misses with perf stat. the number of cache misses during batch inserts in PaC-
trees (Dhulipala et al., 2022) and in PMAs and report the results in Table 1.
PaC-trees222PaC-trees are implemented in a library called CPAM, but we use the
terms “PaC-trees” and “C-PaC” in this paper to avoid confusion with the term
“CPMA.” are a state-of-the-art batch-parallel set implementation based on
cache-optimized blocked trees. The PMA/CPMA incur at least $3\times$ fewer
cache misses when compared to uncompressed/compressed PaC-trees because the
PMA/CPMA take advantage of contiguous memory access.

The CPMA’s cache-friendliness translates into performance: the CPMA overcomes
the traditional tradeoff between updates and queries in trees and PMAs.
Figures 1 and 2 demonstrate that the CPMA outperforms compressed PaC-trees by
$3\times$ on average on batch updates and by at least $1.2\times$ on range
queries. The CPMA can outperform cache-optimized trees on both queries and
updates in practice because it optimizes for sequential memory access.
Finally, CPMAs use similar space to compressed PaC-trees but $2\times-3\times$
less space than uncompressed PMAs.

To demonstrate the applicability of the batch-parallel CPMA, we built F-Graph
333F-Graph uses only one compressed PMA (a flat array) to store the graph. The
F in F-Graph comes from the musical key of F, which has one flat., a dynamic-
graph-processing system built on the CPMA because PMAs have been used
extensively in graph processing (Sha et al., 2017a; Wheatman and Xu, 2018; De
Leo and Boncz, 2019a; Wheatman and Xu, 2021; De Leo and Boncz, 2021; Pandey et
al., 2021; Wheatman and Burns, 2021). F-Graph is on average $1.2\times$ faster
on a suite of graph algorithms and $2\times$ faster on batch updates compared
to C-PaC, a dynamic-graph-processing framework based on compressed PaC-trees
(Dhulipala et al., 2022). F-Graph uses marginally less space to store the
graphs than C-PaC.

hg$10^{1}$hg$10^{2}$hg$10^{3}$hg$10^{4}$hg$10^{5}$hg$10^{6}$hg$10^{7}$hg$10^{4}$hg$10^{6}$hg$10^{8}$Batch
sizeThroughput(inserts / second)hgPMAhgCPMAhgU-PaChgC-PaC Figure 1. Insert
throughput as a function of batch size.
hg$10^{1}$hg$10^{2}$hg$10^{3}$hg$10^{4}$hg$10^{5}$hg$10^{6}$hg$10^{8}$hg$10^{9}$hg$10^{10}$Expected
elements processed per searchThroughput (elements / second)hgPMAhgCPMAhgU-
PaChgC-PaC Figure 2. Range query throughput as a function of range query size.

### Contributions

Specifically, the paper’s contributions are as follows:

  * •

The design and analysis of a theoretically efficient parallel batch-update
algorithm for PMAs (and for CPMAs).

  * •

An implementation of the PMA and CPMA with the parallel batch-update algorithm
in C++.

  * •

An evaluation of the PMA/CPMA with PaC-trees that shows that the CPMA supports
faster queries and batch updates than compressed PaC-trees.

  * •

An empirical study of F-Graph, a dynamic-graph-processing system based on the
CPMA, compared to C-PaC, a dynamic-graph-processing system based on compressed
PaC-trees, that shows that F-Graph supports fast graph algorithms and updates.

#### Map

The rest of the paper is organized as follows. Section 2 reviews related work.
Section 3 describes the structure and operations of a PMA. Section 4 describes
the parallel batch-update algorithm for PMAs. Section 5 presents the structure
and operations of a CPMA. Section 6 empirically compares the PMA/CPMA and PaC-
trees. Section 7 introduces F-Graph, a dynamic-graph-processing system based
on the CPMA, and empirically evaluates F-Graph compared to C-PaC. Finally,
Section 8 provides concluding remarks.

| Work |  | Span
---|---|---|---
Operation | CPMA (this work) |  Compressed PaC-tree  (Dhulipala et al., 2022) |  | CPMA (this work) |  Compressed PaC-tree (Dhulipala et al., 2022)
Insert/delete | $O((\log^{2}(n))/B+\log(n))^{\dagger}$ | $O(\log(n)+P)$ |  | $O(\log(n))$ | $O(\log(n)+P/B)$
Batch insert/delete |  $O(k((\log^{2}(n))/B+\log(n)))$$\dagger$ | $O(k\log(n/Pk))^{\dagger}$ |  | $O(\log(k)+\log^{2}(n))$ | $O(\log(n/P)\log k+P/B)$
Search | $O(\log(n))$ | $O(\log(n)+P)$ |  | $O(\log(n))$ | $O(\log(n)+P/B)$
Range query | $O(\log(n)+r/B)$ | $O(\log(n)+(P+r)/B)$ |  | $O(\log(n))$ | $O(\log(n)+P/B)$
Table 2. Asymptotic bounds for operations in a CPMA and compressed PaC-tree.
We use $B$ to denote the cache-line size, $k$ to denote the size of the batch,
$r$ to denote the number of elements returned by the range query, and $P$ to
denote the user-specified tree node block size in the PaC-tree (called $B$ in
(Dhulipala et al., 2022)). Bounds with $\dagger$ are amortized. All bounds are
$\Omega(1)$, but we omit the $+1$ for simplicity. It is typical, but not
required, to set $P=B$ for in-memory trees.

##  2\. Related work

This section reviews related work in parallel data structures and general data
structure design and describes how this work relates to prior art.
Specifically, it discusses concurrent versus batched updates and array-based
versus tree-based data structures.

The principal contribution of this paper is a work-efficient batch-update
algorithm for PMAs. We further optimize PMAs by introducing compression for
improved parallel scalability and space usage.

#### Batch and concurrent updates

There is extensive work on concurrent data structures such as trees (Aksenov
et al., 2017; Arbel-Raviv et al., 2018; Braginsky and Petrank, 2012; Bronson
et al., 2010; Mao et al., 2012; Ellen et al., 2010; Kung and Lehman, 1980;
Natarajan and Mittal, 2014), skip lists (Herlihy et al., 2006; Pugh, 1998),
and PMAs (Wheatman and Xu, 2021). Concurrent data structures are mostly
orthogonal to this paper, which focuses on batch-parallel data structures.
Existing concurrent trees typically support mostly point operations (i.e.,
linearizable inserts/deletes and finds), whereas the PMA/CPMA in this paper
also support range queries and maps (and associated operations such as filter
and reduce). Some recent work studies range queries in concurrent trees (Basin
et al., 2020; Fatourou et al., 2019). On the other hand, concurrent trees
support asynchronous updates, which are more general than batch updates
because batch updates require a single writer. Therefore, fairly comparing
concurrent and batch-parallel data structures on update throughput is
challenging as their update functionalities are not apples-to-apples.

The PAM paper (Sun et al., 2018) demonstrated that batch-parallel binary trees
can achieve orders of magnitude higher insertion throughput compared to
concurrent cache-optimized trees such as Masstree (Mao et al., 2012), OpenBw-
tree (Wang et al., 2018), and B+-tree (Zhang et al., 2016). The PaC-trees
(Dhulipala et al., 2022) that we evaluate in this paper further improve upon
PAM with blocking and compression.

Batch-parallel and concurrent data structures are suited for different use
cases. For example, batch-parallel data structures have recently become
popular both practically (Ediger et al., 2012; Kyrola et al., 2012; Macko et
al., 2015; Dhulipala et al., 2019) and theoretically (Acar et al., 2019;
Nowicki and Onak, 2021; Dhulipala et al., 2020; Dhulipala et al., 2021;
Ferragina and Luccio, 1994; Tseng et al., 2019) for dynamic graph algorithms
and containers. They are well-suited for applications with a large number of
requests in a short time, such as stream processing or loop join (Kim et al.,
2010). In contrast, concurrent data structures have been used extensively in
key-value stores for online transaction processing applications that emphasize
point operations such as put and get (Cooper et al., 2010).

#### Arrays and trees in the literature

Furthermore, although tree-based data structures are more amenable to the
functional programming paradigm (Dhulipala et al., 2022, 2019), they incur a
performance and space cost over array-based data structures due to their
pointers. As a result, researchers have developed pointerless array-based
representations for fundamental data structures such as quadtrees (Gargantini,
1982; Holroyd and Mason, 1990; Frisken and Perry, 2002) and suffix trees
(Manber and Myers, 1993; Abouelhoda et al., 2004; Grossi and Vitter, 2005; Ko
and Aluru, 2003; Kim et al., 2003) for improved locality and compactness. This
paper presents a similar development in the domain of batch-parallel sets with
the PMA, an array-based data structure.

##  3\. Packed Memory Array

This section reviews the Packed Memory Array (Bender et al., 2000; Itai et
al., 1981) (PMA) data structure to understand the improvements in later
sections. First, it introduces the theoretical models used to analyze the PMA.
It then describes the PMA’s structure and outlines the insert, delete, search,
and range query operations that the PMA supports and their theoretical bounds.
Finally, it details how to perform point updates in a PMA, which forms the
basis for the batch-update algorithm in Section 4.

#### Analysis method

Table 2 summarizes the bounds for key parallel operations in the CPMA and
compressed PaC-tree in the work-span model (Cormen et al., 2009, Chapter 27)
and the external-memory model (Aggarwal and Vitter, 1988). Given a cache-line
size of $B$ elements, the external-memory model captures spatial locality by
measuring algorithm cost in terms of cache-line transfers. The work is the
total time to execute the entire algorithm in serial. The span is the longest
serial chain of dependencies in the computation (or the runtime in
instructions on an infinite number of processors). In the work-span model, a
parallel for loop with $k$ iterations with $O(1)$ work per iteration has
$O(k)$ work and $O(\log(k))$ span because loops can be implemented with
divide-and-conquer fork-join parallelism (Cormen et al., 2009, Chapter 27).

#### Design and operations

The PMA maintains elements in sorted order in an array with (a constant factor
of) empty spaces between its elements. Specifically, a PMA with $n$ elements
uses $N=\Theta(n)$ cells. The empty cells enable fast updates by reducing the
amount of data movement necessary to maintain the elements in order. The
primary feature of a PMA is that it stores data in contiguous memory, which
enables fast cache-efficient iteration through the elements.

A PMA exposes four operations:

  * •

insert(x): inserts element x into the PMA.

  * •

delete(x): deletes element x from the PMA, if it exists.

  * •

search(x): returns a pointer to the smallest element that is at least x in the
PMA.

  * •

range_map(start, end, f): applies the function f to all elements in the range
[start, end).

In this paper, we use the terms “range map” and “range query” interchangeably.
Range queries can be implemented with the more general range map, but we use
the more popular term “range query.”

Given a cache-line size of $B$ elements (Aggarwal and Vitter, 1988), the PMA
supports point queries (search) in $O(\log(n))$ cache-line transfers and
updates in $O(1+(\log^{2}(n))/B)$ (amortized and worst-case) cache-line
transfers (Bender et al., 2017; Bender et al., 2000, 2005; Willard, 1982,
1986, 1992). The PMA supports efficient iteration of the elements in sorted
order, enabling fast scans and range queries. Specifically, the PMA supports
the range_map operation on $k$ elements in $O(\log(n)+k/B)$ transfers. It
implements range_map with a search for the first element in the range, then a
scan until the end of the range.

PMAs are asymptotically worse than cache-optimized trees such as PaC-trees for
updates and match them for queries (Table 2).

The PMA defines an implicit binary tree with leaves of $\Theta(\log(N))$ cells
each. That is, the implicit tree has $\Theta(N/\log(N))$ leaves and height
$\Theta(\log(N/\log(N)))$. Every node in the PMA tree has a corresponding
region of cells. Each leaf $i\in\\{0,\ldots,N/\log(N)-1\\}$ has the region
$[i\log(N),(i+1)\log(N))$, and each internal node’s region encompasses all of
the regions of its descendants. The density of a region in the PMA is the
fraction of occupied cells in that region.

Each node of the PMA tree has an upper density bound that determines the
allowed number of occupied cells in that node. If an insert causes a node’s
density to exceed its upper density bound, the PMA enforces the density bound
by redistributing elements with that node’s sibling, equalizing the densities
between them. The density bound of a node depends on its height.

#### Updating a PMA

Figure 3. Example of an insertion in a PMA with leaf density bound of 0.9 and
leaf size of 4.

Next, we will see how a PMA maintains spaces between elements for efficient
updates. Since deletions are symmetric to insertions, we will focus on the
case of insertions.

As shown in Figure 3, the four main steps in a PMA insertion are as follows:

  1. (1)

Search for the location that the element should be inserted into to maintain
global sorted order.

  2. (2)

Place the element at that location, potentially shifting some elements to make
room.

  3. (3)

If the leaf violates its density bound, count nodes in the PMA to find a
sibling to redistribute into.

  4. (4)

If necessary, redistribute elements to maintain the correct distribution of
empty spaces in the PMA.

The four steps of a PMA insertion use the implicit tree to determine which
leaf to modify and which node to redistribute, if any. Step (1) involves a
binary search on the leaves, which takes $O(\log(n))$ cache-line transfers.
Once the correct leaf is found, step (2) shifts up to $O(\log(n))$ cells of
that leaf to place the element in sorted order. Step (3) involves counting the
density of the leaf after the insertion. If the leaf exceeds its density
bound, the PMA traverses up the corresponding leaf-to-root path, counting
densities in exponentially-growing regions, until it finds a sibling node that
can support a redistribute that satisfies its parent’s density bound. If such
a node has been found, step (4) redistributes elements equally amongst all of
the nodes’ descendants. Counting and redistributing elements takes
$O((\log^{2}(n))/B)$ (amortized and worst-case) cache-line transfers (Bender
et al., 2017; Bender et al., 2000, 2005; Willard, 1982, 1986, 1992).

#### Resizing a PMA

If the root-to-leaf traversal after an insert reaches the root and finds that
its density bound has been violated, the entire PMA is copied to a larger
array and the elements are distributed equally amongst the leaves of the new
PMA.

The growing factor is the amount by which the underlying array in the PMA
grows when it becomes too dense. A growing factor of $2\times$ corresponds to
table doubling, a classical technique in dynamic data structures to
accommodate changing data structure size. The asymptotic bounds of the PMA
still hold as long as the growing factor is a constant greater than 1.

##  4\. Batch Updates in a PMA

Batching updates in a PMA improves throughput by reducing the work per update
and simplifying parallelization. For ease of presentation, this section
describes how to apply batch inserts in a PMA, but batch deletes are symmetric
to inserts.

This section introduces a work-efficient parallel batch-insert algorithm for
PMAs. A work-efficient parallel algorithm performs no more than a constant
factor of extra operations than the serial algorithm for the same problem.
Serially inserting $k$ elements into a PMA with $n$ elements takes
$O(k(\log(n)+(\log^{2}(n))/B))$ work. Unfortunately, a naive parallel
algorithm that parallelizes over the inserts is not work-efficient because it
may recount densities to determine which regions to redistribute, as described
in Section 3. As we shall see, supporting work-efficient batch inserts
requires careful algorithm design to avoid redundant work. Finally, we
conclude the section with a microbenchmark that demonstrates the serial and
parallel scalability of batch updates in PMAs.

#### Batch-insert problem

The batch-insert problem for PMAs takes as input a PMA with $n$ elements and a
batch with $k$ sorted elements to insert. An unsorted batch can be converted
into a sorted batch in $\Theta(k\log(k))$ work.

The optimal strategy for applying a batch of updates depends on the size of
the batch. At one extreme, if $k$ is small, point updates are more efficient
than batch updates. At the other extreme, if $k$ is large, the optimal
algorithm is to rebuild the entire data structure by merging in a sorted
batch. The batch-insert algorithm for PMAs performs local merges to address
the intermediate case between these two extremes.

Figure 4. Example of batch insertion in a PMA with leaf density bound of 0.75
and leaf size of 4. After the merge, there are more elements in the second
leaf than the leaf size, so the number of elements is stored in the leaf, and
the elements are stored out-of-place until the redistribute.

#### Batch-insert algorithm

We introduce a batch-insert algorithm for PMAs, which applies a batch of
updates efficiently in the case where neither point insertions nor a complete
merge are the best options. Therefore, we focus on the case where $k=o(n)$.

The batch-insert algorithm is comprised of three phases: (1) a batch-merge
phase, (2) a counting phase, and (3) a redistribute phase. The phases proceed
in serial, but each phase is parallelized internally. The phases adapt the
steps of a PMA insertion described in Section 3 to the batch setting. The
batch-merge phase combines the search and place steps, and the counting and
redistribute phases generalize their counterparts from point inserts.

#### Batch-merge phase

At a high level, the parallel batch-merge phase divides the PMA and the batch
recursively into independent sections and operates independently on those
sections. Each recursive step first merges elements from the batch into one
leaf of the PMA, and then recurses down on the remaining left and right
portions of the batch. This recursive merge phase is inspired by recursive
join-based algorithms in batch-parallel trees (Adams, 1992, 1993; Dhulipala et
al., 2022, 2019; Blelloch et al., 2016; Sun et al., 2018). However, existing
join-based algorithms rely on maintaining balance in pointer-based data
structures. In contrast, a batch-update algorithm for PMAs maintains balance
in an array-based layout.

At each step of the recursion, we perform a PMA search for the midpoint
(median) of the current batch and merge the relevant elements from the batch
destined for that leaf. Finding the bounds in the batch of all elements in
that leaf takes two searches (one backwards and one forwards). Once the
endpoints have been found, we fork the merge of all relevant elements from the
current batch into the target leaf. If the number of elements destined for a
leaf is sufficiently large, we use a parallel merge algorithm with load-
balancing guarantees to achieve parallelism (Akl and Santoro, 1987). Finally,
we recurse on the remaining left and right sides of the batch in parallel.

###### Lemma 1.

Given a batch of $\;k$ sorted elements, the work of the batch-merge phase is
$O(k\log(n))$, and the span is $O(\log(k)\log(n))$.

###### Proof.

The height of the recursion is $O(\log(k))$, and each search in the PMA takes
$O(\log(n))$ work. Finding the first and last element in the batch destined
for the leaf takes $O(\log(k))$ work with exponential searches, which is
smaller than $O(\log(n))$. Therefore, the work and span of finding the bounds
for the recursion is $O(\log(k)\log(n))$.

In the worst case for the work, each element in the batch could be destined
for a different leaf, so the total work of merging $k$ elements into $k$
leaves is $O(k\log(n))$, which is asymptotically larger than the work to
perform the recursion.

The worst-case span for any of the merges is $O(\log^{2}(k))$, so the total
span of finding the endpoints and the merges is bounded above by
$O(\log(k)\log(n))$. ∎

Figure 5. An example of the work-efficient counting algorithm for batch
updates. The blocks at the top represent the PMA leaves and the dots represent
elements in the PMA. The pink blocks with arrows represent leaves that were
touched during a batch update. The tree below the PMA is the implicit PMA tree
of nodes labeled with a tuple of (height, index) (indices are assigned left to
right). The blue solid circles represent PMA nodes that must be counted
because their sibling or child violated its density. The tan dotted circles
represent PMA nodes that did not need to be counted.

When merging elements from the batch into a leaf, the target leaf may overflow
because it does not have enough space to hold all the elements destined for
it. To resolve this issue, the batch merge copies all elements into separate
memory and keeps the size of the extra memory as well as a pointer to it in
the leaf. This extra data is then cleaned up after the merge during the
redistribution phase. Figure 4 illustrates a batch merge, leaf overflow, and
subsequent redistribution.

During the recursive batch merge, we keep track of all modified PMA leaves in
a thread-safe set for use in the counting and redistribution phases.

#### Counting phase

After inserting all elements into the PMA, the batch insert algorithm performs
a counting phase where it finds the PMA nodes that violate their density
bounds for later redistribution. The $O(\log^{2}(n)/B)$ bound for point
insertions in the PMA comes from amortized analysis of the counting and
redistribution phase (Itai et al., 1981), so efficiently counting and
redistributing in the parallel batch setting is critical to achieving work-
efficiency.

To understand how to avoid redundant work due to counting densities, let us
first consider an efficient serial algorithm in the batch setting that counts
each cell that may be involved in a redistribution exactly once by caching
prior results. The algorithm starts with the set of leaves that were touched
in the batch-merge phase. The ancestors of these leaves in the implicit PMA
tree may need to be redistributed, depending on how many elements were
inserted. The serial algorithm checks every leaf in turn. If a leaf violates
its density bound, the algorithm then walks up the implicit PMA tree from that
leaf until it finds a node that respects its density bound, counting node
densities along the way. By caching every result and checking the cached
results before counting, the serial algorithm counts every cell exactly once
because it can look up any previously counted node.

Unfortunately, simply parallelizing the serial algorithm over the leaves is
not work-efficient because the algorithm may recount PMA nodes whose densities
have not been cached yet. Therefore, the parallel algorithm may recount the
same region more than a constant number of times if many leaves share the same
ancestor to be redistributed.

To resolve this issue, we devise a new work-efficient parallel counting
algorithm that counts each PMA cell that needs to be counted exactly once.
Figure 5 presents a worked example of this counting algorithm. The counting
algorithm takes as input the leaves that were modified in the batch merge and
outputs the set of PMA nodes that need to be redistributed.

The counting algorithm avoids redundant work by processing the levels serially
in a bottom-up fashion (starting from the leaves) and saving any counts for
later lookups by nodes in higher levels. At each level, we maintain a thread-
safe set of nodes that need to be counted. This set is initialized with the
leaves that were affected by the batch merge. The levels are processed
serially, but all nodes at each level are processed in parallel. If any node
at some level $i$ exceeds its density bound, the algorithm adds its parent to
the set of nodes to be counted at level $i+1$. The algorithm terminates when
there are no more nodes to be counted, or it has reached the PMA root.

###### Lemma 2.

The parallel counting algorithm is work-efficient.

###### Proof.

The parallel counting algorithm caches results from each counted region as it
processes the levels of the PMA tree. The serial bottom-up iteration of levels
of the PMA tree ensures that no extra nodes are counted compared to the
efficient serial algorithm described earlier. Next, we will show that the
parallel counting algorithm does not recount any cells.

Suppose that the algorithm is counting the density of some internal node $x$
at level $i$ (i.e., $i>0$). At least one child of $x$ must have been counted
for $x$ to be under consideration. Therefore, there are two cases:

Case 1: Both children of $x$ have been counted. In this case, finding the
density of $x$ just involves combining the cached children’s counts.

Case 2: One child of $x$ has been counted. Let $y$ be the child of $x$ that
has not been counted. In this case, the algorithm counts the density of $y$ by
recursively traversing the subtree rooted at $y$ in a top-down fashion. This
recursion proceeds in parallel, starting with $y$ and ending at the PMA
leaves. For each descendant of $y$, the algorithm checks if its count has been
cached. If yes, that particular branch of the recursion ends and the algorithm
simply incorporates the cached count into the density count for $y$. If not,
the recursion continues down that path. If the recursion reaches a leaf
without finding a cached result, it counts the leaf in parallel and adds it to
the density count for $y$. This top-down recursion ensures that no region will
ever be counted more than once, so the parallel counting algorithm is work-
efficient. ∎

###### Lemma 3.

The span of the parallel counting algorithm is $O(\log^{2}(n))$.

###### Proof.

The counting algorithm serially iterates over at most $O(\log(n))$ levels of
the PMA because the height of the PMA tree is bounded by $O(\log(n))$. In the
worst case, for each level $i$, the algorithm may have to recurse down $i$
levels to count, so the worst-case span of traversing the PMA tree levels is:
$\sum_{i=0}^{\log(n)}i=O(\log^{2}(n))$. The actual counting of each leaf adds
span $O(\log\log(n))$ because counting just involves checking every cell in
parallel in a leaf of size $O(\log(n))$. Therefore, the total span is
$O(\log^{2}(n))$. ∎

#### Redistribution phase

Once the counting phase has identified the correct regions to redistribute,
the PMA redistributes regions with two copies of the relevant data. The first
copy packs the regions to redistribute from the PMA into a buffer, and the
second copy equalizes the densities in the regions to redistribute by
spreading the elements evenly from the buffer into the target leaves.

###### Lemma 4.

Given a batch of $\;k$ sorted elements, the work of the redistribute phase is
$O((k\log^{2}(n))/B))$ amortized cache-line transfers, and the worst-case span
is $O(\log^{2}(n))$.

###### Proof.

The work of the redistribute phase is bounded above by the work of the
counting phase, because the number of elements that need to be redistributed
is at most the number of elements that need to be counted. From Lemma 2, the
counting step is work-efficient, so it takes no more than the serial amortized
work bound of $O((k\log^{2}(n))/B))$ cache-line transfers.

The span of the redistribute phase is bounded above by $O(\log^{2}(n))$
because there are at most $n$ independent sections to redistribute of size $n$
each. Redistributing each one involves a parallel copy in and out, which has
span $O(\log(n))$. ∎

#### Putting it all together

Analyzing the entire batch-insert algorithm just involves summing the work and
span of the merge, counting, and redistribute phases of the batch-insert
algorithm.

###### Theorem 5.

The batch-insert algorithm for PMAs supports inserting a batch of $\;k$ sorted
elements in $O(k(\log(n)+\log^{2}(n)/B))$ amortized work and $O(\log^{2}(n))$
worst-case span.

In contrast to a traditional PMA, the batch-parallel PMA is well-suited for
the case of all insertions targeting the same leaf. The worst-case insertion
distribution for element moves in a non-batch PMA is when all elements target
the same leaf. However, the batch-parallel PMA reduces work in this case
because it only requires a single search before a parallel merge, and triggers
a single large redistribute of the region.

| Batch
---
size
| Serial
---
throughput
| Speedup over
---
serial point
| Parallel
---
throughput
| Speedup over
---
serial batch
1—10 | 2.2E6 | 1.0 | 1.8E6 | 0.8
1E2 | 2.2E6 | 1.0 | 3.9E6 | 1.8
1E3 | 2.2E6 | 1.0 | 9.8E6 | 4.4
1E4 | 2.2E6 | 1.0 | 2.0E7 | 9.3
1E5 | 2.4E6 | 1.1 | 3.6E7 | 15.2
1E6 | 3.2E6 | 1.4 | 6.0E7 | 18.9
1E7 | 6.5E6 | 2.9 | 8.8E7 | 13.7
Table 3. Throughput of serial and parallel batch insertions in the PMA. We use
point insertions for small batches when the batch update algorithm does not
provide practical benefits.

#### Batch insert microbenchmark

To measure the throughput of batch inserts, we use the setup described in
Section 6 to insert 100 million elements into a PMA with varying batch sizes
and report the results in Table 3. The PMA under test starts with 100 million
elements and ends up with 200 million elements.

The batch-update algorithm achieves up to about $3\times$ speedup compared to
point inserts on one core. In practice, batch inserts in a PMA save
computation over point insertions by reducing the number of searches, the
length of each search, and the number of redistributions. The batch insert
algorithm performs only one binary search per updated leaf because the
remaining elements in the batch destined for that leaf are just merged in
directly. With point insertions, all of the insertions to the same leaf
perform the same binary search to that leaf. Additionally, the searches are
smaller because they often search a subsection of the PMA rather than the
entire PMA. Finally, the work-efficient counting algorithm combines ancestor
ranges to redistribute in the PMA, potentially skipping levels of
redistribution that would have occurred with point insertions.

Furthermore, Table 3 shows that batch updates in a PMA achieve parallel
speedup of up to about $19\times$ on $128$ cores as the batch size grows. The
main bottleneck in the parallel scalabilty of the batch updates is memory
bandwidth limitations. Section 5 mitigates these issues by adding compression
to the batch-parallel PMA to reduce data movement.

##  5\. Compressed Packed Memory Array

Figure 6. An example of inserting the same element in a PMA and CPMA for the
same dataset. The density bound in the PMA and CPMA leaves is 0.9. In this
example, uncompressed integers are 8 bits long, and the CPMA uses 4-bit codes.
The blue bits in the CPMA represent continue bits. The green shaded cells in
both the PMA and CPMA contain new data after the insert. The PMA redistributes
its elements after the insertion, but the CPMA does not because the insertion
did not violate the leaf density bound.

This section describes how to improve the space usage and scalability of a
Packed Memory Array by applying data compression, resulting in a new data
structure called a Compressed Packed Memory Array (CPMA). It then shows that
adding compression does not affect the asymptotic PMA operation bounds.
Furthermore, this section empirically shows that the CPMA achieves better
parallel scalability than the PMA because the multiple cores enable the
computation to become memory-bound, so the CPMA’s smaller size makes better
use of memory bandwidth. Finally, we investigate the impact of the growing
factor discussed in Section 3 and find that it bounds the worst-case space
usage and scan time and does not have a straightforward effect on the update
time.

#### Data compression techniques

The CPMA exploits the fact that elements are stored in sorted order in a PMA
to apply delta encoding (Smith et al., 1997), a canonical data compression
technique. Delta encoding stores differences (deltas) between sequential
elements rather than the full element. Given a sorted array $A$ of $n$
elements, delta encoding results in a new array $A^{\prime}$ such that
$A^{\prime}_{0}=A_{0}$ and for all $i=1,2,\ldots,n-1$,
$A^{\prime}_{i}=A_{i}-A_{i-1}$.

The CPMA then stores the differences in byte codes (Shun et al., 2015; Witten
et al., 1999). We chose to use byte codes because they are fast to decode and
achieve most of the memory savings of shorter codes (Shun et al., 2015;
Dhulipala et al., 2019; Blandford et al., 2004). Byte codes are a type of
variable-length encoding, or $k$-bit codes, which stores an integer as a
series of $k$-bit chunks (Blandford et al., 2004; Shun et al., 2015). Each
chunk uses one bit as a _continue bit_ , which indicates if the following
chunk starts a new element or is a continuation of the previous element.

There is nothing fundamental in the CPMA design that requires either delta
encoding or byte codes as opposed to other types of compression. We chose to
use these for their simplicity and performance. Delta encoding and byte codes
add a constant factor of computational overhead for encoding and decoding
blocks (Shun et al., 2015; Dhulipala et al., 2019; Blandford et al., 2004).

#### CPMA structure

At a high level, the CPMA maintains the same implicit binary tree structure as
a PMA and applies delta encoding and byte codes in the leaves. Just like in
the PMA, a CPMA with $n$ elements and $N=\Theta(n)$ cells maintains leaves of
size $\Theta(\log(n))$ in order to achieve its asymptotic time bounds. The
CPMA applies the packed-left optimization, which packs elements to the left in
PMA leaves, for ease of compression (Wheatman and Xu, 2021). Packing the
elements to the left does not affect the PMA’s (or CPMA’s) asymptotic
bounds444A traditional PMA redistributes all elements in a leaf after each
insertion. Therefore, the packed-left property does not incur extra element
moves over a regular PMA because both rearrange all elements in the leaf on
each insert. because the bounds only depend on the density of the elements in
the PMA leaves (Wheatman and Xu, 2021).

A CPMA leaf stores its head, or its first element, uncompressed, and stores
subsequent elements compressed with delta encoding and byte codes. That is, in
a CPMA with elements of type T, the first sizeof(T) bytes in each leaf contain
the uncompressed head. All following cells take 1 byte each rather than
sizeof(T) bytes.

The density bounds in a CPMA count byte density rather than element density.
The density in a CPMA node is the ratio of the number of filled bytes to the
total number of bytes available in the node.

### Operations

This section shows that the CPMA maintains the same asymptotic bounds as the
PMA for point queries (searches) and point updates. Furthermore, compression
does not affect concurrency schemes for PMAs (Wheatman and Xu, 2021) or the
batch-update algorithm from Section 4.

The PMA’s asymptotic bounds are derived from its implicit tree structure and
related density bounds. The main change in the CPMA is the compression of all
elements in each leaf besides the head, which maintains the high-level
implicit tree structure.

#### Point queries

A CPMA on $n$ elements supports point queries, or searches, in $O(\log(n))$
work. There are two steps in a point query in a CPMA: (1) a binary search on
leaf heads, and (2) a pass through the leaf at the end of the binary search to
find the closest element. There are $O(n/\log(n))$ leaves, so a binary search
takes $O(\log(n))$ work. The leaf heads are stored uncompressed, so there is
no additional cost to perform the binary search on leaf heads compared to a
search in a PMA. After finding the target leaf, the CPMA performs a search
within that leaf. The size of each leaf is bounded by $O(\log(n))$, so it
takes $O(\log(n))$ work to search a compressed leaf.

#### Point updates

A CPMA on $n$ elements supports point updates in $O(\log(n)+(\log^{2}(n))/B)$
work. We will focus on the case of inserts, since deletes are symmetric to
inserts. Figure 6 presents a worked example of the same insert in a PMA and a
CPMA.

There are three main steps in a point update in a CPMA: (1) a point query to
find the leaf that needs to be updated, (2) an insert in that leaf, (3) a
traversal up the PMA tree to count nodes if necessary, and (4) a
redistribution of elements to satisfy the density bounds. We will focus on
steps (2)-(4), since we already analyzed point queries.

After performing a point query to find the target leaf, the CPMA performs a
point insertion by adding a delta to the leaf. Updating the leaf can be done
in a single pass, which takes $O(\log(n))$ work because the size of the leaf
is bounded by $O(\log(n))$.

Once the target leaf has been updated, the CPMA traverses up the leaf-to-root
path and redistributes any nodes that violate their density bounds just as in
a PMA. The amortized insert time bound comes from the checking and maintenance
of density bounds, which the CPMA supports in the same asymptotic work as a
PMA. Just as in a PMA, counting and redistributing in a CPMA takes linear work
proportional to the size of the region.

#### Parallelizing the CPMA

The compression in the CPMA does not conflict with existing lock-based
multiple-writer parallelism for PMAs (Wheatman and Xu, 2021) because the
locking scheme depends on the implicit PMA tree structure and locking at a
leaf granularity. Furthermore, compression does not affect the theoretical
performance of concurrent PMAs because the CPMA also supports single-pass
operations within leaves. The CPMA supports multiple readers because reads are
non-modifying.

Finally, the high-level structure of the batch-update algorithm in the CPMA is
identical to the batch-update algorithm for PMAs described in Section 4. The
design and analysis of the batch-update algorithm also depends only on single-
pass operations on leaves.

### Scalability analysis

hg$1$hg$2$hg$4$hg$8$hg$16$hg$32$hg$64$hg$128$hg$10$hg$20$hg$30$hg$40$hg$50$ThreadsSpeeduphgPMAhgCPMA
Figure 7. Strong scaling of batch inserts in the PMA/CPMA.
hg$1$hg$2$hg$4$hg$8$hg$16$hg$32$hg$64$hg$1$hg$1.25$hg$1.5$hg$1.75$hg$2$ProcessesSlowdownhgPMAhgCPMA
Figure 8. Weak scaling of batch inserts in the PMA/CPMA.

We measure the strong scaling of both the uncompressed and compressed PMA on
batch inserts and range queries using the setup described in Section 6. We set
the growing factor of both the PMA and CPMA in these experiments to
$1.2\times$ as it strikes a balance between insert and range query
performance. We conclude this section with a sensitivity analysis based on the
growing factor. In each batch-insert experiment, the PMA and CPMA start with
100 million elements, and we add 100 batches of 1 million elements each. The
PMA and CPMA use the same parallel batch-insert algorithm from Section 4. In
each range-query experiment, the PMA/CPMA is initialized with 100 million
elements. We perform 100,000 range queries in parallel where each query is
expected to return about $1.5$ million elements. To measure strong scaling, we
measure the effect of thread count on one PMA/CPMA.

We also measure the weak scaling of the PMA/CPMA on batch inserts by creating
one independent PMA/CPMA per process and varying the number of processes. We
then measure the process with the slowest completion time. The goal of this
experiment is to evaluate how memory bandwidth limitations affect the
PMA/CPMA. We use multiple PMAs rather than a single larger PMA to ensure no
interference between processes.

Figures 7 and 8 show that the CPMA achieves better strong and weak scaling
than the PMA on batch inserts because compression maximizes the CPMA’s usage
of available memory bandwidth. The CPMA achieves much better scalability with
the same algorithm due to its smaller memory traffic. For strong scaling, the
PMA achieves up to $19\times$ speedup and the CPMA achieves up to $43\times$
speedup on $128$ threads. The CPMA achieves better batch insert throughput
compared to the PMA when the number of threads is sufficiently large (at least
16). When the number of threads is too small, the additional computational
overhead from compression outweighs the benefits of decreased memory traffic.
For weak scaling, the PMA incurs up to $2\times$ slowdown with 64 processes,
while the CPMA incurs about $1.2\times$ slowdown on 64 processes.

hg$1$hg$2$hg$4$hg$8$hg$16$hg$32$hg$64$hg$128$hg$1$hg$2$hg$8$hg$32$hg$128$ThreadsSpeeduphgPMAhgCPMA
Figure 9. Strong scaling of range queries in the PMA/CPMA.

Similarly, Figure 9 demonstrates that CPMA achieves about $118\times$ speedup
for range queries on $128$ threads, while the PMA achieves about $41\times$
speedup on the same workload and thread count. The PMA’s/CPMA’s scalability on
range queries is much better than its scalability on updates because the
queries proceed in parallel and do not need to coordinate. The PMA’s range
query throughput in terms of bytes transferred per second reaches the memory
bandwidth on the machine, but its overall range query throughput is limited
because of the large size per element. The CPMA alleviates the memory
bandwidth issue by decreasing the size per element, enabling it to support
more elements processed per byte transferred.

### Growing factor sensitivity

Finally, we evaluate how the space usage, batch insertion throughput, and scan
throughput of the CPMA changes with the growing factor.

To measure the effect of growing factor on the CPMA, we performed the
following experiment on CPMAs with growing factors
$1.1\times,1.2\times,\ldots,2.0\times$. We started with an empty CPMA and
added 1 billion elements in batches of 1 million elements each (for a total of
1,000 batches). After each batch, we measured the space usage of the CPMA and
performed a parallel scan over all of the elements. We also measure the batch
insertion throughput as a function of growing factor.

Figure 10 demonstrates that a smaller growing factor results in smaller
average space usage and therefore better average scan performance because
smaller sizes require less memory traffic. Figure 11 shows that the growing
factor bounds the worst-case space usage of the CPMA: a CPMA with a higher
growing factor has a higher worst-case space usage. However, the exact space
usage and scan performance depend not only on the growing factor but also on
the state of the CPMA (i.e., how far it is from a growth).

Moreover, the relationship between insert time and growing factor is not as
straightforward as the relationship between size/scan and growing factor.
Figure 10 shows that the CPMA with growing factor $1.5\times$ achieves the
best insertion throughput. Small growing factors (e.g., $1.1\times$) increase
the number of array copies since the CPMA incurs more growths, but also
decrease the size of the array which improves other parts of inserts such as
the binary search and rebalances. On the other hand, large growing factors
(e.g., $2\times$) have fewer array copies but longer searches, which
contribute to more expensive inserts.

hg$1.2$hg$1.4$hg$1.6$hg$1.8$hg$2$hg$0$hg$0.2$hg$0.4$hg$0.6$hg$0.8$hg$1$Growing
factorRatio from besthgInserthgSize (avg)hgScan (avg) Figure 10. Effect of
growing factor on performance and size.

hg$10^{7}$hg$10^{8}$hg$10^{9}$hg$0$hg$5$hg$10$hg$15$Size (bytes)per
elementhg2.0hg1.2

hg$10^{7}$hg$10^{8}$hg$10^{9}$hg$0$hg$0.2$hg$0.4$hg$0.6$hg$0.8$hg$1$hg$\cdot
10^{-10}$ElementsScan time (s)per elementhg2.0hg1.2

Figure 11. Size and scan performance after each batch insertion in CPMAs with
different growing factors.

##  6\. Evaluation on microbenchmarks

| Avg.
---
len.
U-PaC | PMA |  | PMA
---
U-PaC
C-PaC | CPMA |  | CPMA
---
C-PaC
| CPMA
---
PMA
6E0 | 2.0E8 | 1.7E9 | 8.3 | 1.8E8 | 8.1E8 | 4.4 | 0.5
5E1 | 9.5E8 | 6.6E9 | 7.0 | 8.5E8 | 5.1E9 | 6.0 | 0.8
4E2 | 2.1E9 | 1.3E10 | 6.1 | 1.5E9 | 1.5E10 | 10.3 | 1.2
3E3 | 1.0E10 | 1.6E10 | 1.5 | 7.0E9 | 2.2E10 | 3.1 | 1.4
2E4 | 1.6E10 | 1.7E10 | 1.1 | 1.6E10 | 2.4E10 | 1.5 | 1.4
2E5 | 1.8E10 | 1.8E10 | 1.0 | 1.9E10 | 2.4E10 | 1.3 | 1.3
2E6 | 1.9E10 | 1.9E10 | 1.0 | 1.9E10 | 2.4E10 | 1.2 | 1.3

Table 4. Range query throughput (elements per second) on all ($128$) cores in
PaC-trees and the PMA/CPMA.

| Batch
---
size
U-PaC | PMA |  | PMA
---
U-PaC
C-PaC | CPMA |  | CPMA
---
C-PaC
| CPMA
---
PMA
1E1 | 1.9E5 | 1.8E6 | 9.4 | 3.0E5 | 1.5E6 | 5.1 | 0.8
1E2 | 2.4E6 | 3.9E6 | 1.7 | 1.8E6 | 3.1E6 | 1.8 | 0.8
1E3 | 4.8E6 | 9.8E6 | 2.0 | 3.4E6 | 1.1E7 | 3.1 | 1.1
1E4 | 5.9E6 | 2.0E7 | 3.5 | 4.2E6 | 3.4E7 | 8.0 | 1.6
1E5 | 1.1E7 | 3.6E7 | 3.3 | 7.2E6 | 4.6E7 | 6.3 | 1.3
1E6 | 6.1E7 | 6.0E7 | 1.0 | 4.1E7 | 1.1E8 | 2.6 | 1.8
1E7 | 3.5E8 | 8.8E7 | 0.2 | 2.7E8 | 1.6E8 | 0.6 | 1.8

Table 5. Parallel batch insertion throughput (inserts per second) on all
($128$) cores in PaC-trees and the PMA/CPMA.

To measure the improvements described in Sections 4 and 5, this section
evaluates the PMA/CPMA compared to uncompressed/compressed PaC-trees on range
queries, batch inserts, and space usage (Dhulipala et al., 2022). We use the
terms “U-PaC” and “C-PaC” to denote the uncompressed and compressed versions
of PaC-trees, respectively, in all exhibits in this section.

At a high level, the CPMA achieves the best of both worlds in terms of
performance. On average, it is $1.2\times$ faster for range queries and
$3\times$ faster on batch inserts than compressed PaC-trees. According to the
theoretical prediction in Table 2, PaC-trees asymptotically match or beat
CPMAs for all operations. However, in practice, the CPMA supports both fast
queries and updates due to its locality. Finally, CPMAs use about the same
space as compressed PaC-trees, but use less than half the space of
uncompressed PMAs.

#### Experimental setup

We implemented the PMA and CPMA as a C++ library on top of the search-
optimized PMA (Wheatman et al., 2023) and compiled them with clang++-14. To
match the parallelization method from the PaC-trees library, we parallelized
the PMA/CPMA with the Parlaylib toolkit (Blelloch et al., 2020). The PMA and
CPMA are currently implemented as key stores (sets). We set the growing factor
in the PMA/CPMA to $1.2\times$. The code can be found at
https://github.com/wheatman/Packed-Memory-Array.

PaC-trees are implemented in a C++ library (Dhulipala et al., 2022) and also
parallelized with the Parlaylib toolkit (Blelloch et al., 2020). As
recommended by the authors, we compiled PaC-trees with g++-11. We used the in-
place set mode of PaC-trees for a fair comparison (although the library also
supports a functional mode). The PaC-trees library block size is set to the
default for sets at 256, which corresponds to a maximum node size of 4108
bytes. To initialize PaC-trees, we used the library-provided recursive build
functionality, which lays out the tree nodes non-contiguously in memory.

All experiments were run on a 64-core 2-way hyper-threaded Intel® Xeon®
Platinum 8375C CPU @ 2.90GHz with 256 GB of memory from AWS (Amazon, 2022).
Across all the cores, the machine has 3 MiB of L1 cache, 80 MiB of L2 cache,
and 108 MiB of L3 cache. All performance results are the average of 10 trials
after a single warm up trial.

The PaC-trees and PMA/CPMA experiments have identical setups except for the
underlying data structures. For all tests, we used $40$-bit uniform random
numbers as a balance between the compression ratio and the number of
duplicates. The uniform random case is the worst case for compressed data
structures because it maximizes the deltas between elements and therefore
minimizes the compression ratio. The uniform random case is also the worst
case for batch inserts because it minimizes the amount of shared work between
updates that the algorithm can eliminate. However, the uniform random case is
the best case for redistributes in PMAs/CPMAs.

To measure range-query performance, we first initialized the data structure
with 100 million elements and then performed 100,000 range queries in
parallel. We varied the size of the range queries across experiments. To
measure batch-insert performance, we first initialized the data structure with
100 million elements. We then inserted an additional 100 million elements in
batches. We varied the batch size across experiments. If the batch-insert
performance was ever slower than the non-batched insert done in a loop, the
non-batched insert number was used. To measure the space usage, we vary the
number of elements and report the size.

We also evaluate the serial batch-update algorithm from the Rewired PMA (RMA)
(De Leo and Boncz, 2019b) with the provided test code and build scripts. For a
fair comparison, we ran the batch update algorithm for PMAs from Section 4 on
one core.

The RMA’s provided tests do not use $40$-bit uniform random numbers but
instead use the numbers $[1,2,\ldots,n]$ where $n$ is the total number of
elements after the test. However, the ordering of the numbers is uniform
random, which determines the performance of inserts in the PMA, and by
extension, the RMA. Furthermore, the RMA is uncompressed, so the magnitude of
the numbers does not matter.

Batch size |  RMA (De Leo and Boncz, 2019b) | PMA | PMA/RMA
---|---|---|---
1—1E4 | 1.7E6 | 2.2E6 | 1.3
1E5 | 2.0E6 | 2.4E6 | 1.2
1E6 | 2.5E6 | 3.2E6 | 1.3
1E7 | 5.4E6 | 6.5E6 | 1.2
Table 6. Serial batch insert throughput (inserts per second) of the
uncompressed PMA and RMA. We use point insertions for small batches when the
batch update algorithm does not provide practical benefits.

#### Range queries

Figure 2 and Table 4 shows that the CPMA supports range queries at least
$1.2\times$ faster than compressed PaC-trees. The CPMA is faster to scan than
compressed PaC-trees because the CPMA’s contiguous layout enables prefetching,
while PaC-trees require pointer-chasing between tree nodes. Furthermore, for
small ranges, the CPMA is at least $5\times$ faster due to the pre-existing
search layout optimizations, which are orthogonal to the compression and batch
update optimizations (Wheatman et al., 2023).

Furthermore, the CPMA supports range queries $1.3\times$ faster than the PMA
on the largest range because the CPMA’s smaller size enables it to fetch more
elements before reaching memory bandwidth. However, the PMA is faster for
small range queries because of the added overhead of decompression in the
CPMA.

#### Batch inserts

Figure 1 and Table 5 demonstrate that parallel batch inserts in the CPMA are
on average $3\times$ faster than in compressed PaC-trees, despite the
theoretical prediction. The CPMA’s cache-friendliness enables it to support
faster updates than the theory suggests. As mentioned in Section 3, PMAs (and
by extension, CPMAs) support point updates in $O((\log^{2}(n))/B+\log(n))$
work. Trees theoretically dominate PMAs for point updates: balanced binary
trees supports updates in $O(1+\log(n))$ work (Cormen et al., 2009), and
cache-friendly trees such as B-trees (Bayer and McCreight, 1972) support
updates in $O(1+\log_{B}(n))$ work. However, in practice, batch updates in a
CPMA are faster than batch updates in compressed PaC-trees because the CPMA
takes advantage of contiguous memory access.

Table 6 evaluates the batch-insert algorithm for uncompressed PMAs from
Section 4 on one core compared to the existing serial batch-insert algorithm
for RMAs, an optimized version of PMAs (De Leo and Boncz, 2019b). On average,
the batch-insert algorithm in this paper is about $1.2\times$ faster than the
existing batch-insert algorithm for RMAs.

| Num.
---
Elts.
U-PaC | PMA |  | PMA
---
U-PaC
C-PaC | CPMA |  | CPMA
---
C-PaC
| CPMA
---
PMA
1E6 | 8.07 | 11.82 | 1.46 | 4.23 | 4.77 | 1.13 | 0.40
1E7 | 8.12 | 10.51 | 1.30 | 4.01 | 4.25 | 1.06 | 0.40
1E8 | 8.09 | 11.36 | 1.40 | 3.34 | 3.16 | 0.95 | 0.28
1E9 | 8.07 | 11.84 | 1.47 | 2.99 | 2.81 | 0.94 | 0.24

Table 7. Bytes per element in each of the data structures and compression
ratios. The sizeof(T) is 8 bytes.

#### Space usage

Table 7 shows that CPMAs are similar in size to compressed PaC-trees and are
over $2\times$ smaller than uncompressed PMAs. The space savings of the
compressed data structures improves with the number of elements because the
distance between elements decreases as the number of elements increases. The
CPMA uses more space than compressed PaC-trees for smaller inputs but less
space than compressed PaC-trees when the input is sufficiently large (at least
100M elements) because the CPMA leaf size, which defines the ratio of
uncompressed to compressed elements, grows with the number of elements.

##  7\. Evaluation on graph workloads

This section evaluates the CPMA and compressed PaC-trees on an application
benchmark of dynamic-graph processing because both PMAs and trees appear
frequently as dynamic-graph containers (Sha et al., 2017a; Wheatman and Xu,
2018; De Leo and Boncz, 2019a; Wheatman and Xu, 2021; De Leo and Boncz, 2021;
Pandey et al., 2021; Dhulipala et al., 2019, 2022; Wheatman and Burns, 2021).
We introduce F-Graph, a system for processing dynamic graphs that uses the
CPMA as its underlying data structure. We will first define graphs, a
fundamental method of representing connections, and describe how F-Graph
processes dynamic graphs with a single CPMA.

This section then empirically evaluates F-Graph compared to C-PaC (Dhulipala
et al., 2022), a state-of-the-art dynamic-graph-processing system based on
compressed PaC-trees. The evaluation shows that F-Graph is on average
$1.2\times$ faster on a suite of graph algorithms and $2\times$ faster for
batch updates compared to C-PaC. Finally, F-Graph is marginally smaller than
C-PaC.

Graph | Vertices | Edges | Avg. Degree
---|---|---|---
Live Journal (LJ) | 4,847,571 | 85,702,474 | 18
Com-Orkut (CO) | 3,072,627 | 234,370,166 | 76
Erdős-Rényi (ER) | 10,000,000 | 1,000,009,380 | 100
Twitter (TW) | 61,578,415 | 2,405,026,092 | 39
Friendster (FS) | 124,836,180 | 3,612,134,270 | 29
Table 8. Sizes of (symmetrized) graphs used.

#### Graphs

A graph is a way of storing objects as vertices and connections between those
objects as edges. Since the graphs in the evaluation are unweighted, we will
define an unweighted graph. Formally, an unweighted graph $G=(V,E)$ is a set
of vertices $V$ and a set of edges $E$. We denote the number of vertices $|V|$
and the number of edges $|E|$. Each vertex $v\in V$ is represented by a unique
non-negative integer less than $|V|$ (i.e. $v\in\\{0,1,\ldots,|V|-1\\}$). Each
edge is a 2-tuple $(u,v)$ where $u,v\in V$. For each edge, we refer to the
vertex $u$ as the source and the vertex $v$ as the destination. The graphs in
this paper have been symmetrized so that each vertex has the same incoming and
outgoing edges, also known as an undirected graph. The degree of a vertex is
the number of incident edges to that vertex.

#### F-Graph description

F-Graph is built on a single batch-parallel CPMA with delta compression and
byte codes. It differs from traditional graph representations because it uses
only a single array to store both the vertex and edge data.

To understand the distinction, let us consider the canonical Compressed Sparse
Row (CSR) (Tinney and Walker, 1967) representation. For unweighted graphs, CSR
uses two arrays: an edge array to store the edges in sorted order (by source
and then by destination), and a vertex array to store offsets into the edge
array corresponding to the start of each vertex’s neighbor list. The vertex
array saves space: the edge array then only needs to store destinations and
not sources.

In contrast, storing graphs in a CPMA takes only one array. Using a CPMA,
F-Graph stores edges in 64-bit words by representing the source in the upper
32 bits and the destination in the lower 32 bits555 All of the tested graphs
have fewer than $2^{32}$ vertices, so the edges fit in 64-bit words. If there
are more than $2^{32}$ vertices, we can concatenate two 64-bit words to store
each edge.. The start of each vertex’s neighbors is implicit and can be
restored with a search into the underlying CPMA. The delta compression in the
CPMA elides out the source vertex in all edges except for the edges in the
uncompressed PMA leaf heads and the first edge of each vertex.

F-Graph supports batch updates and graph algorithms by adopting the popular
approach of phasing updates and algorithms separately (Ammar et al., 2018;
Busato et al., 2018; Cai et al., 2012; Ediger et al., 2012; Feng et al., 2015;
Green and Bader, 2016; Murray et al., 2016; Sha et al., 2017b; Sengupta and
Song, 2017; Sengupta et al., 2016; Suzumura et al., 2014; Vora et al., 2017;
Winter et al., 2017). It supports batch updates with one writer and therefore
does not use locks.

Finally, F-Graph currently supports unweighted graphs because the CPMA is
currently a key store. F-Graph also currently supports algorithms on
undirected graphs because it is built on a single CPMA, but could be easily
extended to support algorithms on directed graphs with two CPMAs — one for
incoming edges and one for outgoing edges666Since F-Graph stores
source/destination pairs, it can store directed graphs. However, many parallel
graph algorithms require looping over both incoming and outgoing neighbor sets
efficiently.. Many graph algorithms (e.g., all the ones in this paper, among
others) can be run with only the graph topology. Future work includes
extending the CPMA to a key-value store which would allow F-Graph to store
weighted graphs.

#### C-PaC description

C-PaC supports dynamic-graph processing with compressed PaC-trees (one per
vertex) and enables concurrent updates and graph algorithms without locking in
functional mode. Since we are not concurrently performing updates and
algorithms, we use C-PaC’s in-place unweighted mode for a fair comparison.

#### Systems setup

We used the same experimental setup (machine, compilers, parallelization
frameworks, etc.) from Section 6.

All systems run the same algorithms via the Ligra interface, which is based on
the VertexSubset/EdgeMap abstraction (Shun and Blelloch, 2013). Therefore, all
algorithms implemented with C-PaC can be run on top of F-Graph with minor
cosmetic changes (Shun et al., 2016; Dhulipala et al., 2018, 2017).

The VertexSubset in F-Graph has one optimization that helps with some
algorithms. It has a boolean flag which specifies if the subset includes all
of the vertices. If the flag is set, any membership query into the
VertexSubset simply returns true, avoiding a potential lookup (Wheatman and
Burns, 2021).

The CPMA under F-Graph has growing factor $1.2\times$.

#### Datasets

Table 8 lists the graphs used in the evaluation and their sizes. We tested on
real social network graphs and a synthetic graph. We a few social network
graphs of various sizes: the LiveJournal (LJ) (Backstrom et al., 2006), the
Community Orkut (CO)(Yang and Leskovec, 2012), the Twitter (TW) (Beamer et
al., 2015), and Friendster (FS) (Leskovec and Krevl, 2014) graphs.
Additionally, we generated a Erdős-Rényi (ER) graph (Erdös and Rényi, 1959)
with $n=10^{7}$ and $p=5\cdot 10^{-6}$. These graphs represent a wide range of
inputs both in skewness and in size.

### Graph algorithms

hgPRhgCChgBChgAveragehg$0$hg$0.5$hg$1$hg$1.5$hg$1$Speedup over C-PaChgC-
PaChgF-Graph Figure 12. Relative speedup of F-Graph over C-PaC on graph
algorithms.
hg$10^{1}$hg$10^{2}$hg$10^{3}$hg$10^{4}$hg$10^{5}$hg$10^{6}$hg$10^{7}$hg$10^{8}$hg$10^{5}$hg$10^{6}$hg$10^{7}$hg$10^{8}$hg$10^{9}$Batch
sizeThroughput (inserts / second)hgF-GraphhgC-PaC Figure 13. Insert throughput
as a function of batch size on the FS graph.

We evaluate the performance of F-Graph and C-PaC on three fundamental graph
algorithms: PageRank777The PR implementation runs for a fixed number (10) of
iterations. (PR), connected components888The CC implementation does not have a
shortcut. (CC), and single-source betweenness centrality (BC). Figure 12 and
Table 9 presents the results of the evaluation. The algorithms are from the
Ligra (Shun and Blelloch, 2013) distribution with minor cosmetic changes. On
average, F-Graph supports graph algorithms $1.25\times$ faster than C-PaC.

F-Graph is optimized for larger graphs and algorithms that perform large scans
of the data such as PageRank. On average, it is $1.5\times$ faster across all
algorithms on the graphs over 1 billion edges. Furthermore, it is about
$1.5\times$ faster on PageRank on all of the tested graphs.

| PR |  | CC |  | BC
---|---|---|---|---|---
Graph | C-PaC | F-Graph | C-PaC/F-Graph |  | C-PaC | F-Graph | C-PaC/F-Graph |  | C-PaC | F-Graph | C-PaC/F-Graph
LJ | 0.18 | 0.14 | 1.32 |  | 0.05 | 0.05 | 0.85 |  | 0.06 | 0.07 | 0.93
CO | 0.39 | 0.28 | 1.41 |  | 0.08 | 0.08 | 0.97 |  | 0.07 | 0.07 | 0.93
ER | 3.42 | 2.27 | 1.51 |  | 0.54 | 0.41 | 1.32 |  | 0.21 | 0.20 | 1.06
TW | 10.77 | 6.86 | 1.57 |  | 2.08 | 1.76 | 1.18 |  | 1.12 | 1.17 | 0.96
FS | 26.47 | 13.69 | 1.93 |  | 5.66 | 3.75 | 1.51 |  | 3.05 | 2.15 | 1.42
Table 9. Running times (seconds) of F-Graph and C-PaC PR, CC, and BC with all
($128$) threads. A number above 1 in the C-PaC/F-Graph column means that
F-Graph was faster.

Traversals in graph kernels can be organized on a continuum depending on how
many long scans they contain, which depends on the order of vertices accessed.
On one extreme, arbitrary-order algorithms such as PR access vertices in any
order and can be cast as a straightforward pass through the data structure. On
the other extreme, topology-order algorithms such as BC access vertices
depending on the graph topology, and are therefore more likely to incur cache
misses by accessing a random vertex’s neighbors. CC is in between arbitrary
order and topology order because it starts with large scans in the beginning
of the algorithm, but converges to smaller scans as fewer vertices remain
under consideration.

Systems with a flat layout such as F-Graph have an advantage when the
algorithm is closer to arbitrary order — they support fast scans of neighbors
because all of the data is stored contiguously. For example, F-Graph is
$1.5\times$ faster than C-PaC on average on PR. In contrast tree-based systems
such as C-PaC incur more cache misses during large scans due to pointer
chasing.

Since F-Graph uses a single edge array in its flat layout, it must incur a
fixed cost to reconstruct the vertex array of offsets in all algorithms
besides PR (because PR accesses all of the edges in each iteration). The
relative cost of building the vertex array in F-Graph compared to the cost of
the algorithm depends on the amount of other work in the algorithm. For
example, building the vertex array in F-Graph takes about $10\%$ of the total
time in BC. The relative cost of building the offset array also depends on the
average degree: a higher average degree corresponds to a smaller overhead
compared to the cost of the algorithm. Finally, although this experiment
rebuilds the vertex array with each run of the algorithm, the vertex array
could be reused across computations (e.g., from different sources) if there
have been no updates.

### Update throughput

F-Graph does not sacrifice updatability for its improved algorithm speed — on
average, F-Graph is $2\times$ faster than C-PaC on batch inserts.

#### Setup

To evaluate insertion throughput, we first insert all edges from the FS graph
(the largest graph we tested on) into F-Graph and C-PaC. We then add a new
batch of directed edges (with potential duplicates) to the existing graph in
both systems. To generate edges for inserts, we sample directed edges from an
RMAT generator (Chakrabarti et al., 2004) (with $a=0.5;b=c=0.1;d=0.3$ to match
the distribution from the PaC-tree paper (Dhulipala et al., 2022)).

#### Discussion

Figure 13 shows that F-Graph achieves faster updates than C-PaC despite the
theoretical dominance of trees over PMAs in terms of point and batch updates.
Specifically, F-Graph supports batch inserts around $2\times$ faster than
C-PaC. Just as in Section 6, F-Graph is faster than C-PaC on batch inserts due
to the CPMA’s cache friendliness. We find that batch-insert throughput in
F-Graph grows with the batch size — for the largest batch size, F-Graph
achieves a throughput of over 400 million inserts per second. We note that the
distribution of inserts is different here than in Section 6. Here we see that
even with a skewed distribution, while traditionally challenging for PMAs, the
batch parallel CPMA achieves good insert throughput due to the work sharing in
the batch insert algorithm.

### Space usage

Finally, let us consider the space usage of F-Graph and C-PaC. Table 10 shows
that F-Graph uses marginally less space than C-PaC because F-Graph collocates
small neighbor sets by using only one array to store all of the data (rather
than two levels of trees for vertices and edges in C-PaC).

Graph | C-PaC | F-Graph | F-Graph/C-PaC
---|---|---|---
LJ | 0.24 | 0.35 | 0.69
CO | 0.73 | 0.73 | 1.00
ER | 3.74 | 3.80 | 0.98
TW | 7.63 | 8.92 | 0.86
FS | 13.21 | 14.99 | 0.88
Table 10. Memory footprint (GiB) of the graphs in F-Graph and C-PaC. A number
below 1 in the C-PaC/F-Graph column means that F-Graph was smaller.

##  8\. Conclusion

This paper optimizes traditional PMAs with parallel batch updates and data
compression. The compressed PMA (CPMA) outperforms compressed trees (PaC-
trees) by about $1.2\times$ on range queries and $3\times$ on parallel batch
updates due to its cache-friendliness. The CPMA uses similar space compared to
compressed PaC-trees and uses $2\times-3\times$ less space compared to
uncompressed representations. Compression enables the CPMA to scale better
with the number of cores compared to the PMA because its smaller size
mitigates memory bandwidth issues with reduced memory traffic.

To further demonstrate the real-world applicability of the CPMA, we introduce
F-Graph, a dynamic-graph-processing system built on a single CPMA, and
compared it to C-PaC, a state-of-the-art dynamic-graph-processing system built
on compressed PaC-trees. We found that F-Graph is $1.2\times$ faster on graph
algorithms, $2\times$ faster on batch updates, and slightly smaller than
C-PaC.

The empirical advantage of the CPMA over compressed PaC-trees demonstrates the
importance of optimizing parallel data structures for the memory subsystem.
Specifically, the CPMA’s array-based layout enables it to take advantage of
the speed of contiguous memory accesses. Despite the theoretical prediction,
the batch-parallel CPMA empirically overcomes the update/scan tradeoff with
compressed PaC-trees due to its locality.

## References

  * (1)
  * Abouelhoda et al. (2004) Mohamed Ibrahim Abouelhoda, Stefan Kurtz, and Enno Ohlebusch. 2004\.  Replacing suffix trees with enhanced suffix arrays.  _Journal of discrete algorithms_ 2, 1 (2004), 53–86.
  * Acar et al. (2019) Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019.  Parallel Batch-Dynamic Graph Connectivity. In _The 31st ACM Symposium on Parallelism in Algorithms and Architectures_ (Phoenix, AZ, USA) _(SPAA ’19)_. Association for Computing Machinery, New York, NY, USA, 381–392.  https://doi.org/10.1145/3323165.3323196
  * Adams (1992) Stephen Adams. 1992\.  _Implementing sets efficiently in a functional language_.  Technical Report CSTR 92-10. University of Southampton.
  * Adams (1993) Stephen Adams. 1993\.  Functional pearls efficient sets—a balancing act.  _Journal of functional programming_ 3, 4 (1993), 553–561.
  * Aggarwal and Vitter (1988) Alok Aggarwal and Jeffrey S. Vitter. 1988.  The input/output complexity of sorting and related problems.  _Commun. ACM_ 31, 9 (Sept. 1988), 1116–1127.
  * Akl and Santoro (1987) Selim G. Akl and Nicola Santoro. 1987.  Optimal Parallel Merging and Sorting Without Memory Conflicts.  _IEEE Trans. Comput._ C-36, 11 (1987), 1367–1369.  https://doi.org/10.1109/TC.1987.5009478
  * Aksenov et al. (2017) Vitaly Aksenov, Vincent Gramoli, Petr Kuznetsov, Anna Malova, and Srivatsan Ravi. 2017.  A concurrency-optimal binary search tree. In _European Conference on Parallel Processing_. Springer, 580–593.
  * Amazon (2022) Amazon. 2022.  Amazon Web Services.  https://aws.amazon.com/.
  * Ammar et al. (2018) Khaled Ammar, Frank McSherry, Semih Salihoglu, and Manas Joglekar. 2018.  Distributed evaluation of subgraph queries using worst-case optimal low-memory dataflows.  _VLDB_ 11, 6 (2018), 691–704.
  * Arbel-Raviv et al. (2018) Maya Arbel-Raviv, Trevor Brown, and Adam Morrison. 2018\.  Getting to the root of concurrent binary search tree performance. In _2018 USENIX Annual Technical Conference (USENIX ATC 18)_. 295–306.
  * Backstrom et al. (2006) Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006.  Group formation in large social networks: membership, growth, and evolution. In _Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining_. 44–54.
  * Barbuzzi et al. (2010) Antonio Barbuzzi, Pietro Michiardi, Ernst Biersack, and Gennaro Boggia. 2010.  Parallel bulk Insertion for large-scale analytics applications. In _Proceedings of the 4th International Workshop on Large Scale Distributed Systems and Middleware_. 27–31.
  * Basin et al. (2020) Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy. 2020.  KiWi: A Key-Value Map for Scalable Real-Time Analytics.  _ACM Trans. Parallel Comput._ 7, 3, Article 16 (jun 2020), 28 pages.  https://doi.org/10.1145/3399718
  * Bayer and McCreight (1972) Rudolf Bayer and Edward M. McCreight. 1972.  Organization and Maintenance of Large Ordered Indexes.  _Acta Informatica_ 1, 3 (1972), 173–189.
  * Beamer et al. (2015) Scott Beamer, Krste Asanović, and David Patterson. 2015\.  The GAP benchmark suite.  _arXiv preprint arXiv:1508.03619_ (2015).
  * Bender et al. (2019) Michael A Bender, Alex Conway, Martín Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara McAllister, Nirjhar Mukherjee, Prashant Pandey, et al. 2019\.  Small refinements to the DAM can have big consequences for data-structure design. In _The 31st ACM Symposium on Parallelism in Algorithms and Architectures_. 265–274.
  * Bender et al. (2000) Michael A Bender, Erik D Demaine, and Martin Farach-Colton. 2000\.  Cache-oblivious B-trees. In _Proceedings 41st Annual Symposium on Foundations of Computer Science_. IEEE, 399–409.
  * Bender et al. (2005) Michael A Bender, Erik D Demaine, and Martin Farach-Colton. 2005\.  Cache-oblivious B-trees.  _SIAM J. Comput._ 35, 2 (2005), 341–358.
  * Bender et al. (2017) Michael A Bender, Jeremy T Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo Montes. 2017.  File maintenance: when in doubt, change the layout!. In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 1503–1522.
  * Blandford et al. (2004) Daniel K Blandford, Guy E Blelloch, and Ian A Kash. 2004\.  An Experimental Analysis of a Compact Graph Representation. In _ALENEX_.
  * Blelloch et al. (2020) Guy E Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020\.  ParlayLib-A toolkit for parallel algorithms on shared-memory multicore machines. In _Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures_. 507–509.
  * Blelloch et al. (2016) Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016\.  Just Join for Parallel Ordered Sets _(SPAA ’16)_. Association for Computing Machinery, New York, NY, USA, 253–264.  https://doi.org/10.1145/2935764.2935768
  * Braginsky and Petrank (2012) Anastasia Braginsky and Erez Petrank. 2012.  A lock-free B+ tree. In _Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures_. 58–67.
  * Bronson et al. (2010) Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010.  A practical concurrent binary search tree.  _ACM Sigplan Notices_ 45, 5 (2010), 257–268.
  * Busato et al. (2018) Federico Busato, Oded Green, Nicola Bombieri, and David A. Bader. 2018.  Hornet: An efficient data structure for dynamic sparse graphs and matrices on GPUs. In _HPEC_. 1–7.
  * Cai et al. (2012) Zhuhua Cai, Dionysios Logothetis, and Georgos Siganos. 2012\.  Facilitating real-time graph mining. In _CloudDB_. ACM, 1–8.
  * Chakrabarti et al. (2004) Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. 2004\.  R-MAT: A recursive model for graph mining. In _SDM_. 442–446.
  * Cooper et al. (2010) Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010\.  Benchmarking cloud serving systems with YCSB. In _Proceedings of the 1st ACM symposium on Cloud computing_. 143–154.
  * Cormen et al. (2009) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009.  _Introduction to Algorithms_ (3rd ed.).  MIT Press.
  * De Leo and Boncz (2019a) Dean De Leo and Peter Boncz. 2019a.  Fast Concurrent Reads and Updates with PMAs _(GRADES-NDA’19)_. ACM, New York, NY, USA, Article 8, 8 pages.  https://doi.org/10.1145/3327964.3328497
  * De Leo and Boncz (2019b) Dean De Leo and Peter Boncz. 2019b.  Packed memory arrays-rewired. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. IEEE, 830–841.
  * De Leo and Boncz (2021) Dean De Leo and Peter Boncz. 2021.  Teseo and the analysis of structural dynamic graphs.  _Proceedings of the VLDB Endowment_ 14, 6 (2021), 1053–1066.
  * Dhulipala et al. (2022) Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun. 2022\.  PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections.  https://doi.org/10.48550/ARXIV.2204.06077
  * Dhulipala et al. (2017) Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2017\.  Julienne: A framework for parallel graph algorithms using work-efficient bucketing. In _SPAA_. 293–304.
  * Dhulipala et al. (2018) Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018\.  Theoretically efficient parallel graph algorithms can be fast and scalable. In _SPAA_. 393–404.
  * Dhulipala et al. (2019) Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2019\.  Low-latency graph streaming using compressed purely-functional trees. In _PLDI_. 918–934.
  * Dhulipala et al. (2020) Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. 2020.  Parallel batch-dynamic graphs: Algorithms and lower bounds. In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 1300–1319.
  * Dhulipala et al. (2021) Laxman Dhulipala, Quanquan C Liu, Julian Shun, and Shangdi Yu. 2021.  Parallel Batch-Dynamic k-Clique Counting. In _Symposium on Algorithmic Principles of Computer Systems (APOCS)_. SIAM, 129–143.
  * Durand et al. (2012) Marie Durand, Bruno Raffin, and François Faure. 2012\.  A packed memory array to keep moving particles sorted. In _9th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS)_. The Eurographics Association, 69–77.
  * Ediger et al. (2012) David Ediger, Robert McColl, Jason Riedy, and David A. Bader. 2012.  Stinger: High performance data structure for streaming graphs. In _HPEC_. 1–5.
  * Ellen et al. (2010) Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010.  Non-blocking binary search trees. In _Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing_. 131–140.
  * Erb et al. (2014) Stephan Erb, Moritz Kobitzsch, and Peter Sanders. 2014\.  Parallel bi-objective shortest paths using weight-balanced b-trees with bulk updates. In _International Symposium on Experimental Algorithms_. Springer, 111–122.
  * Erdös and Rényi (1959) Paul Erdös and Alfréd Rényi. 1959.  On Random Graphs I.  _Publicationes Mathematicae Debrecen_ 6 (1959), 290–297.
  * Fatourou et al. (2019) Panagiota Fatourou, Elias Papavasileiou, and Eric Ruppert. 2019\.  Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries. In _The 31st ACM Symposium on Parallelism in Algorithms and Architectures_ (Phoenix, AZ, USA) _(SPAA ’19)_. Association for Computing Machinery, New York, NY, USA, 275–286.  https://doi.org/10.1145/3323165.3323197
  * Feng et al. (2015) Guoyao Feng, Xiao Meng, and Khaled Ammar. 2015.  DISTINGER: A distributed graph data structure for massive dynamic graph processing. In _BigData_. 1814–1822.
  * Ferragina and Luccio (1994) Paolo Ferragina and Fabrizio Luccio. 1994.  Batch dynamic algorithms for two graph problems. In _International Conference on Parallel Architectures and Languages Europe_. Springer, 713–724.
  * Frias and Singler (2007) Leonor Frias and Johannes Singler. 2007.  Parallelization of bulk operations for STL dictionaries. In _European Conference on Parallel Processing_. Springer, 49–58.
  * Frisken and Perry (2002) Sarah F Frisken and Ronald N Perry. 2002.  Simple and efficient traversal methods for quadtrees and octrees.  _Journal of Graphics Tools_ 7, 3 (2002), 1–11.
  * Gargantini (1982) Irene Gargantini. 1982\.  An effective way to represent quadtrees.  _Commun. ACM_ 25, 12 (1982), 905–910.
  * Green and Bader (2016) Oded Green and David A. Bader. 2016.  cuSTINGER: Supporting dynamic graph algorithms for GPUs. In _HPEC_. 1–6.
  * Grossi and Vitter (2005) Roberto Grossi and Jeffrey Scott Vitter. 2005.  Compressed suffix arrays and suffix trees with applications to text indexing and string matching.  _SIAM J. Comput._ 35, 2 (2005), 378–407.
  * Herlihy et al. (2006) Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. 2006.  A provably correct scalable concurrent skip list. In _Conference On Principles of Distributed Systems (OPODIS). Citeseer_. 103.
  * Holroyd and Mason (1990) Fred C Holroyd and David C Mason. 1990.  Efficient linear quadtree construction algorithm.  _Image and Vision Computing_ 8, 3 (1990), 218–224.
  * Itai et al. (1981) Alon Itai, Alan G. Konheim, and Michael Rodeh. 1981\.  A sparse table implementation of priority queues. In _ICALP_. 417–431.
  * Kim et al. (2010) Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D Nguyen, Tim Kaldewey, Victor W Lee, Scott A Brandt, and Pradeep Dubey. 2010.  FAST: fast architecture sensitive tree search on modern CPUs and GPUs. In _Proceedings of the 2010 ACM SIGMOD International Conference on Management of data_. 339–350.
  * Kim et al. (2003) Dong Kyue Kim, Jeong Seop Sim, Heejin Park, and Kunsoo Park. 2003\.  Linear-time construction of suffix arrays. In _Annual Symposium on Combinatorial Pattern Matching_. Springer, 186–199.
  * Ko and Aluru (2003) Pang Ko and Srinivas Aluru. 2003.  Space efficient linear time construction of suffix arrays. In _Annual Symposium on Combinatorial Pattern Matching_. Springer, 200–210.
  * Kung and Lehman (1980) HT Kung and Philip L Lehman. 1980.  Concurrent manipulation of binary search trees.  _ACM Transactions on Database Systems (TODS)_ 5, 3 (1980), 354–382.
  * Kyrola et al. (2012) Aapo Kyrola, Guy E Blelloch, and Carlos Guestrin. 2012\.  Graphchi: Large-scale graph computation on just a pc. USENIX.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  Available at http://snap.stanford.edu/data.
  * Macko et al. (2015) Peter Macko, Virendra J. Marathe, Daniel W. Margo, and Margo I. Seltzer. 2015.  LLAMA: Efficient graph analytics using large multiversioned arrays. In _ICDE_. 363–374.
  * Manber and Myers (1993) Udi Manber and Gene Myers. 1993.  Suffix arrays: a new method for on-line string searches.  _siam Journal on Computing_ 22, 5 (1993), 935–948.
  * Mao et al. (2012) Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012\.  Cache craftiness for fast multicore key-value storage. In _Proceedings of the 7th ACM european conference on Computer Systems_. 183–196.
  * Murray et al. (2016) Derek G. Murray, Frank McSherry, Michael Isard, Rebecca Isaacs, Paul Barham, and Martin Abadi. 2016\.  Incremental, iterative data processing with timely dataflow.  _Commun. ACM_ 59, 10 (2016), 75–83.
  * Natarajan and Mittal (2014) Aravind Natarajan and Neeraj Mittal. 2014.  Fast concurrent lock-free binary search trees. In _Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming_. 317–328.
  * Nowicki and Onak (2021) Krzysztof Nowicki and Krzysztof Onak. 2021.  Dynamic graph algorithms with batch updates in the massively parallel computation model. In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_. SIAM, 2939–2958.
  * Pandey et al. (2021) Prashant Pandey, Brian Wheatman, Helen Xu, and Aydı n Buluç. 2021.  Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs. In _SIGMOD_. 1372–1385.
  * Pugh (1998) William Pugh. 1998\.  _Concurrent maintenance of skip lists_.  Technical Report.
  * Sengupta and Song (2017) Dipanjan Sengupta and Shuaiwen Leon Song. 2017.  Evograph: On-the-fly efficient mining of evolving graphs on GPU. In _SC_. 97–119.
  * Sengupta et al. (2016) Dipanjan Sengupta, Narayanan Sundaram, Xia Zhu, Theodore L. Willke, Jeffrey Young, Matthew Wolf, and Karsten Schwan. 2016\.  Graphin: An online high performance incremental graph processing framework. In _EuroPar_. 319–333.
  * Sha et al. (2017a) Mo Sha, Yuchen Li, Bingsheng He, and Kian-Lee Tan. 2017a.  Accelerating Dynamic Graph Analytics on GPUs.  _Proc. VLDB Endow._ 11, 1 (Sept. 2017), 107–120.  https://doi.org/10.14778/3151113.3151122
  * Sha et al. (2017b) Mo Sha, Yuchen Li, Bingsheng He, and Kian-Lee Tan. 2017b.  Accelerating dynamic graph analytics on GPUs.  _VLDB_ 11, 1 (2017), 107–120.
  * Shun and Blelloch (2013) Julian Shun and Guy E. Blelloch. 2013.  Ligra: A lightweight graph processing framework for shared memory. In _PPoPP_. 135–146.
  * Shun et al. (2015) Julian Shun, Laxman Dhulipala, and Guy E. Blelloch. 2015\.  Smaller and faster: Parallel processing of compressed graphs with Ligra+. In _DCC_. 403–412.
  * Shun et al. (2016) Julian Shun, Farbod Roosta-Khorasani, Kimon Fountoulakis, and Michael W Mahoney. 2016.  Parallel Local Graph Clustering.  _VLDB_ 9, 12 (2016), 1041–1052.
  * Smith et al. (1997) Steven W Smith et al. 1997\.  The scientist and engineer’s guide to digital signal processing.  (1997).
  * Sun et al. (2018) Yihan Sun, Daniel Ferizovic, and Guy E Belloch. 2018\.  PAM: parallel augmented maps. In _Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_. 290–304.
  * Suzumura et al. (2014) Toyotaro Suzumura, Shunsuke Nishii, and Masaru Ganse. 2014\.  Towards large-scale graph stream processing platform. In _WWW_. 1321–1326.
  * Tinney and Walker (1967) William F. Tinney and John W. Walker. 1967.  Direct solutions of sparse network equations by optimally ordered triangular factorization.  _Proc. IEEE_ 55, 11 (1967), 1801–1809.
  * Toss et al. (2018) Julio Toss, Cicero AL Pahins, Bruno Raffin, and João LD Comba. 2018.  Packed-Memory Quadtree: A cache-oblivious data structure for visual exploration of streaming spatiotemporal big data.  _Computers & Graphics_ 76 (2018), 117–128.
  * Tseng et al. (2019) Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. 2019\.  Batch-parallel euler tour trees. In _2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)_. SIAM, 92–106.
  * Vora et al. (2017) Keval Vora, Rajiv Gupta, and Guoqing Xu. 2017.  Kickstarter: Fast and accurate computations on streaming graphs via trimmed approximations.  _ACM SIGOPS Operating Systems Review_ 51, 2 (2017), 237–251.
  * Wang et al. (2018) Ziqi Wang, Andrew Pavlo, Hyeontaek Lim, Viktor Leis, Huanchen Zhang, Michael Kaminsky, and David G Andersen. 2018.  Building a bw-tree takes more than just buzz words. In _Proceedings of the 2018 International Conference on Management of Data_. 473–488.
  * Wheatman and Burns (2021) Brian Wheatman and Randal Burns. 2021.  Streaming Sparse Graphs using Efficient Dynamic Sets. In _2021 IEEE International Conference on Big Data (Big Data)_. IEEE, 284–294.
  * Wheatman et al. (2023) Brian Wheatman, Randal Burns, Aydı n Buluç, and Helen Xu. 2023.  Optimizing Search Layouts in Packed Memory Arrays. In _ALENEX_.
  * Wheatman and Xu (2018) Brian Wheatman and Helen Xu. 2018.  Packed compressed sparse row: A dynamic graph representation. In _2018 IEEE High Performance extreme Computing Conference (HPEC)_. IEEE, 1–7.
  * Wheatman and Xu (2021) Brian Wheatman and Helen Xu. 2021.  A Parallel Packed Memory Array to Store Dynamic Graphs. In _ALENEX_. 31–45.
  * Willard (1982) Dan E Willard. 1982\.  Maintaining dense sequential files in a dynamic environment. In _Proceedings of the fourteenth annual ACM symposium on Theory of computing_. 114–121.
  * Willard (1986) Dan E Willard. 1986\.  Good worst-case algorithms for inserting and deleting records in dense sequential files. In _Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data_. 251–260.
  * Willard (1992) Dan E Willard. 1992\.  A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time.  _Information and Computation_ 97, 2 (1992), 150–204.
  * Winter et al. (2017) Martin Winter, Rhaleb Zayer, and Markus Steinberger. 2017\.  Autonomous, independent management of dynamic graphs on GPUs. In _HPEC_. 1–7.
  * Witten et al. (1999) Ian H. Witten, Alistair Moffat, and Timothy C. Bell. 1999\.  _Managing Gigabytes (2nd Ed.): Compressing and Indexing Documents and Images_.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
  * Yang and Leskovec (2012) Jaewon Yang and Jure Leskovec. 2012.  Defining and Evaluating Network Communities based on Ground-truth.  _CoRR_ abs/1205.6233 (2012).  arXiv:1205.6233 http://arxiv.org/abs/1205.6233
  * Zhang et al. (2016) Huanchen Zhang, David G Andersen, Andrew Pavlo, Michael Kaminsky, Lin Ma, and Rui Shen. 2016\.  Reducing the storage overhead of main-memory OLTP databases with hybrid indexes. In _Proceedings of the 2016 International Conference on Management of Data_. 1567–1581.