{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/99229"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/99229","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Perfect clustering from pairwise comparisons","abstract":"We consider a pairwise comparisons model with n users and m items. Each user is shown a few pairs of items, and when a pair of items is shown to a user, he or she expresses a preference for one of the items based on a probabilistic model. The goal is to group users into clusters so that users within each cluster have similar preferences. We present an algorithm which clusters all users correctly with high probability using a number of pairwise comparisons which is within a polylog factor of a lower bound.","abstract_html":"We consider a pairwise comparisons model with n users and m items. Each user is shown a few pairs of items, and when a pair of items is shown to a user, he or she expresses a preference for one of the items based on a probabilistic model. The goal is to group users into clusters so that users within each cluster have similar preferences. We present an algorithm which clusters all users correctly with high probability using a number of pairwise comparisons which is within a polylog factor of a lower bound.","abstract_has_math":false,"creators":["Satpathi, Siddhartha"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-03-13T15:25:25Z","date_published":"2018-03-13T15:25:25Z","updated_at":"2026-07-22T22:24:37Z","subjects":["Pairwise comparison","Spectral clustering","Inference","Ranking"],"languages":["en"],"rights":["Copyright 2017 Siddhartha Satpathi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/99229","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Satpathi, Siddhartha"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-03-13T15:25:25Z","2020-03-14T09:15:25Z","2017-12-05","2017-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Pairwise comparison","Spectral clustering","Inference","Ranking"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Siddhartha Satpathi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/99229"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We consider a pairwise comparisons model with n users and m items. Each user is shown a few pairs of items, and when a pair of items is shown to a user, he or she expresses a preference for one of the items based on a probabilistic model. The goal is to group users into clusters so that users within each cluster have similar preferences. We present an algorithm which clusters all users correctly with high probability using a number of pairwise comparisons which is within a polylog factor of a lower bound.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-12-01","The student, Siddhartha Satpathi, accepted the attached license on 2017-12-04 at 16:23.","The student, Siddhartha Satpathi, submitted this Thesis for approval on 2017-12-04 at 17:29.","This Thesis was approved for publication on 2017-12-05 at 10:04.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11839 on 2018-03-13 at 09:56:48","Made available in DSpace on 2018-03-13T15:25:25Z (GMT). No. of bitstreams: 2 SATPATHI-THESIS-2017.pdf: 494917 bytes, checksum: dced9eff5ca92cbf843427a03b7e443e (MD5) LICENSE.txt: 4216 bytes, checksum: 80002025c234f5f3334cf8d665ac5f00 (MD5) Previous issue date: 2017-12-05","Embargo set by: Seth Robbins for item 105192 Lift date: 2020-03-13T15:25:40Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105192 Lift date: 2020-03-13T15:28:52Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 105192 on 2020-03-14T09:15:25Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Perfect clustering from pairwise comparisons"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam"],"dc:creator":["Satpathi, Siddhartha"],"dc:date":["2018-03-13T15:25:25Z","2020-03-14T09:15:25Z","2017-12-05","2017-12"],"dc:description":["We consider a pairwise comparisons model with n users and m items. Each user is shown a few pairs of items, and when a pair of items is shown to a user, he or she expresses a preference for one of the items based on a probabilistic model. The goal is to group users into clusters so that users within each cluster have similar preferences. We present an algorithm which clusters all users correctly with high probability using a number of pairwise comparisons which is within a polylog factor of a lower bound.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2019-12-01","The student, Siddhartha Satpathi, accepted the attached license on 2017-12-04 at 16:23.","The student, Siddhartha Satpathi, submitted this Thesis for approval on 2017-12-04 at 17:29.","This Thesis was approved for publication on 2017-12-05 at 10:04.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11839 on 2018-03-13 at 09:56:48","Made available in DSpace on 2018-03-13T15:25:25Z (GMT). No. of bitstreams: 2 SATPATHI-THESIS-2017.pdf: 494917 bytes, checksum: dced9eff5ca92cbf843427a03b7e443e (MD5) LICENSE.txt: 4216 bytes, checksum: 80002025c234f5f3334cf8d665ac5f00 (MD5) Previous issue date: 2017-12-05","Embargo set by: Seth Robbins for item 105192 Lift date: 2020-03-13T15:25:40Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 105192 Lift date: 2020-03-13T15:28:52Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 105192 on 2020-03-14T09:15:25Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/99229"],"dc:language":["en"],"dc:rights":["Copyright 2017 Siddhartha Satpathi"],"dc:subject":["Pairwise comparison","Spectral clustering","Inference","Ranking"],"dc:title":["Perfect clustering from pairwise comparisons"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:37Z"}