Hirata Y, Sukegawa N. Two efficient calculations of edit distance between marked point processes.
CHAOS (WOODBURY, N.Y.) 2019;
29:101107. [PMID:
31675806 DOI:
10.1063/1.5125651]
[Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/24/2019] [Accepted: 10/03/2019] [Indexed: 06/10/2023]
Abstract
In this paper, we propose to use linear programming methods or a more specialized method, namely, the Hungarian method, for speeding up the exact calculation of an edit distance for marked point processes [Y. Hirata and K. Aihara, Chaos 25, 123117 (2015)]. The key observation is that the problem of calculating the edit distance reduces to a matching problem on a bipartite graph. Our preliminary numerical results show that the proposed implementations are faster than the conventional ones by a factor of 10-1000.
Collapse