Rankings: From similarity distances computation to interactive synchronization

Su, Lili

Permalink

https://hdl.handle.net/2142/49447 Copy

Description

Title

Rankings: From similarity distances computation to interactive synchronization

Author(s)

Su, Lili

Issue Date

2014-05-30T16:44:29Z

Director of Research (if dissertation) or Advisor (if thesis)

Milenkovic, Olgica

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Rankings
• similarity distance
• synchronization
• order-optimal

Abstract

Two problems related to rankings are investigated in this thesis. We first address the problem of computing distances between rankings that take into account similarities between candidates. The need for evaluating such distances is governed by applications as diverse as rank aggregation, bioinformatics, social sciences and data storage. The problem may be summarized as follows. Given two rankings and a positive cost function on transpositions that depends on the similarity of the candidates involved, find a smallest cost sequence of transpositions that converts one ranking into another. Our focus is on costs that may be described via special metric-tree structures and on full rankings modeled as permutations. The presented results include a quadratic-time algorithm for finding a minimum cost trans- form for simple cycles; and a linear time, 5/3-approximation algorithm for permutations that contain multiple cycles. In addition, for permutations with digraphs represented by non-intersecting cycles embedded in trees, we present a polynomial-time transform algorithm. The proposed methods rely on investigating a newly introduced balancing property of cycles embedded in trees, cycle-merging methods, and shortest-path optimization techniques. The second problem considered is the problem of exact synchronization of two rankings at remote locations connected by a two-way channel. Such synchronization problems arise when items in the data are distinguishable, as is the case for playlists, tasklists, crowd votes and recommender systems rankings. Our model accounts for different constraints on the communication throughput of the forward and feedback links, resulting in different anchoring, syndrome and checksum computation strategies. Information editing is assumed of the form of deletions, insertions, block deletions/insertions, translocations and transpositions. The protocols developed under the given model are order-optimal with respect to genie-aided lower bounds.

Graduation Semester

2014-05

Permalink

http://hdl.handle.net/2142/49447

Copyright and License Information

Copyright 2014 Lili Su

Owning Collections