Efficient search scheme for very large image databases

Sakti K. Pramanik; Jinhua Li; Jiandong Ruan; Sushil K. Bhattacharjee

doi:10.1117/12.373479

20 December 1999 Efficient search scheme for very large image databases

Sakti K. Pramanik, Jinhua Li, Jiandong Ruan, Sushil K. Bhattacharjee

Proceedings Volume 3964, Internet Imaging; (1999) https://doi.org/10.1117/12.373479
Event: Electronic Imaging, 2000, San Jose, CA, United States

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.

Citation Download Citation

Sakti K. Pramanik, Jinhua Li, Jiandong Ruan, and Sushil K. Bhattacharjee "Efficient search scheme for very large image databases", Proc. SPIE 3964, Internet Imaging, (20 December 1999); https://doi.org/10.1117/12.373479

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available