Distribution-based similarity measures for multi-dimensional point set retrieval applications

ABSTRACT

Effective and efficient method of similarity assessment continues to be one of the most fundamental problems in multimedia data analysis. In case of retrieving relevant items from a collection of objects based on series of multivariate observations (e.g., searching the similar video clips in a repository to a query example), satisfactory performance cannot be expected using many conventional similarity measures based on the aggregation of element pairwise comparisons. Some correlation information among the individual elements has also been investigated to characterize each set of multi-dimensional points for ranked retrieval, by making use of an unwarranted assumption that the underlying data distribution has a particular parametric form. Motivated by this observation, this paper introduces a novel collective gauge of relevance ranking by evaluating the probabilities that point sets are consistent with the same distribution of the query. Two non-parametric hypothesis tests in statistics are justified to exploit the distributional discrepancy of samples for assessing the similarity between two ensembles of points. While our methodology is mainly presented in the context of video similarity search, it enjoys great flexibility and can be easily adapted to other applications involving generic multi-dimensional point set representation for each object such as human gesture recognition.

REFERENCES

• 1: Pearson curves. In M. Hazewinkel, editor, Encyclopaedia of Mathematics. Springer-Verlag, 2002. http://eom.springer.de/P/p071920.htm.
• 2: Niall H. Anderson , Peter Hall , D. M. Titterington, Two-sample test statistics for measuring discrepancies between two multivariate probability density functions using kernel-based density estimates, Journal of Multivariate Analysis, v.50 n.1, p.41-54, July 1994 [doi>10.1006/jmva.1994.1033]
• 3: G. Biau and L. Györfi. On the asymptotic properties of a nonparametric l₁-test statistic of homogeneity. IEEE Transactions on Information Theory, 51(11):3965--3973, 2005.
• 4: Karsten M. Borgwardt , Arthur Gretton , Malte J. Rasch , Hans-Peter Kriegel , Bernhard Schölkopf , Alex J. Smola, Integrating structured biological data by Kernel Maximum Mean Discrepancy, Bioinformatics, v.22 n.14, p.e49-e57, July 2006 [doi>10.1093/bioinformatics/btl242]
• 5: Raffaele Cappelli , Dario Maio , Davide Maltoni, Multispace KL for Pattern Representation and Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.977-996, September 2001 [doi>10.1109/34.955111]
• 6: Bernard Chalmond , Stéphane C. Girard, Nonlinear Modeling of Scattered Multivariate Data and Its Application to Shape Change, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.422-432, May 1999 [doi>10.1109/34.765654]
• 7: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 8: B. Efron and R. J. Tibshirani. An Introduction to the Bootstrap. Chapman & Hall/CRC, New York, 1993.
• 9: W. Feller. On the kolmogorov-smirnov limit theorems for empirical distributions. Ann. Math. Statist., 19(2):177--189, 1948.
• 10: J. H. Friedman and L. C. Rafsky. Multivariate generalizations of the wald-wolfowitz and smirnov two-sample tests. Ann. Statist., 7(4):697--717, 1979.
• 11: A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. J. Smola. A kernel method for the two-sample-problem. In NIPS, pages 513--520, 2006.
• 12: N. Henze and M. D. Penrose. On the multivariate runs test. Ann. Statist., 27(1):290--298, 1999.
• 13: David W. Jacobs , Daphna Weinshall , Yoram Gdalyahu, Classification with Nonmetric Distances: Image Retrieval and Class Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.583-600, June 2000 [doi>10.1109/34.862197]
• 14: T. Joachims. Support vector and kernel methods. In SIGIR, Tutorial, 2003.
• 15: Mohammed Waleed Kadous, Temporal classification: extending the classification paradigm to multivariate time series, University of New South Wales, New South Wales, Australia, 2002
• 16: Eamonn Keogh, Exact indexing of dynamic time warping, Proceedings of the 28th international conference on Very Large Data Bases, p.406-417, August 20-23, 2002, Hong Kong, China
• 17: V. S. Korolyuk and Y. Borovskich. Theory of U-Statistics. Kluwer Academic Publishers, Dordrecht, 1994.
• 18: W. J. Krzanowski. Between-groups comparison of principal components. Journal of the American Statistical Association, 74(367):703--707, 1979.
• 19: Similarity Search for Multidimensional Data Sequences, Proceedings of the 16th International Conference on Data Engineering, p.599, February 28-March 03, 2000
• 20: Chuanjun Li , Peng Zhai , Si-Qing Zheng , Balakrishnan Prabhakaran, Segmentation and recognition of multi-attribute motion sequences, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027721]
• 21: Jan Puzicha , Thomas Hofmann , Joachim M. Buhmann, Non-parametric Similarity Measures for Unsupervised Texture Segmentation and Image Retrieval, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.267, June 17-19, 1997
• 22: P. R. Rosenbaum. An exact distribution-free test comparing two multivariate distributions based on adjacency. Journal of The Royal Statistical Society Series B, 67(4):515--530, 2005.
• 23: Yossi Rubner , Jan Puzicha , Carlo Tomasi , Joachim M. Buhmann, Empirical evaluation of dissimilarity measures for color and texture, Computer Vision and Image Understanding, v.84 n.1, p.25-43, October 2001 [doi>10.1006/cviu.2001.0934]
• 24: Heng Tao Shen , Xiaofang Zhou , Zi Huang , Jie Shao, Statistical summarization of content features for fast near-duplicate video detection, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291271]
• 25: Ingo Steinwart, On the influence of the kernel on the consistency of support vector machines, The Journal of Machine Learning Research, 2, p.67-93, 3/1/2002 [doi>10.1162/153244302760185252]
• 26: Ch. Theoharatos , V. K. Pothos , N. A. Laskaris , G. Economou , S. Fotopoulos, Multivariate image similarity in the compressed domain using statistical graph matching, Pattern Recognition, v.39 n.10, p.1892-1904, October, 2006 [doi>10.1016/j.patcog.2006.04.015]
• 27: Michail Vlachos , Dimitrios Gunopoulos , George Kollios, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 28: A. Wald and J. Wolfowitz. On a test whether two samples are from the same population. Ann. Math. Statist., 11(2):147--162, 1940.
• 29: Kiyoung Yang , Cyrus Shahabi, An efficient k nearest neighbor search for multivariate time series, Information and Computation, v.205 n.1, p.65-98, January, 2007 [doi>10.1016/j.ic.2006.08.004]
• 30: W. Zhao, C.-W. Ngo, H.-K. Tan, and X. Wu. Near-duplicate keyframe identification with interest point matching and pattern learning. IEEE Transactions on Multimedia, 9(5):1037--1048, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Multivariate statistics

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
hypothesis tests, minimal spanning tree, multi-dimensional point set, non-parametric, reproducing kernel hilbert space, similarity measures