Approximate Nearest Neighbors in the Space of Persistence Diagrams
Talk by Dr. David Millman (School of Computing, MSU)
10/01/2020 3:10-4:15pm WebEX Talk
Persistence diagrams are important tools in the field of topological data analysis (TDA).
One common pattern in TDA pipelines is to find diagrams in a database that are close to a query diagram.
Unfortunately, the state of the art for searching for persistence diagram checks all diagrams in the database or does not offer performance guarantees.
In this talk, we explore why common search techniques do not work well (spoiler, it is because the space of persistence diagrams has infinite doubling dimension), look at the problem of finding approximate nearest neighbors, and propose the first sublinear time algorithm for searching in the space of persistence diagrams.