University of Illinois Urbana-Champaign

Distances on rankings: from social choice to flash memories

Hassanzadeh, Farzad

Content Files
Farzad_Hassanzadeh.pdf

Permalink

https://hdl.handle.net/2142/44268

Description

Title
Distances on rankings: from social choice to flash memories
Author(s)
Hassanzadeh, Farzad
Issue Date
2013-05-24T22:06:05Z
Director of Research (if dissertation) or Advisor (if thesis)
Milenkovic, Olgica
Doctoral Committee Chair(s)
Milenkovic, Olgica
Committee Member(s)
  • Hajek, Bruce
  • Har-Peled, Sariel
  • Santhanam, Narayana P.
  • Srikant, Rayadurgam
Department of Study
Electrical & Computer Eng
Discipline
Electrical & Computer Engr
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2013-05-24T22:06:05Z
Keyword(s)
  • 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
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.
Graduation Semester
2013-05
Permalink
http://hdl.handle.net/2142/44268
Copyright and License Information
Copyright 2013 Farzad Hassanzadeh

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois