Skip to content

readme.md

Latest commit

 

History

History
193 lines (140 loc) · 7.82 KB

readme.md

File metadata and controls

193 lines (140 loc) · 7.82 KB
Raw

Dynamic Exploration Graph (DEG)

High-throughput approximate nearest neighbor and exploratory search library implementing continuous edge optimization and dynamic stream indexing (MMM '25, ICMR '24).

CI Build & Tests Paper Documentation PyPI License GitHub stars
  • C++20 header-only library with native Python bindings (deglib)
  • Dynamic streaming: Incremental addition, removal, and continuous edge optimization
  • Multi-threaded construction and batch vector search with SIMD acceleration (AVX2, AVX-512)
  • Supported data types: float32, uint8, float16, evp-bits
  • Supported metrics: Euclidean ($L_2$), Inner Product / Cosine, quantized EVP
  • Exploratory graph traversal and label-filtered nearest neighbor search
  • Compact graph serialization and lightweight read-only deployment mode

Getting Started

Python

Install the module via pip:

pip install deglib

Build a search graph and query nearest neighbors:

import numpy as np
import deglib

# 10,000 vectors with 128 dimensions
data = np.random.randn(10_000, 128).astype(np.float32)
query = np.random.randn(128).astype(np.float32)

# 1. Build search index directly from data
graph = deglib.builder.build_from_data(data, metric=deglib.Metric.FP32_L2)

# 2. Search top-10 nearest neighbors
indices, distances = graph.search(query, k=10, eps=0.1)


print("Top-10 neighbor IDs:", indices)
print("Distances:", distances)

# 3. Save graph for serving
graph.save_graph("index.deg")

For more Python examples, check the examples/ directory or read the Official Documentation.

C++

deglib is a header-only C++20 library. Simply add the cpp/deglib/include directory to your project:

#include <deglib/deglib.h>
#include <iostream>
#include <vector>
#include <random>

int main() {
    const uint32_t num_vectors = 10'000;
    const uint32_t dims = 128;

    // Generate example feature dataset
    std::mt19937 rng(42);
    std::uniform_real_distribution<float> dist(0.0f, 1.0f);
    std::vector<float> dataset(num_vectors * dims);
    for (auto& val : dataset) val = dist(rng);

    // Build graph index directly from data
    auto graph = deglib::build_from_data(
        std::span<const float>(dataset),
        dims,
        /*labels=*/{},
        /*edges_per_vertex=*/32,
        deglib::distances::Metric::FP32_L2
    );

    // Query top-10 nearest neighbors
    std::vector<float> query(dims);
    for (auto& val : query) val = dist(rng);

    auto results = graph.search(std::span<const float>(query), /*k=*/10, /*eps=*/0.1f);

    for (const auto& match : results) {
        std::cout << "Label: " << match.getIdentifier() 
                  << " | Distance: " << match.getDistance() << "\n";
    }
}

For full C++ build instructions, CMake presets, and architecture details, refer to the cpp/ README.

Repository Structure

DynamicExplorationGraph/
├── cpp/          # High-performance C++20 Header-Only library, CMake Presets, Tests & Benchmarks
├── python/       # Python Bindings (deglib), Pytest Suite & Wheel Build Configuration
├── examples/     # Ready-to-run Python examples (knng, dynamic_data, static_data, mips)
├── java/         # Java implementation & Benchmarks
└── docs/         # Sphinx / ReadTheDocs Documentation

Performance

Approximate Nearest Neighbor Search (ANNS): Querying unindexed vectors across various graph exploration margins ($\epsilon$).
ANNS QPS vs Recall

Exploratory Search (Indexed Queries): Navigating from existing indexed vertices to discover immediate neighbor clusters. Exploration QPS vs Recall

Datasets & Pre-built Graphs

The following standard datasets and pre-built graph files are supported in benchmarks and examples:

Dataset Dimension Base Vectors Query Vectors Pre-built Graph Reference
SIFT1M 128 1,000,000 10,000 sift_128D_L2_DEG30.deg Texmex
DEEP1M 96 1,000,000 10,000 deep1m_96D_L2_DEG30.deg PPUDA
GloVe-100 100 1,183,514 10,000 glove_100D_L2_DEG30.deg Stanford GloVe
Audio 192 53,387 200 Auto-generated Princeton CASS
Enron 1,369 94,987 200 Auto-generated CMU Enron

Note

When executing benchmarks or Python examples, datasets are automatically downloaded and prepared on first run.

Citation

If you use the library in an academic context, please consider citing our papers:

Hezel, N., Barthel, K.U., Schilling, B., Schall, K., Jung, K. Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets. MultiMedia Modeling (MMM 2025): 333–347.

@article{Hezel2025,
  author    = {Hezel, Nico and Barthel, Uwe Kai and Schilling, Bruno and Schall, Konstantin and Jung, Klaus},
  title     = {Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets},
  booktitle = {MultiMedia Modeling},
  publisher = {Springer Nature},
  pages     = {333--347},
  isbn      = {978-981-96-2054-8},
  year      = {2025}
}

Hezel, N., Barthel, K.U., Schall, K., Jung, K. An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval. Proceedings of the 2024 International Conference on Multimedia Retrieval (ICMR '24): 657–665.

@inproceedings{Hezel2024,
  author    = {Hezel, Nico and Barthel, Uwe Kai and Schall, Konstantin and Jung, Klaus},
  title     = {An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval},
  booktitle = {Proceedings of the 2024 International Conference on Multimedia Retrieval},
  publisher = {Association for Computing Machinery},
  pages     = {657--665},
  isbn      = {9798400706196},
  doi       = {10.1145/3652583.3658117},
  series    = {ICMR '24},
  year      = {2024}
}

License

DEG is available under the MIT License.