Scalable Feature Matching Across Large Data Collections
本文提出一种可扩展的特征匹配方法，将问题建模为可分解成本的多维分配问题，开发了时间与数据集数量近似线性、空间占用小的快速算法，并在神经影像数据库上验证了其优越性能。
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 <i>n</i> 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 (n2) matching problems between pairs of datasets to <i>n</i> 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 <i>github.com/ddegras/matchFeat</i>. Supplementary materials for this article are available online.