Can I read Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures - SPAA '09 - Finding similar users in social networks on EtoBox?

Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures - SPAA '09 - Finding similar users in social networks by Nisgav, Aviv; Patt-Shamir, Boaz is a scholarly article available to read on EtoBox.

What is Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures - SPAA '09 - Finding similar users in social networks about?

We consider a system where users wish to find similar users. To model similarity, we assume the existence of a set of queries, and two users are deemed similar if their answers to these queries are (mostly) identical: each user has a vector of preferences, and two users are similar if their preference vectors differ in only a few coordinates. The preferences are unknown to the system initially, and the goal of the algorithm is to classify the users into classes of roughly the same preferences with the least possible number of queries presented to any user. We prove nearly matching lower and upper bounds on that problem. Specifically, we present an "anytime" algorithm that maintains a partition of the users, and the quality of the partition improves over time: let n be the number of users. At time T , groups of Õ (n/T ) users with the same preferences will be separated (with high probability) if they differ in sufficiently many queries. We present a lower bound that matches the upper bound, up to a constant factor, for nearly all possible distances between user groups.

Author

Nisgav, Aviv; Patt-Shamir, Boaz

Publisher

ACM Press

Published

2009

Language

EN