Distinguished Lecture - Range Searching and its Relatives: From Answering Questions to Answering Questions

Location: Torgersen 2150
Date: Friday, November 6, 2015
Time: 11:15AM - 12:30PM
This talk is open to the general public.

Dr. Pankaj Agarwal
Duke University


Range searching is a classical problem that has been studied extensively both in computational geometry and databases. Over the last three decades, several sophisticated geometric techniques and data structures (e.g. kd-trees, R-trees, range trees, eps-nets, cuttings) have been proposed for range searching that have had a profound impact on the two fields, much beyond range searching. Despite this tremendous progress on range searching, there is a big gap between theoretical results and the approaches used in practice for this problem, partly because the theoretically best known results are not easy to implement and partly because the goals in practice have shifted.

The first half of the talk reviews recent theoretical results on range searching, discusses a few variants of range searching that have emerged in the last few years, and sketches some of the approaches that are being used in practice. The second half focuses on an on-going interdisciplinary project focused on discerning subtle qualities of claims based on some underlying data, e.g., is a claim ``cherry-picking''? We propose a Query Response Surface (QRS) based framework that models claims based on structured data as parametrized queries. A claim is mapped to a point on the QRS, and often it is a singularity on QRS. A key insight is that we can learn much about a claim by analyzing the singularity. This framework allows us to formulate and tackle a variety of journalistic tasks as computational problems, such as reverse-engineering vague claims, countering questionable claims, and finding high-quality leads from data.


Dr. Agarwal earned his PhD in Computer Science from the Courant Institute of Mathematical Sciences at New York University. He joined Duke University in 1989 where he is now the RJR Nabisco Professor of Computer Science and a Professor of Mathematics. He was the Chair of the Department of Computer Science from 2004 to 2010. His research interests include geometric computing, spatial databases, geographic information systems, sensor networks, and robotics. A Sloan Fellow, an ACM Fellow, and a National Young Investigator, Dr. Agarwal has authored four books and more than 350 research articles. He serves or has served on the editorial boards of a number of journals and on the advisory boards of many institutes and centers.