Faster Relational Algorithms Using Geometric Data Structures

Summary: Introduces RBBD trees, a randomized geometric structure expanded on demand via sampling/counting over joins, avoiding join materialization. Improves relational k-center/means/median algorithms by a factor of k with unchanged approximation guarantees. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 2028
Venue: PODS
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,153 | 30.35%
DOI: 10.1145/3801898

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Aryan Esmailpour (University of Illinois Chicago)
2. Stavros Sintos (University of Illinois Chicago)

BibTeX Citation

@inproceedings{esmailpour_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Faster Relational Algorithms Using Geometric Data Structures}},
        url = {https://dl.acm.org/doi/10.1145/3801898},
        doi = {10.1145/3801898},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Esmailpour, Aryan and Sintos, Stavros},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
536	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.0001693369
715	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00014655327
835	Scaling Factorization Machines to Relational Data	2013	VLDB	0.00013721583
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
2,927	In-Database Learning with Sparse Tensors	2018	PODS	7.9531195e-05
4,781	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	6.5116536e-05
5,918	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	6.0427671e-05
6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.8836116e-05
7,286	Efficient Computation of Quantiles over Joins	2023	PODS	5.655242e-05
8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.3766157e-05
10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	5.093636e-05
11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
2	1,479	Computing Joins Of Relations	1975	SIGMOD
3	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
4	8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
5	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
7	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS
9	1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS
10	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS