Faster Relational Algorithms Using Geometric Data Structures
Open Access
- 12 May 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-27
Abstract
Optimization tasks over relational data, such as clustering, often suffer from the prohibitive cost of join operations, which are necessary to access the full dataset. While geometric data structures like BBD trees yield fast approximation algorithms in the standard computational setting, their application to relational data remains unclear due to the size of the join output. In this paper, we introduce a framework that leverages geometric insights to design faster algorithms when the data is stored as the results of a join query in a relational database. Our core contribution is the development of the RBBD tree, a randomized variant of the BBD tree tailored for relational settings. Instead of completely constructing the RBBD tree, by leveraging efficient sampling and counting techniques over relational joins, we enable on-the-fly efficient expansion of the RBBD tree, maintaining only the necessary parts. This allows us to simulate geometric query procedures without materializing the join result. As an application, we present algorithms that improve the state-of-the-art for relational k -center/means/median clustering by a factor of k in running time while maintaining the same approximation guarantees. Our method is general and can be applied to various optimization problems in the relational setting.Keywords
All Related Versions
Funding Information
- National Science Foundation (IIS-2348919)
This publication has 35 references indexed in Scilit:
- Efficient Construction of Nonlinear Models over Normalized Data2021
- A Relational Gradient Descent Algorithm For Support Vector Machine Training2021
- Towards Factorized SVM with Gaussian Kernels over Normalized Data2020
- Learning Models over Relational Data: A Brief Tutorial2019
- Nonlinear Models Over Normalized Data2019
- Adaptive Sampling for k-Means Clustering2009
- Computational Geometry2008
- Approximate range searching☆☆A preliminary version of this paper appeared in the Proc. of the 11th Annual ACM Symp. on Computational Geometry, 1995, pp. 172–181.Computational Geometry, 2000
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974