Princeton University

School of Engineering & Applied Science

Efficient and Scalable Top-K Ranking

Changho Suh, Korea Advanced Institute of Science and Technology
E-Quad, B205
Tuesday, September 29, 2015 - 4:30pm to 5:30pm

Abstract: Ranking is one of the fundamental problems that has proved crucial in a wide spectrum of contexts: social choice, sports competitions, web search, recommendation systems, to name a few. PageRank, the backbone of Google’s search engine, is perhaps the most popular ranking paradigm, but is facing a challenge in the big data era: the vast number of pages on the web makes the ranking problem computationally challenging; hence, PageRank often serves only as an offline algorithm.

To address the challenge, we take two disruptive innovations in our approach. First of all, we focus on identifying only a few significant items, say top-K ranked items, among the huge number of the entire items. Second, we make good use of distributed computing systems to facilitate large-scale information processing. Taking these approaches, we aim to develop an efficient and scalable ranking scheme that achieves the best ranking accuracy given partial measurements of data, and that runs in real time.

In this talk, I will present some of our recent progress towards achieving the goal: (1) characterizing the fundamental limits on the sample size required for identifying the top-K ranked items; (2) developing a computationally efficient algorithm that can achieve the limits; (3) implementing our algorithm on a distributed computing framework, thus offering enhanced scalability. Specifically we consider a prominent pairwise measurement model in which measurements are of the pairwise information type: movie A is preferred over movie B; player A defeats player B.

This is joint work with Dr. Yuxin Chen, Dr. Ioannis Mitliagkas, Sunghyun Kim, and Minje Jang.

Bio: Changho Suh is an Ewon Assistant Professor in the Department of Electrical Engineering at Korea Advanced Institute of Science and Technology (KAIST) since 2012. He received the B.S. and M.S. degrees in Electrical Engineering from KAIST in 2000 and 2002 respectively, and the Ph.D. degree in Electrical Engineering and Computer Sciences from UC-Berkeley in 2011. From 2011 to 2012, he was a postdoctoral associate at the Research Laboratory of Electronics in MIT. From 2002 to 2006, he had been with the Telecommunication R&D Center, Samsung Electronics.
Dr. Suh received the 2013 Stephen O. Rice Prize from the IEEE Communications Society, the David J. Sakrison Memorial Prize (top research award in the Department) from the UC-Berkeley EECS Department in 2011, and the Best Student Paper Award of the IEEE International Symposium on Information Theory in 2009. He was also awarded the Vodafone U.S. Foundation Fellowship in 2006 and 2007, and the Kwanjeong Educational Foundation Fellowship in 2009.