Querying Multidimensional Data in Swift

Using k-d Trees in Swift

Real trees are nice to look at, but not related to k-d trees. Image by Valiphotos from Pixabay

Even in simple apps we are often dealing with multidimensional data. These are elements which contain more than one value, e.g. a struct User with the properties name, age, income and address. Performing queries on these elements based on multiple parameter can be quite time consuming, especially when searching through 100 000 or even 1 000 000 elements.

In this article we will explore socalled k-d trees to increase the performance of our apps. First, we will see what a k-d tree is and how it structures and stores data. Next, we will look at the framework KDTree, which allows us to easily convert any array to a k-d tree. Finally, we will test the performance of k-d trees and compare them with two ways of searching for a given element in an array.

What is a k-d tree

A k-d tree is a special kind of tree which stores data points with multiple dimensions (thus “k-dimensional tree”) and it can be used to perform range searches or for searching the nearest neighbor to a given point. The space of the points is divided into two parts in several steps. Each divider represents a new node in the tree.

Let’s look at an example from Wikipedia which builds a k-d tree for following points: (2, 3), (5, 4), (9, 6), (4, 7), (8, 1) and (7…