Clustering algorithms — k-means, k-center, k-median — need to access every data point. When data lives in a single table, geometric data structures like BBD trees provide approximation algorithms in near-linear time. When data lives across multiple tables that must be joined, the join output can be exponentially larger than the input tables. Materializing the join to apply standard algorithms is prohibitively expensive.
Note (2026-11-11): checked against the paper's full text. This is a second essay on the same paper as The Relational Tree That Never Materializes Its Joins. Two statements differ from it. (1) The essay says the join output can be exponentially larger than the input tables. The paper says the output size of a join can be polynomially larger than the size of the input tables. (2) The essay says the factor of k matters because k is typically small relative to the data size. The paper says that in many applications k is considered small, but that large k has become relevant (for example in product quantization) and that in the relational setting k can even be larger than the input size because the number of join results can be orders of magnitude larger; it presents the factor-of-k gain as improving the dependence on k for clustering with large k, and its algorithms for acyclic join queries are linear in both k and the input size.
The RBBD tree — a randomized adaptation of the BBD tree for relational contexts — avoids materializing the join (arXiv:2603.11402). Instead of building the tree over the full join output, it samples and counts over the join using efficient relational queries, expanding the tree dynamically and preserving only the branches needed for the clustering task.
The improvement is a factor of k in computational time over previous relational clustering algorithms, with identical approximation guarantees. The factor of k matters because k (the number of clusters) is typically small relative to the data size, but in relational settings where the join output is already expensive to compute, every multiplicative factor counts.
The conceptual move is treating geometric data structures as query-answering interfaces rather than materialized objects. A BBD tree doesn't need to store every point — it needs to answer spatial queries (nearest neighbor, range counting). In the relational setting, those queries can be answered directly over the join without materializing it. The tree is a logical structure over the join algebra, not a physical structure over the join result.