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

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.

Authors:

• Mounira Taileb
• Sami Touati

Keywords:

• High-dimensional indexing
• k-nearest neighborssearch.

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.