Fast Queries of Fibered Barcodes

Basic Information

• Paper ID: 2511.05837
• Title: Fast Queries of Fibered Barcodes
• Authors: Michael Lesnick (University at Albany), Matthew Wright (St. Olaf College)
• Classification: math.AT (Algebraic Topology), cs.CG (Computational Geometry)
• Submission Date: Submitted to arXiv on November 8, 2025
• Paper Link: https://arxiv.org/abs/2511.05837

Abstract

This paper investigates the efficient query problem for fibered barcodes in bipersistent homology. The fibered barcode $\mathcal{F}(M)$ maps each affine line $\ell \subset \mathbb{R}^2$ with non-negative slope to the barcode of the bimodule $M$ restricted along $\ell$. The authors improve upon their earlier work (arXiv:1512.00180) by proposing an augmented arrangement data structure based on planar line arrangements for real-time interactive visualization of fibered barcodes. By changing the input from chain complexes to minimal presentations, the paper significantly simplifies the algorithm and its complexity analysis.

Research Background and Motivation

1. Research Problem

Persistent homology in topological data analysis (TDA) is a core tool for studying data shape. For many data types (such as noisy point clouds), single-parameter persistent homology is insufficient to encode data structure, necessitating multiparameter persistent homology. However, defining barcodes in the multiparameter setting faces algebraic obstacles, presenting major challenges to both theoretical and practical development.

2. Problem Importance

• Visualization Challenge: Visualization of multiparameter persistent homology is more difficult than the single-parameter case
• Practical Demand: Interactive visualization requires the ability to quickly query barcodes on a given line $\ell$
• Computational Efficiency: Computing barcodes for each line from scratch is computationally expensive; efficient data structures are needed to support queries

3. Limitations of Existing Methods

• Early methods computed augmented arrangements directly from chain complexes, with poor memory efficiency
• Classical Gröbner basis algorithms lack sufficient efficiency
• Absence of a fast query framework optimized for the biparameter case

4. Research Motivation

• The authors' RIVET software requires real-time interactive visualization support
• The introduction of minimal presentations (in subsequent work) enables algorithm simplification
• Need for a more concise and optimized theoretical exposition

Core Contributions

1. Simplified Augmented Arrangement Algorithm: By using minimal presentations as input, the paper significantly simplifies the computation algorithm for augmented arrangements and its complexity analysis
2. Efficient Query Framework: Proposes a data structure based on planar line arrangements supporting logarithmic-time point location queries and linear-time barcode generation
3. Complexity Bounds (Main Theorems):
   • Theorem 1.2: Augmented arrangement size is $O(m\kappa^2)$, computable in $O(m^3\kappa + \kappa^2(m + \log\kappa))$ time and $O(m^2 + m\kappa^2)$ space
   • Theorem 1.3: Query time is $O(\log\kappa + |\mathcal{B}(M^\ell)|)$
   
   where $m$ is the total number of rows and columns in the minimal presentation, and $\kappa$ is the number of unique coordinate values in the support of Betti numbers
4. Theoretical Refinement: Provides a more refined and complete mathematical exposition compared to the original preprint (arXiv:1512.00180)
5. Practical Value: The framework has been implemented in RIVET software, supporting real-time interactive visualization

Methodology Details

Task Definition

Input: Minimal presentation $\eta: F \to F'$ of a bimodule $M$ (matrix with $\mathbb{R}^2$-valued labels)

Output: Augmented arrangement $\mathcal{A}^\bullet(M)$ supporting fast queries of barcode $\mathcal{B}(M^\ell)$ for any non-negative slope line $\ell$

Constraints:

• $M$ is a finitely presented bimodule
• Queries require logarithmic point location time + linear barcode generation time

Core Concepts

1. Fibered Barcode

For a bimodule $M: \mathbb{R}^2 \to \text{Vec}$, the fibered barcode is defined as: $\mathcal{F}(M): \ell \mapsto \mathcal{B}(M^\ell)$ where $M^\ell$ is the restriction of $M$ along line $\ell$, and $\mathcal{B}(M^\ell)$ is its barcode (multiset of intervals).

Key Properties:

• Equivalent to rank invariant
• Satisfies internal and external stability
• Computable and simple

2. Anchors

For incomparable point pairs $s, t \in S$ (where $S$ is the union of Betti number supports), the anchor is defined as: $\alpha = s \vee t = (\max(s_1, t_1), \max(s_2, t_2))$

Anchors are dual points of the line arrangement in the augmented arrangement.

Augmented Arrangement Structure

The augmented arrangement $\mathcal{A}^\bullet(M)$ consists of three parts:

1. Line Arrangement $\mathcal{A}(M)$

In the right half-plane $H = [0,\infty) \times \mathbb{R}$, the cellular decomposition induced by dual lines of all anchors: $\mathcal{A}(M) = \{\alpha^* \mid \alpha \text{ is an anchor}\}$

Using standard point-line duality:

• Point $(q, r) \in \mathbb{R}^2$ dualizes to line $y = qx - r$
• Line $y = qx + r$ dualizes to point $(q, -r)$

2. Barcode Templates

For each face $\Delta$ of $\mathcal{A}(M)$:

Template Point Set $P^\Delta$: Defined by a total order partition $S^\Delta = \{S^\Delta_1, \ldots, S^\Delta_k\}$, where: $P^\Delta_i = \bigvee\left(\bigcup_{j \leq i} S^\Delta_j\right)$

Barcode Template $\mathcal{B}^\Delta$: The barcode of restricted module $M^\Delta$, where $M^\Delta$ is $M$ restricted to $P^\Delta$.

Key Theorem 3.6: If $\ell^*, {\ell'}^*$ lie in the same face, then $S^\ell = S^{\ell'}$ (same total order partition).

3. Point Location Data Structure

Standard logarithmic-time point location query structure (e.g., Kirkpatrick structure), with size $O(\kappa^2)$ and query time $O(\log\kappa)$.

Push Map

For line $\ell \in \mathcal{L}_{[0,\infty]}$, define the push map: $\text{push}_\ell: \mathbb{R}^2 \to \ell \cup \{\infty\}$$\text{push}_\ell(a) = \min\{b \in \ell \mid a \leq b\}$

Properties:

• Preserves partial order: $a \leq b \Rightarrow \text{push}_\ell(a) \leq \text{push}_\ell(b)$
• For $\text{push}_\ell(a) = c \in \ell$, either $a_1 = c_1$ or $a_2 = c_2$
• Continuity (Lemma 3.5)

Query Algorithm

Input: Line $\ell \in \mathcal{L}_{[0,\infty]}$

Steps:

1. Point Location: Find face $\Delta$ containing $\ell^*$ (or select appropriate adjacent face)
   • Time: $O(\log\kappa)$
2. Barcode Generation: For each $(a,b) \in \mathcal{B}^\Delta$:
   • Compute $\text{push}_\ell(a)$ and $\text{push}_\ell(b)$
   • If $\text{push}_\ell(a) < \text{push}_\ell(b)$, output interval $[\text{push}_\ell(a), \text{push}_\ell(b))$
   • Time: $O(1)$ per interval, total $O(|\mathcal{B}^\Delta|)$

Correctness Theorem 4.2: $\mathcal{B}(M^\ell) = \{[\text{push}_\ell(a), \text{push}_\ell(b)) \mid [a,b) \in \mathcal{B}^\Delta, \text{push}_\ell(a) < \text{push}_\ell(b)\}$

Computation Algorithm

Preprocessing Phase

1. Compute Anchors: Traverse minimal grid, $O(\kappa)$ time
2. Build Line Arrangement: Use Bentley-Ottmann algorithm, $O(\kappa^2\log\kappa)$ time
3. Build Point Location Structure: $O(\kappa^2\log\kappa)$ time

Barcode Template Computation

Strategy: Update from one face's RU decomposition to adjacent faces via dual graph $G$ traversal

Initialization (face $\Delta_0$, topmost face):

• Compute $P^{\Delta_0}$ and $\text{lift}_{\Delta_0}$: $O(m\log m)$ time
• Compute RU decomposition of induced presentation $Q^{\Delta_0}$: $O(m^3)$ time

Traversal Update (from $\Delta$ to adjacent face $\hat{\Delta}$):

Three cases (determined by anchor $\alpha$ on shared boundary):

1. Generic Case: $\alpha = s \vee t$, $s,t$ incomparable
   • Requires permuting matrix row/column blocks
   • Use vineyard update for RU decomposition
2. Merge Case: $S^\Delta_j = \{\alpha\}$
   • $S^\Delta_{j-1}$ and $S^\Delta_j$ merge into $S^{\hat{\Delta}}_{j-1}$
   • RU decomposition requires no update
3. Split Case: $S^{\hat{\Delta}}_{j+1} = \{\alpha\}$
   • $S^\Delta_j$ splits into $S^{\hat{\Delta}}_j$ and $S^{\hat{\Delta}}_{j+1}$
   • RU decomposition requires no update

RU Decomposition Update (Generic Case):

• Identify row/column blocks requiring permutation
• Use vineyard update: decompose into adjacent transpositions
• Each transposition update: $O(m)$ time

Lemma 5.3 provides exact update formulas for template points and lift maps.

Technical Innovations

1. Minimal Presentation Input:
   • Typically much smaller than chain complexes
   • Avoids memory bottleneck of Schreyer algorithm
   • Simplifies algorithm logic
2. Augmented Arrangement Design:
   • Exploits geometric meaning of anchors
   • Theorem 3.6 guarantees consistency within faces
   • Push map provides elegant query mechanism
3. Efficient Update Strategy:
   • Exploits structural similarity of adjacent faces
   • Case-by-case treatment of three scenarios
   • Application of vineyard updates
4. Complexity Optimization:
   • Point location: $O(\log\kappa)$
   • Barcode generation: Linear in output size
   • Overall near-optimal

Experimental Setup

This is a theory/algorithm paper primarily focused on mathematical proofs and complexity analysis, without traditional experimental evaluation. However, the paper mentions:

Software Implementation

• RIVET Software: Biparameter persistent homology visualization software developed by the authors
• Implements the augmented arrangement framework
• Supports real-time interactive queries
• Publicly released: https://github.com/rivetTDA/rivet/

Practical Performance

The paper states (page 3):

"On typical input, queries of our data structure in RIVET are fast enough to enable smooth animations of the changing barcode as the query line $\ell$ is varied by the user."

This indicates practical performance meets real-time interactive requirements.

Related Experimental Work

Authors report experimental results in other papers:

• 80 (Lesnick & Wright 2022): Minimal presentation computation faster and more scalable than standard computer algebra software
• RIVET has been used in multiple practical applications (pages 8-9 list examples)

Experimental Results

Given the paper's nature, here we summarize theoretical results and practical impact:

Main Theoretical Results

1. Size Bounds (Theorem 1.2(i))

Augmented arrangement size: $O(m\kappa^2)$

Analysis:

• Line arrangement: $O(\kappa^2)$ cells
• Per-face storage: $O(m)$-sized barcode template
• Worst case: $\kappa = O(m^2)$, total size $O(m^5)$

2. Computational Complexity (Theorem 1.2(ii))

• Time: $O(m^3\kappa + \kappa^2(m + \log\kappa))$
• Space: $O(m^2 + m\kappa^2)$

Component Breakdown (Table 1):

Bottleneck: Barcode template computation, primarily RU decomposition updates ($O(m^3\kappa)$)

3. Query Complexity (Theorem 1.3)

• Generic Case: $O(\log\kappa + |\mathcal{B}(M^\ell)|)$
• Degenerate Case: $O(\log\kappa + |\mathcal{B}(M^{\ell'})|)$, where $\ell'$ is small perturbation of $\ell$

Near-Optimal:

• Point location: Logarithmic time (optimal)
• Barcode generation: Linear in output size (optimal)

Practical Application Impact

RIVET Software Applications (Page 8)

1. High-Dimensional Data Analysis: Wikipedia article analysis 105
2. Computational Chemistry: Virtual screening problems 96
3. Molecular Generation Models: Structure analysis 96
4. Immuno-Oncology: Spatial transcriptomics 8, 103

Downstream Work Impact

1. Matching Distance Computation: First polynomial-time exact algorithm 11, 68
2. Projected Barcodes: γ-linear projected barcode queries 61
3. Multiparameter Persistent Landscapes: MPL vectorization 102
4. Multipers Software: Integrated RIVET functionality 83

Performance Improvements

Compared to original method (computing from chain complexes):

• Memory Efficiency: Minimal presentations typically far smaller than chain complexes
• Computation Speed: Authors report significant acceleration in 80
• Algorithm Simplification: Avoids complexity of Schreyer algorithm

Related Work

Multiparameter Persistent Homology Algorithms

Early Work (2009-2015)

1. Carlsson et al. (2009) 26: Gröbner basis algorithms applied to multiparameter filtrations
2. Cerri et al. (2011) 9: Approximate matching distance for fibered barcodes
3. Chacholski et al. (2014) 32: Free persistent module chain complex representations

Minimal Presentation Computation

1. Lesnick & Wright (2022) 80:
   • Cubic time, quadratic space algorithm
   • Faster and more scalable than standard software
2. Kerber & Rolle 63, 69: Optimized versions with better practical performance
3. Bauer et al. 6: Cohomology methods for function-Rips bifiltered complexes
4. Morozov & Scoccola 87: Near-linear time algorithm for 0-dimensional homology

Other Query and Visualization Methods

1. Matching Distance: Exact polynomial-time algorithms 11, 68
2. Projected Barcodes: γ-linear projections 61
3. Persistent Sheaves: Piecewise-linear families by Hickok 66
4. Persistable Software 97: Uses RIVET visualization ideas

Alternative Rank Invariant Representations

Signed Barcodes

Two main approaches:

1. Möbius Inversion 19, 71: Following Patel's ideas
2. Relative Homological Algebra 12, 20, 88: Following Botnan et al.'s ideas

Advantages:

• Complete rank invariant visualization in single 2D diagram
• Hook signed barcodes are Lipschitz stable 20, 88

Limitations:

• Size, computability, and instability issues in certain constructions 20, 70
• Difficult interpretation in simple examples

Elder-Rule-Staircase Codes

For 0-dimensional persistence in function-Rips bifiltered complexes 23, determines rank invariant.

Decomposition Methods

Krull-Schmidt-Azumaya Theorem 17

Finite-dimensional multiparameter persistent modules have unique indecomposable decomposition.

Recent Algorithms:

• Optimized for TDA inputs 54, 56
• Can accelerate augmented arrangement computation 54

Note: Decomposition is unstable 7; Bjerkevik proposed systematic treatment 10

Bifiltration Construction

Methods for constructing bifiltrations from data:

1. Density-Sensitive Bifiltrations: Point clouds and metric data 1, 14, 15, 21, 46, 59, 60, 65, 77, 78, 79, 99
2. Morphological Filtrations: Image analysis 40, 41
3. Time Series: Topological representation of dynamic objects 37, 48

Conclusions and Discussion

Main Conclusions

1. Successful Algorithm Simplification: Using minimal presentations as input significantly simplifies augmented arrangement computation
2. Efficient Query Implementation: Query time $O(\log\kappa + |\mathcal{B}(M^\ell)|)$ is near-optimal
3. Practical Verification: RIVET implementation supports real-time interactive visualization
4. Theoretical Contribution: Provides more refined mathematical exposition than original work

Limitations

1. Worst-Case Complexity

• Size: $O(m^5)$ (when $\kappa = O(m^2)$)
• Computation Time: $O(m^5)$

Mitigation Strategies (Remark 1.4):

• Align generator and relation ranks to grid
• Obtain $\delta$-approximation: $d_m(\mathcal{F}(M), \mathcal{F}(M')) \leq \delta$
• Make $\kappa$ a small constant

2. Limited to Biparameter Case

• Method specific to $\mathbb{R}^2$
• Higher dimensions require different approaches

3. Instability Issues

• Fibered barcodes themselves are stable
• Augmented arrangement not directly determined by $\mathcal{F}(M)$ (Remark 3.11)

4. RU Update Strategy

• Vineyard updates may not be optimal
• Global updates or other strategies might be better (Remark 5.5)

Future Directions

1. Augmented Arrangement Depending Only on Fibered Barcode

Remark 3.11 suggests:

"We expect that by defining the set of anchors differently, one can obtain a variant of $\mathcal{A}^\bullet(M)$ which depends only on $\mathcal{F}(M)$."

2. RU Update Strategy Optimization

• Empirical comparison of different update schemes
• Global update vs. vineyard update vs. non-adjacent transpositions

3. Higher-Dimensional Generalization

• Query frameworks for three or more parameters
• May require completely different data structures

4. Application Extension

• More practical data analysis applications
• Integration with machine learning methods

In-Depth Evaluation

Strengths

1. Solid Theoretical Contribution

• Mathematical Rigor: All theorems have complete proofs
• Clear Complexity Analysis: Detailed breakdown of each step's cost
• Key Lemmas: Theorem 3.6 (face consistency) is the framework's foundation

2. Elegant Algorithm Design

• Augmented Arrangement Structure: Clever use of point-line duality and anchor concepts
• Push Map: Provides geometrically intuitive and efficient query mechanism
• Update Strategy: Fully exploits structural similarity of adjacent faces

3. High Practical Value

• RIVET Software: Used in multiple practical applications
• Real-Time Interaction: Query speed meets visualization requirements
• Open Source: Code publicly available and reproducible

4. Clear Writing

• Logical Structure: Clear hierarchy from background to algorithm to complexity analysis
• Consistent Notation: Mathematical symbols used consistently
• Rich Illustrations: Multiple figures aid understanding (e.g., Figures 4-10)

5. Significant Improvements

• Simplifies algorithm compared to original work 79
• Leverages minimal presentation advantages
• Better memory efficiency

Weaknesses

1. Lack of Experimental Evaluation

• No Performance Comparison: No empirical comparison with original method
• No Scale Testing: No runtime reports for different data sizes
• No Case Studies: No concrete application examples shown

While this is a theory paper, some experimental data would strengthen the argument.

2. High Worst-Case Complexity

• $O(m^5)$ size and time are theoretically high
• While grid approximation strategy provided, practical effectiveness unknown

3. Method Limitations

• Limited to Biparameter: Cannot directly extend to higher dimensions
• Depends on Minimal Presentation: Requires computing minimal presentation first (itself non-trivial)
• Instability Issue: Augmented arrangement not completely determined by $\mathcal{F}(M)$

4. Insufficient Implementation Details

• Low-Level Optimization: Section 5.4 provides few data structure details
• Engineering Tricks: References 79's engineering tricks but doesn't elaborate
• Parameter Selection: Doesn't discuss practical parameter choices

5. Limited Comparison with Other Methods

• No in-depth comparison with signed barcode methods
• Doesn't discuss relationship with decomposition methods
• Related work section is lengthy but lacks critical analysis

Impact

1. Academic Impact

• High Citation Value: Provides foundational tools for multiparameter persistent homology
• Abundant Follow-Up Work: Used for matching distance computation, projected barcodes, etc.
• Theoretical Significance: Advances algorithmic research in multiparameter TDA

2. Practical Value

• RIVET Users: Multiple practical application cases
• Software Ecosystem: Influenced Persistable, Multipers, and other software
• Visualization Standard: Interactive queries become reference method for multiparameter visualization

3. Reproducibility

• Open Source Code: https://github.com/rivetTDA/rivet/
• Detailed Algorithm: Paper provides sufficient implementation details
• Mathematical Rigor: All results have proofs

4. Limitation Impact

• Biparameter restriction reduces generality
• Worst-case complexity may limit very large-scale applications

Applicable Scenarios

1. Ideal Scenarios

• Biparameter Data Analysis: Point clouds, images, time series, etc.
• Interactive Exploration: Applications requiring real-time visualization
• Medium-Scale Data: Cases where $m, \kappa$ are not too large
• Multiple Queries: Preprocessing cost amortizable across queries

2. Specific Application Domains

• Computational Topology: TDA research and teaching
• Data Science: Topological feature extraction from high-dimensional data
• Computational Biology: Protein structure, spatial transcriptomics
• Materials Science: Multiparameter material property analysis

3. Inapplicable Scenarios

• Three or Higher Parameters: Method doesn't directly apply
• Ultra-Large-Scale Data: $O(m^5)$ complexity potentially prohibitive
• Single Query: Preprocessing cost cannot be amortized
• Complete Decomposition Needed: Fibered barcodes don't provide complete decomposition information

Key References

1. 79 Lesnick & Wright (2015): Original preprint, first proposes augmented arrangement
2. 80 Lesnick & Wright (2022): Minimal presentation computation algorithm
3. 28 Carlsson & Zomorodian (2009): Theoretical foundations of multiparameter persistent homology
4. 30 Cerri et al. (2013): Definition and properties of fibered barcodes
5. 44 Cohen-Steiner et al. (2006): Vineyard update algorithm
6. 11, 68 Bjerkevik & Kerber et al.: Exact matching distance computation
7. 17 Botnan & Crawley-Boevey (2020): Decomposition theorem
8. 52 de Berg et al. (2008): Computational geometry foundations (Bentley-Ottmann algorithm)

Summary

This is a high-quality theory/algorithm paper making important contributions to multiparameter topological data analysis. Through clever data structure design and algorithmic optimization, it achieves efficient querying of biparameter persistent homology fibered barcodes. While lacking experimental evaluation and limited to the biparameter case, its theoretical rigor, practical value, and existing software implementation make it an important work in the field. For scholars engaged in TDA research and applications, this is an essential reference.