Distributed content collection and rank aggregation

Yang, James Yifei

Permalink

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

Description

Title

Distributed content collection and rank aggregation

Author(s)

Yang, James Yifei

Issue Date

2016-09-13

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

Hajek, Bruce

Doctoral Committee Chair(s)

Hajek, Bruce

Committee Member(s)

• Srikant, Rayadurgam
• Vaidya, Nitin
• Oh, Sewoong
• Chiu, Dah Ming

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

Keyword(s)

• Rank Aggregation
• Score Aggregation
• Mean Field
• Scaling
• Recommendation System
• Peer-to-Peer
• Content Collection
• Independent Crossover Model
• Plackett-Luce
• Zipf
• Clustering
• Multi-Cluster
• Hypothesis Testing

Abstract

Despite the substantial literature on recommendation systems, there have been few studies in distributed settings, where peers provide recommendations locally. Motivated by word of mouth type of social behavior and the advantages of sharing resources, we analyze an online distributed recommendation system with joint content collection and rank aggregation. In such a system, peers contact each other and exchange partial preference information about items, which, for example, could be videos. Peers use recommendation strategies to make decisions with limited knowledge and collect items that are available from the contacted peers. The goal is to maximize the rate at which peers collect their most preferred items. Correlated preferences are modeled as rankings generated by a Plackett-Luce ranking model with Zipf popularity distribution. We establish a performance upper bound and use intuition provided by the bound to design recommendation strategies with a range of complexity. Among these, the direct recommendation rule emerges as being particularly simple and yet effective. The direct recommendation rule is found to be remarkably robust, working well over a broad range of correlation of preferences, initial video availability, storage size, peer arrival pattern, and performance metric. Correlated preferences are modeled as scores generated using an independent crossover model. In order to explore performance for large scale networks, we identify the fluid limit as the number of videos goes to infinity for a mean field limit derived for the number of peers going to infinity under a direct recommendation rule. Simulation results show that the limit analysis accurately predicts performance, not only for the independent crossover model with scores, but also a model with rankings. The performance of the direct recommendation rule is shown to be near optimal for large scale systems. Correlated preferences are modeled as scores generated using a two-stage independent crossover model. We propose four recommendation strategies for heterogeneous preferences. We find that a simple rule, called the nearest stored preference rule, is as effective as the more complex rules. The performance of all the rules is far from a performance upper bound in case the peers in different clusters are nearly independent. We find through simulation that the gap can be nearly closed by using either exponential accumulation of information or neighbor assignments such that most neighbors have similar preferences.

Graduation Semester

2016-12

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2016 James Yang

Owning Collections