{"repo":"ashvardanian/JaccardIndex","free":true,"listed":false,"github":"https://github.com/ashvardanian/JaccardIndex","clone":"git clone https://github.com/ashvardanian/JaccardIndex.git","description":"Optimizing bit-level Jaccard Index and Population Counts for large-scale quantized Vector Search via Harley-Seal CSA and Lookup Tables","language":"Python","stars":22,"topics":["binary-vector","bitset","vector-database","vector-search","hamming-distance","jaccard","jaccard-similarity","tanimoto-coefficient"],"license":"Apache-2.0","category":"databases-storage","readme_excerpt":"Jaccard Index Optimization Jaccard Index is one of the most common tools in Information Retrieval and is used to measure the similarity between two sets, mostly defined at a single bit level: $$ \\text{Jaccard}(A, B) = \\frac{ A \\cap B }{ A \\cup B } = \\frac{ A \\cap B }{ A + B - A \\cap B } $$ In code, one would rarely deal with boolean values due to obvious space-inefficiency, and would generally operate on octets of bits, packed into 8-bit unsigned integers, like this: That's, however, horribly inefficient! Assuming how often bit-level representation are now used in large-scale vector search deployments with USearch, this repository provides benchmarks and custom kernels exploring the performance impacts of following optimizations: - Using lookup tables to speed up population counts. - Using Harley-Seal and Odd-Majority CSAs for population counts. - Loop unrolling and inlining. - 🔜 Precomputed Jaccard JUTs. - 🔜 Floating-point operations instead of integer ones. Running Examples The most interesting part of the repository is the kernels.py file with all kinds of weird kernels worth reading through. Native optimizations are implemented NumBa and Cppyy JIT compiler for Python and C++, and are packed into UV-compatible scripts. To benchmark and test the kernels on your hardware, run the following command: For other benchmarks real data can be used. Luckily, modern embedding models are often trained in Quantization-aware manner, and precomputed WikiPedia embeddings are available o","default_branch":null,"files":null,"tree":[],"storefront":"/r/ashvardanian","claimed":false,"request_supported":{"post":"https://gitbuyer.com/r/ashvardanian/JaccardIndex/request-supported","requests":0},"note":"indexed from public GitHub; nothing is for sale on this page. Clone it from GitHub. Paid listings live at /search."}