How tamimehsan/khorgosh works
1. Project shape
- This is a mostly header-first C++ library for RaBitQ quantization and approximate nearest neighbor search, with Python bindings, sample apps, tests, and documentation.
- The root build is driven by CMake, with a separate pyproject.toml for the Python package surface.
2. Core algorithm layer: RaBitQ quantization
- The main quantization logic lives under include/rabitqlib/quantization/.
- Key responsibilities here are:
- converting dense vectors into compact RaBitQ codes,
- storing packed/extracted code layouts,
- implementing the low-level RaBitQ estimator and its internal mechanics.
- This is the foundation used by all search/index layers.
3. Distance and similarity estimation
- include/rabitqlib/index/estimator.hpp, lut.hpp, and query.hpp provide the query-time machinery for computing approximate Euclidean distance, inner product, and cosine similarity from quantized data.
- This layer is the boundary between “encoded vectors” and “search results”: it takes query vectors plus codes/LUTs and produces ranking scores.
4. Vector search index integrations
- The library contains three search/index subsystems under include/rabitqlib/index/:
- IVF in index/ivf/
- HNSW in index/hnsw/
- Symmetric QG in index/symqg/
- These indexes all reuse RaBitQ codes, but differ in how candidates are generated and traversed during query execution.
5. IVF subsystem
- The IVF implementation (ivf.hpp, cluster.hpp, initializer.hpp) is responsible for clustering vectors into coarse buckets and routing queries to a subset of candidates.
- This is the “coarse pruning” search path: first narrow by centroid/cluster structure, then use RaBitQ-based scoring on candidates.
6. HNSW subsystem
- The HNSW integration (index/hnsw/hnsw.hpp) wraps graph-based nearest-neighbor search around RaBitQ-coded data.
- It depends on the vendored hnswlib implementation under include/rabitqlib/third/hnswlib/, which forms an external algorithm boundary inside the repository.
7. QG / symmetric quantization path
- index/symqg/qg.hpp and qg_builder.hpp implement the QG pathway described in the README.
- Architecturally, this path trades extra memory for better access patterns and faster querying by building multiple quantized representations per vector.
8. FastScan acceleration
- include/rabitqlib/fastscan/ contains FastScan-oriented query acceleration, including a higher-accuracy variant.
- This is the main performance-oriented sublayer for distance estimation from compact codes, used when bitwise/LUT-style scanning is preferable to full raw-vector access.
9. Utility and runtime support
- include/rabitqlib/utils/ contains shared infrastructure used across the library:
- vector/memory helpers,
- I/O and buffering,
- stopwatches,
- hashing/visited-set utilities,
- rotation/FHT helpers,
- space/distance abstractions.
- These are cross-cutting support modules rather than user-facing algorithms.
10. Third-party dependencies are vendored
- The repository vendors Eigen and hnswlib under include/rabitqlib/third/.
- That means core compilation does not rely on those being installed system-wide; they are part of the repo’s source boundary.
11. Python surface
- Python support is split into two parts:
- python_bindings/ provides native bindings for the C++ library,
- python/ contains thin Python helpers/utilities such as I/O helpers and IVF-facing code.
- The binding modules mirror the native subsystems: rabitq, ivf, hnsw, and symqg.
12. Build and packaging boundary
- python_bindings/CMakeLists.txt and the top-level CMakeLists.txt define the native build.
- pyproject.toml indicates the repo can also be treated as a Python-distributed package, but the core architecture remains C++-centric.
13. Samples show the intended data flow
- sample/cpp/ and sample/python/ demonstrate the same pipeline in both languages:
- build/initialize index,
- quantize dataset vectors,
- execute queries,
- optionally rerank or evaluate recall.
- The sample names make the primary flows explicit: *_indexing and *_querying for IVF, HNSW, QG, and quantizer demos.
14. Tests cover both primitives and integration edges
- tests/unit/ focuses on utility-level correctness, especially rotation and vector-space helpers.
- tests/integration/ includes bit pack/unpack validation, which is an important architectural boundary because code layout and decoding are central to correctness.
15. Documentation mirrors the architecture
- docs/docs/ is organized by conceptual subsystem: quick start, index types, kernel/IP behavior, and detailed RaBitQ internals.
- The docs structure reflects the code structure: quantization core first, then search/index integrations, then estimator/rotator/reranking details.
16. Overall data flow
- The main runtime flow is: raw vectors → RaBitQ quantization / packing → index-specific organization (IVF/HNSW/QG) → query-time estimation via LUT/FastScan/helpers → top-k candidates and optional reranking.
- The key architectural boundary is that most query-time scoring operates on compact codes, not raw vectors, unless a specific path chooses to rerank or inspect originals.
Main entry points: rabitq.hpp RaBitQ Core · rabitq_bindings.cpp Python Bindings · ivf.hpp IVF Index · index.md Docs Site
Components 27
Core Library
Header-first C++ quantization, estimation, and search primitives.
- RaBitQ Core · Main RaBitQ quantization and packed-code implementation.
include/rabitqlib/quantization/rabitq.hpp - Code Layout · Packed and extracted code representations.
include/rabitqlib/quantization/data_layout.hpp - Pack / Extract · Encode and decode compact RaBitQ layouts.
include/rabitqlib/quantization/pack_excode.hpp - Estimator · Approximate distance and similarity estimation from encoded data.
include/rabitqlib/index/estimator.hpp - Lookup Tables · LUT machinery used by query-time scoring.
include/rabitqlib/index/lut.hpp - Query API · Query-side boundary between codes, scores, and ranking.
include/rabitqlib/index/query.hpp - IVF Index · Cluster-based candidate pruning with RaBitQ scoring.
include/rabitqlib/index/ivf/ivf.hpp - Clustering · Centroid and bucket organization for coarse routing.
include/rabitqlib/index/ivf/cluster.hpp - Initializer · Build-time initialization and setup for IVF structures.
include/rabitqlib/index/ivf/initializer.hpp - HNSW Index · Graph-based ANN search over RaBitQ-coded data.
include/rabitqlib/index/hnsw/hnsw.hpp - SymQG · Symmetric quantized search path with multiple representations.
include/rabitqlib/index/symqg/qg.hpp - QG Builder · Builds the multi-representation QG structures.
include/rabitqlib/index/symqg/qg_builder.hpp - FastScan · Accelerated compact-code distance estimation path.
include/rabitqlib/fastscan/fastscan.hpp - High-Acc Scan · Higher-accuracy FastScan-oriented estimator variant.
include/rabitqlib/fastscan/highacc_fastscan.hpp
Support
Shared utilities and vendored dependencies.
Python Surface
Native bindings and Python helpers.
- Bindings Common · Shared C++ binding glue and type conversions.
python_bindings/bindings_common.hpp - Python Bindings · Native extension entry points for RaBitQ, IVF, HNSW, and SymQG.
python_bindings/rabitq_bindings.cpp - Python Helpers · Thin Python-facing utilities and IVF helpers.
python/ivf.py
Samples
C++ and Python usage flows.
- C++ Samples · End-to-end demos for indexing and querying across subsystems.
sample/cpp/quantizer.cpp - Python Samples · Python demos mirroring the C++ usage flows.
sample/python/utils.py
Validation
Tests covering primitives and integration boundaries.
- Unit Tests · Utility-level correctness checks for shared primitives.
tests/unit/rabitqlib/utils/space_test.cpp - Integration Tests · Boundary tests for packed-code and layout correctness.
tests/integration/bit_pack_unpack_test.cpp
Docs
Conceptual documentation mirrored to the code structure.
- Docs Site · Conceptual documentation organized by subsystem.
docs/docs/index.md
Other components
- CMake Build · Top-level native build plus Python packaging entry points.
CMakeLists.txt - Py Project · Python packaging surface for distributed use.
pyproject.toml
Connections 41
- CMake Build → RaBitQ Core: builds · Compiles the core header library.
- CMake Build → Python Bindings: builds · Builds native Python extension modules.
- CMake Build → C++ Samples: builds · Builds sample applications.
- Py Project → Python Helpers: packages · Defines Python-distributed package surface.
- RaBitQ Core → Code Layout: uses · Relies on code layout representations.
- RaBitQ Core → Pack / Extract: uses · Encodes and decodes compact codes.
- RaBitQ Core → Estimator: feeds · Provides quantized data for query-time scoring.
- Estimator → Lookup Tables: builds · Uses lookup tables for approximate scoring.
- Query API → Estimator: orchestrates · Runs scoring over encoded vectors and queries.
- Query API → FastScan: accelerates · Can use scan-oriented acceleration paths.
- FastScan → High-Acc Scan: variant · Includes a higher-accuracy scanning variant.
- IVF Index → Clustering: routes by · Uses coarse clusters to prune candidates.
- IVF Index → Initializer: initializes · Build-time setup and index construction.
- IVF Index → Query API: scores with · Reuses shared query-time estimation machinery.
- HNSW Index → hnswlib: wraps · Depends on vendored graph-search implementation.
- HNSW Index → Query API: scores with · Uses shared scoring boundary for coded vectors.
- SymQG → QG Builder: built by · Builder constructs the multi-representation index.
- SymQG → Query API: scores with · Uses query-time estimation boundary.
- Python Bindings → Bindings Common: shares glue · Common conversion and binding support.
- Python Bindings → RaBitQ Core: exposes · Exposes RaBitQ to Python.
- Python Bindings → IVF Index: exposes · Exposes IVF search to Python.
- Python Bindings → HNSW Index: exposes · Exposes HNSW search to Python.
- Python Bindings → SymQG: exposes · Exposes SymQG search to Python.
- Python Helpers → IVF Index: supports · Thin Python-side utilities for IVF workflows.
- C++ Samples → RaBitQ Core: demonstrates · Shows quantizer usage and code generation.
- C++ Samples → IVF Index: demonstrates · Shows IVF indexing and querying flow.
- C++ Samples → HNSW Index: demonstrates · Shows HNSW indexing and querying flow.
- C++ Samples → SymQG: demonstrates · Shows SymQG indexing and querying flow.
- Python Samples → Python Helpers: demonstrates · Shows Python-side usage patterns.
- Python Samples → Python Bindings: calls · Exercises the native extension surface.
- Unit Tests → Utilities: verifies · Covers rotation and space helpers.
- Integration Tests → Pack / Extract: verifies · Checks bit pack/unpack correctness.
- Docs Site → RaBitQ Core: documents · Explains quantizer and estimator internals.
- Docs Site → IVF Index: documents · Explains IVF architecture and usage.
- Docs Site → HNSW Index: documents · Explains HNSW integration.
- Docs Site → SymQG: documents · Explains QG path and query behavior.
- Docs Site → FastScan: documents · Covers compact-code acceleration details.
- RaBitQ Core → Utilities: depends on · Uses shared vector, memory, and math helpers.
- Estimator → Utilities: depends on · Uses shared helper abstractions.
- FastScan → Utilities: depends on · Uses shared support utilities.
- RaBitQ Core → Eigen: depends on · Uses vendored linear algebra support.