#avl-tree #nearest-neighbor #metrics #point #insertion #vp #updateable

nightly vp-avl

A combined Vantage-Point AVL tree, to make VP trees updateable

9 releases

0.1.8 Sep 30, 2024
0.1.7 Sep 29, 2024
0.1.5 Apr 4, 2024
0.1.4 Feb 19, 2024

#146 in Value formatting

Download history 10/week @ 2024-09-21 486/week @ 2024-09-28 30/week @ 2024-10-05 1/week @ 2024-10-12

429 downloads per month

MIT/Apache

44KB
918 lines

VP-AVL

This provides a novel type of VP-tree that also integrates features of an AVL tree, which allows insertion into the tree without complete rebuilding. In practice building the tree in bulk is still faster (empirically by about 40% for a tree with 1000 elements up to about a factor of 2.5 for a tree of 1,000,000), but obviously still much faster than rebuilding the tree upon every insertion.

To bulk insert with the provided Euclidean Metric and some type which implements IntoIterator, simply:

        let random_points = k_random(10000);

        let avl = VpAvl::bulk_insert(EuclideanMetric::default(), random_points);

or iteratively:

        let random_points = k_random(10000);

        let avl = VpAvl::new(EuclideanMetric::default());

        for point in random_points{
            avl.insert(point)
        }

To iterate through the nearest neighbors to a points, call nn_iter:

    let query_point = vec![1.0,1.0,2.0,3.0,5.0];

    for point in avl.nn_iter(&query_point){
        ...
    }

Dependencies

~315KB