Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search Article Swipe
Daniel Severo
,
Giuseppe Ottaviano
,
Matthew J. Muckley
,
Karen Ullrich
,
Matthijs Douze
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2501.10479
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2501.10479
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.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2501.10479
- https://arxiv.org/pdf/2501.10479
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4406692309
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4406692309Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2501.10479Digital Object Identifier
- Title
-
Lossless Compression of Vector IDs for Approximate Nearest Neighbor SearchWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-01-16Full publication date if available
- Authors
-
Daniel Severo, Giuseppe Ottaviano, Matthew J. Muckley, Karen Ullrich, Matthijs DouzeList of authors in order
- Landing page
-
https://arxiv.org/abs/2501.10479Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2501.10479Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2501.10479Direct OA link when available
- Concepts
-
Lossless compression, k-nearest neighbors algorithm, Computer science, Compression (physics), Pattern recognition (psychology), Data compression, Nearest neighbor search, Artificial intelligence, Materials science, Composite materialTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4406692309 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2501.10479 |
| ids.doi | https://doi.org/10.48550/arxiv.2501.10479 |
| ids.openalex | https://openalex.org/W4406692309 |
| fwci | |
| type | preprint |
| title | Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11106 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9922999739646912 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1711 |
| topics[0].subfield.display_name | Signal Processing |
| topics[0].display_name | Data Management and Algorithms |
| topics[1].id | https://openalex.org/T10627 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9726999998092651 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1707 |
| topics[1].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[1].display_name | Advanced Image and Video Retrieval Techniques |
| topics[2].id | https://openalex.org/T10057 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9726999998092651 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1707 |
| topics[2].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[2].display_name | Face and Expression Recognition |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C81081738 |
| concepts[0].level | 3 |
| concepts[0].score | 0.9075870513916016 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q55542 |
| concepts[0].display_name | Lossless compression |
| concepts[1].id | https://openalex.org/C113238511 |
| concepts[1].level | 2 |
| concepts[1].score | 0.578654408454895 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1071612 |
| concepts[1].display_name | k-nearest neighbors algorithm |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.5776747465133667 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C180016635 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5737698078155518 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2712821 |
| concepts[3].display_name | Compression (physics) |
| concepts[4].id | https://openalex.org/C153180895 |
| concepts[4].level | 2 |
| concepts[4].score | 0.47898435592651367 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q7148389 |
| concepts[4].display_name | Pattern recognition (psychology) |
| concepts[5].id | https://openalex.org/C78548338 |
| concepts[5].level | 2 |
| concepts[5].score | 0.4492253363132477 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2493 |
| concepts[5].display_name | Data compression |
| concepts[6].id | https://openalex.org/C116738811 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4197169542312622 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q608751 |
| concepts[6].display_name | Nearest neighbor search |
| concepts[7].id | https://openalex.org/C154945302 |
| concepts[7].level | 1 |
| concepts[7].score | 0.4178091287612915 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[7].display_name | Artificial intelligence |
| concepts[8].id | https://openalex.org/C192562407 |
| concepts[8].level | 0 |
| concepts[8].score | 0.15500575304031372 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q228736 |
| concepts[8].display_name | Materials science |
| concepts[9].id | https://openalex.org/C159985019 |
| concepts[9].level | 1 |
| concepts[9].score | 0.11383956670761108 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q181790 |
| concepts[9].display_name | Composite material |
| keywords[0].id | https://openalex.org/keywords/lossless-compression |
| keywords[0].score | 0.9075870513916016 |
| keywords[0].display_name | Lossless compression |
| keywords[1].id | https://openalex.org/keywords/k-nearest-neighbors-algorithm |
| keywords[1].score | 0.578654408454895 |
| keywords[1].display_name | k-nearest neighbors algorithm |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.5776747465133667 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/compression |
| keywords[3].score | 0.5737698078155518 |
| keywords[3].display_name | Compression (physics) |
| keywords[4].id | https://openalex.org/keywords/pattern-recognition |
| keywords[4].score | 0.47898435592651367 |
| keywords[4].display_name | Pattern recognition (psychology) |
| keywords[5].id | https://openalex.org/keywords/data-compression |
| keywords[5].score | 0.4492253363132477 |
| keywords[5].display_name | Data compression |
| keywords[6].id | https://openalex.org/keywords/nearest-neighbor-search |
| keywords[6].score | 0.4197169542312622 |
| keywords[6].display_name | Nearest neighbor search |
| keywords[7].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[7].score | 0.4178091287612915 |
| keywords[7].display_name | Artificial intelligence |
| keywords[8].id | https://openalex.org/keywords/materials-science |
| keywords[8].score | 0.15500575304031372 |
| keywords[8].display_name | Materials science |
| keywords[9].id | https://openalex.org/keywords/composite-material |
| keywords[9].score | 0.11383956670761108 |
| keywords[9].display_name | Composite material |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2501.10479 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2501.10479 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2501.10479 |
| locations[1].id | doi:10.48550/arxiv.2501.10479 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2501.10479 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5089038476 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-0472-5300 |
| authorships[0].author.display_name | Daniel Severo |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Severo, Daniel |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5003288532 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-1191-8258 |
| authorships[1].author.display_name | Giuseppe Ottaviano |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ottaviano, Giuseppe |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5029739727 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-6525-8817 |
| authorships[2].author.display_name | Matthew J. Muckley |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Muckley, Matthew |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5058031547 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Karen Ullrich |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Ullrich, Karen |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5053822883 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Matthijs Douze |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Douze, Matthijs |
| authorships[4].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2501.10479 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11106 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9922999739646912 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1711 |
| primary_topic.subfield.display_name | Signal Processing |
| primary_topic.display_name | Data Management and Algorithms |
| related_works | https://openalex.org/W2148008870, https://openalex.org/W2948148442, https://openalex.org/W2381195555, https://openalex.org/W2461250372, https://openalex.org/W2394342941, https://openalex.org/W2169853506, https://openalex.org/W2547124190, https://openalex.org/W2350586049, https://openalex.org/W2385628723, https://openalex.org/W2032414556 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2501.10479 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2501.10479 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2501.10479 |
| primary_location.id | pmh:oai:arXiv.org:2501.10479 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2501.10479 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2501.10479 |
| publication_date | 2025-01-16 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 32, 121, 138 |
| abstract_inverted_index.7, | 123 |
| abstract_inverted_index.In | 109 |
| abstract_inverted_index.On | 132 |
| abstract_inverted_index.We | 73 |
| abstract_inverted_index.as | 60 |
| abstract_inverted_index.at | 178 |
| abstract_inverted_index.be | 29 |
| abstract_inverted_index.by | 120, 163 |
| abstract_inverted_index.in | 137, 166 |
| abstract_inverted_index.is | 18, 103 |
| abstract_inverted_index.no | 125 |
| abstract_inverted_index.of | 24, 48, 69, 101, 140, 142 |
| abstract_inverted_index.on | 7, 87, 127 |
| abstract_inverted_index.or | 91, 129 |
| abstract_inverted_index.to | 44, 115 |
| abstract_inverted_index.we | 112, 147 |
| abstract_inverted_index.30% | 141 |
| abstract_inverted_index.The | 171 |
| abstract_inverted_index.and | 54, 63, 75 |
| abstract_inverted_index.are | 10, 85, 113 |
| abstract_inverted_index.can | 28, 66, 155 |
| abstract_inverted_index.for | 4, 51, 80, 150, 174 |
| abstract_inverted_index.has | 40 |
| abstract_inverted_index.ids | 62, 102, 119 |
| abstract_inverted_index.our | 175 |
| abstract_inverted_index.the | 19, 22, 25, 46, 70, 96, 99, 106, 117, 143, 158, 167 |
| abstract_inverted_index.RAM. | 15 |
| abstract_inverted_index.able | 114 |
| abstract_inverted_index.also | 156 |
| abstract_inverted_index.been | 41 |
| abstract_inverted_index.code | 173 |
| abstract_inverted_index.data | 58, 107 |
| abstract_inverted_index.fact | 97 |
| abstract_inverted_index.file | 53 |
| abstract_inverted_index.from | 14, 31 |
| abstract_inverted_index.most | 11, 68 |
| abstract_inverted_index.show | 148 |
| abstract_inverted_index.size | 23, 47 |
| abstract_inverted_index.some | 110, 151 |
| abstract_inverted_index.such | 59 |
| abstract_inverted_index.that | 9, 27, 94, 98, 149 |
| abstract_inverted_index.this | 135 |
| abstract_inverted_index.with | 124 |
| abstract_inverted_index.Lossy | 34 |
| abstract_inverted_index.These | 83 |
| abstract_inverted_index.based | 86 |
| abstract_inverted_index.codes | 161 |
| abstract_inverted_index.cost. | 72 |
| abstract_inverted_index.i.e., | 37 |
| abstract_inverted_index.index | 144 |
| abstract_inverted_index.links | 64 |
| abstract_inverted_index.often | 12 |
| abstract_inverted_index.size. | 145 |
| abstract_inverted_index.these | 81, 153 |
| abstract_inverted_index.trees | 93 |
| abstract_inverted_index.cases. | 82 |
| abstract_inverted_index.factor | 20, 122 |
| abstract_inverted_index.impact | 126 |
| abstract_inverted_index.reduce | 45 |
| abstract_inverted_index.relies | 6 |
| abstract_inverted_index.search | 3, 130 |
| abstract_inverted_index.served | 30 |
| abstract_inverted_index.source | 172 |
| abstract_inverted_index.vector | 35, 61, 118, 160 |
| abstract_inverted_index.within | 105 |
| abstract_inverted_index.(edges) | 65 |
| abstract_inverted_index.applied | 42 |
| abstract_inverted_index.exploit | 95 |
| abstract_inverted_index.indexes | 8 |
| abstract_inverted_index.methods | 154 |
| abstract_inverted_index.nearest | 1 |
| abstract_inverted_index.numeral | 89 |
| abstract_inverted_index.results | 136 |
| abstract_inverted_index.schemes | 79 |
| abstract_inverted_index.storage | 17, 71 |
| abstract_inverted_index.systems | 90 |
| abstract_inverted_index.vectors | 5 |
| abstract_inverted_index.wavelet | 92 |
| abstract_inverted_index.However, | 50 |
| abstract_inverted_index.accessed | 13 |
| abstract_inverted_index.accuracy | 128 |
| abstract_inverted_index.approach | 176 |
| abstract_inverted_index.compress | 116, 157 |
| abstract_inverted_index.database | 26 |
| abstract_inverted_index.evaluate | 76 |
| abstract_inverted_index.indexes. | 49 |
| abstract_inverted_index.indices, | 56 |
| abstract_inverted_index.inverted | 52 |
| abstract_inverted_index.limiting | 21 |
| abstract_inverted_index.lossless | 77 |
| abstract_inverted_index.machine. | 33 |
| abstract_inverted_index.neighbor | 2 |
| abstract_inverted_index.ordering | 100 |
| abstract_inverted_index.original | 168 |
| abstract_inverted_index.runtime. | 131 |
| abstract_inverted_index.auxiliary | 57 |
| abstract_inverted_index.available | 177 |
| abstract_inverted_index.datasets, | 134, 152 |
| abstract_inverted_index.embedding | 38 |
| abstract_inverted_index.introduce | 74 |
| abstract_inverted_index.quantized | 159 |
| abstract_inverted_index.reduction | 139 |
| abstract_inverted_index.represent | 67 |
| abstract_inverted_index.settings, | 111 |
| abstract_inverted_index.Therefore, | 16 |
| abstract_inverted_index.algorithm. | 170 |
| abstract_inverted_index.approaches | 84 |
| abstract_inverted_index.asymmetric | 88 |
| abstract_inverted_index.exploiting | 164 |
| abstract_inverted_index.irrelevant | 104 |
| abstract_inverted_index.Approximate | 0 |
| abstract_inverted_index.compression | 78 |
| abstract_inverted_index.extensively | 43 |
| abstract_inverted_index.graph-based | 55 |
| abstract_inverted_index.losslessly, | 162 |
| abstract_inverted_index.structures. | 108 |
| abstract_inverted_index.Furthermore, | 146 |
| abstract_inverted_index.compression, | 36 |
| abstract_inverted_index.quantization | 169 |
| abstract_inverted_index.billion-scale | 133 |
| abstract_inverted_index.quantization, | 39 |
| abstract_inverted_index.sub-optimalities | 165 |
| abstract_inverted_index.https://github.com/facebookresearch/vector_db_id_compression. | 179 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |