D-MTree (Downward-MTree)

This library implements a datastructure very similar to the MTree datastructure in pure python (for more information, see https://en.wikipedia.org/wiki/M-tree)

The main difference is that the split of a NonLeafNode (inner node) will not propagate to the parent node, but instead creates a new subtree with the two closest routing objects as descendants.

• This has the advantage that the covering-radii of the NonLeafNodes have the least overlap.
• The disadvantage is that if the points are added in an unlucky order, the depth of the tree can grow very fast!

Usage

def distance(p1, p2):
    return abs(p1 - p2)

dmtree = DMTree(distance_measure=distance, leaf_node_capacity=10, inner_node_capacity=5)

# inserting 1000 values with equal identifier:
for i in range(1000):
    dmtree.insert(identifier=i, value=i)     

# search in radius and order them by distance (ascending):
elements = dmtree.find_in_radius(value=50.5, radius=1)

# find the 10 nearest neighbours and order them by distance (ascending):
# the parameter 'truncate' decides if the results is trimmed to exactly k if there are multiple elements with the same distance
elements = dmtree.knn(value=50.5, k=10, truncate=True)

# deleting entries
for identifier in range(1000):
    dmtree.remove(identifier)

• identifier should be a datatype that can be compared with ==, <=, >=, <, >
• mtree.knn(value, k, truncate=True) is equal to mtree.knn(value, k, truncate=False)[:k]

Parameters

Split methods

Best practice

• When inserting the values, do so in a randomized order, or the resulting tree can very quickly become heavily unbalanced