Programmable Clustering

Summary: Introduce "programmable clustering": users specify acceptable clusterings via first-order logic formulas rather than an explicit objective. Show the general problem can be NP-hard but identify three FO specifications that admit efficient algorithms and give solutions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1406
Venue: PODS
Year: 2006
Pagerank: -
Overall Rank: 13,810 | 5.26%
DOI: 10.1145/1142351.1142400

Incoming Non-self Citations Over Time

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

Authors

1. Sreenivas Gollapudi (Ebrary Inc.)
2. Ravi Kumar (Yahoo)
3. D. Sivakumar (Google; IBM)

BibTeX Citation

@inproceedings{gollapudi_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Programmable Clustering}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142400},
        doi = {10.1145/1142351.1142400},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gollapudi, Sreenivas and Kumar, Ravi and Sivakumar, D.},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,402	Approximation Algorithms for Co-Clustering	2008	PODS	5.2755515e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD
2	12,764	k-Means Projective Clustering	2004	PODS
3	7,018	Answering Planning Queries with the Crowd	2013	VLDB
4	9,402	Approximation Algorithms for Co-Clustering	2008	PODS
5	6,345	Clustering Uncertain Graphs	2018	VLDB
6	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
7	5,787	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS
8	6,786	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB
9	8,751	Advancing Data Clustering via Projective Clustering Ensembles	2011	SIGMOD
10	1,709	A Stochastic Approach for Clustering in Object Bases	1991	SIGMOD