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.
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.