{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T07:31:32Z","timestamp":1769931092631,"version":"3.49.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"US-Israel Binational Science Foundation Grant","award":["2022131"],"award-info":[{"award-number":["2022131"]}]},{"name":"NSF","award":["CCF-2223870, IIS-2402823, IIS-2348919"],"award-info":[{"award-number":["CCF-2223870, IIS-2402823, IIS-2348919"]}]},{"name":"Infosys"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>In this paper, we address clustering problems in scenarios where accurate direct access to the full dataset is impractical or impossible. Instead, we leverage oracle-based methods, which are particularly valuable in real-world applications where the data may be noisy, restricted due to privacy concerns or sheer volume. We utilize two oracles, the quadruplet and the distance oracle. The quadruplet oracle is a weaker oracle that only approximately compares the distances of two pairs of vertices. In practice, these oracles can be implemented using crowdsourcing or training classifiers or other predictive models. On the other hand, the distance oracle returns exactly the distance of two vertices, so it is a stronger and more expensive oracle to implement. We consider two noise models for the quadruplet oracle. In the adversarial noise model, if two pairs have similar distances, the response is chosen by an adversary. In the probabilistic noise model, the pair with the smaller distance is returned with a constant probability. We consider a set V of n vertices in a metric space that supports the quadruplet and the distance oracle. For each of the k-center, k-median, and k-means clustering problem on V, we design constant approximation algorithms that perform roughly O(nk) calls to the quadruplet oracle and O(k^2) calls to the distance oracle in both noise models. When the dataset has low intrinsic dimension, we significantly improve the approximation factors of our algorithms by performing a few additional calls to the distance oracle. We also show that for k-median and k-means clustering there is no hope to return any sublinear approximation using only the quadruplet oracle. Finally, we give constant approximation algorithms for estimating the clustering cost induced by any set of k vertices, performing roughly O(nk) calls to the quadruplet oracle and O(k^2) calls to the distance oracle.<\/jats:p>","DOI":"10.1145\/3695830","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-26","source":"Crossref","is-referenced-by-count":1,"title":["k-Clustering with Comparison and Distance Oracles"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2529-4036","authenticated-orcid":false,"given":"Sainyam","family":"Galhotra","sequence":"first","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6610-4404","authenticated-orcid":false,"given":"Rahul","family":"Raychaudhury","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2114-8886","authenticated-orcid":false,"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Chicago, Chicago, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Doubling dimension in real-world graphs. https:\/\/slideplayer.com\/slide\/5331329\/. Accessed: 2024-06-07."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2490670"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467862"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.174"},{"key":"e_1_2_1_5_1","first-page":"40","volume-title":"9th Innovations in Theoretical Computer Science Conference (ITCS","volume":"94","author":"Ailon Nir","year":"2018","unstructured":"Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate clustering with same-cluster queries. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94, page 40. Schloss Dagstuhl--Leibniz- Zentrum fuer Informatik, 2018."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196969"},{"key":"e_1_2_1_8_1","first-page":"3216","volume-title":"Advances in neural information processing systems","author":"Ashtiani Hassan","year":"2016","unstructured":"Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In Advances in neural information processing systems, pages 3216--3224, 2016."},{"key":"e_1_2_1_9_1","first-page":"498","volume-title":"The Thirty Seventh Annual Conference on Learning Theory","author":"Bateni MohammadHossein","year":"2024","unstructured":"MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, and Chen Wang. Metric clustering and mst with strong and weak distance oracles. In The Thirty Seventh Annual Conference on Learning Theory, pages 498--550. PMLR, 2024."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347112"},{"key":"e_1_2_1_11_1","first-page":"12510","volume-title":"Advances in Neural Information Processing Systems","author":"Bressan Marco","year":"2019","unstructured":"Marco Bressan, Nicol\u00f2 Cesa-Bianchi, Andrea Paudice, and Fabio Vitale. Correlation clustering with adaptive similarity queries. In Advances in Neural Information Processing Systems, pages 12510--12519, 2019."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Matteo Ceccarello Andrea Pietracaprina and Geppino Pucci. Solving k-center clustering (with outliers) in mapreduce and streaming almost as accurately as sequentially. PVLDB 12(7).","DOI":"10.14778\/3317315.3317319"},{"key":"e_1_2_1_14_1","first-page":"774","volume-title":"International conference on machine learning","author":"Chatziafratis Vaggos","year":"2018","unstructured":"Vaggos Chatziafratis, Rad Niazadeh, and Moses Charikar. Hierarchical clustering with structural constraints. In International conference on machine learning, pages 774--783. PMLR, 2018."},{"key":"e_1_2_1_15_1","first-page":"6649","volume-title":"Advances in Neural Information Processing Systems","author":"Chien I","year":"2018","unstructured":"I Chien, Chao Pan, and Olgica Milenkovic. Query k-means clustering and the double dixie cup problem. In Advances in Neural Information Processing Systems, pages 6649--6658, 2018."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCC.2019.8732224"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2462357"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_12"},{"key":"e_1_2_1_19_1","volume-title":"Top-k and clustering with noisy comparisons. ACM Transactions on Database Systems (TODS), 39(4):1--39","author":"Davidson Susan","year":"2014","unstructured":"Susan Davidson, Sanjeev Khanna, Tova Milo, and Sudeepa Roy. Top-k and clustering with noisy comparisons. ACM Transactions on Database Systems (TODS), 39(4):1--39, 2014."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684066"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3199672"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175295"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-017-11873-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00683-w"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183755"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526147"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461702.3462558"},{"key":"e_1_2_1_28_1","volume-title":"28th International Symposium on Algorithms and Computation (ISAAC 2017)","author":"Geissmann Barbara","year":"2017","unstructured":"Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with recurrent comparison errors. In 28th International Symposium on Algorithms and Computation (ISAAC 2017), 2017."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09957-5"},{"key":"e_1_2_1_30_1","first-page":"7454","volume-title":"Advances in Neural Information Processing Systems","author":"Ghoshdastidar Debarghya","year":"2019","unstructured":"Debarghya Ghoshdastidar, Micha\u00ebl Perrot, and Ulrike von Luxburg. Foundations of comparison-based hierarchical clustering. In Advances in Neural Information Processing Systems, pages 7454--7464, 2019."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224657"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380045"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276312"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213880"},{"key":"e_1_2_1_36_1","unstructured":"Sariel Har-Peled. Quick sort with high probability."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959883"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_2_1_39_1","first-page":"1957","volume-title":"Conference on Learning Theory","author":"Hopkins Max","year":"2020","unstructured":"Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerant, reliable active classification with comparison queries. In Conference on Learning Theory, pages 1957--2006. PMLR, 2020."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196977"},{"key":"e_1_2_1_41_1","first-page":"10485","volume-title":"Advances in Neural Information Processing Systems","author":"Huleihel Wasim","year":"2019","unstructured":"Wasim Huleihel, Arya Mazumdar, Muriel M\u00e9dard, and Soumyabrata Pal. Same-cluster querying for overlapping clusters. In Advances in Neural Information Processing Systems, pages 10485--10495, 2019."},{"key":"e_1_2_1_42_1","volume-title":"1st Symposium on Foundations of Responsible Computing (FORC 2020)","author":"Ilvento Christina","year":"2020","unstructured":"Christina Ilvento. Metric learning for individual fairness. In 1st Symposium on Foundations of Responsible Computing (FORC 2020), 2020."},{"key":"e_1_2_1_43_1","first-page":"1849","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Kazemi Ehsan","year":"2018","unstructured":"Ehsan Kazemi, Lin Chen, Sanjoy Dasgupta, and Amin Karbasi. Comparison based learning from weak oracles. In International Conference on Artificial Intelligence and Statistics, pages 1849--1858. PMLR, 2018."},{"key":"e_1_2_1_44_1","volume-title":"Relaxed oracles for semi-supervised clustering. arXiv preprint arXiv:1711.07433","author":"Kim Taewan","year":"2017","unstructured":"Taewan Kim and Joydeep Ghosh. Relaxed oracles for semi-supervised clustering. arXiv preprint arXiv:1711.07433, 2017."},{"key":"e_1_2_1_45_1","volume-title":"Semi-supervised active clustering with weak oracles. arXiv preprint arXiv:1709.03202","author":"Kim Taewan","year":"2017","unstructured":"Taewan Kim and Joydeep Ghosh. Semi-supervised active clustering with weak oracles. arXiv preprint arXiv:1709.03202, 2017."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_62"},{"key":"e_1_2_1_47_1","first-page":"3448","volume-title":"International Conference on Machine Learning","author":"Kleindessner Matth\u00e4us","year":"2019","unstructured":"Matth\u00e4us Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In International Conference on Machine Learning, pages 3448--3457, 2019."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035953"},{"key":"e_1_2_1_49_1","first-page":"5788","volume-title":"Advances in Neural Information Processing Systems","author":"Mazumdar Arya","year":"2017","unstructured":"Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems, pages 5788--5799, 2017."},{"key":"e_1_2_1_50_1","first-page":"4682","volume-title":"Advances in Neural Information Processing Systems","author":"Mazumdar Arya","year":"2017","unstructured":"Arya Mazumdar and Barna Saha. Query complexity of clustering with side information. In Advances in Neural Information Processing Systems, pages 4682--4693, 2017."},{"key":"e_1_2_1_51_1","first-page":"344","volume-title":"UAI '02, Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence","author":"Mettu Ramgopal R.","year":"2002","unstructured":"Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. In Adnan Darwiche and Nir Friedman, editors, UAI '02, Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence, pages 344--351. Morgan Kaufmann, 2002."},{"key":"e_1_2_1_52_1","first-page":"170","volume-title":"Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies","volume":"1","author":"Eugene Ng TS","year":"2002","unstructured":"TS Eugene Ng and Hui Zhang. Predicting internet network distance with coordinates-based approaches. In Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 170--179. IEEE, 2002."},{"key":"e_1_2_1_53_1","first-page":"25","volume-title":"WebDB","author":"Polychronopoulos Vassilis","year":"2013","unstructured":"Vassilis Polychronopoulos, Luca De Alfaro, James Davis, Hector Garcia-Molina, and Neoklis Polyzotis. Human-powered top-k lists. In WebDB, pages 25--30, 2013."},{"key":"e_1_2_1_54_1","volume-title":"9th International Conference on Learning Representations, ICLR 2021","author":"Pope Phillip","year":"2021","unstructured":"Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3--7, 2021, 2021."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature21054"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104482.3104567"},{"key":"e_1_2_1_57_1","volume-title":"A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319--2323","author":"Tenenbaum Joshua B","year":"2000","unstructured":"Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319--2323, 2000."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.148"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187969"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582139"},{"key":"e_1_2_1_62_1","first-page":"289","volume-title":"31st InternationalWorkshop, IWOCA 2020, Bordeaux, France, June 8--10, 2020","author":"Verdugo Victor","unstructured":"Victor Verdugo. Skyline computation with noisy comparisons. In Combinatorial Algorithms: 31st InternationalWorkshop, IWOCA 2020, Bordeaux, France, June 8--10, 2020, Proceedings, page 289. Springer."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.collaboratecom.2011.247162"},{"key":"e_1_2_1_65_1","volume-title":"3rd Workshop on Online Social Networks (WOSN 2010)","author":"Zhao Xiaohan","year":"2010","unstructured":"Xiaohan Zhao and Haitao Zheng. Orion: shortest path estimation for large social graphs. In 3rd Workshop on Online Social Networks (WOSN 2010), 2010."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695830","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:29:51Z","timestamp":1755916191000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695830"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":65,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695830"],"URL":"https:\/\/doi.org\/10.1145\/3695830","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}