🤖 machine learning

Exact and Approximate Range Queries for Efficient Ball Mapper Construction

This paper proposes and evaluates exact and approximate range query methods using ball trees and FAISS to accelerate Ball Mapper construction, demonstrating that while approximate methods conservatively reduce graph complexity without introducing false positives, their impact varies significantly based on dataset geometry.

Original authors: Jay-Anne Bulauan, John Rick Manzanares

Published 2026-06-23✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jay-Anne Bulauan, John Rick Manzanares

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Mapping a Crowd

Imagine you have a massive crowd of people (your data) and you want to draw a simple map of how they are grouped together. You don't want to list every single person; you just want to know the "neighborhoods."

Ball Mapper is a tool that does this. It picks a few "landmarks" (representative people) and draws a circle around each one. If two circles overlap, it means those two neighborhoods are connected, and the tool draws a line between them. The result is a simple graph that shows the shape of the crowd: where the clusters are, where the bridges are, and where the gaps are.

The Problem: To draw these circles correctly, the computer has to check every single person in the crowd to see if they fall inside a specific circle. If you have a million people, doing this check one by one is like trying to find a needle in a haystack by looking at every single piece of hay individually. It takes forever, especially if the crowd is spread out in a huge, complex room (high dimensions).

The Solution: Two New Ways to Search

The authors of this paper tested two different "superpowers" to speed up this searching process so the map can be built quickly.

1. The "Smart Organizer" (Ball Trees)

Imagine you are looking for a specific book in a giant library.

The Old Way: You walk down every single aisle and check every book on every shelf.
The Ball Tree Way: The library is organized into sections, then subsections, then shelves. The organizer knows that if the book you want is in the "Fiction" section, you don't need to check the "Cooking" section. The Ball Tree is a digital version of this. It groups data into nested bubbles. If a bubble is too far away from your search point, the computer ignores the whole bubble instantly.
The Catch: This works great in small, tidy rooms (low dimensions). But if the room is huge and the furniture is scattered everywhere (high dimensions), the "sections" stop being helpful, and the organizer gets confused.

2. The "Speedy Scouter" (FAISS)

Imagine you have a team of super-fast scouts who can look at thousands of people at once using special glasses (SIMD and BLAS technology).

The Exact Scout: They check everyone, but they do it so fast that it feels like magic. This is great for speed but requires a lot of memory (like needing a huge warehouse to store all the scout notes).
The Approximate Scout: Sometimes, to go even faster, the scouts skip checking some people or use a quick guess instead of a precise measurement. They might miss a few people who should be in the circle, or they might be unsure about people on the very edge.

The "Approximate" Question: Is It Safe to Guess?

The paper asks a crucial question: If we use the "Approximate Scout" who might make small mistakes, does the final map break?

The authors developed a set of rules to understand what happens when the scout makes mistakes:

Missing a person (False Negative): The scout forgets to put someone in the circle.
- Result: The map might look a little "thinner." It might miss a few connections between neighborhoods, or it might pick an extra landmark nearby just to cover the gap.
Adding a person who shouldn't be there (False Positive): The scout accidentally puts someone in the circle who is actually far away.
- Result: The map might draw a fake connection between two neighborhoods that shouldn't be linked.

The Big Discovery:
The authors tested this with different types of crowds (random clouds, tight clusters, and winding lines). They found that the "Speedy Scouts" (FAISS) behave conservatively.

They almost never add fake people to the circle (no false positives).
They mostly just miss a few people on the edge (false negatives).

This means the map doesn't get "corrupted" with fake connections. It just might look a little less detailed or have a few missing lines.

How the Crowd Shape Matters

The paper found that the shape of the data changes how much the "mistakes" matter:

The Random Cloud (Isotropic Gaussian): This is like a foggy room where people are scattered evenly. This is the most sensitive to mistakes. If the scout misses a few people here, the map loses a lot of connections because every connection relies on those specific people.
The Clusters (Mixture Model): This is like a room with distinct groups of friends. This is more stable. If the scout misses one person in a group, the other friends in that group still hold the connection together.
The Winding Line (Noisy Curve): This is like people standing in a long line. This is the most stable. Even if the scout misses a few people, the line is so obvious that the map stays perfect.

The Trade-Off

Ball Trees: Good for smaller, simpler rooms. They use less memory but get slow in huge, complex rooms.
FAISS (Exact): The fastest for huge, complex rooms, but it needs a lot of computer memory.
FAISS (Approximate): The fastest option. It uses less memory and time. The paper proves that while it might miss a few details, it won't create fake structures. It's a safe trade-off if you need speed.

Summary

The authors built a faster way to draw maps of complex data. They proved that using "smart shortcuts" (approximate search) to find the data points is safe: it won't trick you into seeing connections that aren't there. It might just make the map slightly less detailed, and how much detail you lose depends on whether your data is a random fog, a set of clusters, or a clear line.

Technical Summary: Exact and Approximate Range Queries for Efficient Ball Mapper Construction

Problem Statement

Ball Mapper is a topological data analysis tool that summarizes finite metric datasets by covering them with metric balls and encoding overlaps as a graph. The construction of this graph relies on a greedy algorithm to select a set of "landmarks" (an $\varepsilon$ -net), where each new landmark requires a fixed-radius range query to identify all data points within distance $\varepsilon$ . For large or high-dimensional datasets, this repeated range query step becomes a computational bottleneck. Naive implementations scale poorly with both the number of observations and the ambient dimension, suffering from the "curse of dimensionality" where geometric indexing methods lose pruning efficiency.

This work addresses the need for efficient range query implementations in Ball Mapper. It investigates two acceleration strategies: hierarchical spatial data structures (Ball Trees) and optimized similarity search libraries (FAISS). Furthermore, it addresses the specific challenge of approximate range queries. Unlike nearest-neighbor problems where finding a close point suffices, Ball Mapper requires all points within a radius. The paper seeks to understand how approximation errors (missing points or including false points) affect the resulting landmark set, covering radius, and graph topology.

Methodology

1. Acceleration Techniques

The authors evaluate two primary approaches to accelerate the range query step:

Ball Trees: Hierarchical data structures that recursively partition the dataset into bounded subsets. They utilize the triangle inequality to prune subtrees that cannot intersect a query ball. This method is metric-agnostic but its efficiency depends heavily on the data geometry.
FAISS (Facebook AI Similarity Search): A library optimized for dense vector similarity search.
- Exact Acceleration: Using flat indexes (e.g., IndexFlatL2) that leverage SIMD vectorization, BLAS routines, and multithreading to accelerate distance computations without altering the algorithmic complexity or the set of returned points (up to floating-point precision).
- Approximate Acceleration: Using non-exhaustive indexes (e.g., IndexIVFFlat, IndexHNSWFlat) or compressed indexes (e.g., IndexPQ, IndexSQ). These methods reduce runtime or memory by examining only a subset of data or using compressed representations, potentially altering the returned set of points.

2. Theoretical Framework for Approximation

The paper distinguishes between exact and approximate range queries by formulating deterministic error models:

Additive Error Model: An oracle is $\delta$ -accurate if the approximate range set $\tilde{R}_\varepsilon(q)$ satisfies $R_{\varepsilon-\delta}(q) \subseteq \tilde{R}_\varepsilon(q) \subseteq R_{\varepsilon+\delta}(q)$ .
Multiplicative Error Model: An approximate distance $\tilde{d}$ has relative error $\eta$ if $(1-\eta)d \le \tilde{d} \le (1+\eta)d$ .
Conservative Approximation: An oracle is conservative if $\tilde{R}_\varepsilon(q) \subseteq R_\varepsilon(q)$ , meaning it may miss true points (false negatives) but never includes points outside the true ball (no false positives).

The authors prove that under these error models:

The resulting landmark set $L$ remains an $(\varepsilon+\delta)$ -cover and is $(\varepsilon-\delta)$ -separated.
The approximate nerve (and thus the graph) lies between the exact nerves computed at scales $\varepsilon-\delta$ and $\varepsilon+\delta$ .
Conservative approximations guarantee that the exact $\varepsilon$ -balls of the computed landmarks still cover the dataset, though the landmarks may not be strictly $\varepsilon$ -separated.

3. Empirical Evaluation

Experiments were conducted on synthetic datasets with varying geometries:

Isotropic Gaussian: Unstructured, high-dimensional data.
Gaussian Mixture: Clustered data.
Noisy 1D Curve: Low-intrinsic-dimensional structured data.

The study compared Ball Tree, FAISS (flat, IVF, HNSW), and the baseline pyBallMapper across runtime, memory usage, and scaling behavior. Crucially, the approximation experiments focused on structural stability (range recall/precision, edge recall/precision, landmark count, and separation) rather than just speed.

Key Results

Computational Performance

Runtime: FAISS (flat index) demonstrated the best runtime performance, maintaining low execution times even as dataset size ( $n$ ) and dimension ( $D$ ) increased. It achieved speedups of over two orders of magnitude compared to pyBallMapper in high-dimensional settings. Ball Trees performed well at low dimensions but degraded rapidly as $D$ increased.
Scaling: Log-log regression showed pyBallMapper approaching quadratic scaling ( $p \approx 2$ ) with dimension, while FAISS and Ball Trees maintained significantly lower scaling exponents ( $p < 1.7$ ).
Memory: FAISS exhibited the highest memory footprint due to dense vector representations and indexing structures. Ball Trees and pyBallMapper were more memory-efficient.

Structural Effects of Approximation

Conservative Behavior: Across all tested FAISS configurations (IVF and HNSW), the approximate range queries were conservative. They produced zero false positives (precision was 1.0) but introduced false negatives (recall < 1.0).
Impact on Graph Structure:
- Edge Loss: The primary structural effect was the removal of edges (sparsification) due to missed range memberships.
- Landmark Selection: In end-to-end experiments, false negatives caused some points to remain uncovered, leading to the selection of additional, nearby landmarks. This reduced the minimum landmark separation below $\varepsilon$ , though the covering radius remained close to the target $\varepsilon$ .
Geometry Dependence: The sensitivity to approximation varied significantly by dataset geometry:
- Isotropic Gaussian: Most sensitive. Moderate approximation settings resulted in significant edge loss (e.g., IVF with $nprobe=32$ recovered only ~31% of edges).
- Gaussian Mixture: More stable due to clustered structure, which provides multiple witnesses for ball intersections.
- Noisy Curve: Most stable. Low-dimensional structure allowed approximate indexes to recover nearly 100% of memberships and edges even with aggressive parameters.

Significance and Claims

The paper claims to provide a rigorous framework for integrating approximate search into topological data analysis without compromising the theoretical guarantees of the Ball Mapper construction. Its main contributions are:

Implementation: It develops and benchmarks Ball Tree and FAISS implementations for the greedy Ball Mapper construction, demonstrating that FAISS offers superior scalability for large, high-dimensional Euclidean datasets.
Theoretical Bounds: It establishes deterministic bounds showing that approximate range queries (under additive or multiplicative error models) result in landmark sets and graphs that are bounded by exact constructions at slightly perturbed scales.
Empirical Characterization: It demonstrates that standard FAISS approximate indexes behave conservatively (no false positives), making them safe for Ball Mapper construction provided the user accepts potential edge sparsification and minor variations in landmark separation.
Geometry Sensitivity: It highlights that the stability of approximate Ball Mapper is not uniform; it is highly dependent on the intrinsic geometry of the data, with clustered and low-dimensional structures being more robust to approximation errors than isotropic high-dimensional data.

The authors conclude that while the definition of Ball Mapper need not change, its computational implementation can be significantly improved using FAISS. However, users must be aware that approximation introduces a trade-off: reduced computational cost in exchange for potential loss of graph connectivity and reduced landmark separation, the severity of which is dictated by the data's geometric structure.