Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment

• Segments need efficient and accurate HVSS within tight storage and computing limits, while leaving little space for index storage.A single large index can also hinder availability, migration, scaling, load balancing, and fault tolerance.Source: §1 · p. 2
• SPANN can require excessive disk space through vector replication, whereas DiskANN fits segment capacity but suffers high latency from random disk I/Os.Source: §1 · p. 2, Figure 1 · p. 3
• Starling combines a sampled in-memory navigation graph with a reordered disk graph and block search to reduce search-path length and wasted disk bandwidth.Block shuffling groups vertices with neighbors; the search checks block contents and adds potentially useful vertices.Source: §1 · p. 3
• 43.9× higher throughput and 98% lower query latency than state-of-the-art methods at the same accuracy are reported for Starling.Source: §1 · p. 4
• The paper formulates block shuffling as NP-hard and proposes three heuristic shuffling algorithms, plus computation-specific optimizations and ANNS and range-search algorithms.Source: §1 · p. 4
• Starling is presented as a framework that improves the efficiency of graph-index algorithms, including Vamana, NSG, and HNSW, on a data segment.Source: §1 · p. 4

2 PRELIMINARIES

• The preliminaries identify nearest-neighbor and range-search queries as the two critical vector-database query types addressed in the paper.Source: §2 · p. 4

2.1 Two Query Types for HVSS

• KNNS seeks the k closest vectors, ANNS approximates that result and uses recall to measure accuracy, while range search returns vectors within radius r and uses average precision.Source: §2.1 · pp. 4–5

2.2 HVSS on Data Segment.

• Segments may have less than 2GB of memory and under 10GB of disk capacity; SPANN’s vector replication can exceed that space, while DiskANN requires disk I/O per vertex access.Source: §2.2 · p. 5

2.3 Our Optimization Objective

• The paper sets the objective as improving disk-resident graph search efficiency without adding memory or disk space overhead.It identifies I/O time as the dominant search-time factor, reporting that DiskANN’s I/O reaches 92.5% of total search time on BIGANN.Source: §2.3 · pp. 5–6

3.1 I/O-efficiency Analysis

• I/O efficiency depends on useful-vertex utilization per disk block and the number of hops from entry point to result.The baseline wastes up to 94% of data read and can require hundreds of hops even for top-10 search on datasets of tens of millions of vectors.Source: §3.1 · pp. 6–7
• The baseline groups ID-consecutive vertices rather than graph neighbors, wasting bandwidth, and its fixed or random entry point can lengthen the search path.Source: §3.1 · pp. 6–7

3.2 Framework Overview

• Starling shuffles disk blocks according to graph topology so a read can fetch the target vertex and likely neighbor candidates together.This increases useful vertices per I/O and may reduce the number of disk reads.Source: §3.2 · p. 7
• A sampled in-memory navigation graph finds query-close vertices to use as disk-search entry points, reducing the disk graph’s search path.Source: §3.2 · p. 7
• Block search examines every vertex in a loaded block, selecting close vertices and checking their neighbors, trading more computation for lower disk-operation cost.In the illustrated example, the reordered layout reduces disk I/Os from at least six to three; starting from a navigation-graph entry point takes two.Source: §3.2 · pp. 7–8

4.2 In-Memory Navigation Graph

• Starling samples segment data to build a memory-resident navigation graph that returns query-aware entry points and reduces the disk search path length.The sampled subset contains less than 10% of the segment’s vertices.Source: §4 · p. 8, §4.2 · p. 13

4.1 Block Shuffling on the Disk

• DiskANN’s overlap ratio is close to 0 on 33 million BIGANN vectors, indicating poor locality in its disk layout.A layout with optimal locality has overlap ratio 1.Source: §4.1 · p. 9
• Block shuffling is NP-hard and has no polynomial-time approximation algorithm with a finite factor unless P=NP.The goal is to maximize overlap ratio while assigning vertices to disk blocks.Source: §4.1 · p. 9
• BNP, BNF, and BNS all improve overlap ratio over the original layout; BNS improves it most, while BNF balances efficiency and effectiveness.BNP is fastest; BNS guarantees overlap ratio does not decrease across iterations, and BNF does not guarantee convergence.Source: §4.1 · pp. 11–12

5.1 Block Search

• Block search explores vertices in each loaded block, updates query-distance results, and expands neighbor IDs of closer vertices; pruning checks only the top-((ε−1)·σ) vertices.The evaluated pruning ratio σ=0.3 is reported as optimal for better performance.Source: §5.1 · p. 13
• Starling overlaps disk reads with distance computation and uses PQ short codes to estimate distances for neighbors without additional disk I/Os.The authors report that the I/O and computation pipeline reduces query latency significantly.Source: §5.1 · pp. 13–14

5.2 Approximate Nearest Neighbor Search

• For approximate nearest-neighbor search, Starling starts from navigation-graph entry points, explores the closest unvisited candidate’s block, and returns the top-k results ranked by exact distance.PQ short codes rank candidates approximately before final sorting with full-precision vectors.Source: §5.2 · p. 14

5.3 Range Search

• Range search dynamically expands its candidate-set limit when the result-to-candidate ratio is high, then resumes using saved results, candidates, and closer kicked-out vertices.This continuation avoids extra computation and disk access; the evaluation reports φ=0.5 as optimal.Source: §5.3 · p. 15

6.2 Search Performance

• At Recall=0.95 on BIGANN, Starling took 5ms versus DiskANN's 10ms and SPANN's 50ms; at AP=0.9, it was 43.9× faster than DiskANN.The RS comparison reports up to 98% lower latency than DiskANN at the same AP.Source: Figure 6 · p. 17, Figure 7 · p. 17, Figure 4 · p. 17

6.3 I/O-efficiency

• Starling improves both measured I/O-efficiency factors over DiskANN: it loads more relevant vertices per block and takes a shorter search path.Block shuffling improves vertex utilization, while query-aware entry points from the in-memory navigation graph shorten the path.Source: Table 2 · p. 17, §6.3 · pp. 17–18

6.4 Index Cost

• On BIGANN, Starling's shuffling and in-memory graph construction together take less time than DiskANN's hot-vertex acquisition, while Starling also has lower memory overhead and equal disk cost.The disk-based graph and PQ preprocessing times are equal for the two frameworks.Source: Figure 8 · p. 18, §6.4 · pp. 18–19

6.5 Ablation Study

• On BIGANN, the in-memory graph reduces disk I/Os by about 20% at the same Recall, while block pruning improves QPS by skipping distant, non-neighbor vertices.The I/O-computation pipeline raises QPS at the same Recall; PQ-based approximate-distance ranking reduces disk I/Os while maintaining accuracy.Source: Figure 10 · p. 19, §6.5 · pp. 19–20, Figure 11 · p. 19

6.6 Parameter Sensitivity

• Across thread settings from 4 to 16, Starling's QPS is twice DiskANN's while Recall remains constant; Starling also has higher QPS across tested k and search-radius values.The thread and k evaluations use BIGANN; the radius comparison also reports Starling outperforming DiskANN across tested radii.Source: Figure 13 · p. 20, Figure 14 · p. 21

6.7 Scalability

• Starling maintains higher QPS across varying segment sizes and outperforms DiskANN with NSG and HNSW graph indexes as well as Vamana.Starling-HNSW's QPS is over 2× Disk-HNSW's; the segment-count evaluation reports Starling outperforming DiskANN for both ANNS and RS at equivalent accuracy.Source: Figure 16 · p. 21, §6.7 · p. 21, Figure 15 · p. 21

6.8 In- and Not-in-Database Queries; 6.9 Evaluation on Other Segment Setups

• Starling outperforms DiskANN on both in-database and not-in-database queries, and it outperforms rival methods across tested disk capacities and dataset sizes.In-database queries achieve higher throughput than not-in-database queries for both frameworks; the performance gap grows with dataset size.Source: Figure 17 · p. 22, §6.8 · p. 22, §6.9 · p. 22

6.10 Large-scale Search Results; 6.11 Evaluation on Billion-scale Data

• At k=5,000 and Recall=0.99, Starling saves more than 20,000 disk I/Os per query; on billion-scale data, it is over 2× faster than DiskANN when Recall exceeds 0.96.The billion-vector evaluation splits BIGANN into 31 segments, each with 2GB memory and 10GB disk.Source: §6.10 · p. 22, §6.11 · p. 22, Figure 19 · p. 23

Memory-based related work

• Memory-based graph methods offer strong efficiency–accuracy trade-offs but require raw vectors and graph indexes in memory, increasing memory use and limiting large-scale scalability.Starling can integrate graph algorithms such as HNSW into its disk-index component.Source: §7 · p. 23

Comparison analysis with SPANN

• Unlike SPANN’s k-means clusters, Starling uses an in-memory graph to shorten graph-search paths and block shuffling to improve disk locality; block shuffling achieves 12× the overlap ratio of k-means assignment on SSNPP.The in-memory graph guides query routes rather than caching frequently accessed data; the discussion also reports better search performance and memory overhead than the baseline hot-points strategy.Source: §7 · p. 23

Central assumption; Data update

• Starling retains simultaneous fetching of multiple SSD blocks per round-trip while improving vertex utilization within each loaded block to reduce total query I/Os.For updates, the described database-level approach keeps dynamic data in an incremental in-memory index and asynchronously merges it into the static disk index, requiring index reconstruction.Source: §7 · p. 24

Applications of range search (RS)

• Range search is used in applications including face recognition and near-duplicate detection, and can follow ANNS to retrieve results around seed vertices using similarity thresholds.The discussion notes that several vector databases and memory-based works support both ANNS and range search on the same dataset.Source: §7 · p. 24

8 CONCLUSION

• Starling targets HVSS on vector-database data segments, where accuracy, efficiency, memory use, and disk capacity must be considered together.The conclusion identifies the data segment as an essential vector-database component.Source: §8 · p. 24
• Starling uses a disk-based graph index and optimizes data layout and search strategy to reduce costly disk I/O operations.The conclusion characterizes the resulting space overhead as small.Source: §8 · p. 24
• Experiments show significant performance improvements over state-of-the-art methods while maintaining small space overhead; future work includes cache and GPU optimizations and Milvus integration.Source: §8 · p. 24

A PROOF OF THEOREM 4.1

• The reduction constructs a graph with a clique of size α_i for each input integer, yielding a graph of polynomial size ρ·Ω under the stated bounds.The triple-shuffling instance has t=3·ρ integers, each strictly between Ω/4 and Ω/2.Source: A PROOF OF THEOREM 4.1 · p. 28
• Block shuffling is NP-hard because a layout attaining the largest overlap ratio corresponds exactly to grouping the integers into triples summing to Ω.Each block represents three cliques whose sizes sum to Ω, and each clique size maps to an integer.Source: A PROOF OF THEOREM 4.1 · p. 28
• A finite-factor polynomial-time approximation for block shuffling would decide triple shuffling, so no such approximation exists unless P=NP.The argument distinguishes layouts attaining the maximum overlap ratio from those below it, a distinction the proof states is NP-hard to check.Source: A PROOF OF THEOREM 4.1 · p. 28

B DISK-BASED GRAPH INDEX METHOD

• Disk blocks hold multiple vertices’ adjacency lists and vector data, allowing one disk access to read both for a vertex.The described example stores four vertices per block, and accessing any vertex loads the entire block into memory.Source: B DISK-BASED GRAPH INDEX METHOD · p. 28
• Greedy vertex search starts at an entry vertex and repeatedly visits neighbors, selecting a closer candidate until none is closer; the illustration’s path is 8, 5, 2, 15, then 3.The example uses a priority queue to maintain candidate vertices.Source: B DISK-BASED GRAPH INDEX METHOD · p. 28, Figure 20 · p. 29
• With vertex utilization ratio ξ, block capacity ε, out-degree o, and path length ℓ, the stated I/O complexity is O((o·ℓ)/(ξ·ε)); the described current method has ξ·ε=1 and average complexity O(o·ℓ).The passage says disk I/O is the main cost of disk-based vector search; keeping compressed vectors in memory can skip some disk accesses but trades accuracy for efficiency.Source: B DISK-BASED GRAPH INDEX METHOD · p. 29

C PARAMETERS OF BNF

• BNF’s overlap ratio stabilizes after a few iterations; τ=0.01 and β=8 are the reported defaults, balancing overlap gains against processing time.The passage reports that smaller τ raises overlap ratio but takes more time, while increasing β raises time sharply as overlap ratio grows slowly; Tables 5 and 6 report overlap ratio and execution time, respectively.Source: C PARAMETERS OF BNF · p. 29, Table 5 · p. 30, Table 6 · p. 30
• The BNF parameter evaluation uses BIGANN vectors of 128 dimensions, 4 KB blocks, and a maximum of 12 vertices per block under the stated graph settings.The passage specifies maximum neighbors Λ=48 and 64 threads for block shuffling; Table 4 is identified as reporting block counts and edge counts across dataset volumes.Source: C PARAMETERS OF BNF · p. 29, Table 4 · p. 30

D BNF EVALUATION ON DATA SEGMENT

• BNF uses β=8 by default for the reported data-segment evaluation.The authors select this setting as an efficiency–efficacy balance.Source: D BNF EVALUATION ON DATA SEGMENT · p. 30

E BNS ALGORITHM

• BNS has time complexity O(β·o^3·ε·|V|), or O(β·o^2·ε·|E|), for β iterations.Here o is the average out-degree and ε is the number of vertices in a block.Source: E BNS ALGORITHM · p. 30

F BNF VS. BNS

• BNS achieves better OR(G) with fewer iterations, but its slower iterations make it impractical on larger datasets.The authors leave speeding up BNS for future work and use BNF by default.Source: F BNF VS. BNS · p. 31

G GRAPH PARTITIONING EVALUATION

• BNF outperforms three graph-partitioning methods in both time and OR(G) across the tested datasets.The authors attribute the mismatch to graph partitioning’s social-network targets versus proximity graphs’ navigation and similarity edges.Source: G GRAPH PARTITIONING EVALUATION · p. 32

H BLOCK SHUFFLING COST

• Block shuffling takes 3%–12% of disk-based graph construction time across the four reported datasets.The evaluation reports disk-graph construction and shuffling times in Table 13.Source: H BLOCK SHUFFLING COST · p. 32, Table 13 · p. 32

J IN-MEMORY NAVIGATION GRAPH VS. CACHING HOT VERTICES

• Compared with caching hot vertices, the in-memory navigation graph performs better at Recall 0.90–0.97 and uses less memory at Recall 0.99.The performance difference is small above Recall 0.97; the navigation graph stores a lightweight index on sampled data.Source: Figure 22 · p. 33, Figure 23 · p. 34, Table 15 · p. 34

I PARAMETERS OF IN-MEMORY NAVIGATION GRAPH

• As the navigation-graph sample ratio μ increases, Recall and QPS rise, but memory overhead also grows.The authors attribute the search gains to closer entry points that can reduce disk I/Os and improve the chance of finding true nearest vectors.Source: I PARAMETERS OF IN-MEMORY NAVIGATION… · p. 33, Table 14 · p. 33

K PRUNING RATIO FOR BLOCK PRUNING

• On BIGANN, pruning ratio σ=0.3 is optimal; higher σ reduces Mean I/Os but eventually lowers QPS at the same Recall through redundant computation.The reported QPS decline occurs as σ exceeds a threshold between 0.3 and 0.5.Source: K PRUNING RATIO FOR BLOCK PRUNING · p. 34

L PARAMETERS FOR INDEX PROCESS; M PARAMETERS FOR SEARCHING; P MAIN PARAMETERS OF SPANN AND DISKANN

• Parameter choices trade accuracy against resources: larger Λ increases index size and construction time, while larger Γ improves accuracy but slows search and uses more memory.The text also describes SPANN’s replication, posting-list, and pruning parameters, and DiskANN’s graph, candidate-set, PQ-memory, and hot-vertex parameters.Source: L PARAMETERS FOR INDEX PROCESS · p. 34, M PARAMETERS FOR SEARCHING · p. 36, P MAIN PARAMETERS OF SPANN AND DISKANN · pp. 37–38

N MEMORY COST AND SEARCH PERFORMANCE

• Starling has lower memory overhead and higher QPS than DiskANN at higher Recall in the reported memory-cost comparison.The segment memory limit is 2 GB; Starling stores a navigation graph, PQ short codes, and vertex-to-block mappings.Source: N MEMORY COST AND SEARCH PERFORMANCE · p. 36, Table 19 · p. 36

O RELATED WORK

• Graph-based methods commonly require both vectors and graph indexes in memory; Starling instead combines a disk-based graph with block shuffling and a sampled in-memory navigation graph.The related-work discussion says Starling addresses search optimization within data segments, which prior distributed vector-database work ignores.Source: O RELATED WORK · pp. 36–37

Q DIFFERENT SEGMENT AND DATA SIZE SETUPS

• Starling consistently has lower Mean I/Os than DiskANN and SPANN across the tested disk capacities and dataset sizes, with its gain increasing as dataset size grows.The comparisons use a fixed 4GB dataset while varying disk capacity, and fixed 2GB memory plus 32GB disk while varying dataset size from 4GB to 16GB.Source: Q DIFFERENT SEGMENT AND DATA SIZE SETUPS · p. 38
• For SPANN, larger datasets limit data duplication and result in numerous Mean I/Os.Source: Q DIFFERENT SEGMENT AND DATA SIZE SETUPS · p. 39

R EVALUATION ON 341M DEEP DATASET

• Up to 56% higher QPS than DiskANN at Recall > 0.96 on the 341M DEEP dataset split across 31 segments.Each segment had 2GB memory and 10GB disk; both systems used the same setting, and results were merged across segments.Source: R EVALUATION ON 341M DEEP DATASET · p. 39

S DISCUSSION ON DATA LOCALITY

• Vector graph indexes make data locality challenging because similar, long-link neighbors with uniform degree may be scattered across clusters.The HNSW paper reports this scattering.Source: S DISCUSSION ON DATA LOCALITY · p. 39
• Relational databases achieve locality by partitioning related data into clusters and storing it in the same disk sector.Source: S DISCUSSION ON DATA LOCALITY · p. 39
• Real-world graph engines such as Pregel and Ligra exhibit locality because power-law degree distributions make neighbors tend to cluster.Source: S DISCUSSION ON DATA LOCALITY · p. 39