[FEA] BSDG: Investigate build times of synthetic data <-> real data

[jinsolp]

BSDG (Billion Scale Data Generator)

Need to compare the index build times of synthetic data <-> real data

[jinsolp]

Build time Investigation of Vamana graph

Code Snippet

from cuvs.neighbors import vamana

index_params = vamana.IndexParams(
        metric="sqeuclidean",
        graph_degree=64,
        visited_size=256,
        vamana_iters=1,
        alpha=1.2,
        max_fraction=0.06,
    )
index = vamana.build(index_params, device_data)
# serialize and save index, feed into DiskANN

About Vamana Graph

Vamana maintains a directed graph where each node has upto graph_degree out-edges.
Build inserts points one at a time. For each new point it runs BeamSearch of width visited_size from a designated start node to find candidate neighbors, then runs RobustPrune to select upto graph_degree out-edges from those candidates, applying alpha-occlusion to keep edges in diverse directions.
Search runs the same BeamSearch (in DiskANN) with width L and returns the top-K.

RobustPrune terminates in one of three states

1. space-limited: found enough candidates to fill graph_degree slots.
2. candidate-limited: the alpha-occlusion sweep ran out before filling all graph_degree slots. This case means low effective local dimensionality because it means a lot of neighbors are in similar directions
3. pool-starved: BeamSearch couldn't visit enough notes to hand over a proper candidate pool larger than graph_degree to the RobustPrune step.

Gap between Real-Synth

Ran on Falcon 10M.

Difficult to match build times and search recall together. Using SS=100K

• Data geometrics affect build time match, but search recall is affected by graph topology.
• real build time ≈ncomp64 build time >> ncomp16 build time
• ncomp64 recall << ncomp16 recall ≈ real recall

Analyzing the RobustPrune step:

The RobustPrune step shows similar termination breakdowns for the real and ncomp64 cases, making the build times similar.
ncomp16 has a high pool starved and candidate limited termination cases, making each call take a shorter time, resulting in shorter build times than the real data.

Analyzing the Vamana Graph

TLDR; ncomp16 reproduces real's hub topology, contributing to similar recall and search time.

Hub / connectivity structure of the built Vamana graph.

1. In-degree CCDF: in-degrees of nodes sorted from largest to smallest (real has a very large hub)
2. In-degree histogram
3. In-degree key stats. anti-hub is the nodes with in-degree=0
4. out-degree histogram: Bounded by graph_degree=64. ncomp16 saturates least, which is consistent with ncomp16's pool starvation
5. out-degree key stats: for ncomp16, RobustPrune only fills 41% of nodes to the graph_degree cap. However recall still matches real, showing pool starvations isn't a recall bottleneck when a mega hub exists.
6. BFS search curve: Starting from a saved random entry point, real reaches 99% in 5 hops, ncomp16 and ncomp64 both need 6~7 hops.

Analzying the Data

Base's data geometry. For this I sampled 500K based points out of 10M for quick brute force analysis.

1. r_1 nearest neighbor distance: distance to nearest neighbor. ncomp16 is more tightly packed than real and ncomp64
2. Discriminability ratio: ratio of distance of nearest neighbor VS 10-th nearest of 100-th nearest
3. LID: ncomp16's local manifold is lower-dimensional than real or ncomp64's. However, ncomp16 still matches real on graph topology and recall.
4. Radial Profile: CV (std/mean of distance to own centroid)
5. Cluster leakage: fraction of top-10 nearest neighbors that sit in a different KMeans cluster.