Persistent Union-Find, in depth: path-copied arrays, union by rank without compression, timestamped partial persistence and the Conchon-Filliatre design

Grades of persistence

Persistence comes in grades. A partially persistent structure lets you query any past version but only update the newest, so the versions form a line. A fully persistent structure lets you update any version, so the versions form a tree. Confluent persistence also merges two versions into one, which union-find rarely needs. A weaker, very practical grade is backtracking (sometimes called semi-persistence): you may return to an older version and continue from there, after which the abandoned newer versions are not used again. Union-find with rollback serves exactly that case with an undo log and no extra memory per version.

Pick the weakest grade your access pattern allows, because each step up costs time or memory. A depth-first search over choices is backtracking. Answering "were these two connected at time t" over a log of edge insertions is partial. A search that keeps a frontier of states and expands whichever is most promising, as in best-first or beam search, needs full persistence.

Why compression and amortisation break

The standard structure combines union by rank and path compression for an amortised inverse-Ackermann bound. Both halves of that sentence break under persistence. Path compression writes to the structure during a read, so a persistent version would have to copy on every find. And amortised bounds assume an expensive operation pays for cheaper future ones; with persistence, an adversary can return to the one version holding a long path and call find on it a million times, paying full price each time.

Union by rank alone is enough for a worst-case bound. Attach the root of lower rank under the root of higher rank, and increase the rank only when the two are equal. A root of rank r then has at least 2^r nodes in its tree, by induction: rank r arises only from merging two rank r-1 trees, each with at least 2^(r-1) nodes. So no rank exceeds log2 n, and every find follows at most log2 n parent pointers, with no amortisation to exploit. Union by size gives the same bound.

Design: two path-copied arrays

Store parent and rank in two persistent arrays. The simplest persistent array is a balanced binary tree over the indices whose leaves hold the values. Reading index i walks log2 n levels. Writing index i copies the log2 n nodes on the root-to-leaf path and reuses every other subtree, a technique called path copying (the persistent segment tree article uses the same idea for range queries). A version of the union-find is simply a pair of array roots.

Costs follow directly. Find makes at most log2 n hops, each a log2 n array read, so O(log squared n). Union does two finds, one array write to link the roots and at most one to bump a rank, so O(log squared n) time and O(log n) new nodes. A union of two elements already in the same set allocates nothing and returns the same version.

Implementation

class PArray:
    """Immutable array as a balanced binary tree; set() path-copies O(log n) nodes."""
    __slots__ = ("n", "root")
    def __init__(self, n, root):
        self.n, self.root = n, root
    @staticmethod
    def build(values):
        def b(lo, hi):
            if hi - lo == 1:
                return values[lo]
            mid = (lo + hi) // 2
            return (b(lo, mid), b(mid, hi))
        return PArray(len(values), b(0, len(values)))
    def get(self, i):
        node, lo, hi = self.root, 0, self.n
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if i < mid: node, hi = node[0], mid
            else:       node, lo = node[1], mid
        return node
    def set(self, i, v):
        def s(node, lo, hi):
            if hi - lo == 1:
                return v
            mid = (lo + hi) // 2
            if i < mid: return (s(node[0], lo, mid), node[1])
            return (node[0], s(node[1], mid, hi))
        return PArray(self.n, s(self.root, 0, self.n))

class PDSU:
    """Fully persistent union-find: union by rank, no path compression."""
    __slots__ = ("parent", "rank")
    def __init__(self, parent, rank):
        self.parent, self.rank = parent, rank
    @staticmethod
    def make(n):
        return PDSU(PArray.build(list(range(n))), PArray.build([0] * n))
    def find(self, x):
        while True:                         # at most log2(n) hops
            p = self.parent.get(x)
            if p == x:
                return x
            x = p
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return self                     # same version, nothing allocated
        ka, kb = self.rank.get(ra), self.rank.get(rb)
        if ka < kb:
            ra, rb, ka, kb = rb, ra, kb, ka
        parent = self.parent.set(rb, ra)
        rank = self.rank.set(ra, ka + 1) if ka == kb else self.rank
        return PDSU(parent, rank)
    def same(self, a, b):
        return self.find(a) == self.find(b)

Worked example: a branching version tree

v0 = PDSU.make(8)
v1 = v0.union(0, 1)
v2 = v1.union(2, 3)
v3 = v2.union(1, 3)        # {0,1,2,3}
v4 = v2.union(4, 5)        # a branch from v2, not from v3

v3.same(0, 2)   # True
v4.same(0, 2)   # False: v4 never saw union(1, 3)
v4.same(4, 5)   # True
v3.same(4, 5)   # False: the branch did not leak into v3
v0.same(0, 1)   # False: the original is untouched

The version tree here is v0, v1, v2 and then two children of v2. Each version answers according to its own history only. For a stronger check, 2,000 unions were applied each to a randomly chosen earlier version over 50 elements, and 200 of the resulting versions were compared against component labels recomputed from scratch from their own histories; all 6,000 queries agreed.

Measured costs, counting new internal nodes in the parent and rank trees for n random unions on n elements: at n = 1,024 the initial build took 2,046 nodes and each union allocated 11.4 nodes on average (log2 n is 10; unions within one set allocate nothing, and a rank bump adds a second path). At n = 65,536 the figures were 131,070 and 18.3 (log2 n is 16). The deepest find among sampled elements was 4 hops and 7 hops respectively, well under the log2 n ceiling, because random unions rarely build worst-case trees. Budget memory as roughly two to three tree nodes per element plus about 1 to 2 log2 n nodes per union you keep alive.

Partial persistence with timestamps

If unions only ever happen on the newest version and you just need to query the past, you can drop the copying completely. Use union by rank without compression, and record for each node the time it stopped being a root. A node's parent pointer, once set, never changes, so the state at time t is recovered by following parent pointers only while the recorded time is at most t.

class TimedDSU:
    """Partially persistent: unions in time order, queries at any past time t."""
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.when = [float("inf")] * n     # time this node stopped being a root
        self.now = 0
    def _root_at(self, x, t):
        while self.when[x] <= t:           # O(log n) hops: no compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        self.now += 1
        ra, rb = self._root_at(a, self.now), self._root_at(b, self.now)
        if ra != rb:
            if self.rank[ra] < self.rank[rb]:
                ra, rb = rb, ra
            self.parent[rb], self.when[rb] = ra, self.now
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
        return self.now
    def same_at(self, a, b, t):
        return self._root_at(a, t) == self._root_at(b, t)

Each query costs O(log n) and the whole history fits in three arrays, O(n) memory. Because connectivity only grows with time, the earliest moment two elements became connected can be found by binary search on t over same_at. With unions (0,1), (2,3), (4,5), (1,3), (3,5) at times 1 to 5, elements 0 and 2 first connect at time 4 and 0 and 5 at time 5, and same_at(0, 4, 3) is false. The class was checked against brute-force labels at every one of 121 time points of a 120-union history.

The Conchon-Filliatre structure

Sylvain Conchon and Jean-Christophe Filliatre presented "A Persistent Union-Find Data Structure" at the ACM SIGPLAN Workshop on ML in 2007, with a Coq proof of correctness. Their structure keeps both rank and path compression. It stores parent and rank in Baker-style persistent arrays: one version holds the real mutable array, and the others hold chains of differences pointing towards it. Accessing an older version reroots: the differences are reversed so that version owns the real array, making repeated access to the same version O(1). Compression is allowed because it does not change which representative find returns, so it is invisible to every version; this is what the paper calls observational persistence.

The result is as fast as the imperative structure when versions are used in a backtracking pattern, which is how their solver uses it. When a program alternates between distant versions, each switch pays for rerooting the difference chain, so performance depends on the access pattern rather than a clean worst-case bound. Baker-style arrays rely on mutation under the hood, so sharing versions across threads needs care; later ports such as the Haskell persistent-equivalence package note they trade backtracking speed for thread safety.

Choosing a design

Operational guidance

• Start from the access pattern. Log, for a real workload, which versions get queried and which get updated. Most systems that ask for persistence turn out to need rollback or timestamps, both of which are far cheaper.
• Bound the number of live versions. Path-copied versions are garbage collected only when unreachable; a search frontier that keeps every state alive grows memory by about log n nodes per union. Cap the frontier or drop dominated states.
• Use wider nodes in production. Binary nodes waste pointer overhead. Leaves holding 32 or 64 integers, with path copying above them, cut depth and allocation, as in the wide tries described in the persistent data structures article.
• Write find iteratively. Recursion depth is small here, but iterative loops avoid stack issues and interpreter overhead.
• Keep a brute-force oracle in tests. Recompute components from each version's own history and compare; branching bugs are invisible to linear tests.

Failure modes

• Adding path compression to a path-copied DSU. Every find then allocates, and an old version gains nothing because its arrays are immutable.
• Mutating a shared node. One in-place write leaks a union into every version that shares the node, and the bug appears only on branching histories.
• Linking by index instead of rank. Without a rank or size rule, trees grow to depth n and every find becomes linear.
• Using timestamps on a branching history. The timestamp design assumes one timeline; updating an old version silently corrupts newer ones.
• Expecting the Conchon-Filliatre speed for random access. Its efficiency depends on backtracking-style use; jumping between distant versions pays rerooting each time.

What to do next

1. Classify your access pattern as backtracking, partial or fully branching.
2. For backtracking use rollback; for history queries implement TimedDSU and add an earliest-connection query by binary search.
3. For branching search, implement PDSU, then test it against a brute-force oracle over random version trees.
4. Measure allocation per union and peak live versions on real data, and widen leaf nodes if memory dominates.
5. Read the related union-find variants to see which aggregates (size, parity, sums) you can carry into each version.