Faster Relational Algorithms Using Geometric Data Structures
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-27
DOI: 10.1145/3801898 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Aryan Esmailpour und 1 weiteren Autor:innen. Die Arbeit nennt 59 Literaturangaben. Gefördert von: NSF.
Abstract (Originalsprache)
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.
Förderung
- NSF
Zitieren
APA
Esmailpour, A., & Sintos, S. (2026). Faster Relational Algorithms Using Geometric Data Structures. Proceedings of the ACM on Management of Data, 4(2), 1-27. https://doi.org/10.1145/3801898
Vancouver
Esmailpour A, Sintos S. Faster Relational Algorithms Using Geometric Data Structures. Proceedings of the ACM on Management of Data. 2026;4(2):1-27. doi:10.1145/3801898
BibTeX
@article{Esmailpour2026,
author = {Esmailpour, Aryan and Sintos, Stavros},
title = {Faster Relational Algorithms Using Geometric Data Structures},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--27},
doi = {10.1145/3801898}
}
EUVIMED