Share Email Print

Proceedings Paper

Efficient search scheme for very large image databases
Author(s): Sakti K. Pramanik; Jinhua Li; Jiandong Ruan; Sushil K. Bhattacharjee
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Nearest Neighbor search is a fundamental task in many applications. At present state of the art, approaches to nearest neighbor search are not efficient in high dimensions. In this paper we present an efficient angle based balanced index structure called AB-tree, which uses heuristics to decide whether or not to access a node in the index tree based on the estimated angle and the weight of the node. We have presented the result of AB-tree for up to 64 dimensions, and have shown that the performance of the AB-tree algorithm does not deteriorate when processing nearest neighbor queries as dimension increases. However, it is no longer guaranteed that the entire true K nearest neighbors to a query point will be found. Extensive experiments on synthetic data and real data demonstrate that the search time is improved by a factor of up to 85 times over that of SS-tree in 64 dimension while maintaining 90 percent accuracy. Real data includes color histogram and corner like features in a heterogenous collection of natural images.

Paper Details

Date Published: 20 December 1999
PDF: 12 pages
Proc. SPIE 3964, Internet Imaging, (20 December 1999); doi: 10.1117/12.373479
Show Author Affiliations
Sakti K. Pramanik, Michigan State Univ. (United States)
Jinhua Li, Michigan State Univ. (United States)
Jiandong Ruan, Michigan State Univ. (United States)
Sushil K. Bhattacharjee, Ecole Polytechnique Federale de Lausanne (Switzerland)

Published in SPIE Proceedings Vol. 3964:
Internet Imaging
Giordano B. Beretta; Raimondo Schettini, Editor(s)

© SPIE. Terms of Use
Back to Top