Pith. sign in

REVIEW 2 major objections 5 minor 65 references

Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Vector-search indexes can shed order information and shrink 30% with no recall loss.

desk verdict Solid IVF compression results with a practical payoff, but the graph-index claim needs an order-invariance ablation and the abstract overstates the runtime story. read the letter →

arxiv 2501.10479 v1 pith:ECRNDDOJ submitted 2025-01-16 cs.LG cs.DBcs.IR

Daniel Severo , Giuseppe Ottaviano , Matthew Muckley , Karen Ullrich , Matthijs Douze This is my paper · ORCID
classification cs.LGcs.DBcs.IR MSC 68P3094A29
keywords approximatenearestneighborsearchlosslesscompressionvectoridasymmetricnumeralsystemsrandomordercodingwavelettreesinvertedfileindexgraph-based
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's claim is that a large fraction of a vector-search index is order information that the search never uses, and that this can be removed losslessly. In inverted-file indexes each cluster is a set of vector ids, and in graph indexes each node's neighbor list is a set, so coding these lists as ordered sequences wastes about $\log n!$ bits per list. The authors build entropy coders, random-order coding on asymmetric numeral systems for online access, wavelet trees for full random access, and random-edge coding for offline graph compression, that realize these savings. On million-scale benchmarks the id storage falls from 32 or 64 bits to about 8–12 bits per id, a sevenfold reduction in IVF settings, and on a billion-scale index the overall size drops about 30% at unchanged recall. For some datasets the same conditional entropy argument also compresses the quantized vector codes by up to 19%.

What carries the argument

The load-bearing object is the order-invariance itself: a list of ids stores membership and nothing else, so the compressor can discard the ordering. The codec that carries the argument is Random Order Coding (ROC), a bits-back scheme built on asymmetric numeral systems (ANS), an entropy coder, that models an observed sequence as a set plus a hidden permutation, samples the permutation back from the ANS state during decoding, and thereby pays about $\log n!$ fewer bits. For full random access to individual ids, the paper uses a wavelet tree over the cluster-id sequence, where the select operation finds the database id at a given offset inside a cluster; the compressed-bitvector variant trades speed for more compression. For offline graph compression, Random Edge Coding (REC) flattens all edges of the graph into one ANS-coded node sequence and exploits the edge-order freedom globally. The same ANS machinery, with an adaptive per-cluster byte model, is what extracts the redundancy from quantized product-quantization codes.

What would settle it

Run a query batch on an NSG or HNSW index, then on the same index with every node's friend list randomly permuted, and compare the fraction of true nearest neighbors returned and the sequence of visited nodes; any systematic difference would show that order is not irrelevant for graph search. Separately, compress and decompress an index and verify that every id comes back bit-identical, distinguishing lossless storage from lossless search behavior.

Watch

Extended reading notes

Core claim

The central discovery is that auxiliary identifiers in approximate nearest neighbor indexes are sets, not sequences, and therefore carry $\log n!$ redundant bits that a lossless codec can recover. The paper demonstrates this with Random Order Coding (ROC), which uses bits-back coding with a latent permutation to encode each inverted list or friend list at close to the set-entropy rate, and with Random Edge Coding (REC) for whole-graph offline compression. The measured consequences are concrete: IVF ids compress from 64 bits to about 9 bits per id, graph friend lists compress to roughly 16–20 bits per id, with short lists failing to beat the $\lceil \log N\rceil$ baseline, and the total size of a billion-scale IVF+QINCo index falls from 17.8 GB to 12.5 GB with recall unchanged. The paper also shows that product-quantization codes, usually assumed to be incompressible, are not uniformly distributed within clusters: conditioning the entropy model on cluster membership compresses SIFT1M codes by up to 19%.

Load-bearing premise

Everything rests on the claim that the ordering of ids inside a cluster list or a graph node's neighbor list is irrelevant to search results and speed; if reordering a neighbor list changes which approximate neighbors a greedy search finds, the graph-index savings are not behaviorally lossless.

Editorial extensions

If this is right

  • IVF indexes can store ids at about 14.7% of their uncompressed size, roughly 9 bits per id instead of 64, with search accuracy identical because the representation is lossless and with negligible slowdown for typical product-quantization settings.
  • On billion-scale IVF+QINCo indexes the total RAM footprint falls from 17.8 GB to 12.5 GB at the same recall@10, so the same machine can serve a larger database.
  • Compressed indexes trade access granularity against rate: wavelet trees provide random access to any id at a 2–3x select cost, per-cluster streams give partial random access at near-optimal rates, and single-stream offline compression gives the best rates but requires full decompression before search.
  • For graph indexes, offline REC compression reaches up to 2.31x reduction on HNSW/NSG graphs, but online per-node friend-list coding is only competitive when lists are long; for NSG16 the baseline $\lceil\log N\rceil$ bits per id wins.
  • Quantized vector codes are not always max-entropy; conditional entropy coding within clusters extracts up to 19% for SIFT1M and about 5% for Deep1M, with negligible benefit for FB-ssnpp.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the order-invariance argument is structural, so the same lossless id-compression recipe should transfer to other graph and partitioned index families, with similar bit savings wherever membership lists appear.
  • Beyond the paper, the uniform probability model used in ROC ignores correlations among ids; a data-dependent neighbor model could shave more bits from graph friend lists, at the price of slower decoding.
  • Beyond the paper, the graph-index claim of unchanged search behavior implicitly assumes friend-list order does not affect greedy routing; rerunning queries after randomly permuting each friend list would test that directly, and the paper reports no such ablation.
  • Beyond the paper, the cluster-conditional code compression implies quantizers leave cluster-local structure on the table, so jointly training quantizers with an entropy model could make the lossless code gains larger than the reported 19%.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes and evaluates lossless compression methods for auxiliary data in approximate nearest neighbor (ANN) indexes: vector identifiers in IVF inverted lists and edges in graph-based indexes. It applies entropy coders based on asymmetric numeral systems (ANS), notably ROC for sets/multisets and REC for graphs, as well as wavelet-tree and Elias-Fano baselines, under three access regimes: full random access, partial random access, and offline whole-index compression. On 1M-vector benchmarks, it reports reducing IVF ID storage from 64 bits per ID to roughly 9-12 bits per ID (a factor of about 7 for IVF256), and reducing graph ID storage from 32 bits to about 14-20 bits per ID depending on graph degree. On a billion-scale QINCo+IVF index, it reports an overall index-size reduction of about 30%. The paper also reports lossless compression of PQ codes conditioned on cluster ID for some datasets. Because the transformations are lossless by construction, the paper does not measure search recall, and it claims no impact on accuracy or search runtime.

Significance. If the claims hold, this is a useful systems contribution: it shows that a large fraction of ANN index memory can be saved by exploiting the order-invariance of ID sets, with measured rates close to information-theoretic bounds. The IVF results are internally consistent and reproducible in spirit: the authors implement the codecs in Faiss, report bit rates on standard datasets, and the Elias-Fano/ROC gap is consistent with the known 0.56-bit redundancy. The main novelty is empirical rather than methodological, since ROC/REC are prior work by the same group; nevertheless, an independent evaluation of speed versus compression for ANN indexes is valuable. The central caveat is that the graph-index 'lossless with same search behavior' claim relies on an unvalidated assumption about friend-list order invariance, and the runtime claims are stronger than some of the paper's own tables support.

major comments (2)
  1. [Section 4, "Exploiting invariances for compression"; Section 5.1, Metrics] The claim that graph-based search is invariant to the order of elements in friend lists is load-bearing for the graph compression results in Tables 1-3, but it is not empirically validated. ROC and REC encode each friend list as a set, so after decompression the adjacency lists are stored in a canonical order that may differ from the original. Best-first graph search with a bounded candidate set (the paper uses efSearch=16 for NSG) and with possible tie-breaking can plausibly be sensitive to the order in which neighbors are inserted into the priority queue. The paper explicitly does not measure recall (Section 5.1: 'we do not evaluate the vector search recall'), so this premise is asserted rather than tested. Please add an ablation that randomly permutes each friend list (and, separately, applies the actual compress-decompress pipeline) and compares recall@k and, if feasible, the set of visited nodes against the original graph. Without such evidence, the 'lossless, same behavior' claim for graph indexes is unsupported.
  2. [Abstract; Tables 2 and 4] The abstract states that the methods compress IDs 'with no impact on accuracy or search runtime,' but the paper's own timing results show substantial slowdowns in several settings. In Table 2, NSG16 with ROC is 0.29s versus 0.12s for the uncompressed index (about 2.4x slower), and NSG64 with ROC is 0.51s versus 0.29s (about 1.8x slower). In the billion-scale experiment of Table 4, ROC raises search time from 11.8s to 14.9s (about 26% slower), while the text emphasizes only the 30% index-size reduction. If the 'no impact on search runtime' claim is meant to apply only to the IVF settings where vector compression dominates, it should be qualified explicitly; as written, it is contradicted by the reported data.
minor comments (5)
  1. [Section 3.1] Typo: 'natural numberss' should be 'natural numbers'.
  2. [Section 4.1] Typo: 'if the distance if better than the worst' should be 'if the distance is better than the worst'; similarly, 'or or they are evicted' should be 'or they are evicted'.
  3. [Section 5.2] Typo: 'the baseline WT uses a flat binary binary string' should read 'a flat binary string'; also, 'Succint library' should be 'Succinct library'.
  4. [Equation (7)] The displayed formula for the sequential predictive distribution is hard to parse because of the line break; please use a proper fraction, e.g., Pr(...) = (1 + count) / (256 + i), and clarify the role of the Laplace smoothing term.
  5. [Abstract] Minor wording: 'The source code for our approach available' should be 'The source code for our approach is available'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: compression ratios are measured with existing codecs against external baselines.

full rationale

The paper's central contribution is an empirical evaluation of lossless entropy coders (ROC and REC) applied to IVF and graph index IDs. The reported bits-per-id numbers are measured outputs of the codecs on public datasets (SIFT1M, Deep1M, FB-ssnpp1M), not predictions derived from fitted parameters. No parameter in the main result is tuned to match the compression ratios, and the comparisons include independent baselines (uncompressed 64/32-bit, compact ⌈log N⌉, Elias-Fano, and Zuckerli). The ROC/REC citations are to published, code-reproduced algorithms used as tools; the paper does not invoke a uniqueness theorem or self-citation to forbid alternatives, and it discloses that the REC probability model is not tailored to ANNS graphs. The order-invariance assumption for friend lists in Section 4 is a correctness/validation concern (no permutation ablation is reported), but it is not a circularity: the lossless claim is defined at the level of set reconstruction, and the claim that search behavior is unchanged is an empirical/algorithmic assumption, not an equation that reduces to the paper's inputs. Since the work is self-contained against external benchmarks and the savings are measured rather than fitted, no circular step is present.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central claims use standard information-theoretic tools (entropy coding, ANS, bits-back) from the literature. No new entities are invented, and no parameter is fitted to tune the main results. The main load-bearing postulate is the order-invariance of IDs and friend lists for search; it is asserted in Section 4 and never empirically validated. The code-compression side result introduces a hand-chosen Laplace smoothing prior.

free parameters (1)
  • Laplace smoothing strength in sequential predictive model = 1
    Eq. (7) adds a fixed count of 1 to each symbol's observed frequency when computing Pr(x_i = x | history) for entropy-coding PQ codes. This is a hand-chosen prior strength; it affects the code-compression rate and is not derived from data.
assumptions (3)
  • domain assumption Permuting the rows of X, the partition labels, and the order of elements in friend lists does not affect ANNS search results or speed.
    Section 4, 'Exploiting invariances for compression'. This is load-bearing for the claimed compression savings; it is asserted but not empirically verified with a permutation ablation.
  • standard math Shannon's entropy lower bound and ANS near-optimality justify that the ANS-based codecs approach the theoretical set-compression rate.
    Section 3.1 and Eq. (4) rely on standard information theory (Shannon entropy, cross-entropy) and Duda's ANS redundancy bound; these are standard results cited from the literature.
  • domain assumption The sequential predictive distribution in Eq. (7) is a valid probability model for the PQ codes within a cluster.
    The code-compression experiment relies on this adaptive distribution being a correct conditional PMF; it is constructed by design and not tested against alternative priors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/ECRNDDOJ

@misc{pith2026250110479,
  author       = {Pith},
  title        = {Pith review of: Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ECRNDDOJ}},
  note         = {Machine review of arXiv:2501.10479}
}
read the original abstract

Approximate nearest neighbor search for vectors relies on indexes that are most often accessed from RAM. Therefore, storage is the factor limiting the size of the database that can be served from a machine. Lossy vector compression, i.e., embedding quantization, has been applied extensively to reduce the size of indexes. However, for inverted file and graph-based indices, auxiliary data such as vector ids and links (edges) can represent most of the storage cost. We introduce and evaluate lossless compression schemes for these cases. These approaches are based on asymmetric numeral systems or wavelet trees that exploit the fact that the ordering of ids is irrelevant within the data structures. In some settings, we are able to compress the vector ids by a factor 7, with no impact on accuracy or search runtime. On billion-scale datasets, this results in a reduction of 30% of the index size. Furthermore, we show that for some datasets, these methods can also compress the quantized vector codes losslessly, by exploiting sub-optimalities in the original quantization algorithm. The source code for our approach available at https://github.com/facebookresearch/vector_db_id_compression.

Figures

Figures reproduced from arXiv: 2501.10479 by the authors.

Figure 1
Figure 1. How we apply lossless compression in state-of-the-art in [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. Results for compress￾ing quantization codes condi￾tioned on clusters (originally 8 bits-per-element). Lower is bet￾ter. a permutation [mi ] to its elements without affecting search. In this work, we exploit these invariances to im￾prove lossless database compression. The set of codes X is the result of applying vector quantization algo￾rithms to the embedding vectors, and therefore we ex￾pect them to be mostly incom… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 59 canonical work pages

  1. [1]

    Additive quan- tization for extreme vector compression

    Artem Babenko and Victor Lempitsky. Additive quan- tization for extreme vector compression. In Conference on Computer Vision and Pattern Recognition, 2014. 2

    work page 2014

  2. [2]

    Efficient index- ing of billion-scale datasets of deep descriptors

    Artem Babenko and Victor Lempitsky. Efficient index- ing of billion-scale datasets of deep descriptors. InCon- ference on Computer Vision and Pattern Recognition, 2016. 6

    work page 2016

  3. [3]

    Revisiting the inverted indices for billion-scale approx- imate nearest neighbors

    Dmitry Baranchuk, Artem Babenko, and Yury Malkov. Revisiting the inverted indices for billion-scale approx- imate nearest neighbors. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018. 2

    work page 2018

  4. [4]

    Dedrift: Robust similarity search under content drift

    Dmitry Baranchuk, Matthijs Douze, Yash Upadhyay, and I Zeki Yalniz. Dedrift: Robust similarity search under content drift. In Proceedings of the IEEE/CVF In- ternational Conference on Computer Vision, pages 11026– 11035, 2023. 8

    work page 2023

  5. [5]

    The webgraph framework i: compression techniques

    Paolo Boldi and Sebastiano Vigna. The webgraph framework i: compression techniques. In Proceedings of the 13th international conference on World Wide Web , pages 595–602, 2004. 1

    work page 2004

  6. [6]

    The webgraph framework ii: Codes for the world-wide web

    Paolo Boldi and Sebastiano Vigna. The webgraph framework ii: Codes for the world-wide web. In Data Compression Conference, 2004. Proceedings. DCC 2004 , page 528. IEEE, 2004. 1

    work page 2004

  7. [7]

    Multiary wavelet trees in practice

    Alex Bowe. Multiary wavelet trees in practice. Mag- istarski rad, School of Computer Science and Information Technology RMIT University, Melbourne, Australia, 2010. 4

    work page 2010

  8. [8]

    Roargraph: A projected bipartite graph for efficient cross-modal approximate nearest neighbor search

    Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X Sean Wang. Roargraph: A projected bipartite graph for efficient cross-modal approximate nearest neighbor search. arXiv preprint arXiv:2408.08933, 2024. 2

    arXiv 2024

Show all 65 references
  1. [9]

    Elements of information theory

    Thomas M Cover. Elements of information theory . John Wiley & Sons, 1999. 3, 5, 1

    1999

  2. [10]

    Thomas. M. Cover and Joy A. Thomas. Elements of In- formation Theory. Wiley Series in Telecommunications

  3. [11]

    Locality-sensitive hashing scheme based on p-stable distributions

    Mayur Datar, Nicole Immorlica, Piotr Indyk, and Va- hab S Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry , pages 253–262, 2004. 2

    2004

  4. [12]

    Efficient k- nearest neighbor graph construction for generic simi- larity measures

    Wei Dong, Charikar Moses, and Kai Li. Efficient k- nearest neighbor graph construction for generic simi- larity measures. In Proceedings of the 20th international conference on World wide web, pages 577–586, 2011. 2

    2011

  5. [13]

    The faiss library

    Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazar ´e, Maria Lomeli, Lucas Hosseini, and Herv ´e J ´egou. The faiss library. arXiv preprint arXiv:2401.08281, 2024. 2, 6

    2024 arXiv

  6. [14]

    The yael library

    Matthijs Douze and Herv ´e J´egou. The yael library. In Proceedings of the 22nd ACM international conference on Multimedia, pages 687–690, 2014. 5

    2014

  7. [15]

    Link and code: Fast indexing with graphs and compact regression codes

    Matthijs Douze, Alexandre Sablayrolles, and Herv ´e J´egou. Link and code: Fast indexing with graphs and compact regression codes. In Proceedings of the IEEE conference on computer vision and pattern recogni- tion, pages 3646–3654, 2018. 2, 3

    2018

  8. [16]

    Asymmetric numeral systems

    Jarek Duda. Asymmetric numeral systems. arXiv preprint arXiv:0902.0271, 2009. 3

    2009 arXiv

  9. [17]

    Efficient storage and retrieval by content and address of static files

    Peter Elias. Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM) , 21(2):246–260, 1974. 3, 6, 7

    1974

  10. [18]

    On the number of bits required to im- plement an associative memory

    Robert Mario Fano. On the number of bits required to im- plement an associative memory . Massachusetts Institute of Technology, Project MAC, 1971. 6

    1971

  11. [19]

    Peter M. Fenwick. A new data structure for cumula- tive frequency tables. Software: Practice and Experience , 24(3):327–336, 1994. 7

    1994

  12. [20]

    Fast approximate nearest neighbor search with the navigating spreading-out graph

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143, 2017. 2

    2017 arXiv

  13. [21]

    Op- timized product quantization for approximate nearest neighbor search

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Op- timized product quantization for approximate nearest neighbor search. In Conference on Computer Vision and Pattern Recognition, 2013. 2

    2013

  14. [22]

    Iterative quantization: A pro- crustean approach to learning binary codes for large- scale image retrieval

    Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. Iterative quantization: A pro- crustean approach to learning binary codes for large- scale image retrieval. IEEE Trans. Pattern Analysis and Machine Intelligence, 2012. 2

    2012

  15. [23]

    Gray and David L

    Robert M. Gray and David L. Neuhoff. Quantization. IEEE transactions on information theory, 44(6):2325–2383,

  16. [24]

    The wavelet trie: maintaining an indexed sequence of strings in compressed space

    Roberto Grossi and Giuseppe Ottaviano. The wavelet trie: maintaining an indexed sequence of strings in compressed space. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 203–214, 2012. 4

    2012

  17. [25]

    Ac- celerating large-scale inference with anisotropic vec- tor quantization

    Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Ac- celerating large-scale inference with anisotropic vec- tor quantization. In International Conference on Machine Learning. PMLR, 2020. 2

    2020

  18. [26]

    Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

    Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015. 2

    2015 arXiv

  19. [27]

    Keeping the neural networks simple by minimizing the description length of the weights

    Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational Learning Theory, pages 5–13,

  20. [28]

    Huijben, Matthijs Douze, Matthew J

    Iris A.M. Huijben, Matthijs Douze, Matthew J. Muck- ley, Ruud J.G. van Sloun, and Jakob Verbeek. Residual quantization with implicit neural codebooks. In Inter- national Conference on Machine Learning (ICML), 2024. 1, 2, 8

    2024

  21. [29]

    Hamming embedding and weak geometric consistency for large scale image search

    Herve Jegou, Matthijs Douze, and Cordelia Schmid. Hamming embedding and weak geometric consistency for large scale image search. In Computer Vision–ECCV 2008: 10th European Conference on Computer Vision, Mar- seille, France, October 12-18, 2008, Proceedings, Part I 10 , pages ...

    2008

  22. [30]

    Product quantization for nearest neighbor search

    Herv ´e J ´egou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Analysis and Machine Intelligence ,

  23. [31]

    Billion- scale similarity search with GPUs

    Jeff Johnson, Matthijs Douze, and Herv ´e J´egou. Billion- scale similarity search with GPUs. IEEE Trans. on Big Data, 2019. 5

    2019

  24. [32]

    Practical shuffle coding

    Julius Kunze, Daniel Severo, Jan-Willem van de Meent, and James Townsend. Practical shuffle coding. In The Thirty-eighth Annual Conference on Neural Informa- tion Processing Systems. 7

  25. [33]

    Entropy coding of unordered data structures

    Julius Kunze, Daniel Severo, Giulio Zani, Jan-Willem van de Meent, and James Townsend. Entropy coding of unordered data structures. In The Twelfth International Conference on Learning Representations. 7

  26. [34]

    Overview of h

    Soon-kak Kwon, A Tamhankar, and KR Rao. Overview of h. 264/mpeg-4 part 10. Journal of Visual Communica- tion and Image Representation, 17(2):186–216, 2006. 2

    2006

  27. [35]

    Distinctive image features from scale- invariant keypoints

    David G Lowe. Distinctive image features from scale- invariant keypoints. International Journal of Computer Vision, 60(2), 2004. 6

    2004

  28. [36]

    David J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. 3

    2003

  29. [37]

    Efficient and ro- bust approximate nearest neighbor search using hierar- chical navigable small world graphs

    Yu A Malkov and Dmitry A Yashunin. Efficient and ro- bust approximate nearest neighbor search using hierar- chical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence , 42(4):824– 836, 2018. 2

    2018

  30. [38]

    LSQ++: lower running time and higher recall in multi-codebook quantization

    Julieta Martinez, Shobhit Zakhmi, Holger H Hoos, and James J Little. LSQ++: lower running time and higher recall in multi-codebook quantization. InEuropean Con- ference on Computer Vision, 2018. 2

    2018

  31. [39]

    Unsupervised neural quantization for compressed-domain similarity search

    Stanislav Morozov and Artem Babenko. Unsupervised neural quantization for compressed-domain similarity search. In International Conference on Computer Vision ,

  32. [40]

    Scalable nearest neighbor algorithms for high dimensional data

    Marius Muja and David G Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence , 36(11):2227–2240, 2014. 2

    2014

  33. [41]

    Residual vector product quantization for approximate nearest neigh- bor search

    Lushuai Niu, Zhi Xu, Longyang Zhao, Daojing He, Jianqiu Ji, Xiaoli Yuan, and Mian Xue. Residual vector product quantization for approximate nearest neigh- bor search. Expert Systems with Applications , page 120832, 2023. 1

    2023

  34. [42]

    Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus, 2023

    Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus, 2023. 2

    2023

  35. [43]

    Object retrieval with large vo- cabularies and fast spatial matching

    James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman. Object retrieval with large vo- cabularies and fast spatial matching. In Conference on Computer Vision and Pattern Recognition, 2007. 1

    2007

  36. [44]

    A self-supervised descriptor for image copy detection

    Ed Pizzi, Sreya Dutta Roy, Sugosh Nagavara Ravindra, Priya Goyal, and Matthijs Douze. A self-supervised descriptor for image copy detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14532–14542, 2022. 1, 6

    2022

  37. [45]

    An overview of the jpeg 2000 still image compression standard

    Majid Rabbani and Rajan Joshi. An overview of the jpeg 2000 still image compression standard. Signal pro- cessing: Image communication, 17(1):3–48, 2002. 2

    2000

  38. [46]

    Succinct indexable dictionaries with applica- tions to encoding k-ary trees, prefix sums and multi- sets

    Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applica- tions to encoding k-ary trees, prefix sums and multi- sets. ACM Transactions on Algorithms (TALG), 3(4):43– es, 2007. 6

    2007

  39. [47]

    Robinson and C

    A.H. Robinson and C. Cherry. Results of a prototype television bandwidth compression scheme. Proceedings of the IEEE, 55(3):356–364, 1967. 1

    1967

  40. [48]

    Spreading vectors for simi- larity search

    Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Herv ´e J´egou. Spreading vectors for simi- larity search. International Conference on Learning Repre- sentations, 2019. 2

    2019

  41. [49]

    Random permutation codes: Lossless source coding of non-sequential data, 2024

    Daniel Severo. Random permutation codes: Lossless source coding of non-sequential data, 2024. 5

    2024

  42. [50]

    Random cycle coding: Lossless compression of cluster assignments via bits-back coding

    Daniel Severo, Ashish J Khisti, and Alireza Makhzani. Random cycle coding: Lossless compression of cluster assignments via bits-back coding. In The Thirty-eighth Annual Conference on Neural Information Processing Sys- tems. 5

  43. [51]

    Random edge coding: One-shot bits-back coding of large labeled graphs

    Daniel Severo, James Townsend, Ashish Khisti, and Alireza Makhzani. Random edge coding: One-shot bits-back coding of large labeled graphs. arXiv preprint arXiv:2305.09705, 2023. 2, 4, 6, 8

    2023 arXiv

  44. [52]

    Compressing multisets with large alphabets

    Daniel Severo, James Townsend, Ashish Khisti, Alireza Makhzani, and Karen Ullrich. Compressing multisets with large alphabets. IEEE Journal on Selected Areas in Information Theory, 3(4):605–615, 2022. 2, 4, 5, 6, 7, 8, 1

    2022

  45. [53]

    Claude. E. Shannon. A mathematical theory of com- munication. The Bell System Technical Journal, 27(3):379– 423, July 1948. 2

    1948

  46. [54]

    Results of the neurips’21 challenge on billion-scale approximate nearest neigh- bor search

    Harsha Vardhan Simhadri, George Williams, Martin Aum ¨uller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Kr- ishnaswamny, Gopal Srinivasa, Suhas Jayaram Subra- manya, and Jingdong Wang. Results of the neurips’21 challenge on billion-sc...

    2021

  47. [55]

    Video google: A text retrieval approach to object matching in videos

    Sivic and Zisserman. Video google: A text retrieval approach to object matching in videos. In Proceedings ninth IEEE international conference on computer vision , pages 1470–1477. IEEE, 2003. 1, 2

    2003

  48. [56]

    Diskann: Fast accurate billion-point nearest neighbor search on a single node

    Suhas Jayaram Subramanya, Rohan Kadekodi, Ravis- hankar Krishaswamy, and Harsha Vardhan Simhadri. Diskann: Fast accurate billion-point nearest neighbor search on a single node. In Neurips, 2019. 2

    2019

  49. [57]

    Automat- ing nearest neighbor search configuration with con- strained optimization

    Philip Sun, Ruiqi Guo, and Sanjiv Kumar. Automat- ing nearest neighbor search configuration with con- strained optimization. arXiv preprint arXiv:2301.01702,

    arXiv

  50. [58]

    A tutorial on the range variant of asymmetric numeral systems

    James Townsend. A tutorial on the range variant of asymmetric numeral systems. arXiv:2001.09186 [cs, math, stat], 2020. 3

    2001 arXiv

  51. [59]

    Hilloc: Lossless image compression with hierarchical latent variable models

    James Townsend, Thomas Bird, Julius Kunze, and David Barber. Hilloc: Lossless image compression with hierarchical latent variable models. ICLR, 2020. 7

    2020

  52. [60]

    Practi- cal lossless compression with latent variables using bits back coding

    James Townsend, Tom Bird, and David Barber. Practi- cal lossless compression with latent variables using bits back coding. ICLR, 2019. 3

    2019

  53. [61]

    USearch by Unum Cloud, June 2022

    Ash Vardanian. USearch by Unum Cloud, June 2022. 2

    2022

  54. [62]

    Zuckerli: A new compressed represen- tation for graphs

    Luca Versari, Iulia-Maria Comsa, Alessio Conte, and Roberto Grossi. Zuckerli: A new compressed represen- tation for graphs. IEEE Access, 8:219233–219243, 2020. 3, 6, 8 10

    2020

  55. [63]

    The jpeg still picture compres- sion standard

    Gregory K Wallace. The jpeg still picture compres- sion standard. IEEE transactions on consumer electronics, 38(1):xviii–xxxiv, 1992. 2

    1992

  56. [64]

    Spectral hashing

    Yair Weiss, Antonio Torralba, Robert Fergus, et al. Spectral hashing. In NeurIPS, volume 1, page 4, 2008. 2

    2008

  57. [65]

    Google landmarks dataset v2-a large-scale bench- mark for instance-level recognition and retrieval

    Tobias Weyand, Andre Araujo, Bingyi Cao, and Jack Sim. Google landmarks dataset v2-a large-scale bench- mark for instance-level recognition and retrieval. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2575–2584, 2020. 1 11 A Baseli...

    2020

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.