> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-4/advanced_data_structures/multidimensional-data.md).

# Multidimensional Data

We use various tree structures to represent data in 1, 2, 3, ..., k dimensions.

## High Level Overview

Each node divides the current region. Each children represents a subregion.

We care about the 5 essential operations that define the characteristics of that data structure.

* Insertion
  * Search for the right position to insert, determine which subregion this node would fall into
* Search
  * Very similar to insert, except when if not found, return return null
* Deletion
  * Remove the node is easy, just do a search operation
* * The key here is (recursively) finding the best replacement that keep the properties of the subtrees
* Range Query
  * Find all points within a range/region
  * Check if the region(node) intersections with the query region
  * Then check node.point and recursively search on the children nodes
* Nearest Neighbor Query
  * Keep two global values, bestDist and bestSol
  * need a function to compute dist(region(node), query point)
  * If dist(region(node), query point) < bestDist, update bestSol, visit all children
  * Else prune this subtree

TBC