Bypassing combinatorial explosions in equivalence structure extraction

摘要

Equivalence structure (ES) extraction enables us to determine correspondence relations within a dataset or between multiple datasets. Applications of ES extraction include the analysis of time series data, preprocessing of imitation learning, and preprocessing of transfer learning. Currently, pairwise incremental search (PIS) is the fastest method to extract ESs; however, a combinatorial explosion can occur when employing this method. In this paper, we show that combinatorial explosion is a problem that occurs in the PIS, and we propose a new method where this problem does not occur. We evaluate the proposed method via experiments; the results show that our proposed method is 39 times faster than the PIS for synthetic datasets where a 20-dimensional ES exists. For the experiment using video datasets, the proposed method enabled us to obtain a 29-dimensional ES, whereas the PIS did not because the memory usage reached its limit when the number of dimensions was 9. In this experiment, the total processing time for our proposed method up to 29 dimensions was 6.3 times shorter than that for PIS up to even 8 dimensions.