Manhattan Tree

The manhattan tree is a spatial tree, based on the octree, that allows logarithmic time insertion, removal, and querying for the element with the lowest manhattan distance to an arbitrary point in space.

Octree

The design of this tree is based on the octree.

The total domain of the coordinate space is represented as a cube. This cube can be recursively sub-divided into 8 octants.

We introduce two types for tracking these octants:

• The BaseCoord, containing unsigned integer coordinates, [u64; 3].
• The OctCoord, containing unsigned integer coordinates, [u64; 3], as well as scale factor, u8.

With these coordinates, we can define the two variants for an Octant (a node of the tree):

• Leaf, which contains a BaseCoord and some element that the tree is storing
• Branch, which contains an OctCoord and 8 optional child Octants

In the case of the branch, in each dimension, the branch's domain covers the coordinate range from coordinates[n] * (2 pow scale) (inclusive) to (coordinates[n] + 1) * (2 pow scale) (exclusive).

From here, we can lay out a couple important invariants:

1. Only leaves have elements
2. Only branches have children
3. An octant's domain is always a subdomain of its parent
4. A branch always has at least two children
5. Each of a branch's children are in a different suboctant of the branch

Tree shortening

This repository implements the manhattan tree in 3 dimensions, but it actually can work in any dimension. Let's take the example of a 1-dimensional manhattan tree.

A balanced 1-dimensional manhattan tree with 32 elements would look like this:

|----------------------------------------------------------------------------------------------|
|----------------------------------------------||----------------------------------------------|
|----------------------||----------------------||----------------------||----------------------|
|----------||----------||----------||----------||----------||----------||----------||----------|
|----||----||----||----||----||----||----||----||----||----||----||----||----||----||----||----|
|-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-||-|
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

A 1-dimensional manhattan tree has a branch factor of 2 pow 1 == 2, and log base 2 (32) == 5, and this tree has 5 branching layers (not including the root layer, or alternatively, not including the leaf layer), so it could be considered maximally efficient.

However, let's take a case where there are less elements, and we handle this incorrectly:

|----------------------------------------------------------------------------------------------|
|----------------------------------------------||----------------------------------------------|
|----------------------|                        |----------------------||----------------------|
            |----------|                                    |----------||----------|
                  |----|                                          |----||----|
                  |-||-|                                          |-|   |-|
                  6  7                                            22    24 

We have reduced the number of elements, but our tree is still just as tall. And remember, the time complexity of a tree is generally dependent on its height. We want to shorten the tree while maintaining invariants 1 and 3:

Only leaves have elements

An octant's domain is always a subdomain of its parent

Furthermore, this tree structure severely breaks invariant 4:

A branch always has at least two children

Fortunately, invariant 3 does not mean that an octant's domain must be a direct subdomain of its parent; it can be further down the chain. As such, we can shorten the tree by simply cutting out the branches which only have one child, thus actualizing invariant 4, as such:

|----------------------------------------------------------------------------------------------|
|----------------------------------------------||----------------------------------------------|
                  |-||-|                                          |-|   |-|
                  6  7                                            22    24 

Now, the tree only has a height of three, and each branch has at least two children. Remember that, that although it's now harder to see, each leaf is still in a different suboctant of its parent branch.

Bounds tracking

We include an additional piece of information in each octant, which was not previously mentioned. For each branch, and for each of the three dimensions, we encode the minimum and maximum component in that dimension stored in the entire subtree. This data must be properly maintained upon insertions or removal into the manhattan tree.

Manhattan distance

Given these invariants, we can efficiently perform the manhattan tree's namesake operation: find the element with closest manhattan distance to an arbitrary focus.

The focus is some arbitrary coordinate, just like any other key in the tree.

As such, the function for closest element by manhattan distance to a focus, in Rust-like pseudo code, is as follows:

fn closest(node: Octant, focus: BaseCoord, competitor: Option<BaseCoord>) -> Option<Leaf>:
    if node is a leaf:
        return the leaf, unless its mahattan dist (henceforth mdist) to focus is greater
        ...than the mdist between focus and competitor, if competitor exists
    if node is a branch:
        // here we take advantage of bounds to short circuit, which is the main performance boost
        if competitor exists:
            for each of the three dimensions:
                let a = competitor.mdist(focus)
                let b = the distance in that one dimension between focus, and node's 
                ...closest element to focus, according to the bounds tracking
                if a < b:
                    return None
    
        let best = None
        for each child, ordered nearest to furthest from focus:
            let child_competitor = {
                if best exists: Some(best's coord)
                else if competitor exists: Some(competitor)
                else: None
            } 
            if let Some(better) = closest(child, focus, child_competitor):
                best = Some(better)
        return best

Bit-level hacking

Many of these operations, which are brushed over by abstract explanations and pseudocode, require operations on coordinates, such as:

• Which suboctant of an OctCoord contains a certain BaseCoord
• Which suboctant of an OctCoord is closest to a certain BaseCoord
• Convert a OctCoord into a BaseCoord
• What is the lowest common OctCoord for which two BaseCoords are suboctants

Fortunately, because coordinates under the hood are stored as unsigned binary integers, and because recursive binary subdivision is performed on each dimension, the binary properties of the unsigned integers can be exploited to implement all of these operations using bitwise manipulation. This is best expressed in actual code, which can be found in the tree/coord module of this crate.

Performance

I ran a performance test on the tree, testing insertion, removal, and closest element querying, with different sizes of trees. To minimize external variables, these tests were run on a t2.medium server, rented from Amazon EC2, running Ubuntu server 18.04.

These results clearly show a logarithmic time complexity. Running an additional test, going up to a tree size of 100,000, I manually fitted a natural logarithm function to the data.

The curve appears to closely follow the relation:

time = 2220ns * ln(size) + 5200ns