HIBF

This library contains the HIBF and layout algorithm.

Quick start

To use the HIBF lib in your app:

include (FetchContent)
FetchContent_Declare (
    hibf_fetch_content
    GIT_REPOSITORY "https://github.com/seqan/hibf"
    GIT_TAG "main")
option (INSTALL_HIBF "" OFF)
FetchContent_MakeAvailable (hibf_fetch_content)

# ...

target_link_libraries (<your_app> PUBLIC seqan::hibf)

A quick overview on how to use the HIBF lib:

// SPDX-FileCopyrightText: 2006-2026, Knut Reinert & Freie Universität Berlin
// SPDX-FileCopyrightText: 2016-2026, Knut Reinert & MPI für molekulare Genetik
// SPDX-License-Identifier: CC0-1.0

#include <cstddef>    // for size_t
#include <cstdint>    // for uint64_t
#include <functional> // for function
#include <iostream>   // for basic_ostream, operator<<, cout
#include <ranges>     // for __fn, iota, views
#include <vector>     // for vector

#include <hibf/config.hpp>                                // for insert_iterator, config
#include <hibf/hierarchical_interleaved_bloom_filter.hpp> // for hierarchical_interleaved_bloom_filter

int main()
{
    // Let's say we have groups that have data that we find interesting.
    // For example, each file of the RefSeq data set could be such a group.
    // In the context of the HIBF, we call such groups user bins.

    // Given a query, we want to quickly determine which user bins this query is likely to occur in.
    // This is also called Approximate Membership Query (AMQ).

    // In this example, we have three user bins. Each of these user bins is characterized by a range of
    // unsigned integer values. Some popular techniques for obtaining such unsigned integers from
    // biological sequences include k-mers, minimisers, and syncmers.

    // For clarity, we show each user bin individually before copying them to user_bin_data.
    std::vector<uint64_t> user_bin_1{1u, 2u, 3u, 4u, 5u, 6u, 7u, 8u, 9u, 10u};
    std::vector<uint64_t> user_bin_2{1u, 2u, 3u, 4u, 5u};
    std::vector<uint64_t> user_bin_3{3u, 9u, 11u};
    std::vector<std::vector<uint64_t>> user_bin_data{user_bin_1, user_bin_2, user_bin_3};

    // The HIBF uses a config. There are two required options:
    // 1) The number of user bins: 3 (user_bin_data.size())
    // 2) A function to access the input data.
    //    The signature is (size_t const user_bin_id, seqan::hibf::insert_iterator it). You need to
    //    provide the function body, and the hibf lib will use this function to access the data of each
    //    user bin. When this function is called by the library with a specific user_bin_id, all
    //    unsigned integer values (data) belonging to this user bin have to be assigned to the
    //    seqan::hibf::insert_iterator.
    //    Conveniently, this function can be a lambda, and hence capture data outside the function body.
    auto get_user_bin_data = [&](size_t const user_bin_id, seqan::hibf::insert_iterator it)
    {
        for (auto value : user_bin_data[user_bin_id])
            it = value;
    };

    // Now we can construct a config, any other settings are optional. We have included some interesting
    // settings with their respective default values here.
    seqan::hibf::config config{.input_fn = get_user_bin_data, // required
                               .number_of_user_bins = 3u,     // required
                               .number_of_hash_functions = 2u,
                               .maximum_fpr = 0.05,
                               .threads = 1u};

    // The HIBF constructor will determine a hierarchical layout for the user bins and build the filter.
    seqan::hibf::hierarchical_interleaved_bloom_filter hibf{config};

    // Now we can search for some query.
    std::vector<uint64_t> query1{3u, 9u, 12u, 14u};

    // For this, we use the membership agent of the HIBF. This agent only needs to be created once and
    // can be reused for multiple subsequent queries.
    // If you are using multiple threads in your app, each thread should have its own membership agent.
    auto agent = hibf.membership_agent();

    // The membership_for function takes the query and a threshold. Here, a threshold of two means that
    // at least (>=) 2 values of the query must be found within a user bin to be a hit.
    // While exact thresholds can be obtained for some approaches such as k-mers, another popular
    // approach is to require at least x% of the values in the query to hit.
    // For example, a threshold of 2 equals 40% of the values in query1 (5 values).
    // This threshold needs to be provided by the user. In general, some care should be taken with the
    // threshold. A low threshold requires a traversal of more parts of the hierarchy and slows down
    // the search.
    // Note that we bind the result with a `&` to avoid copies!
    auto & result1 = agent.membership_for(query1, 2u);

    // query1 hits in user_bin_1 and user_bin_3, which have the IDs 0 and 2, respectively.
    for (uint64_t hit_user_bin : result1)
        std::cout << hit_user_bin << ' '; // The results are not sorted: 2 0
    std::cout << '\n';

    // Another query.
    // A query is simply a range of unsigned integer values, e.g., it does not have to be a vector.
    auto query2 = std::views::iota(0u, 15u); // 0,1,2,...,14
    auto & result2 = agent.membership_for(query2, 5u);
    agent.sort_results(); // Sort the results.

    // query2 hits in user_bin_1 and user_bin_2, which have the IDs 0 and 1, respectively.
    for (uint64_t hit_user_bin : result2)
        std::cout << hit_user_bin << ' '; // The results are sorted: 0 1
    std::cout << '\n';
}

C++20 modules (experimental)

HIBF can additionally be consumed as a named module. Configure with -DHIBF_MODULE=ON:

cmake -S . -B build -G Ninja -DHIBF_MODULE=ON

seqan::hibf then also carries a CXX_MODULES file set, and consumers can write:

#include <cstddef>
#include <vector>

import hibf;

int main()
{
    seqan::hibf::interleaved_bloom_filter ibf{seqan::hibf::bin_count{64u}, seqan::hibf::bin_size{1024u}};
    ibf.emplace(126u, seqan::hibf::bin_index{0u});

    auto agent = ibf.containment_agent();
    return agent.bulk_contains(126u)[0u] ? 0 : 1;
}

On top of HIBF's usual requirements, this needs CMake >= 3.28 and the Ninja generator; every compiler HIBF supports can build the module. CI covers the latest GCC and Clang version.

The switch is additive rather than exclusive. src/hibf.cppm includes the headers in its global module fragment, so imported and included declarations name the same entities:

• libhibf.a is the same either way; the module adds one almost empty object file.
• Headers keep working unchanged, and a single translation unit may both #include <hibf/...> and import hibf;. Downstream projects can therefore migrate file by file.
• HIBF_HAS_MODULE is defined when the module was built, for code that has to support both modes.

Two caveats:

• Only the names listed in src/hibf.cppm are visible to importers. seqan::stl (the include/hibf/contrib standard library backports) is not exported; use the headers for those.
• GCC 16 rejects a textual #include that appears after an import hibf; in the same translation unit. Put includes first. Clang accepts either order.