{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T22:50:37Z","timestamp":1772837437513,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["FP7 ERC grant MoDaS agreement 291071"],"award-info":[{"award-number":["FP7 ERC grant MoDaS agreement 291071"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS 1302212, IIS 0803524, IIS 0911036, IIS 1115188"],"award-info":[{"award-number":["IIS 1302212, IIS 0803524, IIS 0911036, IIS 1115188"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,12,30]]},"abstract":"<jats:p>\n            We study the problems of max\/top-\n            <jats:italic>k<\/jats:italic>\n            and clustering when the comparison operations may be performed by oracles whose answer may be erroneous. Comparisons may either be of\n            <jats:italic>type<\/jats:italic>\n            or of\n            <jats:italic>value<\/jats:italic>\n            : given two data elements, the answer to a type comparison is \u201cyes\u201d if the elements have the same type and therefore belong to the same group (cluster); the answer to a value comparison orders the two data elements. We give efficient algorithms that are guaranteed to achieve correct results with high probability, analyze the cost of these algorithms in terms of the total number of comparisons (i.e., using a fixed-cost model), and show that they are essentially the best possible. We also show that fewer comparisons are needed when values and types are correlated, or when the error model is one in which the error decreases as the distance between the two elements in the sorted order increases. Finally, we examine another important class of cost functions, concave functions, which balances the number of rounds of interaction with the oracle with the number of questions asked of the oracle. Results of this article form an important first step in providing a formal basis for max\/top-\n            <jats:italic>k<\/jats:italic>\n            and clustering queries in crowdsourcing applications, that is, when the oracle is implemented using the crowd. We explain what simplifying assumptions are made in the analysis, what results carry to a generalized crowdsourcing setting, and what extensions are required to support a full-fledged model.\n          <\/jats:p>","DOI":"10.1145\/2684066","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Top-k and Clustering with Noisy Comparisons"],"prefix":"10.1145","volume":"39","author":[{"given":"Susan","family":"Davidson","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tova","family":"Milo","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145204.2145277"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2531602.2531653"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP'13)","author":"Andre Paul","unstructured":"Paul Andre , Haoqi Zhang , Juho Kim , Lydia B. Chilton , Steven P. Dow , and Robert C. Miller . 2013. Community clustering: Leveraging an academic crowd to form coherent conference sessions . In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP'13) . Paul Andre, Haoqi Zhang, Juho Kim, Lydia B. Chilton, Steven P. Dow, and Robert C. Miller. 2013. Community clustering: Leveraging an academic crowd to form coherent conference sessions. In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP'13)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-009-9120-y"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808735"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.122"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102363"},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms 3 rd Ed. The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms 3rd Ed. The MIT Press.","edition":"3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448524"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346806"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00357-008-9004-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482595"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989331"},{"key":"e_1_2_1_17_1","volume-title":"Crowdclustering. In Proceedings of the Neural Information Processing Systems Conference (NIPS'11)","author":"Gomes Ryan","year":"2011","unstructured":"Ryan Gomes , Peter Welinder , Andreas Krause , and Pietro Perona . 2011 . Crowdclustering. In Proceedings of the Neural Information Processing Systems Conference (NIPS'11) . 558--566. Ryan Gomes, Peter Welinder, Andreas Krause, and Pietro Perona. 2011. Crowdclustering. In Proceedings of the Neural Information Processing Systems Conference (NIPS'11). 558--566."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00119934"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213880"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP'13)","author":"Heikinheimo Hannes","year":"2013","unstructured":"Hannes Heikinheimo and Antti Ukkonen . 2013 . The crowd-median algorithm . In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP'13) . Hannes Heikinheimo and Antti Ukkonen. 2013. The crowd-median algorithm. In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP'13)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1982624.1982625"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Neural Information Processing Systems Conference (NIPS'11)","author":"Karger David R.","year":"2011","unstructured":"David R. Karger , Sewoong Oh , and Devavrat Shah . 2011 . Iterative learning for reliable crowdsourcing systems . In Proceedings of the Neural Information Processing Systems Conference (NIPS'11) .1953--1961. David R. Karger, Sewoong Oh, and Devavrat Shah. 2011. Iterative learning for reliable crowdsourcing systems. In Proceedings of the Neural Information Processing Systems Conference (NIPS'11).1953--1961."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 3rd Human Computation Workshop (HCOMP'11)","author":"Lease Matthew","year":"2011","unstructured":"Matthew Lease . 2011 . On quality control and machine learning in crowdsourcing . In Proceedings of the 3rd Human Computation Workshop (HCOMP'11) . AAAI, 97--102. Matthew Lease. 2011. On quality control and machine learning in crowdsourcing. In Proceedings of the 3rd Human Computation Workshop (HCOMP'11). AAAI, 97--102."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.16"},{"key":"e_1_2_1_25_1","unstructured":"Hongwei Li Bin Yu and Dengyong Zhou. 2013. Error rate bounds in crowdsourcing models. http:\/\/arxiv.org\/pdf\/1307.2674.pdf.  Hongwei Li Bin Yu and Dengyong Zhou. 2013. Error rate bounds in crowdsourcing models. http:\/\/arxiv.org\/pdf\/1307.2674.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000016"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336676"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978942.1978975"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047487"},{"key":"e_1_2_1_30_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 1995. Randomized Algorithms . Cambridge University Press , New York . Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press, New York."},{"key":"e_1_2_1_31_1","volume-title":"Deco: Declarative crowdsourcing","author":"Parameswaran Aditya","year":"2011","unstructured":"Aditya Parameswaran , Hyunjung Park , Hector Garcia-Molina , Neoklis Polyzotis , and Jennifer Widom . 2011 . Deco: Declarative crowdsourcing . http:\/\/ilpubs.stanford.edu:8090\/1015\/. Aditya Parameswaran, Hyunjung Park, Hector Garcia-Molina, Neoklis Polyzotis, and Jennifer Widom. 2011. Deco: Declarative crowdsourcing. http:\/\/ilpubs.stanford.edu:8090\/1015\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213878"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216066"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB'13)","author":"Polychronopoulos Vassilis","year":"2013","unstructured":"Vassilis Polychronopoulos , Luca De Alfaro , James Davis , Hector Garcia-Molina , and Neoklis Polyzotis . 2013 . Human-powered top-k lists . In Proceedings of the International Workshop on the Web and Databases (WebDB'13) . 25--30. Vassilis Polychronopoulos, Luca De Alfaro, James Davis, Hector Garcia-Molina, and Neoklis Polyzotis. 2013. Human-powered top-k lists. In Proceedings of the International Workshop on the Web and Databases (WebDB'13). 25--30."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281254"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the NAACL HLT Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk (CSLDAMT'10)","author":"Rashtchian Cyrus","year":"2010","unstructured":"Cyrus Rashtchian , Peter Young , Micah Hodosh , and Julia Hockenmaier . 2010 . Collecting image annotations using amazon's mechanical turk . In Proceedings of the NAACL HLT Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk (CSLDAMT'10) . Association for Computational Linguistics, 139--147. Cyrus Rashtchian, Peter Young, Micah Hodosh, and Julia Hockenmaier. 2010. Collecting image annotations using amazon's mechanical turk. In Proceedings of the NAACL HLT Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk (CSLDAMT'10). Association for Computational Linguistics, 139--147."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126556"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859894"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168655"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204030"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187969"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350263"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536337"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the Neural Information Processing Systems Conference (NIPS'12)","author":"Yi Jinfeng","year":"2012","unstructured":"Jinfeng Yi , Rong Jin , Anil K. Jain , Shaili Jain , and Tianbao Yang . 2012 . Semi-crowdsourced clustering: Generalizing crowd labeling by robust distance metric learning . In Proceedings of the Neural Information Processing Systems Conference (NIPS'12) . 1781--1789. Jinfeng Yi, Rong Jin, Anil K. Jain, Shaili Jain, and Tianbao Yang. 2012. Semi-crowdsourced clustering: Generalizing crowd labeling by robust distance metric learning. In Proceedings of the Neural Information Processing Systems Conference (NIPS'12). 1781--1789."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2684066","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2684066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:45Z","timestamp":1750227225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2684066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2684066"],"URL":"https:\/\/doi.org\/10.1145\/2684066","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,30]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}