Scalable Feature Matching Across Large Data Collections. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Degras, David
• Is Part Of: Journal of computational and graphical statistics. Volume 32:Issue 1(2023)
• Page Start: 196
• Page End: 212
• Publication Date: 2023-01-02
• Subjects: Combinatorial optimization -- Constrained clustering -- Multidimensional assignment problem; Mathematical statistics -- Data processing -- Periodicals; Mathematical statistics -- Graphic methods -- Periodicals; 519.50285
• DOI: 10.1080/10618600.2022.2074429
• Languages: English
• ISSNs: 1061-8600

Abstract

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 ( n 2 ) 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.