NOHIS-Tree: High-Dimensional Index Structure for Similarity Search

Authors: Mounira Taileb, Sami Touati

Abstract:

In Content-Based Image Retrieval systems it is important to use an efficient indexing technique in order to perform and accelerate the search in huge databases. The used indexing technique should also support the high dimensions of image features. In this paper we present the hierarchical index NOHIS-tree (Non Overlapping Hierarchical Index Structure) when we scale up to very large databases. We also present a study of the influence of clustering on search time. The performance test results show that NOHIS-tree performs better than SR-tree. Tests also show that NOHIS-tree keeps its performances in high dimensional spaces. We include the performance test that try to determine the number of clusters in NOHIS-tree to have the best search time.

Keywords: High-dimensional indexing, k-nearest neighborssearch.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335466

References:

[1] C. Faloutsos, "Searching Multimedia Databases by Content". Kluwer Academic Publishers, 1996.
[2] R. Bellman, "Adaptive Control Process: A Guided Tour". Princeton University Press, 1961.
[3] N. Bouteldja, V. Gouet-Brunet and M. Scholl, "Evaluation of strategies for multiple sphere queries with local image descriptors". IS&T/SPIE Conference on Multimedia Content Analysis, Management and Retrieval, San Jose CA, USA, 2006.
[4] A. Guttman. "R-trees: A dynamic index structure for spatial searching". In Proceedings of the ACM SIGMOD International Conference on Management of data, Boston, Masachussets, USA, pages 47-57. 1984.
[5] T. Zhang, R. Ramakrishnan, M. Linvy, "Birch: An efficient data clustering method for very large databases". In Proceedings of the ACM SIGMOD International Conference on Management of Data, Montreal, Canada, pp.103-114, 1996.
[6] N. Beckman, H.P.Kriegel, R. Schneider, & B. Seeger, (1990). "The R*- tree: An efficient and robust access method for points and rectangles". In Proceeding of the ACM SIGMOD International Conference on Management of Data, Atlantic City, New Jersey, USA, pp. 322-331, 1990.
[7] S. Bertchold, D.A. Keim, H.P. Kriegel, "The X-tree: An index structure for hight-dimentional data". In Proceeding of the 22nd Internatioanl Conference on Very Large Data Bases, Mumbai (Bombay), India, pp. 28-39, 1996.
[8] D.A. White and R. Jain, "Similarity Indexing with the SS-Tree". In Proceeding of the 12th Int-l Conf Data Eng., pp. 516-523, 1996.
[9] N. Katayama, S. Satoh. "The SR-tree : An index structure for highdimensional nearest neighbor queries". In Proceeding of the ACM SIGMOD, International Conference on Management of Data, Tuscon, Arizona, USA, pages 369-380. 1997.
[10] J.T. Robinson, "The k-d-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes," Proc. ACM SIGMOD Int-l Conf. Management of Data, pp. 10-18, Apr. 1981.
[11] D.B. Lomet and B. Salzberg, "The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance," ACM Trans. Database Systems, vol. 15, no. 4, pp. 625-658, 1990.
[12] A. Henrich, "The LSDh-Tree: An Access Structure for Feature Vectors". Proc. 14th Int-l Conf. Data Eng., pp. 362-369, 1998.
[13] J. Bentley, "Multidimensional Binary Search Trees Used for Associative Searching," Comm. ACM, vol. 18, no. 9, pp. 509- 517, 1975.
[14] M. Taileb, S. Lamrous and S. Touati, "Non Overlapping Hierarchical Index Struture", International Journal of Computer Science, vol. 3 no. 1, pp. 29-35, 2008.
[15] D. L. Boley, "Principal Direction Divisive Partitioning", Data Mining and Knowledge Discovery 2(4):325-344, 1998.
[16] S. Savaresi, D. L. Boley, S. Bittanti, G. Gazzaniga. "Choosing the cluster to split in bisecting divisive clustering algorithms". CSE Report TR-00-055, University of Minnesota, 2000.
[17] N. Roussopoulos, S. Kelly, F. Vincent. "Nearest Neighbor Queries". In Proceeding of ACM SIGMOD, May 1995.