The current performance is unacceptable. After profiling the code, it is clear that there are issues with cache locality. Here is the closure taking up 71.85% of all the time:

let lookup_distance = |index| (lookup(index) ^ feature).count_ones();

This performs a single trivial operation, so it looks innocuous, but it seems that the way hwt allows the user to store features outside of the tree is actually working against it, making it much slower than linear search (except maybe on huge data sets > 1B).

The API should be changed to give back features and not indices. The user can use their features to look up their data afterwards, which should have negligible performance impact since they only need to do a few lookups (k lookups for k-NN).

This has two negative impacts:

• This could make the tree slightly larger.
• This will make it harder for the user to store the data however they want.

Seeing as performance is the most important thing here, that takes precedence over these issues.

Profiling currently shows a lot of time is spent in FeatureHeap::add doing XOR, popcount, and comparations. We can speed this up with SIMD by doing the XOR, popcnt, and compares in parallel.

We can currently support approximate nearest neighbor search trivially by simply allowing neighbors that are at the current search radius + n. This means that we can be off by up to a distance of n. The performance gain should be high and it is easy to control precisely how much off you want to be (exactly by n at most).

$ cargo build
    Updating crates.io index
error: failed to select a version for the requirement `ahash = "^0.1.18"`
candidate versions found which didn't match: 0.8.0, 0.7.6, 0.7.5, ...
location searched: crates.io index
required by package `hwt v0.4.2`
    ... which is depended on by `bfp v0.1.0 (/workplace/amooren/sandbox/src/Amooren/bfp)`

Clean crate, just adding hwt latest version.

I'm interested in using this crate to collate hashes produced by my img_hash library. I started to work on an implementation of a multiple vantage-point tree but I haven't had the time to fill out the tests or even finish the documentation and I have a feeling it's going to perform pretty abysmally by default. I really prefer your approach in this crate as I feel like we're working in the same problem space.

However, one of the features of img_hash is that it can produce hashes of varying sizes depending on a user's preference between performance and accuracy. By default, I have it producing 64-bit hashes so representing them as u128 would be pretty wasteful, and I also want to experiment with hash sizes of 256 bits and maybe greater so in that case u128 would require discarding information from the hash.

In the 3.0.0-alpha I have yet to release I have a generic representation of hash bytes which gives the option of either allocating them on the heap (for dynamic sizes) or inline (to save a misdirection and possibly improve codegen). I think this kind of generic approach would benefit hwt as well but I'm wondering what your opinion is of it.

I don't entirely understand the HWT algorithm so I don't know if 128-bit features are integral to its function but I have a feeling it wouldn't be too difficult to generalize over any size feature as long as they're all the same size in the tree.

Currently the search module is implemented in a convenient, but inefficient, way. It defines an iterator for 2 bit slices, then another one for 4 bit slices that flat maps two 2 bit slice ones, and so on. This causes the type name length (Rust compiler/type issue) to grow out of control and then requires Box to be used to wrap the types. In addition to the type name length issue, it is also very wasteful because of how it uses up to 128 128-bit operations on 1-bit numbers. The search module should be refactored (possibly at the expense of code size) to accommodate speed. SIMD should be used where possible.

Performance is currently only beating linear (which is incredibly fast on modern processors) for exact search at > 1M features. This is probably beatable, but it will require some optimizations. Below is the list of optimizations and their issues that need to be made:

k-NN

• [x] Use packed_simd to speed up FeatureHeap::add
• [ ] Convert search module to use a hand-optimized iterator for each level of the tree
• [ ] Investigate if the search module can be sped up using SIMD or bit twiddling
• [ ] Implement more SIMD optimizations upstream in swar

Once we reach a search distance for the second nearest neighbor that exceeds the Lowes ratio, we know that the Lowes ratio test has succeeded. We should return a Result<u128, (u128, u128)> for this operation. If the Lowes ratio test succeeds, we return the nearest neighbor. If the Lowes ratio test fails, we return the nearest neighbor and also the feature that caused the Lowes ratio test to fail (which is the second nearest neighbor).

This will speed up photogrammetry algorithms because we can stop searching once the Lowes ratio has been fulfilled.