Keynote Speech 1: Similarity Search in High-Dimensional Datasets

The problem of finding "similar" multimedia objects is a central one, and a popular approach is to represent objects as vectors in a high-dimensional space, and to build a spatial index over a collection of such vectors in order to retrieve the "nearest neighbors" of a query object. There are some fundamental assumptions involved here. First, that the user's notion of similarity can be captured by distance in the space that the vectors are embedded, and second, that nearest neighbors can be efficiently retrieved. In this talk, we discuss these assumptions, based on our experience with the PiQ image database project, carried out at the University of Wisconsin-Madison, and some subsequent work.

We will first present a brief overview of the PiQ system and its goal of identifying the DBMS infrastructure required to support image databases, and discuss the role of similarity and nearest-neighbor queries in content-based querying. Next, we consider when the notion of "nearest neighbor" is well-defined in high-dimensional spaces, and when efficient indexing is feasible. The goal is not to suggest that indexing high-dimensional data is impossible, although our results here are mainly negative. Rather, we seek to identify the conditions under which effective indexing and retrieval techniques are feasible, and to identify the key difficulties that must be overcome. Finally, we present some indexing techniques to retrieve nearest neighbors under appropriate conditions, highlighting the role played by redundancy and approximation.

Keynote Speaker: Raghu Ramakrishnan

Raghu Ramakrishnan is Professor of Computer Sciences at the University of Wisconsin-Madison, and was founder and CTO of QUIQ, a company that pioneered collaborative customer support (acquired by Kanisa). His research is in the area of database systems, with a focus on data retrieval, analysis, and mining. His earlier projects have spanned deductive databases, data integration, and content-based retrieval, and produced several influential results, many of which have found their way into the SQL standard and commercial database systems.

He is on the Board of Trustees of the VLDB Endowment, an associate editor of ACM Transactions on Database Systems, and was previously editor-in-chief of the Journal of Data Mining and Knowledge Discovery and the Database area editor of the Journal of Logic Programming. Dr. Ramakrishnan is a Fellow of the Association for Computing Machinery (ACM), and has received several awards, including a Packard Foundation Fellowship, NSF Presidential Young Investigator Award, and an ACM SIGMOD Contributions Award. He has authored over 100 technical papers and written the widely-used text "Database Management Systems" (WCB/McGraw-Hill), now in its third edition (with J. Gehrke).

Keynote Speaker: Jonathan Goldstein

Jonathan Goldstein is a Researcher in the Database Group at Microsoft Research, where he has focused on similarity searching and database query optimization. Prior to working at Microsoft Research, he completed his Ph.D. at the University of Wisconsin - Madison, where his research focused on multidimensional indexing, compression, and similarity searching. A special focus of his similarity searching work involves understanding the consequences of employing approximation and space/time tradeoffs to help cope with the performance aspects of the curse of dimensionality.

Keynote Speaker: Uri Shaft

From 1993 to 1999 Uri Shaft studied for Ph.D. in University of Wisconsin-Madison, advised by Raghu Ramakrishnan. The research included two distinct issues: database support for image queries, and nearest neighbors indexing theory for high dimensional data. Uri Shaft still researches the high dimensional data topic. From 1999 to 2002 he was one of the architects of Quiq Inc., developing a hybrid database system that included capabilities of information retrieval as well as relational databases. Since 2002, Uri Shaft has been a member of Oracle's manageability team, developing tools for automatic performce diagnostics. For decades, computer vision researchers have been trying to extract high level information from images. While the semantics of images is still unreachable from the signal in most real cases, users would like to express requests to image data bases using high-level queries. This gap between the user needs and the image processing capabilities will limit the use of image databases in the near to mid term future.