{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/44268"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/44268","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Distances on rankings: from social choice to flash memories","abstract":"From social choice to statistics to coding theory, rankings are found to be a useful vehicle for storing and presenting information in modern data systems. Often, in order to process the information, an appropriately defined distance on rankings is required or at least helpful. For example, in social choice, the quality of the results of distance-based voting rules depends almost entirely on the chosen distance function; in statistics, distances between rankings are used to measure correlation and to model data; and in coding theory, in the context of rank modulation, designing codes with a given minimum distance is required for preserving data integrity. It is however well-known that conventional distances are not adequate for many applications. Motivated by several problems from different disciplines, including problems in social choice and bioinformatics, we axiomatically introduce two novel classes of distances on rankings to address the shortcomings of conventional distances. In addition, we propose several algorithms for computing or approximating these distances. The algorithms are based on graph-search techniques, Viterbi-type algorithms, and dynamic programming. Furthermore, we present algorithms for rank aggregation using the proposed distances. One algorithm is based on finding a minimum weight bipartite matching and another is a PageRank-type algorithm in which the transition probabilities of a Markov chain model yield the aggregate ranking. In the context of coding theory, we introduce permutation codes in the Ulam metric that were not previously reported in the literature. Compared to known codes, the proposed codes can handle more diverse types of errors, including arbitrary charge-drop errors as well as other errors that affect a single cell, such as read disturb or write disturb errors. We present capacity achieving codes that can correct a constant number of errors and asymptotically good codes that can correct a linear number of errors in the length of the code. Our results also include derivation of the asymptotic capacity of permutation codes in the Ulam metric and simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes, and substitution error-correcting codes.","abstract_html":"From social choice to statistics to coding theory, rankings are found to be a useful vehicle for storing and presenting information in modern data systems. Often, in order to process the information, an appropriately defined distance on rankings is required or at least helpful. For example, in social choice, the quality of the results of distance-based voting rules depends almost entirely on the chosen distance function; in statistics, distances between rankings are used to measure correlation and to model data; and in coding theory, in the context of rank modulation, designing codes with a given minimum distance is required for preserving data integrity. It is however well-known that conventional distances are not adequate for many applications. Motivated by several problems from different disciplines, including problems in social choice and bioinformatics, we axiomatically introduce two novel classes of distances on rankings to address the shortcomings of conventional distances. In addition, we propose several algorithms for computing or approximating these distances. The algorithms are based on graph-search techniques, Viterbi-type algorithms, and dynamic programming. Furthermore, we present algorithms for rank aggregation using the proposed distances. One algorithm is based on finding a minimum weight bipartite matching and another is a PageRank-type algorithm in which the transition probabilities of a Markov chain model yield the aggregate ranking. In the context of coding theory, we introduce permutation codes in the Ulam metric that were not previously reported in the literature. Compared to known codes, the proposed codes can handle more diverse types of errors, including arbitrary charge-drop errors as well as other errors that affect a single cell, such as read disturb or write disturb errors. We present capacity achieving codes that can correct a constant number of errors and asymptotically good codes that can correct a linear number of errors in the length of the code. Our results also include derivation of the asymptotic capacity of permutation codes in the Ulam metric and simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes, and substitution error-correcting codes.","abstract_has_math":false,"creators":["Hassanzadeh, Farzad"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Milenkovic, Olgica","Hajek, Bruce","Har-Peled, Sariel","Santhanam, Narayana P.","Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-05-24T22:06:05Z","date_published":"2013-05-24T22:06:05Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Distance","Rankings","Permutations","Social choice","Flash memories","Kendall tau distance","Weighted Kendall distance","Weighted Transposition distance","Rank aggregation","Information Retrieval","Collaborative filtering","Rank modulation","Ulam distance","error-correcting codes"],"languages":["en"],"rights":["Copyright 2013 Farzad Hassanzadeh"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/44268","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica","Hajek, Bruce","Har-Peled, Sariel","Santhanam, Narayana P.","Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Hassanzadeh, Farzad"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-05-24T22:06:05Z","2013-05"]},{"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":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Distance","Rankings","Permutations","Social choice","Flash memories","Kendall tau distance","Weighted Kendall distance","Weighted Transposition distance","Rank aggregation","Information Retrieval","Collaborative filtering","Rank modulation","Ulam distance","error-correcting codes"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Farzad Hassanzadeh"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/44268"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["From social choice to statistics to coding theory, rankings are found to be a useful vehicle for storing and presenting information in modern data systems. Often, in order to process the information, an appropriately defined distance on rankings is required or at least helpful. For example, in social choice, the quality of the results of distance-based voting rules depends almost entirely on the chosen distance function; in statistics, distances between rankings are used to measure correlation and to model data; and in coding theory, in the context of rank modulation, designing codes with a given minimum distance is required for preserving data integrity. It is however well-known that conventional distances are not adequate for many applications. Motivated by several problems from different disciplines, including problems in social choice and bioinformatics, we axiomatically introduce two novel classes of distances on rankings to address the shortcomings of conventional distances. In addition, we propose several algorithms for computing or approximating these distances. The algorithms are based on graph-search techniques, Viterbi-type algorithms, and dynamic programming. Furthermore, we present algorithms for rank aggregation using the proposed distances. One algorithm is based on finding a minimum weight bipartite matching and another is a PageRank-type algorithm in which the transition probabilities of a Markov chain model yield the aggregate ranking. In the context of coding theory, we introduce permutation codes in the Ulam metric that were not previously reported in the literature. Compared to known codes, the proposed codes can handle more diverse types of errors, including arbitrary charge-drop errors as well as other errors that affect a single cell, such as read disturb or write disturb errors. We present capacity achieving codes that can correct a constant number of errors and asymptotically good codes that can correct a linear number of errors in the length of the code. Our results also include derivation of the asymptotic capacity of permutation codes in the Ulam metric and simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes, and substitution error-correcting codes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-09T15:26:11Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Hassanzadeh_Farzad.pdf: 1499723 bytes, checksum: d3962a6504c8f6bf8f101b84e36557d5 (MD5)","Made available in DSpace on 2013-05-24T22:06:05Z (GMT). No. of bitstreams: 2 Farzad_Hassanzadeh.pdf: 1499723 bytes, checksum: d3962a6504c8f6bf8f101b84e36557d5 (MD5) license.txt: 4068 bytes, checksum: f4e84f06d2dd6c8e5981030cce4cfe10 (MD5)"]},{"key":"dc:title","label":"Title","values":["Distances on rankings: from social choice to flash memories"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica","Hajek, Bruce","Har-Peled, Sariel","Santhanam, Narayana P.","Srikant, Rayadurgam"],"dc:creator":["Hassanzadeh, Farzad"],"dc:date":["2013-05-24T22:06:05Z","2013-05"],"dc:description":["From social choice to statistics to coding theory, rankings are found to be a useful vehicle for storing and presenting information in modern data systems. Often, in order to process the information, an appropriately defined distance on rankings is required or at least helpful. For example, in social choice, the quality of the results of distance-based voting rules depends almost entirely on the chosen distance function; in statistics, distances between rankings are used to measure correlation and to model data; and in coding theory, in the context of rank modulation, designing codes with a given minimum distance is required for preserving data integrity. It is however well-known that conventional distances are not adequate for many applications. Motivated by several problems from different disciplines, including problems in social choice and bioinformatics, we axiomatically introduce two novel classes of distances on rankings to address the shortcomings of conventional distances. In addition, we propose several algorithms for computing or approximating these distances. The algorithms are based on graph-search techniques, Viterbi-type algorithms, and dynamic programming. Furthermore, we present algorithms for rank aggregation using the proposed distances. One algorithm is based on finding a minimum weight bipartite matching and another is a PageRank-type algorithm in which the transition probabilities of a Markov chain model yield the aggregate ranking. In the context of coding theory, we introduce permutation codes in the Ulam metric that were not previously reported in the literature. Compared to known codes, the proposed codes can handle more diverse types of errors, including arbitrary charge-drop errors as well as other errors that affect a single cell, such as read disturb or write disturb errors. We present capacity achieving codes that can correct a constant number of errors and asymptotically good codes that can correct a linear number of errors in the length of the code. Our results also include derivation of the asymptotic capacity of permutation codes in the Ulam metric and simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes, and substitution error-correcting codes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-09T15:26:11Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Hassanzadeh_Farzad.pdf: 1499723 bytes, checksum: d3962a6504c8f6bf8f101b84e36557d5 (MD5)","Made available in DSpace on 2013-05-24T22:06:05Z (GMT). No. of bitstreams: 2 Farzad_Hassanzadeh.pdf: 1499723 bytes, checksum: d3962a6504c8f6bf8f101b84e36557d5 (MD5) license.txt: 4068 bytes, checksum: f4e84f06d2dd6c8e5981030cce4cfe10 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/44268"],"dc:language":["en"],"dc:rights":["Copyright 2013 Farzad Hassanzadeh"],"dc:subject":["Distance","Rankings","Permutations","Social choice","Flash memories","Kendall tau distance","Weighted Kendall distance","Weighted Transposition distance","Rank aggregation","Information Retrieval","Collaborative filtering","Rank modulation","Ulam distance","error-correcting codes"],"dc:title":["Distances on rankings: from social choice to flash memories"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:34Z"}