Accelerated Equivalence Structure Extraction via Pairwise Incremental Search

Seiya Satoh (National Institute of Advanced Industrial Science and Technology); Yoshinobu Takahashi (The University of Electro-Communications); Hiroshi Yamakawa (DWANGO Co., Ltd.)

Equivalence structure (ES) extraction can allow for finding correspondence relations between different sequential datasets. A K -dimensional ES is a set of K -tuples to specify K -dimensional sequences that are considered equivalent. Whether or not two K -dimensional sequences are equivalent is decided based on comparisons of all of their subsequences. ES extraction can be used for preprocessing for transfer learning or imitation learning, as well as an analysis of multidimensional sequences. A recently proposed method called incremental search (IS) was much faster than brute-force search. However, IS can still take a long time to obtain ESs, because ESs obtained by IS can be subsets of other ESs and such subsets must be removed in the process. In this paper, we propose a new fast method called pairwise incremental search (PIS). In the process of PIS, the aforementioned problem about subsets of ESs does not exist, because the elements of ESs are searched pairwise. As shown by results of two experiments we conducted, PIS was 48 times faster than IS in an experiment using synthetic datasets and 171 times faster in an experiment using motion capture datasets.

Promotional Video