Open Access Open Access  Restricted Access Subscription or Fee Access

BLBTree: an Efficient Index Structure for Fast Search

(*) Corresponding author

Authors' affiliations



Due of its interest in different areas, similarity search in high-dimensional spaces is one of the principal research axes today for CBIR Systems. The properties for high-dimensional data demand some adequate search methods to have a research in optimal time. Due to the curse of dimensionality, search time in the index structure exponentially increases, according the dimension of the descriptor. However, the performances of classical index structures become less than the sequential scan of data in search time when answering exact nearest neighbor queries. To overcome this problematic, two major approaches for high-dimensional data in CBIR systems have been proposed: The first approach permits to speed up the search by using multiple levels of lower bound distances, the second approach exploits the BTree index structure to speed up the search. We propose to combine both techniques to search for large nearest neighbors in a high-dimensional space. We develop a new multidimensional index structure, called BLBTree. In BLBTree, instead of computing the distances in the high-dimensional original space to find the nearest neighbor, lot of candidates are to be rejected based on the lower bound distances: the research in BLBTree does not calculate the distances in the high-dimensional original space to find the nearest neighbor if the lower bounding distance exceeds the threshold, because the distances in the high-dimensional cannot be lower than the distances in the low-dimensional. We note that each object in BLBTree is described by a pyramid structure of histograms, with each histogram representing the lower resolution of the other histogram; due to this property, our index structure is well-suited for high-dimensional and large-scale problems. We have shown that our approach provides interesting and powerful experimental results.
Copyright © 2016 Praise Worthy Prize - All rights reserved.


Bag of Visual Word; High-Dimensional Space; B-Tree; Va-File; Idistance; Pcdistance; EBVW; Blbtree

Full Text:



Boomilingam, T., Subramaniam, M., Review on CBIR Trends and Techniques to Upgrade Image Retrieval, (2014) International Review on Computers and Software (IRECOS), 9 (7), pp. 1227-1240.

A.W.M. Smeulders, M.Worring, S. Santini, A. Gupta, and R. Jain. Content-based image retrieval at the end of the early years. IEEE Transactions on pattern analysis and machine intelligence, 22(12) :1349-1380, 2000.

A.C Carrilero. Les espacesc de representation de la couleur. Technical Report 99 D006, ENST, Paris, 1999.

Rajesh, R., Arif Abdul Rahuman, S., Veerappan, J., CBIR Using Similarity Measure Analysis Based on Region Based Level Set Segmentation, (2014) International Review on Computers and Software (IRECOS), 9 (1), pp. 154-160.

A. Heinrichs, D. Koubaroulis, B. Levienaise-Obadia, P. Rovida, and J. Jolion. Image indexing and content based search using pre-attentive similarities. In IEEE Conference on Image Processing, volume 138. Citeseer, 2000.

D.G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2) :91-110, 2004.

G.J. Burghouts and J.M. Geusebroek. Performance evaluation of local colour invariants. Computer Vision and Image Understanding, 113(1) :48-62, 2009.

K.E.A. van de Sande, T. Gevers, and C.G.M. Snoek. Evaluating color descriptors for object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010.

Y. Ke and R. Sukthankar. PCA-SIFT : A more distinctive representation for local image descriptors. In Proceedings of Computer Vision and Pattern Recognition. IEEE Computer Society, 2004.

K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), pages 1615- 1630, 2005.

H. Bay, T. Tuytelaars, and L.J.V Gool. Surf : Speeded up robust features. In Proceedings of the European Conference on Computer Vision (ECCV), Graz, Austria, pages 404417, 2006.

K.E.A.V. Sande, T. Gevers, and C.G.M. Snoek. Evaluation of color descriptors for object and scene recognition. Computer Vision and Pattern Recognition, pages 1-8, 2008.

Y.G. Jiang, C.W. Ngo, and J. Yang. Towards optimal bag-of-features for object categorization and semantic video retrieval. In CIVR ’07 : Proceedings of the 6th ACM international conference on Image and video retrieval, pages 494-501, 2007.

S. Lazebnik, C. Schmid, and J. Ponce. Beyond bags of features : Spatial pyramid matching for recognizing natural scene categories. In CVPR ’06 : Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 169-2178, 2006.

L. FeiFei and P. Perona. A bayesian hierarchical model for learning natural scene categories. In CVPR’ 05 : Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), pages 524-531, 2005.

J. Sivic and A. Zisserman. Video google : A text retrieval approach to object matching in videos. In Proc. ICCV (2003), vol. 2, pp. 1470-1477, Nice, France, 2003.

G. Csurka, C.R. Dance, L. Fan, J. Willamowski, and C. Bray. Visual categorization with bags of keypoints. In In Workshop on Statistical Learning in Computer Vision, ECCV, 2004.

P.H. Gosselin, M. Cord, and S. Philipp-Foliguet. Combining visual dictionary, kernel based similarity and learning strategy for image category retrieval. CVIU, 2008.

J. B. Macqueen. Some methods for classification and analysis of ultivariate observations. In Procedings of the Fifth Berkeley Symposium on Math, Statistics, and Probability, volume 1, pages 281-297. University of California Press, 1967.

D. Nistfier and H.Stewfienius : Scalable recognition with a vocabulary tree. In: CVPR (2). (2006) 2161-168.

F. Moosmann, W. Triggs, and F. Jurie, Randomized clustering forests for building fast and discriminative visual vocabularies. In Proc. Neural Inform. Process. Syst. Conf., Nov. 2006, pp.1-7.

J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, ”Object retrieval with large vocabularies and fast spatial matching. In Proc. IEEE Conf. Comput. Vision Pattern Recognition, vol. 3613. Jun. 2007, pp. 1575-1589.

T. Tuytelaars and C. Schmid, Vector quantizing feature space with a regular lattice. In Proc. IEEE Int. Conf. Comput. Vision, Oct. 2007, pp. 1-8.

Y. Mu, J. Sun, T. Han, L. Cheong and S. Yan, Randomized locality sensitive vocabularies for bag-of-features model. In Proc. Eur. Conf. Comput. Vision, vol. 6313. 2010, pp. 748-761.

Haridas, K., Thanamani, A., An Efficient Image Clustering and Content Based Image Retrieval Using Fuzzy K Means Clustering Algorithm, (2014) International Review on Computers and Software (IRECOS), 9 (1), pp. 147-153.

Vanisri, D., A Novel Fuzzy Clustering Algorithm Based on K-Means Algorithm, (2014) International Review on Computers and Software (IRECOS), 9 (10), pp. 1731-1735.

A.Bahri, H.Zouaki , Y. Bourass, Robust Method for Codebook Generation Using Embedding Algorithm for Large Image Collections. International Journal of Emerging Sciences, vol 5, issue 1, mars 2015.

V. Gaede and O. G unther. Multidimensional access methods. ACM Computing Surveys, 30(2):170-231, 1998.

C. Bohm, S. Berchtold, and D.A. Keim. Searching in high dimensional spaces : Index structures for improving the performance of multimedia databases. ACM computing surveys, 2001.

R. Weber, H. Schok, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high dimensional space. Proceedings of the 24th VLDB Conference New York, USA, 1998.

Sid-Ahmed Berrani,Approximate search of nearest neighbors with probabilistic control of the accuracy, application to content-based image retrieval, phd thesis Universit´e Rennes 1,, feb 2004

P. Indyk and R. Motwani. Approximate nearest neighbors : Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, pages 604-613, New York, NY, USA, 1998.

S. Berchtold, C. Bohm, and H.-P. Kriegal. The pyramid-technique: towards breaking the curse of dimensionality. In Proceedings of the 1998 ACM SIGMOD international conference on Management of data, SIGMOD ’98, pages 142-153, New York, NY, USA, 1998.

H. V. Jagadish, B. C. Ooi, K.-L. Tan, C.Yu, and R. Zhang. idistance: An adaptive b+-tree based indexing method for nearest neighbor search. ACM Trans. Database Syst., 30(2):364-397, 2005.

J. Cu, Z. An, Y. Guo, and S. Zhou, Efficient nearest neighbor query based on extended B+-tree in high-dimensional space. In Pattern Recognition Letters, 2010.

I.T. Jolliffe, Principal Component Analysis. New York, USA: Springer-verlag, 1986.

C. Yu, B. C. Ooi, K.-L. Tan, and H. V. Jagadish. Indexing the distance: An efficient method to knn processing. In VLDB ’01: Proceedings of the 27th International Conference on Very Large Data Bases, pages 421-430, San Francisco, CA, USA, 2001.

R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indicies. Acta informatica, 1: 173-189, 1972.

J.Z. Wang , J. Li and G. Wiederhold. SIMPLIcity: Semantics sensitive integrated matching for picture libraries. IEEE Transactions on Pattern Analysis and Machine Intelligence, (2001), vol. 23, no. 9, pages 947-963.

S.A. Nene , S.K. Nayar and H. Murase. Columbia object image library (coil-100). Technical Report CUCS-006-96, 1996.

M. J. Huiskes, B. Thomee and M. S. Lew, New trends and ideas in visual concept detection: the MIR flickr retrieval evaluation initiative. In MIR ’10: Proceedings of the 2010 ACMInternational Conference on Multimedia Information Retrieval, ACM Press, New York, pp. 527-536, 2010.

Demidova, L., Sokolova, Y., Nikulchev, E., Use of Fuzzy Clustering Algorithms Ensemble for SVM Classifier Development, (2015) International Review on Modelling and Simulations (IREMOS), 8 (4), pp. 446-457.

Nalini Muruganantham, D., Periasamy, R., Lloyd and Minkowski Based K-Means Clustering for Effective Diagnosis of Heart Disease and Stroke, (2015) International Review on Computers and Software (IRECOS), 10 (6), pp. 573-579.

Tunardi, Y., Suharjito, S., Fuzzy Expert System for Classifying Pests and Diseases of Paddy Using Bee Colony Algorithms, (2016) International Review on Computers and Software (IRECOS), 11 (5), pp. 381-387.

Chandramohan, G., Subramanian, S., An Efficient Hybrid Segmentation Algorithm for Computer Tomography Image Segmentation, (2014) International Review on Computers and Software (IRECOS), 9 (9), pp. 1576-1582.

Lakshmi, M., Prasad, S., Rahman, M., Efficient Speckle Noise Reduction Techniques for Synthetic Aperture Radars in Remote Sensing Applications, (2016) International Review of Aerospace Engineering (IREASE), 9 (4), pp. 114-122.

Hannane, A., Fizazi, H., Metaheuristics and Neural Network for Satellite Images Classification, (2016) International Review of Aerospace Engineering (IREASE), 9 (4), pp. 107-113.

Subrahmanyam, C., Venkata Rao, D., Usha Rani, N., Implementation of No Reference Distortion Patch Features Image Quality Assessment Algorithm Based on Human Visual System, (2014) International Journal on Communications Antenna and Propagation (IRECAP), 4 (5), pp. 195-201.

Udaya Kumar, N., Krishna Rao V., E., Madhavi Latha, M., Multi Directional Wavelet Filter Based Region of Interest Compression for Low Resolution Images, (2015) International Journal on Communications Antenna and Propagation (IRECAP), 5 (2), pp. 54-62.

Latrach, L., Rihem, N., Hanen, H., Gharsallah, A., Parametric and Comparative Studies of Leaky Wave Image NRDG Antenna Designed with the Ordinary Single-Layer and the Double-Layers Rectangular Image NRD Guide, (2016) International Journal on Communications Antenna and Propagation (IRECAP), 6 (2), pp. 108-110.


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2024 Praise Worthy Prize