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