ETD

• Approximate Nearest Neighbor Search
• Graph Compression and Reordering
• Hierarchical Navigable Small World

This thesis studies lossless compression of HNSW graph indexes for Approximate Nearest Neighbor Search, focusing on reducing the memory cost of adjacency lists and related metadata without changing the graph topology or the search algorithm. The work evaluates fixed-width and gap-based encodings, introduces a StreamVByte-based adjacency layout with efficient random access, and shows that compressing offsets with Elias–Fano can reduce memory traffic enough to offset succinct decoding costs in large-scale settings.
A structure-aware preprocessing step based on Enhanced Graph Bisection (EGB) is analyzed to improve locality and boost compression effectiveness. Experiments on standard 1M benchmarks and on the 8M-vector cocondenser dataset quantify space–time trade-offs using bits/edge, index size, and average query latency, with recall always matching the uncompressed baseline.