Treffer: Efficient persistence landscape generation.

Using topological summary tools such as persistence landscapes have greatly enhanced the practical usage of topological data analysis to analyze large-scale, noisy, and complex datasets. A central element of persistence landscape usage involves computing the top- k landscapes. This article presents a novel output-sensitive plane sweep algorithm for computing the top- k persistence landscapes in optimal time and space: significantly outperforming previous algorithms. Our algorithm can determine in optimal O (n * log (n)) if a given birth-death pair appears in the top- k landscapes. The runtime performance of the approach on a botnet dataset and several synthetically generated point cloud topologies, showing that the algorithm can achieve significant speedups for these datasets due to its better algorithmic design. The speedups seen range from slightly worse (in some extreme examples) to equal compared to previous works while returning exactly the same output and is significantly faster when filtering is used (15x for birth-death pairs when removing 75% of birth-death pairs). Filtering is shown to maintain machine learning performance on both synthetically generated and real world datasets while providing orders of magnitude speedup depending on how intensive of filtering is done. Due to the introduced algorithm's algorithmic design, the speedup seen is greater when filtering using the introduced birth-death filtering algorithm. The software is freely provided in Rust with Python bindings online. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Algorithms & Computational Technology is the property of Sage Publications Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)