Fast approximate search algorithm for nearest neighbor queries in high dimensions

Author

Pramanik, Sakti ; Li, Jinhua

Author_Institution

Dept. of Comput. Sci. & Eng., Michigan State Univ., East Lansing, MI, USA

fYear

1999

fDate

23-26 Mar 1999

Firstpage

251

Abstract

We present a fast approximate nearest neighbor (NN) search index structure called the AB-tree, which uses heuristics to decide whether or not to access a node in the index tree based on the intersecting angle and the weight of the node. The goal of the NN search algorithm presented is to decrease unnecessary node accesses in the search due to overlap among bounding regions in existing index structures. We have observed the following three properties of bounding hyperspheres that motivated the creation of the proposed heuristics for NN search: distance property; radius property; and angle property

Keywords

database indexing; query processing; tree data structures; tree searching; trees (mathematics); AB-tree; NN search algorithm; NN search index structure; angle property; bounding hyperspheres; bounding regions; distance property; fast approximate search algorithm; heuristics; high dimensions; index structures; index tree; intersecting angle; nearest neighbor queries; node accesses; radius property; Ear; Electrical capacitance tomography; Multimedia databases; Nearest neighbor searches; Neural networks; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Engineering, 1999. Proceedings., 15th International Conference on

Conference_Location

Sydney, NSW

ISSN

1063-6382

Print_ISBN

0-7695-0071-4

Type

conf

DOI

10.1109/ICDE.1999.754931

Filename

754931