Eastern Great Lakes Theory Workshop Talk

Regret-Minimizing Representative Databases

Ashwin Lall, Denison University

Saturday, October 9, 2:30-3:30pm

ABSTRACT

In this talk we will motivate and describe the k-representative regret minimization query (k-regret) as an operation to support multi-criteria decision making. Like top-k, the k-regret query assumes that users have some utility or scoring functions; however, it never asks the users to provide such functions. Like skyline, it filters out a set of interesting points from a potentially large database based on the users~R criteria; however, it never overwhelms the users by outputting too many tuples. In particular, for any number k and any class of utility functions, the k-regret query outputs k tuples from the database and tries to minimize the maximum regret ratio. This captures how disappointed a user could be had she seen k representative tuples instead of the whole database. We focus on the class of linear utility functions, which is widely applicable.

The first challenge of this approach is that it is not clear if the maximum regret ratio would be small, or even bounded. We will answer this question affirmatively by proving that the maximum regret ratio can be bounded and, surprisingly, that this bound is independent of the database size. We will also present a lower bound for the problem. The talk will be concluded with a number of open problems related to the k-regret operation.

This is joint work with Danupon Nanongkai, Atish Das Sarma, Richard Lipton, and Jim Xu. It recently appeared in VLDB 2010.

Speaker Bio

Ashwin Lall is an Assistant Professor in the Department of Mathematics and Computer Science at Denison University. In 2008 he received his Ph.D. at the University of Rochester where he was a Sproull Fellow. He recently completed a postdoc at the Georgia Institute of Technology with Prof. Jim Xu. His research interests are in data streaming algorithms with applications in networking, databases, and natural language processing.

< Schedule < EaGL-III homepage