Flat & BinaryFlat Indexes
Relevant source files
The following files were used as context for generating this wiki page:
Flat and BinaryFlat indexes in EdgeVec provide a brute-force approach to vector similarity search, serving as a baseline for performance and accuracy. Unlike graph-based methods like HNSW Index Layer, these indexes perform exhaustive scans of the dataset to find the nearest neighbors, ensuring 100% recall at the cost of O(n) search complexity.
The project utilizes these indexes primarily for small-to-medium datasets (typically <100k vectors) or in scenarios where the overhead of graph construction is undesirable. They are optimized using SIMD instructions where available and support both standard 32-bit floating-point vectors and highly compressed binary vectors.
Sources: README.md:16-30, examples/browser/binary-test.html:565-575, GATE_1_COMPLETE.md:120-130
Architecture and Components
The Flat index system is built upon a storage-centric architecture where vector data is laid out contiguously in memory to facilitate fast sequential access.
Core Structures
The implementation revolves around two primary variations:
- Flat Index: Stores vectors as
f32arrays, optimized for L2 and Cosine similarity. - BinaryFlat Index: Stores vectors as bitsets (using
Uint8Arrayin JS/WASM or bit-packed representations in Rust), optimized for Hamming distance.
The diagram shows the relationship between the index high-level types and the underlying storage layer.
Sources: GATE_1_COMPLETE.md:120-135, examples/browser/binary-test.html:580-600
Logic and Data Flow
When a search is initiated, the index iterates through every non-deleted vector in the VectorStorage. For each vector, it calculates the distance using the configured metric and maintains a priority queue (or a sorted list) of the top-k results.
Exhaustive search logic used by Flat indexes to ensure 100% recall.
Sources: src/index/flat.rs, examples/browser/binary-test.html:840-860
Key Features and Metrics
| Feature | Description | Complexity |
|---|---|---|
| Exhaustive Scan | Scans every vector in the storage for the query. | O(n) Search |
| O(1) Insert | Vectors are appended to an arena-based contiguous layout. | O(1) Insert |
| Binary Quantization | Supported via BinaryFlat, offering 32x memory reduction. | O(n/32) Distance |
| SIMD Acceleration | Uses f32x4 or bitwise SIMD for distance calculations. | 2x-8x Speedup |
| Recall | Guarantees perfect accuracy as no approximation is used. | 100% |
Sources: README.md:130-150, examples/browser/binary-test.html:1050-1070, GATE_1_COMPLETE.md:150-160
Implementation Details
Binary Quantization (BQ) in Flat Indexes
In the BinaryFlat variant, vectors are represented as bits. The distance calculation is performed using the Hamming distance, which is significantly faster than floating-point metrics due to the use of XOR and popcount operations.
- Memory Savings: A 1024-dimensional vector is reduced from 4096 bytes (FP32) to 128 bytes (Binary).
- Throughput: SIMD-accelerated Hamming distance can reach over 40 GiB/s for bitwise operations.
Sources: README.md:155-170, examples/browser/binary-test.html:1075-1090
Performance Benchmarks
EdgeVec includes specific benchmarks comparing Flat and HNSW indexes. While Flat indexes are slower for large datasets, they outperform HNSW in terms of insertion speed and memory overhead for smaller sets.
| Dataset Size | Flat Search (ms) | HNSW Search (ms) | Notes |
|---|---|---|---|
| 1k (768D) | ~0.15ms | ~0.38ms | Flat is faster due to low overhead |
| 10k (768D) | ~1.2ms | ~0.94ms | HNSW begins to excel |
| 100k (768D) | ~12.0ms | ~1.5ms | HNSW is significantly faster |
Sources: wasm/examples/benchmark-dashboard.html:1050-1070, examples/browser/binary-test.html:1030-1050
Configuration Options
Flat indexes are configured via EdgeVecConfig. Key parameters influencing the Flat index behavior include:
| Parameter | Type | Default | Description |
|---|---|---|---|
indexType | JsIndexType | Flat | Set to JsIndexType.Flat for exhaustive search. |
dimensions | usize | (Required) | The length of the vectors to be indexed. |
metricType | MetricType | L2 | Valid: L2, Cosine, Hamming (Binary only). |
vector_type | VectorType | Float32 | Set to Binary for BinaryFlat functionality. |
Sources: examples/browser/binary-test.html:585-610, README.md:180-195
Conclusion
Flat and BinaryFlat indexes provide a robust foundation for vector search in EdgeVec. By leveraging contiguous arena allocation and SIMD-optimized exhaustive scans, they offer a high-performance alternative to graph-based indexing for datasets where 100% recall is required or where dataset size is small enough that graph maintenance overhead outweighs the search benefits.