How mchatzakis/daisy works
1. What this repo is
DaiSy is a C++-first library for exact similarity search over data series and vectors, with optional Python bindings. The repo is organized as a layered system: core search algorithms in lib/, shared loaders/utilities in commons/, runnable examples in demos/, performance harnesses in benchmark/, and correctness checks in tests/.
2. Core library boundary
The central API lives under lib/, with lib/daisy.hpp acting as the main umbrella include. The key abstraction is SimilaritySearchAlgorithm, which is implemented by multiple algorithms and consumes a DataSource-style input model. This is the part that other components build on.
3. Algorithm subsystem
The main algorithm implementations are:
- Bruteforce
- LbBruteforce (adds lower-bound pruning)
- Messi
- ParIS
- Sing
- Odyssey
These live in lib/algos/ and represent different execution environments: in-memory CPU, disk-oriented, GPU-accelerated, and distributed.
4. Indexing and search primitives
The lib/isax/ subtree provides SAX/iSAX-based indexing and search structures, including iSAXIndex, iSAXSearch, priority queue utilities, and SAX conversion/breakpoints. This is the internal indexing layer used by the higher-level algorithms that need symbolic indexing or candidate pruning.
5. Distance computation layer
lib/distance_computers/DistanceComputer.* is the boundary for distance metrics used by the algorithms. The repository clearly supports at least L2-square and DTW flows, and the demos/tests are split along those two metric families. This layer is what allows the same search framework to be reused across different distance functions.
6. Optional execution backends
Two major optional technology boundaries affect architecture:
- lib/algos/odyssey/ and lib/algos/hodyssey/ are the distributed/MPI-oriented Odyssey implementations.
- lib/algos/singlib.cu and singlib.hpp are the CUDA/GPU path for SING.
These are enabled or disabled at build time, so they are not always part of the deployed binary.
7. Shared utility and data-loading layer
commons/ contains reusable code for vector loading, parameter setup, benchmark/test helpers, and common definitions. This is the glue between raw binary datasets, algorithm objects, and the runnable front-ends. It likely handles reading the binary files in data/ and shaping them into the format expected by the search algorithms.
8. Demo applications as integration front-ends
demos/ contains paired C++ and Python examples for each algorithm and metric combination, such as demo_Messi_L2Square or demo_bruteforce_DTW. These are the clearest end-to-end data flow examples in the repo: load data/query sets, configure the algorithm, run search, and print ranked results. They also demonstrate the Python interface alongside the native C++ path.
9. Benchmarking subsystem
benchmark/ provides Google Benchmark-based performance tests for the same algorithms, including a Faiss comparison (bm_FaissFlat_L2Square.cpp). This subsystem is for throughput/latency evaluation rather than correctness, and it reuses shared benchmark helpers in benchmark/bm_utils.* plus the common loaders/parameter setup code.
10. Correctness and ground truth
tests/ focuses on validating algorithm outputs against stored ground truth artifacts in tests/groundtruth/. The repo includes precomputed expected indices and distances for different datasets and k values. Separate test files exist per algorithm/metric, which suggests output comparison is a major verification boundary.
11. Ground truth generation and external dependencies
scripts/groundtruth/ contains Python tooling to generate baseline results, including integrations with FAISS and tslearn. This is important architecturally because correctness data is produced outside the core C++ runtime and then checked into the repo for repeatable tests.
12. Python packaging and bindings
pybinds/ contains the binding build entry point, while setup.py, pyproject.toml, and MANIFEST.in indicate standard Python packaging. The repo supports both source builds and pip distribution, so the Python layer is not a separate implementation—it is a binding surface over the C++ core.
13. Build, CI, and repo orchestration
The top-level CMake build drives the native targets across lib/, demos/, benchmark/, and tests/. GitHub Actions under .github/workflows/ provide CI. The README’s build flags show the major compile-time boundaries: Python, benchmarks, tests, demos, MPI/Odyssey, and CUDA/SING.
14. How the data flows
The typical flow is: binary datasets in data/ or external inputs are loaded by commons/ helpers, passed into a selected algorithm in lib/algos/, which uses distance computation and, when needed, iSAX indexing. Results are then consumed by demos, benchmark harnesses, or tests. Ground truth flows in the opposite direction: external scripts generate reference outputs, which are stored under tests/groundtruth/ and used to validate the core library.
Main entry points: SimilaritySearchAlgorithm.hpp Search API · DistanceComputer.hpp Distance core · CMakeLists.txt Build & CI · common.hpp Commons
Components 19
Core library
C++ search engine and reusable primitives
- daisy.hpp · Main public include for the C++ library
lib/daisy.hpp - Search API · SimilaritySearchAlgorithm and DataSource boundary
lib/algos/SimilaritySearchAlgorithm.hpp - Bruteforce · Exact in-memory brute force search
lib/algos/Bruteforce.hpp - LbBruteforce · Brute force with lower-bound pruning
lib/algos/LbBruteforce.hpp - Messi · Exact search algorithm built on indexing and pruning
lib/algos/Messi.hpp - ParIS · Parallel exact search algorithm
lib/algos/ParIS.hpp - Sing · CUDA-accelerated exact search path
lib/algos/Sing.hpp - Odyssey · MPI-oriented distributed search implementation
lib/algos/odyssey/Odyssey.cpp - iSAX layer · SAX conversion, breakpoints, index structures, and candidate search
lib/isax/iSAXIndex.hpp - Distance core · DistanceComputer boundary for L2-square and DTW flows
lib/distance_computers/DistanceComputer.hpp - Core utils · Shared low-level utilities such as timing and SIMD helpers
lib/utils/TimerManager.hpp
Frontends
Runnable demos and Python bindings
- Commons · Reusable data loading, parameter setup, and benchmark/test helpers
commons/common.hpp - Demos · End-to-end C++ and Python examples for each algorithm and metric
demos/demo_bruteforce_L2Square.cpp - Python bindings · pybind11 setup and Python packaging entry points
pybinds/setup.cpp
Evaluation
Benchmarks, tests, and ground truth
- Benchmarks · Google Benchmark harnesses for algorithms and comparisons
benchmark/bm_utils.cpp - Tests · Algorithm validation against stored ground truth
tests/test_utils.cpp - Ground truth · Checked-in expected indices and distances for validation
tests/groundtruth/Indices/bruteForce_gtDTW_I_astronomy_len256_size50000_q100_k1.txt
Tooling
Build, CI, and data generation support
- GT scripts · Python tooling that generates reference outputs using external libraries
scripts/groundtruth/gt_utils.py - Build & CI · CMake, packaging, and GitHub Actions workflows
CMakeLists.txt
Connections 34
- daisy.hpp → Search API: exports · Umbrella include exposes the public search abstraction
- daisy.hpp → Distance core: exports · Public header surface includes metric computation APIs
- Search API → Bruteforce: implements · Concrete algorithm implementations satisfy the common search interface
- Search API → LbBruteforce: implements · Concrete algorithm implementations satisfy the common search interface
- Search API → Messi: implements · Concrete algorithm implementations satisfy the common search interface
- Search API → ParIS: implements · Concrete algorithm implementations satisfy the common search interface
- Search API → Sing: implements · Concrete algorithm implementations satisfy the common search interface
- Search API → Odyssey: implements · Concrete algorithm implementations satisfy the common search interface
- Bruteforce → Distance core: uses · Baseline exact search depends on the metric boundary
- LbBruteforce → Distance core: uses · Pruning relies on distance bounds and scoring
- Messi → iSAX layer: uses · Messi depends on symbolic indexing and candidate pruning
- Messi → Distance core: uses · Search results are verified with distance computations
- ParIS → Distance core: uses · Parallel search still routes scoring through the shared metric layer
- Sing → Distance core: uses · GPU search path computes exact distances through the shared layer
- Odyssey → Distance core: uses · Distributed search coordinates exact distance evaluation
- Odyssey → Core utils: uses · Distributed execution reuses shared timers and low-level helpers
- Commons → Demos: feeds · Loaders and parameter setup power the example front-ends
- Commons → Benchmarks: feeds · Benchmark harnesses reuse common loaders and setup helpers
- Commons → Tests: feeds · Test code reuses common data and helper utilities
- Demos → Search API: runs · Demo programs instantiate algorithms through the shared API
- Demos → Commons: loads · Demos use common data-loading and parameter setup code
- Python bindings → Search API: binds · Python package exposes the C++ search surface
- Python bindings → Commons: loads · Binding examples and packaging rely on shared support code
- Benchmarks → Search API: measures · Benchmark binaries exercise algorithm implementations
- Benchmarks → Distance core: measures · Performance suites compare metric-specific paths
- Tests → Ground truth: verifies · Correctness checks compare outputs to stored references
- Tests → Search API: exercises · Test binaries invoke algorithms through the common interface
- GT scripts → Ground truth: generates · External Python tooling produces checked-in reference data
- Build & CI → daisy.hpp: builds · CMake and CI coordinate native library builds
- Build & CI → Demos: builds · Build system compiles demo targets
- Build & CI → Benchmarks: builds · Build system compiles benchmark targets
- Build & CI → Tests: builds · Build system compiles test targets
- Build & CI → Python bindings: packages · Packaging and CI support Python distribution flows
- Build & CI → GT scripts: orchestrates · Repo tooling supports generating and refreshing references