Abstract: In recent years, there has been a great deal of interest in developing effective techniques for ad-hoc search and retrieval in relational databases, document and multimedia databases, scientific information systems, and so on. A popular paradigm for tackling this problem is top-k querying, i.e., the ranking of the results and returning the k results with the highest scores. Numerous variants of the top-k retrieval problem and several algorithms have been introduced in recent years. In this tutorial we shall discuss the top-k problem in detail, especially the fundamental algorithms such as FA and TA, important variants such as algorithms operating under restricted sorted/random access, deterministic and probabilistic approximations, as well as distributed and streaming top-k computations. A significant portion of the tutorial will be focused on applications of these top-k algorithms, especially in the context of the Web services and online databases, multimedia, documents and relational databases.

Bio: Gautam Das is an Associate Professor and Head of the Database Exploration Laboratory (DBXLAB) at the CSE department of the University of Texas at Arlington. Prior to joining UTA in Fall 2004, Dr. Das has held positions at Microsoft Research, Compaq Corporation and the University of Memphis. He graduated with a
B.Tech in computer science from IIT Kanpur, India, and with a PhD in computer science from the University of Wisconsin, Madison. Dr. Das's research interests span data mining, information retrieval, databases, algorithms and computational geometry. He is currently interested in ranking, top-k query processing, and sampling problems in databases, as well as data management problems in P2P and sensor networks, social networks, blogs and web communities. His research has resulted in over 85 papers, many of which have appeared in premier database, data mining and algorithms conferences and journals. Dr. Das has served as Program Co-Chair of COMAD 2008, CIT 2004 and SIGMOD-DMKD 2004, Best Paper Awards Chair of KDD 2006, as well as in program committees of numerous conferences. He has served as a Guest Editor for the ACM TKDD special issue devoted to the best papers of KDD 2006. Dr. Das's research has been supported by grants from National Science Foundation, Office of Naval Research, Microsoft Research, Nokia Research, Cadence Design Systems and Apollo Data Technologies.