Files in this item

FilesDescriptionFormat

application/pdf

application/pdfYANG-DISSERTATION-2016.pdf (1MB)
(no description provided)PDF

Description

Title:Distributed content collection and rank aggregation
Author(s):Yang, James Yifei
Director of Research:Hajek, Bruce
Doctoral Committee Chair(s):Hajek, Bruce
Doctoral Committee Member(s):Srikant, Rayadurgam; Vaidya, Nitin; Oh, Sewoong; Chiu, Dah Ming
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Rank Aggregation
Score Aggregation
Mean Field
Scaling
Recommendation System
Peer-to-Peer
Content Collection
Independent Crossover Model
Plackett-Luce
Zipf
Independent Crossover Model
Clustering
Multi-Cluster
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.
Issue Date:2016-09-13
Type:Thesis
URI:http://hdl.handle.net/2142/95281
Rights Information:Copyright 2016 James Yang
Date Available in IDEALS:2017-03-01
Date Deposited:2016-12


This item appears in the following Collection(s)

Item Statistics