Efficient clustering with limited distance information

Konstantin Voevodski, Maria-Florina Balcan, Heiko Roeglin, Shang-Hua Teng, Yu Xia
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:631-639, 2010.

Abstract

Given a point set S and an unknown metric d on S, we study the problem of efficiently par- titioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s $\in$S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. We use our al- gorithm to cluster proteins by sequence sim- ilarity. This setting nicely fits our model be- cause we can use a fast sequence database search program to query a sequence against an entire dataset. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual clas- sification.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-voevodski10a, title = {Efficient clustering with limited distance information}, author = {Voevodski, Konstantin and Balcan, Maria-Florina and Roeglin, Heiko and Teng, Shang-Hua and Xia, Yu}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {631--639}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/voevodski10a/voevodski10a.pdf}, url = {https://proceedings.mlr.press/r8/voevodski10a.html}, abstract = {Given a point set S and an unknown metric d on S, we study the problem of efficiently par- titioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s $\in$S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. We use our al- gorithm to cluster proteins by sequence sim- ilarity. This setting nicely fits our model be- cause we can use a fast sequence database search program to query a sequence against an entire dataset. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual clas- sification.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient clustering with limited distance information %A Konstantin Voevodski %A Maria-Florina Balcan %A Heiko Roeglin %A Shang-Hua Teng %A Yu Xia %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-voevodski10a %I PMLR %P 631--639 %U https://proceedings.mlr.press/r8/voevodski10a.html %V R8 %X Given a point set S and an unknown metric d on S, we study the problem of efficiently par- titioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s $\in$S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. We use our al- gorithm to cluster proteins by sequence sim- ilarity. This setting nicely fits our model be- cause we can use a fast sequence database search program to query a sequence against an entire dataset. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual clas- sification. %Z Reissued by PMLR on 04 October 2026.
APA
Voevodski, K., Balcan, M., Roeglin, H., Teng, S. & Xia, Y.. (2010). Efficient clustering with limited distance information. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:631-639 Available from https://proceedings.mlr.press/r8/voevodski10a.html. Reissued by PMLR on 04 October 2026.

Related Material