Scalable Feature Matching Across Large Data Collections

Abstract

This article is concerned with matching feature vectors in a one-to-one fashion across large collections of datasets. Formulating this task as a multidimensional assignment problem with decomposable costs (MDADC), we develop fast algorithms with time complexity roughly linear in the number n of datasets and space complexity a small fraction of the data size. These remarkable properties hinge on using the squared Euclidean distance as dissimilarity function, which can reduce $\left(\begin{array}{c}n\\ 2\end{array}\right)$ matching problems between pairs of datasets to n problems and enable calculating assignment costs on the fly. To our knowledge, no other method applicable to the MDADC possesses these linear scaling and low-storage properties necessary to large-scale applications. In numerical experiments, the novel algorithms outperform competing methods and show excellent computational and optimization performances. An application of feature matching to a large neuroimaging database is presented. The algorithms of this article are implemented in the R package matchFeat available at github.com/ddegras/matchFeat. Supplementary materials for this article are available online.

Keyword:

• Combinatorial optimization
• Constrained clustering
• Multidimensional assignment problem

Supplementary Materials

Details on data analysis and theoretical aspects: List of regions of interest and of resting state networks considered in the fMRI data analysis (Section 4). Proof of global optimality result in the convex relaxation of the matching problem (Appendix B). File: supplement.pdf.

Acknowledgments

The author thanks the Editor and two anonymous reviewers for their helpful comments. He also thanks Vince Lyzinski for his valuable insights on convex relaxation.