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 partitioning 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 algorithm to cluster proteins by sequence similarity. This setting nicely fits our model because 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 classification.

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 partitioning 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 algorithm to cluster proteins by sequence similarity. This setting nicely fits our model because 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 classification.}, 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 partitioning 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 algorithm to cluster proteins by sequence similarity. This setting nicely fits our model because 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 classification. %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