An Indexing Approach for Representing Multimedia Objects in High-Dimensional Spaces Based on Expectation Maximization Algorithm

  • Giuseppe Boccignone
  • Vittorio Caggiano
  • Carmine Cesarano
  • Vincenzo Moscato
  • Lucio Sansone
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3665)


In this paper we introduce a new indexing approach to representing multimedia object classes generated by the Expectation Maximization clustering algorithm in a balanced and dynamic tree structure. To this aim the EM algorithm has been modified in order to obtain at each step of its recursive application balanced clusters. In this manner our tree provides a simple and practical solution to index clustered data and support efficient retrieval of the nearest neighbors in high dimensional object spaces.


Expectation Maximization Query Image Range Query Expectation Maximization Algorithm Indexing Approach 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Baeza-Yates, R., Cunto, W., Manber, U., Wu, S.: Proximity matching using Fixed-queries trees. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol. 807, pp. 198–212. Springer, Heidelberg (1994)Google Scholar
  2. 2.
    Banerjee, A., Dhillon, I.S., Ghosh, J., Sra, S.: Clustering on hyperspheres using Expectation Maximization. Technical Report TR-03-07, Department of Computer Sciences, University of Texas (February 2003)Google Scholar
  3. 3.
    Bilmes, J.A.: A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Technical Report, U.C. Berkeley (April 1998)Google Scholar
  4. 4.
    Boccignone, G., Chianese, A., Moscato, V., Picariello, A.: Fovaeted Shot Detection for Video Segmentation. IEEE Trans. on Circuits and Sistems for Video Technology 15(3) (March 2005)Google Scholar
  5. 5.
    Brin, S.: Near neighbor search in large metric spaces. In: Proc. of VLDB 1995, Switzerland, pp. 574–584 (1995)Google Scholar
  6. 6.
    Burkhard, W.A., Keller, R.M.: Some approaches to best-match file searching. Comm. of the ACM 16(4), 230–236 (1973)zbMATHCrossRefGoogle Scholar
  7. 7.
    Celeux, G., Govaert, G.: A classification EM algorithm for clustering and two stochastic versions. Computational Statistics and Data Analysis 14, 315–332 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Chavez, E., Navarro, G., Baeza-Yates, R., Marroquin, J.L.: Searching in Metric Spaces. ACM Computing Surveys (1999)Google Scholar
  9. 9.
    Ciaccia, P., Patella, M., Zezula, P.: M-tree: An efficient Access Method for Similarity Search in Metric Spaces. In: Proc. of 23rd International Conference on VLDB, pp. 426–435 (1997) FQ tree 0..5825 FQ tree (with bag distance) 0.4124Google Scholar
  10. 10.
    Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data. Journal of the Royal Statistical Society 39, 1–38 (1977)zbMATHMathSciNetGoogle Scholar
  11. 11.
    Ganti, V., Ramakrishnan, R., Gehrke, J., Powell, A., French, J.: Clustering large datasets in arbitrary metric spaces. In: The Proceedings of International Conference on Data Engineering (1999)Google Scholar
  12. 12.
    Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice Hall, Englewood Cliffs (1998)Google Scholar
  13. 13.
    Kalantari, I., McDonald, G.: A data structure and an algorithm for the nearest point problem. IEEE Transactions on Software Engineering 9(5) (1983)Google Scholar
  14. 14.
    Neal, R.M., Hinton, G.E.: A view of the EM algorithm that justifies incremental, sparse, and other variants. In: Jordan, M.J. (ed.) Learning in Graphical Models, pp. 355–368. MIT Press, Cambridge (1998)Google Scholar
  15. 15.
    Uhlmann, J.: Satisying general proximity/similarity queries with metric trees. Information Processing Letters 40, 175–179 (1991)zbMATHCrossRefGoogle Scholar
  16. 16.
    Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, January 25-27, pp. 311–321 (1993)Google Scholar
  17. 17.
    Yu, D., Zhang, A.: ClusterTree: Integration of Cluster Representation and Nearest-Neighbor Search for Large Data Sets with High Dimensions. IEEE Trans. on KDE 15(5), 1316–1330 (2003)MathSciNetGoogle Scholar
  18. 18.
    Zhong, S., Ghosh, J.: A Unified Framework for Model-based Clustering. Journal of Machine Learning Research 4, 1001–1037 (2003)CrossRefMathSciNetGoogle Scholar
  19. 19.
    Wu, J.-K.: Content-Based Indexing of Multimedia Databases. IEEE Transactions on Knowledge and Data Engineering 9(6) (1997)Google Scholar
  20. 20.
    Bohm, C., Berchtold, S., Keim, D.A.: Searching in High-Dimensional Spaces-Index Structures for Improving the Performance of Multimedia Databases. ACM Computing Surveys 33(3) (2001)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Giuseppe Boccignone
    • 1
  • Vittorio Caggiano
    • 2
  • Carmine Cesarano
    • 2
  • Vincenzo Moscato
    • 2
  • Lucio Sansone
    • 2
  1. 1.Dipartimento di Ingegneria dell’InformazioneUniversity of SalernoFisciano (SA)Italy
  2. 2.Dipartimento di Informatica e SistemisticaUniversity Federico IINaplesItaly

Personalised recommendations