kiddo

🐛 Bug Fixes

• Correct optional dependency feature gates (@sdd)

• Preserve fixed-to-float distance queries (@sdd)

🐛 Bug Fixes

• Correct optional dependency feature gates (@sdd)

• Preserve fixed-to-float distance queries (@sdd)

🐛 Bug Fixes

• Ensure kibrary compiles for wasm32-unknown-unknown target (@sdd, Fixes:#515)

• Dispatch the /fuzz command the way /benchmark does (@sdd)

• Grant the aggregate gate the permissions its called workflows need (@sdd)

• Chebyshev over-pruning found by fuzz testing (@sdd)

• Simd block-4 construction panic found by fuzzer (@sdd)

• Fuzzer-found SIMD backtracking optimisatition correctness issue (@sdd)

• Fuzz-uncovered construction bug (@sdd)

• Prevent f32 over-prune found in fuzz test (@sdd)

• Block-at-once strats now immutable-only (@sdd)

🤖 CI

• Aggregate required checks into a single PR Mergeable status (@sdd)

• Run the v6 fuzz suite on demand via a /fuzz comment (@sdd)

🧹 Chore

• Bump taiki-e/install-action from 2 to 2.85.5 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

🐛 Bug Fixes

• Ensure kibrary compiles for wasm32-unknown-unknown target (@sdd, Fixes:#515)

• Dispatch the /fuzz command the way /benchmark does (@sdd)

• Grant the aggregate gate the permissions its called workflows need (@sdd)

• Chebyshev over-pruning found by fuzz testing (@sdd)

• Simd block-4 construction panic found by fuzzer (@sdd)

• Fuzzer-found SIMD backtracking optimisatition correctness issue (@sdd)

• Fuzz-uncovered construction bug (@sdd)

• Prevent f32 over-prune found in fuzz test (@sdd)

• Block-at-once strats now immutable-only (@sdd)

🤖 CI

• Aggregate required checks into a single PR Mergeable status (@sdd)

• Run the v6 fuzz suite on demand via a /fuzz comment (@sdd)

🧹 Chore

• Bump taiki-e/install-action from 2 to 2.85.5 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

Almost a year in the making and counting, Kiddo v6 is effectively a full rewrite, addressing some
long-standing issues.

• V6 represents a fundamental shift to a unified single KdTree struct, replacing the previous
  mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has
  been removed by introducing the LeafStrategy trait, which the KdTree has as a generic parameter.
  LeafStrategies can be mutable or immutable.
• KdTree is also now generic over the new StemStrategy trait too. The combination of these two
  orthogonal traits allow experimentation and selection of alternative stem layouts and traversal
  mechanisms, alongside configurable leaf strategies, for performance experimentation.
• The query API has been refactored from a handful of separate methods that were not particularly
  cohesive into a single unified fluent builder API. The builder approach is much more orthogonal,
  and protects against breaking changes when new options are introduced in the future. It permits
  constraints to be encoded in the type system for impossible option combinations, prevents the need
  for as many methods that differ only by some combination of features; allowing for configurable
  result type projection, query types, and query configurations with defaults that match the v5-era
  separate methods.
• Some of the other new features added include configurable boundary-inclusivity, periodic boundary
  conditions, the within_unsorted_visit result mode to avoid materialization of results, TryFrom
  for converting between different KdTree types, new_from_source, and replace_item.
• Distance metric coverage has also been expanded and tidied up, including the addition of Chebyshev
  and Minkowski metrics and support for queries whose result type is wider than the
  stored coordinate type, which is especially important for fixed-point trees.
• With regard to the Stem Strategy trait system, alongside the Eytzinger ordering from v5 and prior
  is still available but now supports configurable prefetch behaviour. I've introduced the new
  Donnelly stem ordering via a family of stem strategies, featuring configurable pre-fetch and block size,
  unrolled traversal, SIMD descent, and full SIMD pruning and backtracking variants. The SIMD variant
  contains custom AVX2, AVX512, and NEON kernels.

🐛 Bug Fixes

• Preserve mutable leaf split associations (@sdd)

Almost a year in the making and counting, Kiddo v6 is effectively a full rewrite, addressing some long-standing issues.

• V6 represents a fundamental shift to a unified single KdTree struct, replacing the previous mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has been removed by introducing the LeafStrategy trait, which the KdTree has as a generic parameter. LeafStrategies can be mutable or immutable.
• KdTree is also now generic over the new StemStrategy trait too. The combination of these two orthogonal traits allow experimentation and selection of alternative stem layouts and traversal mechanisms, alongside configurable leaf strategies, for performance experimentation.
• The query API has been refactored from a handful of separate methods that were not particularly cohesive into a single unified fluent builder API. The builder approach is much more orthogonal, and protects against breaking changes when new options are introduced in the future. It permits constraints to be encoded in the type system for impossible option combinations, prevents the need for as many methods that differ only by some combination of features; allowing for configurable result type projection, query types, and query configurations with defaults that match the v5-era separate methods.
• Some of the other new features added include configurable boundary-inclusivity, periodic boundary conditions, the within_unsorted_visit result mode to avoid materialization of results, TryFrom for converting between different KdTree types, new_from_source, and replace_item.
• Distance metric coverage has also been expanded and tidied up, including the addition of Chebyshev and Minkowski metrics and support for queries whose result type is wider than the stored coordinate type, which is especially important for fixed-point trees.
• With regard to the Stem Strategy trait system, alongside the Eytzinger ordering from v5 and prior is still available but now supports configurable prefetch behaviour. I've introduced the new Donnelly stem ordering via a family of stem strategies, featuring configurable pre-fetch and block size, unrolled traversal, SIMD descent, and full SIMD pruning and backtracking variants. The SIMD variant contains custom AVX2, AVX512, and NEON kernels.

🐛 Bug Fixes

• Preserve mutable leaf split associations (@sdd)

✨ Features

• Add result capacity hint for radius queries (@sdd)

• Add adaptive parallel tree construction (@sdd)

• Specialize within-radius result projection (@sdd)

🐛 Bug Fixes

• Handle padded stems in parallel construction (@sdd)

♻️ Refactor

• Within_unsorted to a visitor (@sdd)

• Switch from propagating points as indexes to actual values (@sdd)

🧪 Testing

• Add result collection threshold profiler (@sdd)

• Add v6 release parity benchmark suites (@sdd)

• Add point projection benchmark (@sdd)

🤖 CI

• Add stem strategy benchmark variant (@sdd)

• Rename basic benchmark variant (@sdd)

• Pass benchmark features explicitly (@sdd)

• Cap leaf benchmark tree size (@sdd)

• Fix leaf benchmark export filter (@sdd)

• Cap benchmark trees at 2^25 (@sdd)

• Fix benchmark v5-v6 chart matching (@sdd)

• Add ISA-specific stem benchmark reporting (@sdd)

• Add tree construction benchmarks (@sdd)

🧹 Chore

• Bump actions/download-artifact from 4 to 8 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Bump actions/upload-artifact from 4 to 7 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Bump actions/setup-python from 5 to 7 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Add external comparison and projection tooling (@sdd)

• Remove projection design markdown (@sdd)

• Remove throwaway projection benchmark (@sdd)

✨ Features

• Add result capacity hint for radius queries (@sdd)

• Add adaptive parallel tree construction (@sdd)

• Specialize within-radius result projection (@sdd)

🐛 Bug Fixes

• Handle padded stems in parallel construction (@sdd)

♻️ Refactor

• Within_unsorted to a visitor (@sdd)

• Switch from propagating points as indexes to actual values (@sdd)

🧪 Testing

• Add result collection threshold profiler (@sdd)

• Add v6 release parity benchmark suites (@sdd)

• Add point projection benchmark (@sdd)

🤖 CI

• Add stem strategy benchmark variant (@sdd)

• Rename basic benchmark variant (@sdd)

• Pass benchmark features explicitly (@sdd)

• Cap leaf benchmark tree size (@sdd)

• Fix leaf benchmark export filter (@sdd)

• Cap benchmark trees at 2^25 (@sdd)

• Fix benchmark v5-v6 chart matching (@sdd)

• Add ISA-specific stem benchmark reporting (@sdd)

• Add tree construction benchmarks (@sdd)

🧹 Chore

• Bump actions/download-artifact from 4 to 8 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Bump actions/upload-artifact from 4 to 7 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Bump actions/setup-python from 5 to 7 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Add external comparison and projection tooling (@sdd)

• Remove projection design markdown (@sdd)

• Remove throwaway projection benchmark (@sdd)

✨ Features

• Make local query scratch the default (@sdd)

🐛 Bug Fixes

• Remove broken dot product dist metric and associated code (@sdd)

⚡️ Performance

• Alternate path to avoid wasted calcs on descent (@sdd)

• Add IS_SIGNED assoc value to Axis (@sdd)

• Dist1 on Manhattan and Chebyshev use saturating_dist (@sdd)

• Improved offset update for Chebyshev and Manhattah (@sdd)

• Use fused linear insertion for threshold vec results (@sdd)

• Tune sorted and unsorted threshold vec limits (@sdd)

🤖 CI

• Harden pre-release string updater workflow against no changes (@sdd)

• Publish custom benchmark reports (@sdd)

• Add bench chart justfile tasks (@sdd)

• Fix benchmark workflow bootstrap (@sdd)

• Derive benchmark key without just (@sdd)

• Pass benchmark args to just correctly (@sdd)

• Pass benchmark recipe arguments positionally (@sdd)

• Authenticate initial benchmark pages push (@sdd)

• Rank featured chart by relative change (@sdd)

• Add distance metric ISA matrix (@sdd)

• Fix distance metric ISA benchmark builds (@sdd)

• Simplify benchmark workflows (@sdd)

• Fix benchmark workflow shellcheck (@sdd)

• Suggest benchmarks for performance-sensitive PRs (@sdd)

• Use heuristic benchmark suggestions (@sdd)

• Allow benchmark suggestion comment updates (@sdd)

• Add leaf strategy benchmark variant (@sdd)

• Allow org members to trigger benchmark runs (@sdd)

• Clarify benchmark run names (@sdd)

• Split nightly debug and release tests (@sdd)

🧹 Chore

• Bump actions/setup-node from 6 to 7 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Update las requirement in the cargo-dependencies group (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

✨ Features

• Make local query scratch the default (@sdd)

🐛 Bug Fixes

• Remove broken dot product dist metric and associated code (@sdd)

⚡️ Performance

• Alternate path to avoid wasted calcs on descent (@sdd)

• Add IS_SIGNED assoc value to Axis (@sdd)

• Dist1 on Manhattan and Chebyshev use saturating_dist (@sdd)

• Improved offset update for Chebyshev and Manhattah (@sdd)

• Use fused linear insertion for threshold vec results (@sdd)

• Tune sorted and unsorted threshold vec limits (@sdd)

🤖 CI

• Harden pre-release string updater workflow against no changes (@sdd)

• Publish custom benchmark reports (@sdd)

• Add bench chart justfile tasks (@sdd)

• Fix benchmark workflow bootstrap (@sdd)

• Derive benchmark key without just (@sdd)

• Pass benchmark args to just correctly (@sdd)

• Pass benchmark recipe arguments positionally (@sdd)

• Authenticate initial benchmark pages push (@sdd)

• Rank featured chart by relative change (@sdd)

• Add distance metric ISA matrix (@sdd)

• Fix distance metric ISA benchmark builds (@sdd)

• Simplify benchmark workflows (@sdd)

• Fix benchmark workflow shellcheck (@sdd)

• Suggest benchmarks for performance-sensitive PRs (@sdd)

• Use heuristic benchmark suggestions (@sdd)

• Allow benchmark suggestion comment updates (@sdd)

• Add leaf strategy benchmark variant (@sdd)

• Allow org members to trigger benchmark runs (@sdd)

• Clarify benchmark run names (@sdd)

• Split nightly debug and release tests (@sdd)

🧹 Chore

• Bump actions/setup-node from 6 to 7 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Update las requirement in the cargo-dependencies group (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

✨ Features

• Configurable scratch location (@sdd)

• Introduce QueryMetric public trait (@sdd, Fixes:Issue #390)

• Ensure third-party leaf strategies can be used (@sdd)

• Add example showing how to embed a kd-tree (@sdd)

• Add ThresholdVecResultCollection for small-k nearest_n (@cbueth)

🐛 Bug Fixes

• Add dafault impl of LeafStrategy::new_with_empty_leaf (@sdd)

• Cache threshold_distance in ThresholdVecResultCollection (@cbueth)

• Apply ThresholdVecResultCollection to scratch-based nearest_n path (@cbueth)

• Dispatch into_sorted_vec() through into_vec() in ThresholdVec (@cbueth)

• Extend ThresholdVec optimisation to unsorted nearest_n path (@cbueth)

⚡️ Performance

• Pre-allocate unsorted result Vec with capacity 64 (@cbueth)

• Use select_nth_unstable extraction in ThresholdVecResultCollection (@cbueth)

• Hybrid sorted-vec result collection for small-k nearest_n (@cbueth)

🧪 Testing

• Add regression test to ensure KdTree::default works (@sdd)

• Add k=21 nearest_n_within case for BinaryHeap coverage, remove padding test (@cbueth)

🤖 CI

• Prepare embedded example artifacts in CI (@sdd)

• Add bencher for master push and non-fork PRs (@sdd)

• Run codspeed in simulation mode only (@sdd)

• Install cmake for bencher runner (@sdd)

• Add eytzinger nearest_n bencher profiles (@sdd)

• Allow bencher runs for collaborators or manually permissioned forks (@sdd)

• Switch to standard collab model now that repo is in a personal org (@sdd)

• Ensure examples/data is .gitignored (@sdd)

• Ensure git-cliff emits well-formatted md (@sdd)

• Ensure git-cliff emits well-formatted md (@sdd)

• Ensure git-cliff emits well-formatted md (@sdd)

• Git-cliff nicer formatting (@sdd)

• Git-cliff fix formatting yet again (@sdd)

🧹 Chore

• Bump LoliGothick/clippy-check (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Migrate config renovate.json (@renovate[bot])

• Move binaries to be examples or benches to avoid confusion in the crates.io page (@sdd)

• Bump actions/github-script from 8 to 9 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Bump LoliGothick/clippy-check (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Update reqwest dep (@sdd)

• Update rust crate zip to v8 (@renovate[bot])

• Update git-cliff config (@sdd)

• Workflow to permit /intro comments on release-plz prs (@sdd)

• Ensure release-plz and intro-comment format changelog (@sdd)

✨ Features

• Configurable scratch location (@sdd)

• Introduce QueryMetric public trait (@sdd, Fixes:Issue #390)

• Ensure third-party leaf strategies can be used (@sdd)

• Add example showing how to embed a kd-tree (@sdd)

• Add ThresholdVecResultCollection for small-k nearest_n (@cbueth)

🐛 Bug Fixes

• Add dafault impl of LeafStrategy::new_with_empty_leaf (@sdd)

• Cache threshold_distance in ThresholdVecResultCollection (@cbueth)

• Apply ThresholdVecResultCollection to scratch-based nearest_n path (@cbueth)

• Dispatch into_sorted_vec() through into_vec() in ThresholdVec (@cbueth)

• Extend ThresholdVec optimisation to unsorted nearest_n path (@cbueth)

⚡️ Performance

• Pre-allocate unsorted result Vec with capacity 64 (@cbueth)

• Use select_nth_unstable extraction in ThresholdVecResultCollection (@cbueth)

• Hybrid sorted-vec result collection for small-k nearest_n (@cbueth)

🧪 Testing

• Add regression test to ensure KdTree::default works (@sdd)

• Add k=21 nearest_n_within case for BinaryHeap coverage, remove padding test (@cbueth)

🤖 CI

• Prepare embedded example artifacts in CI (@sdd)

• Add bencher for master push and non-fork PRs (@sdd)

• Run codspeed in simulation mode only (@sdd)

• Install cmake for bencher runner (@sdd)

• Add eytzinger nearest_n bencher profiles (@sdd)

• Allow bencher runs for collaborators or manually permissioned forks (@sdd)

• Switch to standard collab model now that repo is in a personal org (@sdd)

• Ensure examples/data is .gitignored (@sdd)

• Ensure git-cliff emits well-formatted md (@sdd)

• Ensure git-cliff emits well-formatted md (@sdd)

• Ensure git-cliff emits well-formatted md (@sdd)

• Git-cliff nicer formatting (@sdd)

• Git-cliff fix formatting yet again (@sdd)

🧹 Chore

• Bump LoliGothick/clippy-check (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Migrate config renovate.json (@renovate[bot])

• Move binaries to be examples or benches to avoid confusion in the crates.io page (@sdd)

• Bump actions/github-script from 8 to 9 (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Bump LoliGothick/clippy-check (@dependabot[bot], Signed-off-by:dependabot[bot] [email protected])

• Update reqwest dep (@sdd)

• Update rust crate zip to v8 (@renovate[bot])

• Update git-cliff config (@sdd)

• Workflow to permit /intro comments on release-plz prs (@sdd)

• Ensure release-plz and intro-comment format changelog (@sdd)

Almost a year in the making and counting, Kiddo v6 is effectively a full rewrite, addressing some
long-standing issues.

• V6 represents a fundamental shift to a unified single KdTree struct, replacing the previous
  mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has
  been removed by introducing the LeafStrategy trait, which the KdTree has as a generic parameter.
  LeafStrategies can be mutable or immutable.
• KdTree is also now generic over the new StemStrategy trait too. The combination of these two
  orthogonal traits allow experimentation and selection of alternative stem layouts and traversal
  mechanisms, alongside configurable leaf strategies, for performance experimentation.
• The query API has been refactored from a handful of separate methods that were not particularly
  cohesive into a single unified fluent builder API. The builder approach is much more orthogonal,
  and protects against breaking changes when new options are introduced in the future. It permits
  constraints to be encoded in the type system for impossible option combinations, prevents the need
  for as many methods that differ only by some combination of features; allowing for configurable
  result type projection, query types, and query configurations with defaults that match the v5-era
  separate methods.
• Some of the other new features added include configurable boundary-inclusivity, periodic boundary
  conditions, the within_unsorted_visit result mode to avoid materialization of results, TryFrom
  for converting between different KdTree types, new_from_source, and replace_item.
• Distance metric coverage has also been expanded and tidied up, including the addition of Chebyshev
  Minkowski, and Dot Product metrics and support for queries whose result type is wider than the
  stored coordinate type, which is especially important for fixed-point trees.
• With regard to the Stem Strategy trait system, alongside the Eytzinger ordering from v5 and prior
  is still available but now supports configurable prefetch behaviour. I've introduced the new
  Donnelly stem ordering via a family of stem strategies, featuring configurable pre-fetch and block size,
  unrolled traversal, SIMD descent, and full SIMD pruning and backtracking variants. The SIMD variant
  contains custom AVX2, AVX512, and NEON kernels.

Almost a year in the making and counting, Kiddo v6 is effectively a full rewrite, addressing some long-standing issues.

• V6 represents a fundamental shift to a unified single KdTree struct, replacing the previous mutable/immutable and float/fixed splits. The need for separate mutable / immutable trees has been removed by introducing the LeafStrategy trait, which the KdTree has as a generic parameter. LeafStrategies can be mutable or immutable.
• KdTree is also now generic over the new StemStrategy trait too. The combination of these two orthogonal traits allow experimentation and selection of alternative stem layouts and traversal mechanisms, alongside configurable leaf strategies, for performance experimentation.
• The query API has been refactored from a handful of separate methods that were not particularly cohesive into a single unified fluent builder API. The builder approach is much more orthogonal, and protects against breaking changes when new options are introduced in the future. It permits constraints to be encoded in the type system for impossible option combinations, prevents the need for as many methods that differ only by some combination of features; allowing for configurable result type projection, query types, and query configurations with defaults that match the v5-era separate methods.
• Some of the other new features added include configurable boundary-inclusivity, periodic boundary conditions, the within_unsorted_visit result mode to avoid materialization of results, TryFrom for converting between different KdTree types, new_from_source, and replace_item.
• Distance metric coverage has also been expanded and tidied up, including the addition of Chebyshev and Minkowski metrics and support for queries whose result type is wider than the stored coordinate type, which is especially important for fixed-point trees.
• With regard to the Stem Strategy trait system, alongside the Eytzinger ordering from v5 and prior is still available but now supports configurable prefetch behaviour. I've introduced the new Donnelly stem ordering via a family of stem strategies, featuring configurable pre-fetch and block size, unrolled traversal, SIMD descent, and full SIMD pruning and backtracking variants. The SIMD variant contains custom AVX2, AVX512, and NEON kernels.

Ci

• Don't run comitlint for dependabot PRs
• Add v5 eytzinger profile benchmarks
• Split v5 nightly debug and release tests
• Allow nightly chunks lint at MSRV
• Stop ignoring the pinned v5 lockfile

🐛 Bug Fixes

• Correct v5 unsorted nearest-n parity reporting
• Preserve stem alignment in rkyv conversion
• Use metric accumulation for immutable nearest one
• Allow mutable splits past constant axes

🧪 Testing

• Add v5 release parity benchmark reporting

🧹 Chore

• Bump LoliGothick/clippy-check, Signed-off-by:dependabot[bot] [email protected]
• Bump rand deps
• Bump criterion deps
• Bump LoliGothick/clippy-check, Signed-off-by:dependabot[bot] [email protected]
• Bump codecov/codecov-action from 5 to 7, Signed-off-by:dependabot[bot] [email protected]
• Bump actions/checkout from 6 to 7, Signed-off-by:dependabot[bot] [email protected]
• Bump LoliGothick/clippy-check, Signed-off-by:dependabot[bot] [email protected]
• Bump actions/cache from 5 to 6, Signed-off-by:dependabot[bot] [email protected]
• Bump LoliGothick/clippy-check, Signed-off-by:dependabot[bot] [email protected]
• Bump LoliGothick/clippy-check, Signed-off-by:dependabot[bot] [email protected]
• Bump LoliGothick/clippy-check, Signed-off-by:dependabot[bot] [email protected]
• Pin v5 lockfile for msrv
• Bump actions/upload-artifact from 4 to 7, Signed-off-by:dependabot[bot] [email protected]
• Bump actions/setup-python from 5 to 7, Signed-off-by:dependabot[bot] [email protected]
• Bump actions/download-artifact from 4 to 8, Signed-off-by:dependabot[bot] [email protected]

Ci

• Backport workflow and repo config updates
• Backport build and coverage workflow updates

🐛 Bug Fixes

• Add msrv, use algernative to f64::fract

💄 Styling

• Formatting and clean up unneeded md file

Ci

• Backport workflow and repo config updates
• Backport build and coverage workflow updates

🐛 Bug Fixes

• Add msrv, use alernative to f64::fract

💄 Styling

• Formatting and clean up unneeded md file

🐛 Bug Fixes

• Add a compile-time assertion to prevent bucket size of less than 2 for KdTree to avoid UB when trying to split a bucket of size 1. Fixes https://github.com/sdd/kiddo/issues/295. (Note that even though bucket sizes of 2 are possible, I would generally not recommend using a value of B below 32 anyway, for best performance.)

I'm extremely grateful to @cbueth for his fantastic set of contributions to this release. The new distance metrics are a great addition to the library, come with extensive tests, and he was even able to contribute a big fix and some welcome refactors along the way. Thanks very much, Carlson!

✨ Features

• Add Chebyshev (L_∞ norm) distance metric (https://github.com/sdd/kiddo/pull/290, @cbueth)
• Add Generalised Minkowski (L_p norm) distance metric (https://github.com/sdd/kiddo/pull/291, @cbueth)
• Add *_exclusive methods for querying with an exclusive (<) rather than inclusive (<=) boundary check (https://github.com/sdd/kiddo/pull/294, @cbueth)

🐛 Bug Fixes

• Ensure that all existing query methods have boundary checks that are inclusive (<=), in line with typical k-d tree expectations (@cbueth) If you were relying on these checks being exclusive, switch over to using the new *_exclusive variants of the query methods.

Docs

• Correct a mistake in the docs for fixed::distance::Manhattan (https://github.com/sdd/kiddo/pull/283, @Luca-spopo)

Deps

• update cmov dep from 0.4 to 0.5 (@sdd)

Deps

• update cmov dep from 0.3 to 0.4 after 0.3 got yanked (see https://github.com/RustCrypto/utils/issues/1304). Thanks @yuby and @jqnatividad

🐛 Bug Fixes

• Correct slice access in remainder processing and remove unsafe (@MarkusZoppelt)
• Use try_from() with error for leaf_items.len() (@MarkusZoppelt)

♻️ Refactor

• within_unsorted_iter no longer uses a generator (@KvA2KLvAST)
• Remove needless SubAssign trait bound from Content trait

Deps

• Remove doc-comment dependency and use doc attribute that was added in Rust 1.54 instead (@jqnatividad)
• Use doc attribute instead of doc_comment! (@jqnatividad)
• Update actions/checkout action to v6
• Update codspeedhq/action action to v4
• Update ad-m/github-push-action action to v1
• Update rust crate rstest to 0.26
• Update rust crate codspeed-criterion-compat to v4

Ci

• Update CI workflow triggers to include PR and workflow_dispatch
• Permit coverage to run for PRs as well
• Fix release-plz and add commitlint

💄 Styling

• Remove unnecessary parentheses
• Fix formatting
• Fix some lint issues

🧪 Testing

• Add regression test for remainder slice access bug (@MarkusZoppelt)

🐛 Bug Fixes

• Correct slice access in remainder processing and remove unsafe (@MarkusZoppelt)
• Use try_from() with error for leaf_items.len() (@MarkusZoppelt)

♻️ Refactor

• within_unsorted_iter no longer uses a generator (@KvA2KLvAST)
• Remove needless SubAssign trait bound from Content trait

Deps

• Remove doc-comment dependency and use doc attribute that was added in Rust 1.54 instead (@jqnatividad)
• Use doc attribute instead of doc_comment! (@jqnatividad)
• Update actions/checkout action to v6
• Update codspeedhq/action action to v4
• Update ad-m/github-push-action action to v1
• Update rust crate rstest to 0.26
• Update rust crate codspeed-criterion-compat to v4

Ci

• Update CI workflow triggers to include PR and workflow_dispatch
• Permit coverage to run for PRs as well
• Fix release-plz and add commitlint

💄 Styling

• Remove unnecessary parentheses
• Fix formatting
• Fix some lint issues

🧪 Testing

• Add regression test for remainder slice access bug, Signed-off-by:Markus Zoppelt [email protected]

📝 Documentation

• Update some stale documentation. Remove the global_allocate feature which is no longer used for anything

It's been a while since the last release as my focus has been elsewhere, but I'm back in the k-d tree groove now and looking to bring some new features and performance updates over the next few weeks.

The major addition in this release is support for version 0.8 of Rkyv. Rkyv 0.8 is almost a complete rewrite compared to 0.7, and so this required quite a lot of changes.

Right now, the pre-existing rkyv crate feature still provides support for Rkyv 0.7 as before, and so the introduction of Rkyv 0.8 is non-breaking. To use Rkyv 0.8, enable the crate feature that is unsurprisingly named rkyv_08. There are some caveats to Rkyv 0.8 support:

• The rkyv 0.8.x Archived structs are prefixed with ArchivedR8 rather than Archived to avoid clashing with the pre-existing rkyv 0.7 types.
• You're unlikely to be able to successfully deserialize a tree serialized with Rkyv 0.7 into an Rkyv 0.8 object, and vice-versa.
• Anyone using rkyv and f16 / half at the same time may encounter issues updating to Rkyv 0.8. This is because the half crate only supports Rkyv 0.7 at version 2.4.1 and below, and only supports Rkyv 0.8 at versions 2.5.0+.
• Supporting both Rkyv 0.7 and 0.8 in the Kiddo crate at the same time is a massive pain and will add significant maintenance burden going forward. As such, this 5.x.x branch will be the only one that supports both Rkyv 0.7 and Rkyv 0.8. An upcoming version 6 of Kiddo will remove support for Rkyv 0.7 entirely and only support Rkyv 0.8. At this point the annoying non-standard ArchivedR8 prefix for the rkyv 0.8 types will be dropped in favour of the default naming scheme.

✨ Features

• Add support for Rkyv v0.8
• Gate fixed support behind a crate feature to reduce compile times
• Preallocate binary heap capacity

🧪 Testing

• Fixup rkyv doctests

Ci

• Update github actions to exercise rkyv_08 feature
• Update renovate bot config so that it ignores deps that are pined to old versions for legacy feature compatibility

Chore

• address spacing causing clippy lint failure
• Update rust crate rstest to 0.25
• Convert doctest file load unwraps to expects to help track down when files are missing
• Clean up unused deps and move some deps to dev-deps that did not need to be full deps
• Update to latest versions of rand crates
• Update to latest version of criterion
• Update bincode dev dep to v2 for serde example
• Update itertools dependency to 0.14
• Update formatting to comply with updated clippy rules of recent versions of Rust
• Update rust crate ordered-float to v5

All the best! Scott (@sdd)

5.1.0 was yanked. It only supported Rkyv 0.7 and 0.8 in a mutually exclusive way, but I found a way to support both simultaneously a few days after publishing 5.1.0. This came at the expense of being a breaking change to 5.1.0, and to respect semver I'd have needed to release a 6.0.0 version that would have been immediately superseded by 7.0.0 that removed rkyv 0.7. Since 5.1.0 had only been out for a couple of days, and since the mutual exclusivity meant that the rkyv 0.8 structs were not even mentioned in the 5.1.0 docs on docs.rs, I chose to yank 5.1.0 instead.

Deps

• Update generator dependency to 0.8.4, Fixes:https://github.com/sdd/kiddo/issues/182

🐛 Bug Fixes

• Disable broken get_best_from_dists_f64_avx2 until fixed
• only export WithinUnsortedIter on archs where the within_unsorted_iter mod is configured (https://github.com/sdd/kiddo/issues/190)
• fix: consistently use CACHELINE_ALIGN (https://github.com/sdd/kiddo/issues/190)

Performance

• fix a performance regression on the immutable tree.

Documentation

• ensure that the top-level documentation example shows v5 being imported.

Version 5 bundles a complete re-write of ImmutableKdTree alongside some rationalization of feature names and a change of type of the max_qty parameter present in some query methods from usize to NonZero<usize>.

ImmutableKdTree rewrite

BREAKING CHANGE: For anyone that has been serializing ImmutableKdTree (using either serde or rkyv), version 5 constitutes a breaking change as serialized trees from prior versions will not be deserializable with v5 and vice-versa.

Quite a few people (https://github.com/sdd/kiddo/issues/172, https://github.com/sdd/kiddo/issues/158, https://github.com/sdd/kiddo/issues/78) have previously unsuccessfully tried to use ImmutableKdTree with data containing many points that have the same value on one or more of their axes, for example point cloud data containing many points on a flat axis-aligned plane. The v5 rewrite of ImmutableKdTree experiences none of these kinds of problems and can be safely used no matter what your data looks like. Query performance is in many cases faster than the prior version, but sometimes slightly slower - your mileage may vary but differences in query performance is pretty small. Construction performance is considerably improved, with up to a 2x speedup, with the improvement becoming more pronounced as the tree size increases. Memory efficiency is slightly better also.

Behind-the-scenes, the structure of the ImmutableKdTree has changed from using a Vec of fixed-size array-based buckets to using a single array-of-vecs to store all the points, with per-bucket offsets being stored for each leaf. To avoid dynamic allocation at query time, a fixed slice that chunks the bucket is used, permitting autovectorisation to work well and giving the opportunity for manual SIMD to be used on the fixed-length slice. Trailing values beyond the last full slice are processed individually.

Modified van Emde Boas Stem Ordering

The experimental modified_van_emde_boas feature allows an alternative stem node ordering mode to be enabled. When enabled, the ordering of stem nodes changes from using Eytzinger ordering to a modified van Emde Boas (can I call this a Donnelly ordering? :-p) order. This is a novel implementation unique to Kiddo v5 that ensures that a cache line only needs to be retrieved at most once every three levels (on most CPUs when using f64), or every four levels (on most CPUs when using f32). This increases by an extra one level on CPU architectures with a 128-byte cache line width (this is quite rare at the moment but can be found on some Apple M3 and newer CPUs). Previous literature has indicated that a standard van Emde Boas layout provided no advantage, but thanks to an efficient branchless implementation of the stem ordering logic, and a refinement to leave the last slot on each cache line empty, rather than straddling levels across cache lines, cache efficiency is improved to the point where gains can sometimes be seen over the previously-best Eytzinger layout. Typically, performance varies from between 1% faster an 5% slower than Eytzinger, from what I've seen during testing, with the differences often being statistically insignificant.

ImmutableKdTree + rkyv

The v5 ImmutableKdTree uses an Aligned Vec internally for storing stem nodes. It is not possible to zero-copy deserialize into an Aligned Vec with rkyv as there is no guarantee that the stem vec in the underlying buffer respects the alignment. As such, unfortunately this means that ImmutableKdTree itself can't be fully zero-copy serialized / deserialized, but there are some related types that are provided that allow zero-copy deserialization to be performed for all other parts of the tree except for the stems, which themselves get copied into an aligned array from the buffer. In practice this is still very fast as the stems are only a very small part of the overall tree.

See immutable-rkyv-serialize and immutable-rkyv-deserialize in the examples for how to do this.

Feature name changes

BREAKING CHANGE: It was pointed out in https://github.com/sdd/kiddo/issues/159 that it was necessary to enable both rkyv and serialize_rkyv features to use Rkyv serialization. I took the opportunity of the major version bump to rationalize the feature names to make them easier to use. serialize_rkyv has been removed and now only rkyv feature is needed to enable Rkyv serialization. serialize has been renamed to serde in line with ecosystem conventions. half has been renamed to f16 for clarity (but is not needed for f16 support anyway and is only used to ensure that the half crate is only depended upon within the "half" examples and not as a core dependency)

max_qty Changed to NonZero<usize>

BREAKING CHANGE: It was noted by @ezrasingh that specifying max_qty as 0 in version 4.2.1 alongside sorted = false resulted in a panic. Since requesting a max_qty of zero makes no sense, and to avoid adding a run-time check for users who have no possibility of specifying a max_qty of 0, the type of max_qty has been changed to NonZero<usize> to make this a compile-time check instead.

Chore

• Refactor trait bounds to silence new clippy lints
• Silence new lint error
• Silence error regarding doc_cfg no longer working
• Update codspeedhq/action action to v3
• Update rust crate generator to 0.8.1

🐛 Bug Fixes

• Nearest_n_within does not limit num of items when not sorted, Issue:https://github.com/sdd/kiddo/issues/168
• Update rust crate itertools to 0.13

✨ Features

• Add f16 support, example and docs to show usage with half crate

🐛 Bug Fixes

• Prevent assertion failure when stem optimisation needs a large shift

🐛 Bug Fixes

• Prevent overflow in capacity_with_bucket_size on non-64 bit architectures

Chore

• Remove unused import
• Update actions/cache action to v4
• Update codecov/codecov-action action to v4
• Update baptiste0928/cargo-install action to v3

Ci

• Fix issue with CI lint steps

Deps

• Relax strictness of some deps to reduce renovate noise

♻️ Refactor

• Remove need for gated import

✨ Features

• Make tracing an optional dependency gated by tracing feature flag
• Iterate over trees
• Make rand and rayon optional

🐛 Bug Fixes

• Stdsimd removed from unstable, fix:fixup simd removal
• Add missing global_allocate feature definition and sort feature defs alphabetically
• Update benches to require test_utils feature. update clippy and test steps to include new test_utils feature
• Claytonwramsey bug, Fixes:#138

🧪 Testing

• Fix iter doctests and remove unused var
• Add hacky workaround to enable tests to run without having to specify --features=test_utils

Despite the major version bump, this is unlikely to be a breaking change for any users. The within_unsorted_iter method of ImmutableKdTree is now only present on x86_64 and Aarch64 targets. Considering that v3.0.0 would not even compile on these targets when the immutable crate feature was activated, it seems vanishingly unlikely that this breaks anyone. Additionally, the immutable feature has been removed and the global_allocate feature added. If you were using ImmutableKdTree and your build breaks because the immutable feature does not exist - don't worry, you don't need it anymore. Simply remove any reference to it ant the ImmutableKdTree should be available without it.

✨ Features

• ImmutableKdTree now works on stable

🐛 Bug Fixes

• Update rust crate itertools to 0.12
• Re-enable support for wasm targets

📝 Documentation

• Update feature docs in lib.rs

I can't believe how long it has taken me to get v3 into shape, but it's finally here! :tada:

The ImmutableKdTree is finally ready! :tada: Designed for use cases where all the points that you need to add to the tree are known up-front, and no modifications need to be made after the tree is initially populated. ImmutableKdTree balances and optimises the tree at construction time, ensuring much more efficient memory usage (and a correspondingly smaller size on-disk for serialized trees). Since the interior nodes of the ImmutableKdTree also take up less space in memory, more of them can fit in the CPU cache, potentially improving performance in some cases.

The immutable crate feature needs to be activated in order to use ImmutableKdTree. More info on ImmutableKdTree can be found below in the 3.0.0 beta and RC changelog entries.

Version 3.x changes the distance metrics syntax, switching from function pointers to a trait-based approach that permitted some ergonomics and performance improvements. This is a breaking change though: whereas prior to v3, you may have had queries that look like this:

use kiddo::distance::squared_euclidean;

let result = kdtree.nearest_one(&[0f64, 0f64], &squared_euclidean);

Now in v3, you'll need to switch to this syntax:

use kiddo::SquaredEuclidean;

let result = kdtree.nearest_one::<SquaredEuclidean>(&[0f64, 0f64]);

Features

• the ImmutableKdTree is now only usable by enabling the immutable crate feature. This ensures that the crate as a whole retains compatible with stable rust, as ImmutableKdTree depends on some unstable features at present.

Refactors

• Leaf nodes for Immutable now store their points in columnar format. Searches across them have been re-written to autovectorise better. This has been tested on Compiler Explorer to demonstrate that AVX512 instructions are generated, ensuring vectorization is as wide as is possible. Handwritten SIMD intrinsics have been used (activated by enabling the simd crate feature) to manually vectorise code that the compiler could not autovectorise. NOTE simd is currently quite unstable and not as well tested as the rest of the library, so use it with caution until it stabilizes in the full v3.0.0 release!

Style / Tests

• Increase reliability of within() test for ImmutableKdTree.
• Remove some commented-out code and some useless comments

Style / Tests

• Increase reliability of within() test for ImmutableKdTree.
• Remove some commented-out code and some useless comments in some tests

Introducing the ImmutableKdTree for floating point! :tada:

ImmutableKdTree is intended for use when the smallest possible on-disk serialized size of a tree is of paramount importance, and / or the fastest possible query speed is required.

Expect improvements in query time of 10-15%, and a reduction in the size of serialized trees by 33% or so on average.

These capabilities come with a few trade-offs:

1. This tree does not provide the capability to modify its contents after it has been constructed. The co-ordinates of the points to be stored must have all been generated in advance.
2. Construction time can be quite a bit slower. Typically, this can be twice as long as the default kiddo::float::kdtree::KdTree.
3. The more common that duplicate values are amongst your source points, the slower it will take to construct the tree. If you're using f64 data that is fairly random-ish, you will probably not encounter any issues. I've successfully created 250 million node ImmutableTree instances with random f64 data with no issues, limited only by RAM during construction. Likewise for f32 based trees, up to a few million nodes. As per the other Kiddo float-type trees, points being stored in the tree must be floats (f64 or f32 are supported currently).

Breaking Changes

• feat!: queries return structs instead of tuples. Query methods have been updated so that they all return either a NearestNeighbour, Vec<NearestNeighbour>, or Vec<BestNeighbour>, for consistency.
• feat!: use a trait instead of a function pointer for distance metrics (See SquaredEuclidean and Manhattan)
• feat: add within_unsorted_iter query

Performance

• perf: refactor within to simply sort the result of within_unsorted. Previously, within was keeping its results in a BinaryHeap and calling its into_sorted_vec method to, well, return a sorted Vec. Whilst a BinaryHeap is great if you are frequently adding and removing items, if your use case is to gradually add all your items, and then sort them all at once, it's quicker to just put things in a Vec and then sort the Vec at the end. Benchmarking shows that this change improves performance by anything from 5 to 60% in practice.

Fixes

• fix incompatibility with the num-traits feature of the fixed crate

Refactor

• update Axis trait to include some methods so that the nearest_one methods can be identical between float and fixed.
• float and fixed both use a common macro for best_n_within
• float and fixed both use a common macro for within_unsorted
• float and fixed both use a common macro for within
• float and fixed both use a common macro for nearest_n

CI

• Update pre-release.yml to remove Clippy check
• Add CI for format/clippy/test/coverage/release/publish