Using KD Tree to Find the Nearest Neighbor

Let’s look at a spatial engine that provides KD Tree, to find the nearest neighbor!

KD Tree to Find the Nearest Neighbor and bounding box search

Are you tired of slow and inefficient algorithms for finding nearest neighbor in high-dimensional spaces? If so, you might want to consider using a KD tree, a versatile data structure that can significantly speed up your search queries.

A KD tree (short for k-dimensional tree) is a binary search tree that partitions the data points into regions based on their coordinates. Each internal node of the tree represents a hyperplane that divides the space into two subspaces, and each leaf node represents a single data point.

By recursively splitting the space along different dimensions, a KD tree can efficiently narrow down the search to a subset of points that are likely to be nearest to the query point. This can be particularly useful in applications such as image recognition, natural language processing, and recommendation systems, where the number of features or dimensions can be very high.

In this article, we will explore the KD trees to find the nearest neighbor. We will utilize Geo Assist, a spatial engine, that provides the ability to store spatial data and find the nearest neighbors.

Geo Assist

Geo Assist is a Java library that provides an out-of-the-box implementation of different data structures to manage and query spatial data. One of these data structures is the KD Tree. The spatial engine provides a thorough implementation of KD Trees in the 2-dimensional space. It provides features such as finding nearest neighbors or findings within a bounding box (range). Whether you are a data scientist, a machine learning engineer, or a hobbyist programmer, you will find plenty of practical tips and examples to apply KD trees to your own projects.

So, let’s get started and see how KD trees can help you find your nearest neighbor faster and more accurately!

Install

Geo Assist is available on the maven repository for easy plug-and-play support. You need to add the below dependency to your maven project.

We will create a Java Maven project to use Geo Assist spatial engine in our project.

<!-- https://mvnrepository.com/artifact/com.thegeekyasian/geo-assist -->
<dependency>
    <groupId>com.thegeekyasian</groupId>
    <artifactId>geo-assist</artifactId>
</dependency>

If you are using a Gradle project, here is a Gradle dependency for you

// https://mvnrepository.com/artifact/com.thegeekyasian/geo-assist
implementation("com.thegeekyasian:geo-assist:1.0.2")

Initialize KD Tree

Once the dependency is added, you can simply create an instance of KDTree class. Since Geo Assist provides you to add custom data to your KD Tree data store, you can provide two datatypes. One for the ID of your custom object, and the second for your object type.

Here is how you can create a KD Tree

KDTree<Long, Object> kdTree = new KDTree<>();

In the above object creation, the Long class represents the type of ID for your custom object, while the Object class represents the type of Object that can be stores in the KD Tree.

Once the KD tree is created, let’s initialize it by adding the objects into the tree.

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(1)
		.latitude(25.1967512)
		.longitude(55.2732038)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(2)
		.latitude(25.1962077)
		.longitude(55.2714443)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(3)
		.latitude(25.1954312)
		.longitude(55.2811432)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(4)
		.latitude(25.1903843)
		.longitude(55.2798557)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(5)
		.latitude(25.2002450)
		.longitude(55.2734184)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(6)
		.latitude(25.2028848)
		.longitude(55.2783966)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(7)
		.latitude(25.2012544)
		.longitude(55.2569389)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(8)
		.latitude(25.1644242)
		.longitude(55.2450943)
		.build());

kdTree.insert(new KDTreeObject.Builder<String, Object>()
		.id(9)
		.latitude(25.0763827)
		.longitude(55.1616669)
		.build());

With above calls to insert, we have now initialized the tree with certain geo-coordinates.

KD Tree: Find Nearest Neighbors

After initializing the KD Tree with the provided coordinates, let’s try to find the nearest neighbors.

We need to create a Point instance with coordinates that we need to find the nearest neighbors for. We will pass the Point parameter to findNearestNeighbor method of KDTree along with the distance in radius.

Point point = new Point.Builder()
				.latitude(25.2012544)
				.longitude(55.2569389)
				.build();
List<KDTreeObject<Long, Object>> nearestNeighbors = 
        kdTree.findNearestNeighbor(point, 2); // 2 kilometers based on haversine distance.

The KDTree uses haversine algorithm to calculate the distance. The distance provided should be in kilometer.

Calling the findNearestNeighbor with the provided coordinates will return the list of all the nearest objects.

KD Tree: Find in Bounding Box

In addition to finding the nearest neighbors, this implementation of KD Tree allows you to find objects in a bounding box as well. A bounding box is a rectangular area defined by its four coordinates of latitude and longitude i.e. lower left coordinates and upper right coordinates.

Here is how you can find the objects in a bounding box

BoundingBox boundingBox = new BoundingBox.Builder()
				.lowerPoint(new Point.Builder()
						.latitude(24.836135)
						.longitude(66.976089)
						.build())
				.upperPoint(new Point.Builder()
						.latitude(24.951953)
						.longitude(67.157364)
						.build())
				.build();
				
List<KDTreeObject<String, Object>> objects = kdTree.findInRange(boundingBox);

The findInRange method will return a list of objects that lie in a rectangular bounding box.

Conclusion

In conclusion, the KD Tree is a powerful data structure that allows for efficient spatial searching of large datasets. By using Geo Assist library, we can easily perform nearest neighbor and bounding box queries on spatial data. This can be particularly useful in a variety of applications, such as geospatial analysis, machine learning, and computer vision.

By leveraging the capabilities of the KD Tree, we can enhance the speed and accuracy of our spatial computations and unlock new possibilities for data-driven insights.

You can get more details on the Geo Assist on the GitHub. For any questions or feedback, you can join the Geo Assist discord server.