Indexing Nearest Neighbor Queries

Sammanfattning: In database technology, one very well known problem is K nearest neighbor (KNN). However, the cost of finding a solution of the KNN problem may be expensive with the increase of database size. In order to achieve efficient data mining of large amounts of data, it is important to index high dimensional data to support KNN search. Xtree, an index structure for high dimensional data, was investigated and then integrated into Amos II, an extensible functional Database Management System (DBMS). The result of the integration is AmosXtree, which has showed that the query time for KNN search on high dimensional data, is scale well with both database size and dimensionality. To utilize the functionality of AmosXtree, an example is given on how to define an index structure in searching pictures.