Improved Approximation Algorithms for Relational Clustering

Summary: Relational k-median and k-means clustering without join materialization. Relational k-median: first efficient relative-approximation; relational k-means: improved (1+ε)γ-approximation with faster runtime via fractional hyper-tree width fhw; runtime ~O(k^2 N fhw)+T_γ(k^2). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1949
Venue: PODS
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,924 | 24.01%
DOI: 10.1145/3695831

Incoming Non-self Citations Over Time

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

Authors

1. Aryan Esmailpour
2. Stavros Sintos

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,003	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.1945683e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
834	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016135159
850	Scaling Factorization Machines to Relational Data	2013	VLDB	0.00015955971
1,167	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00013547713
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
2,093	Scalable K-Means++	2012	VLDB	9.5588104e-05
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
5,858	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	5.2997454e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
7,195	Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue	2024	PODS	4.8037242e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,971	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD	4.1945683e-05
5,861	Machine Learning for Databases	2021	VLDB	5.298883e-05
1,595	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00011222442
3,529	Merging the Results of Approximate Match Operations	2004	VLDB	7.0059524e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
1,510	Summarizing Relational Databases	2009	VLDB	0.00011606901
10,923	k-Clustering with Comparison and Distance Oracles	2024	PODS	4.1945683e-05
1,860	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.0001028857
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
10,003	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.1945683e-05