Both 2025 SISAP Challenges require participants to develop memory-efficient indexing solutions. Proposed solutions are run in a Linux container limited to 8 virtual CPUs and 16 GiB of memory, where virtual memory must not be enabled. Challenge 1 is to query a data set of 24 million items, and Challenge 2 is to build a near-neighbour table of 3 million items, making the memory restriction a significant limitation. We have submitted solutions to both challenges using our newly-invented technique of 2-bit quantisation based on Equi-Voronoi Polytopes (EVPs). This gives two very clear advantages: the data is compressed to 2 bits per vector element, therefore requiring only around 6% of the 32-bit floating point space. This representation is paired with a binary similarity metric, \(b_2sp\) , which is highly parallelisable on SIMD processors. The compression maintains sufficient accuracy to give reasonable results over the original Euclidean space. For both challenges we build a near-neighbour (NN) table using the ultra-quantised data and the \(b_2sp\) metric. This is built using a variant of the NN-Descent algorithm, which has the advantage of using fixed-size memory. The combination of these techniques along with a parallel, lock-free Rust implementation allows us to build a reasonably accurate near-neighbour table very quickly. For Challenge 1, a 10NN table is constructed within the allowed memory in around 50 min, and for Challenge 2 the 15NN table is constructed in around 10 min.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast, Compact NN-Table Build Using Equi-Voronoi Polytopes

  • Alan Dearle,
  • Richard Connor,
  • Ben Claydon,
  • Ferdia McKeogh

摘要

Both 2025 SISAP Challenges require participants to develop memory-efficient indexing solutions. Proposed solutions are run in a Linux container limited to 8 virtual CPUs and 16 GiB of memory, where virtual memory must not be enabled. Challenge 1 is to query a data set of 24 million items, and Challenge 2 is to build a near-neighbour table of 3 million items, making the memory restriction a significant limitation. We have submitted solutions to both challenges using our newly-invented technique of 2-bit quantisation based on Equi-Voronoi Polytopes (EVPs). This gives two very clear advantages: the data is compressed to 2 bits per vector element, therefore requiring only around 6% of the 32-bit floating point space. This representation is paired with a binary similarity metric, \(b_2sp\) , which is highly parallelisable on SIMD processors. The compression maintains sufficient accuracy to give reasonable results over the original Euclidean space. For both challenges we build a near-neighbour (NN) table using the ultra-quantised data and the \(b_2sp\) metric. This is built using a variant of the NN-Descent algorithm, which has the advantage of using fixed-size memory. The combination of these techniques along with a parallel, lock-free Rust implementation allows us to build a reasonably accurate near-neighbour table very quickly. For Challenge 1, a 10NN table is constructed within the allowed memory in around 50 min, and for Challenge 2 the 15NN table is constructed in around 10 min.