Towards Multi-criteria Decision Making in Massive Databases

Speaker: Atish Das Sarma, EBay Research Labs

Abstract:

Extracting a few tuples from a database to support multi-criteria decision making is an important functionality for database systems. This is important in many application domains where the end-users are more interested in the most important query answers in a potentially massive answer space. In this setting, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users quickly find the most desired point. For example, the user might want to find a hotel with the best price-rating combination out of hundreds of hotels or a car that has a high miles per gallon and a high horse power. In this talk, I will present several different approaches aimed towards an efficient way to support such multi-criteria decision making:

1) Skyline Computation: The skyline query is one classic approach to assist the users. Its computation has been extensively studied earlier. In this talk, I will present an algorithm that is significantly faster than previous algorithms both theoretically and experimentally. The idea is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. 

2) Beyond Skyline: Skyline and its sibling, Top-k, are known to have some drawbacks and there have been several approaches to deal with these drawbacks recently. I will present a few new directions towards this goal. One important direction is the notion of minimum regret ratio which is used to identify the output quality in terms of ``user satisfaction''. The goal is to identify a small number of tuples such that every linear preference function is approximately met.

This talk will be self-contained (no database background will be assumed). The talk is based on joint works with Danupon Nanongkai, Ashwin Lall, Kazuhisa Makino, Jim Xu, and Richard J. Lipton.

Bio: 

Atish Das Sarma is currently a Staff Research Scientist at eBay Research Labs. Prior to his current position, he was a Research Scientist at Google Research. Atish received his Ph.D. degree from Georgia Tech. and undergraduate degree from IIT-Bombay. He has published over 40 research papers and filed over 10 patents. Atish received the Best Paper Award at PODS-2008 and received a Facebook award in 2009 for work done that was named a top-50 fbFund Finalist for most promising upcoming start-up ideas. His works have been featured in New Scientist and MIT Technology Review, and invited to interview at NPR, and several of his papers have been invited to top journals. Atish serves on numerous international program committees. His research publications include those in algorithms (STOC, SICOMP, JACM, TCS), Databases (SIGMOD, VLDB, PODS, ICDE), Data Mining (WSDM, WWW, KDD), and Distributed Computing (PODC, SPAA, DISC, INFOCOM). Atish's current research interests include ranking, large graph algorithms, social network analysis, social media and user behavioral analysis.