KD-Tree

Some data structure fun for algorithms!

                                                         

Overview

The goal of the project was to implement a 2-dimensional tree data structure (k-d tree implementation) and evaluate its performance of datasets of increasing size N. The nearest neighbor query search was tested, and its evaluated performance outperformed the brute force approach on random data sets of size N. Additionally, an interactive GUI was implemented to visualize the k-d trees spatial structure in a 2-d space.

Required Software

This is project uses no external libraries. It runs with all the included libraries in Java.

How to Run the Code

KD-Tree Unit Tests

To validate the correctness of the KD-tree implementation run the unit test file:

kdtree -> tests -> KDTreeTests.java                         

KD-Tree Performance Tests

The performance test results will print out the terminal window when run. To run the performance test on the KD-tree structure locally run the test file:

kdtree -> tests -> TimeEval.java                          

KD-Tree Interactive GUI

To run the KD-tree interactive GUI run the following file:

kdtreeGUI -> KDViewer -> KDViewer.java                         

Deliverables

GITHUB REPO

In case this code does not compile or run. Pull the latest code from the following github repo:

https://github.com/JosuContrer/KD-Tree                         

VIDEO LINK

The link to the video on the summary of our teams implementation and discoveries is provided in the link below:

https://youtu.be/DNuXnstsf1U                       

REPORT

The report is included in this zip file as a pdf.

Authors

• Will Burke
• Josue Contreras
• Ian Coolidge
• Mayank Govilla

Acknowledgments

• Algorithms in a Nutshell
• Introduction to KD Trees article
• Implementing a KD Tree article
• An Introductory Tutorial on KD Trees article
• Multidimensional Binary Search Trees Used for Associative Searching article