The game theory laboratory has developed a new library for topological data analysis
Konstantin Sorokin, deputy head of the laboratory, together with his colleagues, published the qfcore software library for working with large datasets and the preprint A data structure for quotient flag complexes, which presents a toolkit for topological data analysis.
In the world of data science, researchers often try to understand the shape of information. They take vast clouds of points—perhaps representing stars in a galaxy, genes in a cell, or customers in a market—and connect nearby points to form a mesh of triangles, tetrahedra, and higher-dimensional shapes. This mesh, known as a flag complex, acts like a skeleton that reveals the hidden holes, loops, and voids within the data. To make sense of these shapes, scientists use a standard tool called a simplex tree, which is essentially a highly efficient filing system. Because the rules of these shapes are strict, the filing system does not need to store every single connection; it only needs to know which points are connected, and the rest of the structure can be inferred automatically. This economy allows computers to handle massive datasets that would otherwise be too large to process.
However, real-world data is rarely static. Sometimes, a chunk of the data is known to be unimportant or redundant, and scientists want to shrink it down to a single point to simplify the analysis. Imagine taking a tangled knot of string and crushing a specific loop of it flat until it becomes a single dot. The rest of the string remains, but its connections to that dot have changed. This operation, called a quotient, creates a new shape where the old rules no longer apply. The neat filing system that worked before breaks down because the new shape has loops and connections that cannot be guessed just by looking at the points. The question becomes: how can we store this new, altered shape efficiently without losing the information needed to understand its true structure?
A team of researchers has developed a new data structure, called the QF-tree, designed specifically to handle these crushed shapes. Their work addresses a fundamental problem: when you collapse a part of a complex shape, the remaining pieces often attach to each other in ways that are no longer obvious. A simple edge might turn into a loop, or a triangle might get glued down to a single line. The researchers proved that if the part being crushed follows a specific geometric rule—meaning it is made of all possible connections between its points—then the new shape retains a predictable order. They found that for these specific cases, you do not need to store the entire new shape to know what it is. Instead, you only need to keep track of the small pieces, specifically those with up to three corners, and the computer can reconstruct the rest. This is a significant saving, as it means the storage requirements do not grow with the size of the entire shape, but only with the complexity of its smallest building blocks.
The team also discovered a precise tipping point for when this new method is better than the old way of handling these problems. Traditionally, if scientists wanted to simplify a shape, they would attach a cone to the part they wanted to crush, creating a homotopy-equivalent model that is easier to store but mathematically different in its details. The researchers calculated that if the part being crushed makes up more than a certain fraction of the total shape—specifically, a fraction determined by the average number of connections each remaining piece has—then their new QF-tree method uses less memory than the cone method. In tests involving millions of data points, the new method consistently used less space when the crushed portion was large enough, and the predicted crossover point matched the actual measurements with extreme precision.
Beyond just storage, the researchers built a software library that allows these operations to happen locally. Instead of rebuilding the entire shape every time a small part is crushed, the system can update just the affected area, which is often a thin shell around the crushed region. This makes the process incredibly fast, especially for large datasets. In experiments, maintaining the shape locally was found to be hundreds of times cheaper than rebuilding it from scratch. Furthermore, when scientists needed to perform complex calculations on the resulting shape, such as analyzing the loops and holes to understand the data's topology, doing so on the retained quotient was significantly faster than starting over with the original, uncrushed data. The library even allows for dynamic changes, letting researchers add or remove points and connections while keeping the structure intact, and it can compute fundamental properties like the number of holes or the ways loops can be formed.
The work also clarifies what happens when the rules are broken. If the part being crushed does not contain all the connections between its points, the new shape can become irregular and unpredictable, losing the nice properties that make it easy to store. The researchers showed that in these cases, the simple filing system fails, and more complex data is required. They provided a clear test to check if a shape will remain regular after crushing: if every edge connecting two points in the crushed area is also part of the crushed area itself, the new shape will be well-behaved. This insight helps scientists decide when they can safely use the efficient storage method and when they must be more careful.
Ultimately, this research provides a robust toolkit for topological data analysis, a field dedicated to finding the shape of data. By solving the problem of how to store and manipulate shapes after parts of them have been simplified, the team has removed a major bottleneck. Their method ensures that even when data is heavily processed and parts are collapsed, the essential topological information is preserved and accessible. The accompanying software, which is open and available for use, allows researchers to apply these techniques immediately, enabling them to work with larger, more complex datasets than ever before while keeping the computational cost low. The findings confirm that with the right structure, the economy of the original data representation can survive even the most drastic simplifications.
The text is taken from a website where you can find it in other languages.
