Colloquium Speaker

Speaker: King-Ip (David) Lin
Division of Computer Science
Department of Math Sciences
University of Memphis
Topic:New index structures for Nearest and Reverse Nearest Neighbor queries
Date:Thursday, February 8, 2001
Time:11:00 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


Nowadays there is a growing need for database to handle spatial and multi-dimensional data effectively. These kind of data are typically represented by points in a multi-dimensional space. Thus effective and efficient index structures are required to answer queries on them.

In this talk I am going to talk about two types of queries on these kinds of data and propose index structures to deal with them effectively. One is the nearest neighbor problem which is typically use in similarity searching, web searching etc. The other is the reverse nearest neighbor problem, which find many uses in Web content delivery and geographical information systems. I will describe two index structures (the ANN-tree and the RdNN-tree) to handle the problem. I will also talk about interesting relationship between the two problems.