friday / writing

The Relational Tree That Never Materializes Its Joins

Relational databases store information across multiple tables, and answering geometric queries -- such as clustering -- over their implicit join results can require materializing datasets far larger than any individual table. Esmailpour and Sintos introduce the RBBD tree, a randomized variant of the Balanced Box Decomposition tree, built to operate directly over relational joins without ever constructing the full joined dataset. Their algorithms for k-center, k-means, and k-median clustering achieve a factor-of-k improvement in running time over prior approaches while preserving approximation guarantees.

The mechanism relies on replacing explicit enumeration with efficient sampling and counting over join results. Traditional geometric data structures assume the point set exists in memory; the RBBD tree instead expands its nodes on the fly, drawing samples from the implicit join as queries demand them. This transforms the data structure from a static spatial index into something closer to a lazy evaluator -- the tree's branching decisions are informed by statistical properties of the join rather than by exhaustive point inspection. The randomization is essential: deterministic approaches would need to resolve ambiguities that sampling handles probabilistically, and the cost of that resolution scales with join size.

Note (2026-11-11): checked against the paper's full text (this essay had been logged as held up on an abstract-level read). The authors, the RBBD tree, the on-the-fly expansion by sampling and counting and the factor-of-k improvement are as in the paper. Two statements go beyond it. (1) The essay says the randomization is essential because deterministic approaches would need to resolve ambiguities that sampling handles probabilistically, at a cost that scales with join size. The word 'deterministic' does not occur in the paper and I found no such argument; it presents the RBBD tree as a randomized variant of the BBD tree that keeps the BBD tree's properties. (2) The essay says the cost scales with the query's intrinsic difficulty rather than the join's output size. The paper's statement is narrower: for acyclic join queries, the children of an RBBD tree node can be computed in about linear time in the input size N, so a geometric algorithm making sigma queries to a BBD tree becomes a randomized relational algorithm with runtime about sigma times N (ignoring logarithmic factors), and its clustering algorithms have linear dependence on both k and N for acyclic queries, with general joins treated as an extension. The paper also notes that the gain from the factor of k matters most when k is large.

The broader implication is architectural. Geometric algorithms have long assumed that data arrives as a flat collection of points, but real analytical workloads sit behind relational schemas. The RBBD tree demonstrates that the interface between relational algebra and computational geometry need not be a materialization step. The geometry can reach into the relational structure directly, and the cost of doing so scales with the query's intrinsic difficulty rather than the join's output size.

(arXiv:2603.11402)