Clustering with Set Outliers and Applications in Relational Clustering

Summary: Defines k-center clustering with set outliers—can discard up to z candidate subsets H to model structured noise (faulty sources, corrupted join tuples). Presents first tri-criteria approximations (≤2k centers, ≤2fz sets, constant-factor cost), near-linear geometric algorithms, coresets for f=1, hardness barrier and applications to relational clustering (join-result and input-tuple outliers). (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 2053
Venue: PODS
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,176 | 30.19%
DOI: 10.1145/3767712

Incoming Non-self Citations Over Time

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

Authors

1. Vaishali Surianarayanan (University of California Santa Cruz)
2. Neeraj Kumar (Meta)
3. Stavros Sintos (University of Illinois Chicago)

BibTeX Citation

@inproceedings{surianarayanan_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Clustering with Set Outliers and Applications in Relational Clustering}},
        url = {https://dl.acm.org/doi/10.1145/3767712},
        doi = {10.1145/3767712},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Surianarayanan, Vaishali and Kumar, Neeraj and Sintos, Stavros},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,719	Subset Sampling over Joins	2026	PODS	5.2319816e-05
10,153	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS	5.093636e-05

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
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
1,101	KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing	2015	SIGMOD	0.00012168934
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,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.7407122e-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
11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS	5.093636e-05
11,175	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
2	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
3	9,575	Local Search Methods for k-Means with Outliers	2017	VLDB
4	9,820	How to Design Robust Algorithms using Noisy Comparison Oracle	2021	VLDB
5	693	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB
6	578	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD
7	4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB
8	10,153	Faster Relational Algorithms Using Geometric Data Structures	2026	PODS
9	10,065	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD
10	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS