Accelerating k-Nearest-Neighbour Classification of

Kepler Exoplanet Candidates with a k-d Tree

Data Structures and Algorithms, Summer 2026

Habib University
Contents
Right-click here and choose "Update Field" to build the table of contents.
Data Structures and Algorithms, Summer 2026 Habib University

Abstract
This report presents a k-d tree implemented from scratch in Python and applies it to k-nearest-neighbour (k-
NN) classification of NASA Kepler Objects of Interest into three dispositions: CONFIRMED, CANDIDATE, and
FALSE POSITIVE. The tree is built from primitive Python types only, with no classes and no library nearest-
neighbour code. Its correctness is established by proving that it returns exactly the same neighbour sets as an
exhaustive scan, and its performance is measured against two baselines: brute-force search and a uniform
spatial grid.

On the cleaned dataset of 9,201 candidates described by 10 numeric features, the tree answers a k=10 query
in 6.49 ms against brute force's 15.06 ms, a speedup of 2.32x, while producing byte-identical results. The
more interesting finding is that this modest speedup is itself the main scientific result. Controlled
experiments on synthetic data show the tree is 45x faster than brute force at 2 dimensions but slower than
brute force beyond roughly 9 dimensions, and that at 10 dimensions its advantage depends entirely on
whether the points are clustered or uniform. The real dataset benefits only because astronomical
measurements are strongly correlated, so its intrinsic dimension is well below its nominal 10. This is the curse
of dimensionality observed directly rather than quoted, and it is the central lesson of the project.
Part I: Theory
Sections 1 to 6 establish the problem, the data structure, its interface and its complexity, and the two
conventional alternatives it is measured against.

1. Introduction and problem statement

1.1 The astronomical problem
NASA's Kepler space telescope searched for planets outside the solar system using the transit method. When
a planet passes in front of its host star, it blocks a small fraction of the light, and the star appears to dim
briefly and periodically. Kepler monitored roughly 150,000 stars and recorded these dips in brightness. Each
periodic dimming signal that survives automated vetting becomes a Kepler Object of Interest, or KOI.

Not every KOI is a planet. A signal can be produced by an eclipsing binary star, by instrumental noise, or by
light from a nearby star contaminating the target aperture. Each KOI is therefore assigned a disposition by
the Kepler team:

 CONFIRMED, verified as a planet by follow-up observation,

 FALSE POSITIVE, shown to be something other than a transiting planet,
 CANDIDATE, consistent with a planet but not yet confirmed.
The classification task in this project is: given the measured physical properties of a KOI, predict its
disposition.

1.2 The computer science problem

The classifier used here is k-nearest neighbours, which answers a query by finding the k training points
closest to it and taking a majority vote of their labels. This makes the entire cost of classification the cost of a
nearest-neighbour search.

Done naively, answering one query means computing the distance to every training point, which is O(n)
distance computations for n training points. Classifying the whole 1,840-row test set therefore costs 1,840 x
7,361 = 13.5 million distance computations. The question this project addresses is whether a spatial data
structure can do better by organising the training points so that most of them are never examined at all.

The structure chosen is the k-d tree, introduced by Bentley (1975). The report builds it, proves it correct,
measures it, and, importantly, identifies the conditions under which it fails to help.

1.3 Constraints
The implementation operates under deliberate constraints set by the course:

 The data structures use only primitive Python types: dicts, lists, and tuples. No classes are defined
anywhere in the tree or grid code.
 No library nearest-neighbour or spatial-index code. No [Link], no
[Link].
 Standard library plus matplotlib only.
The no-classes constraint deserves comment, because it is not merely a restriction. A tree node here is a plain
dict:
{'point': [...], 'label': '...', 'axis': 3, 'left': {...}, 'right': {...}}

This makes explicit something that an object-oriented implementation hides: a tree is nothing more than
nested dictionaries with a discipline about which key means what. Every recursive call in the implementation
manipulates ordinary data rather than invoking a method, which makes the recursion structure easier to
trace by hand and easier to defend.

2. The dataset
2.1 Source and size
The data is the NASA Kepler KOI cumulative table, obtained as a CSV of approximately 9,500 rows. Each row
is one Kepler Object of Interest with roughly 50 columns of measured and derived quantities plus the
koi_disposition label.

2.2 Feature selection

Ten numeric columns were selected, split evenly between properties of the candidate planet and properties
of its host star:

Feature Meaning Unit

koi_period Orbital period, the candidate's year days
koi_duration How long each transit lasts hours
koi_depth Fractional drop in stellar brightness parts per million
during transit
koi_prad Candidate radius Earth radii
koi_teq Equilibrium temperature Kelvin
koi_insol Stellar radiation received relative to Earth
koi_model_snr Signal-to-noise ratio of the transit fit dimensionless
koi_steff Host star effective temperature Kelvin
koi_slogg Host star surface gravity log10(cm/s^2)
koi_srad Host star radius Solar radii

2.3 Excluded columns and label leakage

Two groups of columns were deliberately excluded, and this is a methodological point rather than a
convenience:

 koi_score, a disposition confidence value produced by the Kepler vetting pipeline.

 koi_fpflag_nt, koi_fpflag_ss, koi_fpflag_co, koi_fpflag_ec, four binary flags recording why
a candidate was judged a false positive.
These columns are derived from the disposition decision itself. Including them would let the classifier read
the answer rather than infer it from physical measurements, a failure mode known as label leakage. Accuracy
would rise sharply and would mean nothing: the model would be reporting the Kepler team's conclusion back
to us. The 10 features above are all physical measurements or quantities derived from the light curve, so a
prediction from them is a genuine inference.

2.4 Cleaning
cleaning_data.py reads the CSV with [Link] and discards any row that has a blank in any of
the 10 selected features or a blank disposition. Rows are dropped rather than imputed, because inventing a
value for a missing physical measurement would place a synthetic point into the very space whose geometry
the tree is exploiting.

This leaves 9,201 clean rows from approximately 9,500, a loss of about 3 percent. The class balance of the
cleaned data is:

Disposition Count Share

FALSE POSITIVE 4,724 51.3%
CONFIRMED 2,292 24.9%
CANDIDATE 2,185 23.7%

This imbalance matters for interpreting accuracy and is returned to in section 9.1.

2.5 Scaling, and why it is not optional

Every feature is rescaled to [0, 1] by min-max normalisation:
scaled = (value - min) / (max - min)

This is the single most consequential preprocessing decision in the project, because of how Euclidean
distance behaves. The squared distance between two candidates is
d(a, b)^2 = sum over i of (a_i - b_i)^2

Each feature contributes a squared difference, so a feature whose raw values span a wide numeric range
contributes far larger terms than one that spans a narrow range. The actual ranges in this dataset differ by six
orders of magnitude:

Feature Min Max Range

koi_insol 0 1.095e7 1.095e7
koi_depth 0 1.541e6 1.541e6
koi_period 0.2418 1.3e5 1.3e5
koi_steff 2,661 1.59e4 1.32e4
koi_slogg 0.047 5.364 5.317
koi_srad 0.109 229.9 229.8

Without scaling, a difference of 10,000 in koi_insol contributes 10^8 to the squared distance, while the
entire possible range of koi_slogg contributes at most 5.317^2 = 28.3. Insolation flux would decide
essentially every neighbour, and the other nine features would function as rounding error. The classifier
would be a one-dimensional classifier wearing a ten-dimensional costume.
Min-max scaling gives every feature an identical [0, 1] span, so each contributes at most 1 to the squared
distance and all ten participate. This encodes a specific assumption, namely that all ten features are equally
relevant, which is an assumption rather than a fact, but it is a far better default than letting the choice of
physical units decide feature importance.

Scaling has a second benefit specific to this project. Both spatial structures assume the data occupies a
bounded region: the grid's cell-size search starts from a cell width of 1.0 and shrinks, which is meaningful
precisely because the data lives in the unit hypercube.

Implementation note. scale_data computes the per-feature minimum and maximum from the data it is
given. For the CLI to classify a hand-entered candidate, those same values must be reused, since scaling a
new point by its own min and max is meaningless. cleaning_data.py therefore exposes
feature_ranges and scale_point so that a query is transformed with exactly the constants used for the
training set.

Fitting the scaler on the training split only. The order of operations matters. Splitting first and computing the
minimum and maximum from the training rows alone is what the pipeline does, and the same constants are
then applied to the test rows. Computing them over the full dataset before splitting would be a mild form of
data leakage: the minimum and maximum are set by extreme values, and if an extreme value happens to fall
in the test split then a fact about test data has influenced how the training points are laid out in space, and
therefore which neighbours are nearest.

The effect is small here but it is real and it is measurable. Fitting the scaler on all rows rather than on training
rows alone raises the reported three-class accuracy from 0.6522 to 0.6533, and the two-class accuracy from
0.8432 to 0.8589. Both move in the optimistic direction, which is the signature of leakage rather than of
noise. Applying the training-only convention costs 0.11 percentage points on the headline number and
removes the objection.

A consequence worth noting is that test points may scale outside [0, 1] when they fall beyond the training
range. Nothing in the tree or the search requires the unit interval, so this is harmless. Only the grid's cell-size
search assumes it, and only as a starting width for the shrink loop rather than as a correctness condition.

3. k-Nearest-Neighbour classification
3.1 The rule
k-NN is a lazy or instance-based learner. There is no training phase and no fitted model: the training set itself
is the model. To classify a query point q:

1. Compute the distance from q to every training point.

2. Take the k training points with the smallest distances.
3. Return the label held by the majority of those k.
All of the method's inductive content sits in the distance function, which is why section 2.5 matters as much
as it does. k-NN assumes that points close together in feature space tend to share a label. For this dataset
that assumption is physically reasonable: two KOIs with similar orbital periods, transit depths, and host star
properties plausibly have similar underlying causes.
3.2 Squared distance
The implementation never takes a square root:
def euclidean(a, b):
total = 0
for i in range(len(a)):
total += (a[i] - b[i]) ** 2
return total

The function returns squared Euclidean distance. Because the square root is monotonically increasing for
non-negative arguments, comparing squared distances orders points identically to comparing true distances,
so every nearest-neighbour decision is unaffected. Omitting n square-root operations per query is free
performance. The consequence to remember is that every distance reported internally is squared, and the
same convention must be applied on both sides of any comparison, including in the pruning tests of section
5.6 and the correctness check of section 7. The CLI takes the square root only for display.

3.3 Choice of k
k = 10 is used throughout. The choice trades two failure modes: small k makes the prediction sensitive to a
single mislabelled or outlying neighbour, while large k blurs genuine local structure by averaging over a
region larger than the class boundaries. With three classes, k = 10 also cannot produce a clean three-way tie.

Ties between two classes are possible, for example 5-5 at k = 10. Both the tree and the brute-force voting
loops resolve these by keeping the first label to reach the maximum count, which depends on dict insertion
order. This is arbitrary but consistent, and section 7 explains why the correctness test is designed not to
depend on it.

3.4 Train and test split

train_test_split shuffles the scaled data and holds back 20 percent. This yields 7,361 training points
and 1,840 test points. The split is seeded in [Link] and [Link] so that every number in this report is
reproducible.

4. Baseline 1: brute-force search

4.1 Algorithm
The exhaustive baseline is direct:
function knn_bruteforce(train, q, k):
results = empty list
for each (point, label) in train:
append (euclidean(point, q), label) to results
sort results ascending by distance
return majority label among the first k entries

4.2 Complexity
Let n be the number of training points and d the number of features.

 Computing one distance is O(d).

 Computing all distances is O(nd).
 Sorting the n distances is O(n log n).
Total per query: O(nd + n log n). With d = 10 and n = 7,361, log2(n) is about 12.9, so nd dominates and the
practical behaviour is linear in n. The measured log-log slope of brute force against n is 1.03 to 1.06 across
both synthetic experiments, confirming linearity.

Sorting the full array is wasteful, since only the k smallest entries are needed and a partial selection would be
O(n) rather than O(n log n). This inefficiency is retained deliberately: the baseline is meant to be the obvious
implementation, and because sorting is not the dominant term it does not distort the comparison.

4.3 Why keep it

Brute force serves two purposes beyond being a speed baseline. It is trivially correct, which makes it the
oracle against which both spatial structures are verified in section 7. And it establishes that the accuracy
figures in this report are properties of k-NN itself, not artefacts of any index.

5. The k-d tree

5.1 Idea and origin
The k-d tree, short for k-dimensional tree, was introduced by Bentley (1975) as a generalisation of the binary
search tree to multidimensional keys. A binary search tree splits a one-dimensional set at a value: everything
smaller goes left, everything larger goes right. Searching discards half the remaining data at each comparison.

A k-d tree does the same in d dimensions, but with one addition: because there is no single ordering of points
in d-space, each node splits on one chosen coordinate, and the choice of coordinate cycles with depth. A
node at depth dep splits on axis
axis = dep mod d

so in this project the root splits on koi_period, depth 1 on koi_duration, and so on, wrapping back to
koi_period at depth 10. Each node therefore represents an axis-aligned hyperplane cutting its region in
two, and the tree as a whole is a recursive partition of the feature space into nested axis-aligned boxes.

The critical structural consequence is this: a node's splitting hyperplane defines a geometric boundary, so the
distance from a query point to that hyperplane is a lower bound on the distance to every point on its far side.
That single fact is what makes pruning possible, and it is the whole reason the structure is worth building.

5.2 Node representation without classes

A node is a dict with five keys:

Key Contents
point the 10 scaled feature values of the point stored at this
node
label its disposition string
axis which coordinate this node splits on
left subtree of points below the split value on that axis, or
 None
right subtree of points above it, or None

An empty subtree is None, which gives recursion its base case.

Storing axis in the node is technically redundant, since it is recomputable from depth. It is stored because it
makes each node self-describing: the search function can decide which way to descend by reading the node
alone, without also threading depth through every call. This trades a few bytes per node for a simpler and
more defensible search function.

5.3 The interface

The tree is exposed to the rest of the program through five functions in [Link]. All of them take the tree
as their first argument and none of them know anything about exoplanets, which keeps the data structure
reusable for any problem that stores labelled points in a metric space.

Operation Signature Returns Cost

Build build_kdtree(point root node, or None O(n log^2 n)
s)
Insert insert(tree, root node O(log n) balanced, O(n)
point, label) worst case
Membership exist(tree, point) True or False O(log n) balanced, O(n)
worst case
k nearest knn_search(tree, list of (point, label, see section 5.8
query, k) sq_distance)
Distance euclidean(a, b) squared distance O(d)

knn_search is the operation the whole project is built around, and sections 5.6 to 5.8 are devoted to it. The
other three are what make the structure a usable ADT rather than a single-purpose routine, and they are
worth stating precisely because two of them behave differently from their binary-search-tree equivalents.

Insert. Insertion descends exactly as a search does. At each node it compares the new point against that
node's stored point on that node's split axis only, goes left when the value is less than or equal and right
otherwise, and hangs the new node off the first None it reaches. The new node's axis is its depth mod d.

The critical difference from build_kdtree is that insertion cannot choose the split value. Construction sorts
each subset and splits at the median, which is why it produces a tree of depth exactly ceil(log2 n). Insertion
has no such freedom: it must accept wherever the descent lands it, because moving the point elsewhere
would break the invariant for every node already in the tree. A k-d tree has no rotation operation that
preserves the axis-cycling invariant, so unlike an AVL or red-black tree it cannot rebalance itself after an
insert.

The consequence is that a tree built by n successive inserts is only balanced if the insertion order is
favourable. Inserting points already sorted on the first coordinate produces a path of length n rather than a
tree of depth log2 n, and every operation degrades from O(log n) to O(n). This is the standard reason the
literature builds k-d trees in bulk from a static point set, as is done here, and treats insertion as a convenience
for small updates rather than the primary way to populate the structure. Bentley (1975) discusses this
asymmetry directly. Where a workload is insert-heavy the usual remedy is periodic bulk rebuild, which
amortises to O(log n) per insert.

Membership. exist reports whether an exact point is stored in the tree. It looks like an ordinary binary-
search-tree lookup but has one subtlety that a BST does not. Construction splits at the median, so a point
whose value on the split axis is exactly equal to the median's may be placed in either subtree depending on
where the sort put it. A strict left-if-less-or-equal descent would therefore walk past points that really are
present. exist handles this with three cases: strictly less descends left, strictly greater descends right, and
exactly equal must search both subtrees. The equal case is rare on continuous data, so the expected cost
stays O(log n), but the code is correct on the tied values that scaled discrete columns such as
koi_model_snr do produce.

Note that this is exact-match lookup, not proximity search. exist([0.5, 0.5, ...]) answers a different
question from knn_search, and only the latter is useful for classification. exist is included because a
membership test is part of what makes this an ADT, and because it is the natural way to confirm that insert
did what it claimed.

Deletion is deliberately not implemented. Removing an internal node from a k-d tree is substantially harder
than removing one from a BST: the replacement cannot simply be the in-order successor, because the
successor must be the minimum along the deleted node's split axis, found by a recursive search of the right
subtree that is itself O(n^(1-1/d)). Bentley's original paper gives the procedure. It is omitted here because the
application is a classifier over a fixed training set, which never removes a point, and implementing an
operation the application cannot exercise would add untested code to the submission.

5.4 Construction
function build_kdtree(points, depth = 0):
if points is empty:
return None
axis = depth mod d
sort points by coordinate `axis`
mid = length(points) // 2
return {
'point': points[mid].features,
'label': points[mid].label,
'axis': axis,
'left': build_kdtree(points[0 : mid], depth + 1),
'right': build_kdtree(points[mid+1 : ], depth + 1)
}

Splitting at the median rather than at an arbitrary or first element is what keeps the tree balanced. Because
the median puts an equal count on each side by construction, the depth is Theta(log n) regardless of how the
points are distributed. Inserting points in arrival order, as one might into a plain BST, risks a degenerate near-
linear chain on sorted or clustered input, which would destroy the search bound. The dataset is genuinely
clustered, so this is a real rather than theoretical risk.

The number of features is read from the data itself:

axis = depth % len(lst[0][0])
An earlier version hardcoded depth % 10, which silently produced a wrong tree for any input that was not
10-dimensional. Deriving it from the data is what allows the same code to be exercised at 2 through 14
dimensions in section 9.4.

5.5 Construction complexity

The recurrence is
T(n) = 2 T(n/2) + O(n log n)

because each call sorts its own sublist before recursing on two halves. The sort is the O(n log n) term. By the
master theorem this gives

T(n) = O(n log^2 n)

and not the O(n log n) often quoted for k-d tree construction. The textbook bound assumes median selection
in linear time, either by the median-of-medians algorithm or by pre-sorting once per axis and maintaining
those orders through the recursion. Sorting afresh at every node costs an extra logarithmic factor.

This was accepted as a deliberate trade. Construction happens once, takes 0.034 seconds on the real dataset,
and is dwarfed by the cost of the queries it serves. Sorting is also far easier to state, trace, and defend than
median-of-medians. The measured build times are 0.014 s at n = 5,000 and 0.300 s at n = 50,000; at these
sizes memory allocation and Python interpreter overhead contribute enough that the ratio should not be
read as a precise confirmation of the exponent, only as consistent with a mildly super-linear cost.

One further implementation detail: the build uses sorted(lst, key=...) rather than
[Link](key=...). In-place sorting would reorder the caller's own list as a side effect, which is a
surprising thing for a constructor to do to its argument.

5.6 Nearest-neighbour search

Search is where the structure earns its cost, and it is the part most worth understanding in detail. The naive
hope, that one can simply descend to a leaf and report the point found there, is wrong. Descending to a leaf
finds a point in the same box as the query, but the true nearest neighbour may sit just across a splitting plane
in a neighbouring box. Correct search must therefore descend and then unwind, reconsidering the branches
it skipped.

The algorithm has three phases at every node:

1. Descend on the query's own side. Compare the query's coordinate on this node's axis against the node's
own. Recurse first into the subtree containing the query. This reaches a good candidate quickly, which
matters because a tight current best is what makes the later pruning aggressive.

2. Consider the node itself while unwinding. After the near subtree returns, compute the distance from the
query to this node's own point and update the best found so far.

3. Decide whether the far side can be skipped. This is the pruning test. The distance from the query to this
node's splitting plane is
plane_distance = query[axis] - [Link][axis]
along a single coordinate. Every point on the far side of that plane must differ from the query by at least this
much on that one axis, and since the total squared distance is a sum of non-negative per-axis terms, every
far-side point is at squared distance at least plane_distance^2. Therefore:

 If plane_distance^2 is greater than the current best squared distance, no far-side point can beat the
current best. The entire subtree is discarded without examining any of it.
 Otherwise the far subtree might contain something closer and must be searched.
This is the pruning rule, and the correctness of the whole structure rests on it being a genuine lower bound
rather than a heuristic. Note that the comparison is between two squared quantities, consistent with section
3.2.

5.7 Extension from 1 to k neighbours

Generalising from the single nearest neighbour to the k nearest requires two changes.

First, the single best is replaced by a list of up to k best, held sorted by distance. knn_search creates one
fresh list per query and passes it down into the recursive worker _search, so that state is per-query rather
than global:
def knn_search(root, query, k):
best = []
_search(root, query, k, best)
return best

The list is maintained by append, sort, and trim: the current node is appended, the list is re-sorted by
distance, and if it now holds more than k entries the worst is discarded. With k = 10 this is cheap, though a
bounded max-heap would be the right structure for large k.

Second, and more subtly, the pruning threshold changes meaning. With one neighbour the threshold is the
distance to the single best point. With k neighbours it becomes the distance to the current k-th best, that is,
the worst member of the list, best[-1]. A far-side point only matters if it can displace the current worst
member.

This creates an additional case. While fewer than k neighbours have been collected, there is no threshold to
prune against, because any point at all is an improvement over having no k-th neighbour. The far branch
must then always be searched:
if len(best) < k or best[-1][2] >= (query[axis] - node['point'][axis]) ** 2:
_search(far, query, k, best)

Omitting the len(best) < k clause is a natural bug to write, and it produces a search that returns fewer
than k neighbours or misses genuine ones near the root, where the list is still filling. The correctness test in
section 7 checks the length of the returned list explicitly for this reason.

5.8 Search complexity

For a balanced tree with n points, the depth is Theta(log n), so an ideal search that pruned every far branch
would cost O(log n). Friedman, Bentley, and Finkel (1977) show that expected O(log n) query time is achieved
for uniformly distributed points, but only under the condition
 n >> 2^d

That condition is the key to interpreting every result in this report, and it is worth stating plainly why it holds.
Pruning succeeds when the current best distance is small compared with the distance to a splitting plane. In d
dimensions, the tree only gets to cut each axis roughly log2(n) / d times, so for large d each cell remains
wide along every individual axis. A query's nearest neighbour then tends to be far enough away, in absolute
terms, that the plane-distance lower bound almost never exceeds it, and almost no branch can be discarded.

Quantitatively, for the tree to cut every axis even once, the depth must reach d, which needs n >= 2^d. For
the pruning to be effective rather than merely possible, n must exceed 2^d substantially.

Substituting this project's numbers is illuminating:

Setting n d 2^d log2(n)

Real KOI data 7,361 10 1,024 12.9
Dimension sweep 5,000 10 1,024 12.3
Dimension sweep 5,000 14 16,384 12.3

At d = 10 with n = 5,000, n exceeds 2^d by a factor of only about 5, which is not the comfortable margin the
analysis requires. At d = 14, n is smaller than 2^d and the condition fails outright. The prediction is therefore
that the tree should perform well at low d, lose its advantage somewhere near d = log2(n), and be actively
counterproductive beyond that. Section 9.4 measures exactly this, and the crossover lands near d = 9 with
log2(5000) = 12.3.

The worst case is O(n): if no branch is ever pruned, every node is visited, and the tree has done strictly more
work than brute force because it pays recursion, list maintenance, and pruning-test overhead on top of the
same distance computations. This is not a hypothetical, and section 9.2 shows it happening.

6. Baseline 2: the uniform spatial grid

6.1 Why a second baseline
Comparing a k-d tree only against brute force answers a weak question, since almost any spatial structure
beats an exhaustive scan under favourable conditions. On the course instructor's direction, the tree is
therefore also compared against a genuine spatial method: a uniform spatial grid, also called spatial hashing.
This asks the sharper question of whether the tree's recursive partition is worth its complexity relative to the
simplest possible spatial decomposition.

6.2 Structure
The grid divides space into equal axis-aligned cells of fixed width cell_size and stores the points of each
cell together. The implementation is one dict:
def cell_of(point, cell_size):
return tuple(int(coord // cell_size) for coord in point)
The cell index is a tuple of integers, one per dimension, used directly as the dict key. Floor division is used
rather than truncation so that negative coordinates map correctly, which matters because a hand-entered
query in the CLI can fall outside the training range and scale to a negative value.

The contrast with the tree is instructive. The grid's decomposition is fixed and data-independent: cell
boundaries are decided by the chosen width alone. The tree's decomposition is data-adaptive: every split is
placed at a median, so the partition follows wherever the points actually are. This difference drives the
results in section 9.3.

6.3 Query
The query proceeds in two stages:
function knn_grid(grid, cell_size, q, k):
best = empty list
home = cell_of(q, cell_size)
if home exists in grid:
scan every point in home, keeping the k best
for each (cell, points) in grid:
if cell is home: skip
if best already holds k and min_dist(cell, q) > distance of k-th best:
skip this cell entirely
scan every point in cell, keeping the k best
return best

The home cell is scanned first specifically to seed the k-best list with plausible candidates, so that the
threshold used to reject other cells is tight from the start.

The rejection test needs the minimum possible distance from the query to any point that could lie inside a
given cell. Since a cell is an axis-aligned box, this decomposes per axis: for each coordinate, the gap is zero if
the query lies within the cell's span on that axis, and otherwise the distance to the nearer face. Summing the
squared gaps gives the squared distance from the query to the closest corner or face of the box:
def cell_min_sq_dist(cell, query, cell_size):
total = 0
for i in range(len(query)):
low = cell[i] * cell_size
high = low + cell_size
if query[i] < low: gap = low - query[i]
elif query[i] > high: gap = query[i] - high
else: gap = 0
total += gap * gap
return total

This is a true lower bound, so the grid search is exact, not approximate. It is the same style of geometric
argument as the tree's plane-distance bound, applied to a box instead of a hyperplane.

6.4 Why not ring expansion

The textbook uniform-grid query does something different: it examines the query's own cell, then the shell of
cells one step away, then two steps away, stopping when the guaranteed-covered radius exceeds the current
k-th distance. That design was implemented in neither form here, and the reason is a direct consequence of
dimensionality.
The shell of cells at Chebyshev distance exactly 1 from a given cell in d dimensions contains 3^d - 1 cells. At
d = 10 that is
3^10 - 1 = 59,048 cells

Enumerating a single ring would require 59,048 dict lookups, and the second ring would require 5^10 -
3^10, over 9.7 million. Against a dataset of 9,201 points in total, examining one ring costs several times more
than simply computing the distance to every point. Ring expansion is a low-dimensional technique, and
applying it at d = 10 would have produced a baseline so bad that beating it would prove nothing.

The min-distance cell filter of section 6.3 avoids this entirely. Its cost is proportional to the number of
occupied cells, which is bounded by n and is typically far smaller, rather than to the number of possible cells,
which grows as 3^d. It is still an ordinary uniform grid, and it remains exact. This substitution is the main
design decision in the baseline and is flagged here because it is the kind of choice that a comparison stands or
falls on.

6.5 Cell size, and the fairness of the comparison

A grid has a free parameter that a k-d tree does not: the cell width. The two failure modes are opposite and
both severe.

 Cells too large. Few cells, each holding many points. Almost nothing is rejected and the query
degenerates into brute force with extra bookkeeping.
 Cells too small. Very many cells, each holding almost nothing. The per-cell rejection test now runs a
number of times proportional to the point count, so the filter loop itself becomes the bottleneck.
The optimum lies between. tune_cell_size finds it by starting from a width of 1.0 and shrinking
geometrically until the number of occupied cells reaches n/k, which targets an average occupancy of about k
points per cell:
def tune_cell_size(data, k, max_steps=30, shrink=1.3):
target = max(len(data) / k, 1)
cell_size = 1.0
best_size, best_gap = cell_size, None
for _ in range(max_steps):
occupied = len(build_grid(data, cell_size))
gap = abs([Link](occupied) - [Link](target))
if best_gap is None or gap < best_gap:
best_gap, best_size = gap, cell_size
if occupied >= target:
break
cell_size = cell_size / shrink
return best_size

Counting occupied rather than possible cells is essential, because the data is clustered and the two differ
enormously. At a width of 0.5 the real dataset occupies only 19 of the 2^10 = 1,024 available cells.

The gap is measured in log space. An earlier version compared occupancy to the target by absolute difference
and behaved badly, because occupancy grows geometrically as cells shrink: successive candidate widths
might yield 1 cell and then 2,000 cells against a target of 500, and |1 - 500| < |2000 - 500| would
select the single-cell grid. That is the worst possible choice, a grid that is exactly brute force. The bug was
caught because the dimension sweep reported cells = 1 at d = 12 and d = 14, where the grid's timing was
suspiciously identical to brute force. Comparing log-ratios instead makes the selection scale-free and fixes it.

Section 9.5 measures the sensitivity directly. The point of including it is methodological: an untuned grid is a
strawman, and a comparison against a strawman would not survive scrutiny.

6.6 Complexity
Let C be the number of occupied cells and m the number of points in cells that survive the filter.

 Build: O(nd) to hash every point into its cell, plus the tuning search, which rebuilds the grid up to 30
times and therefore costs up to O(30 nd). This shows up as the grid's build time being about 6x the tree's
despite being algorithmically cheaper.
 Query: O(Cd) for the filter tests plus O(md) for the points actually examined.
Because tuning targets C ~ n/k, the filter term is O(nd/k): still linear in n, but with a constant factor roughly k
times smaller than brute force, and each iteration does a cheap box test rather than a full distance
computation. The grid therefore does not change the asymptotic class of the search, it improves the
constant. This prediction is tested in section 9.2, and the caveat it implies is discussed in section 10.3.
Part II: Application and Experiments
Sections 7 to 11 establish that the implementation is correct, describe the experiments, and report and
discuss the measured results.

7. Correctness verification
7.1 What to compare
Both spatial structures are supposed to be exact: they must return the same k nearest neighbours as an
exhaustive scan, merely faster. [Link] tests this against brute force as the oracle. The choice of what to
compare is the substance of the test, and three candidates were considered.

Comparing predicted labels is too weak. Two methods can vote the same class while having selected
different neighbours. A search bug that swaps one neighbour for another of the same class leaves the
prediction unchanged, so label agreement would pass while the search was broken. Since FALSE POSITIVE
alone accounts for 51 percent of the data, such coincidental agreement is likely rather than rare.

Comparing the returned points is too strict. When two training points sit at exactly equal distance from the
query, which method reports which is arbitrary and depends on traversal order. A point-by-point comparison
would flag these ties as mismatches even though nothing is wrong, producing false alarms that obscure real
failures.

Comparing the sorted list of k distances is correct. It is immune to ties, because tied points contribute
identical distances in either order, and it tests precisely the property that must hold: an exact method must
find neighbours at the same distances. This is what [Link] compares, using squared distances
throughout so both sides use the same convention, with a 1e-9 tolerance for floating-point error.

The test additionally asserts that exactly k neighbours were returned. Without this, a structure that returned
only 7 neighbours would silently pass, because zip stops at the shorter sequence.
def disagrees(candidate, reference, k):
if len(candidate) != k:
return True
return any(abs(a - b) > 1e-9 for a, b in zip(candidate, reference))

7.2 Results
Over 250 test queries at k = 10, against brute force as oracle:
train 7361 points, 10 features
grid cell size 0.0725, 698 occupied cells
checked 250 queries at k=10
kd-tree mismatches vs brute force: 0
grid mismatches vs brute force: 0

A second, independent check comes from the CLI. Scoring the entire 1,840-row test set with all three
methods gives:
 k-d tree accuracy : 0.6522
uniform grid accuracy: 0.6522
brute force accuracy : 0.6522
all three agreed on : 1840/1840 rows

Identical accuracy to four decimal places and unanimous agreement on every single test row. Together these
establish that the speedups reported next are genuine algorithmic savings and not the result of returning
approximate answers.

8. Experimental method
8.1 What is measured
Two quantities are timed separately, because they scale differently and are paid at different frequencies:

 Build time, paid once, measured in seconds.

 Query time, paid per classification, reported as mean milliseconds per query.
Query timing measures neighbour retrieval only, excluding the majority vote, so that all three methods are
timed on identical work. Brute force in the timing loop computes all distances, sorts, and takes the first k,
matching what the tree and grid return.

8.2 Controls
 All randomness is seeded (SEED = 20260730) so every figure reproduces exactly.
 Queries are drawn from the same distribution as the training points. For the clustered generator, training
and query points are produced in a single call and then split, so both share the same cluster centres.
Generating them separately would have given the queries their own unrelated centres and measured the
wrong thing.
 The grid's cell size is retuned for every configuration, so it is never compared at a width tuned for a
different n or d.
 Each reported figure is the mean over 50 queries in the synthetic experiments and 100 to 300 on the real
data.

8.3 Limitations
Wall-clock timing in CPython measures the implementation as much as the algorithm. Constant factors from
interpreter overhead, attribute lookup, and memory allocation are large and are not identical across the
three methods: brute force spends almost all its time in a tight arithmetic loop, whereas the tree pays Python
function-call overhead at every node. Repeated runs vary by a few percent. The comparisons here are
therefore sound for identifying trends and crossover points, which is what the conclusions rest on, and should
not be read as precise measurements of asymptotic constants. A node-visit count would be machine-
independent and is noted in section 10.5 as the natural extension.
9. Results
9.1 Real dataset
On the cleaned KOI data, 7,361 training points, d = 10, k = 10, averaged over 300 queries:

Method ms per query Range over 4 runs Speedup vs brute force

Brute force 15.06 14.62 to 15.71 1.00x
Uniform grid 5.22 5.10 to 5.43 2.89x
k-d tree 6.49 6.37 to 6.86 2.32x

Figures are the median of four runs of 300 queries each, with the observed range given alongside, because
the run-to-run spread of roughly 7 percent noted in section 8.3 is large enough that a single run should not
be quoted as if exact.

Build cost: tree 0.032 s, grid 0.217 s including the cell-size search. The tuned grid used a width of 0.0725,
giving 726 occupied cells.

Both spatial methods beat brute force by roughly a factor of 3, and the grid is marginally ahead of the tree.
This is reported as measured rather than argued away. Section 10.3 discusses what it does and does not
mean.

Accuracy. All three methods score 0.6522 on the 1,840-row test set at k = 10. Two baselines are needed to
read this number honestly:

Comparison Accuracy
Uniform random guess among 3 classes 0.3333
Always predict the majority class (FALSE POSITIVE) 0.5234
k-NN at k = 10 0.6522

The random baseline is the weaker comparison and flatters the result. Against the majority-class baseline,
which is the honest one for imbalanced data, k-NN adds 12.9 percentage points. That is a real but modest
gain, and section 10.4 considers why. The majority baseline is computed on the test split itself (0.5234) rather
than on the full dataset (0.5134), since that is what a trivial classifier would actually score on the rows being
used for evaluation.

It bears repeating that the data structure has no effect whatsoever on accuracy. The tree is an exact
accelerator: it changes how fast the neighbours are found, not which neighbours they are. Any report
claiming a k-d tree improved classification accuracy would be describing a bug.
9.2 Scaling with n, uniform data

Figure 1: k-NN query cost vs dataset size, uniform data

Uniformly random points in the unit hypercube, d = 10, k = 10:

n Brute force Uniform grid k-d tree

100 0.181 0.329 0.285
500 0.842 1.196 1.442
1,000 1.725 2.010 2.827
5,000 9.422 6.442 14.346
10,000 20.716 9.732 27.605
50,000 111.145 46.996 73.608

Fitted log-log slopes: brute force 1.041, grid 0.777, tree 0.916.

This is the report's most uncomfortable result and its most informative one. The k-d tree is slower than brute
force at every size up to and including n = 10,000. At n = 1,000 it is 1.6x slower. Only at n = 50,000 does it
finally win, by 1.5x.

The explanation is section 5.8's condition. At d = 10, pruning almost never fires: the plane-distance lower
bound rarely exceeds the current k-th best distance, so the far branch is nearly always searched. The tree
ends up visiting nearly every node while additionally paying recursion overhead, list sorting, and a failed
pruning test at each one. Its slope of 0.916 is only slightly below brute force's 1.041, confirming that it is
behaving close to linearly rather than logarithmically.
9.3 Scaling with n, clustered data

Figure 2: k-NN query cost vs dataset size, clustered data

Ten Gaussian clusters (sigma = 0.05) in the unit hypercube, d = 10, k = 10:

n Brute force Uniform grid k-d tree

100 0.183 0.182 0.181
500 0.933 0.295 0.384
1,000 1.833 0.518 0.479
5,000 9.946 2.238 1.968
10,000 22.065 4.628 3.892
50,000 111.859 20.804 13.912

Fitted log-log slopes: brute force 1.038, grid 0.798, tree 0.721.

Changing only the point distribution, with n, d, and k identical to Figure 1, transforms the result. The tree is
now 8.0x faster than brute force at n = 50,000, against 1.5x on uniform data, and its slope drops to 0.721,
clearly sublinear.

The mechanism is intrinsic dimension. Ten Gaussian clusters in a 10-dimensional cube do not fill that cube:
the points lie in ten small neighbourhoods, so locally the data occupies far fewer effective dimensions than
10. Nearest neighbours are genuinely close, the current best distance is small, and the plane-distance bound
exceeds it often enough to prune whole subtrees. The median-split construction also places its cuts where
the points actually are, so cells adapt to the clusters.
The tree also overtakes the grid here, having trailed it on uniform data. This is the data-adaptive versus fixed
decomposition distinction of section 6.2 becoming visible: the grid imposes one width everywhere, so its cells
are simultaneously too coarse inside a dense cluster and mostly empty between clusters, while the tree's
median splits subdivide exactly where density demands it.

9.4 Scaling with dimensionality

Figure 3: k-NN query cost vs dimensionality

n = 5,000 uniform points, k = 10, varying d:

d Brute force Uniform grid k-d tree Tree speedup

2 3.984 0.407 0.089 44.8x
4 5.730 0.855 0.462 12.4x
6 6.942 1.936 1.573 4.4x
8 8.854 3.337 7.602 1.16x
10 10.473 7.099 14.745 0.71x
12 11.179 10.623 18.097 0.62x
14 12.521 15.979 19.652 0.64x

This figure is the clearest single result in the project. At d = 2 the tree is 44.8x faster than brute force, close to
textbook behaviour. The advantage then collapses monotonically: 12.4x at d = 4, 4.4x at d = 6, essentially
break-even at d = 8, and by d = 10 the tree is slower than the exhaustive scan it was built to replace. The
crossover sits near d = 9.

Section 5.8 predicted a crossover near d = log2(n) = log2(5000) = 12.3, and the condition n >> 2^d requires d
comfortably below that. Observing the crossover at d = 9 rather than exactly 12.3 is the expected direction of
error: the analysis requires n to greatly exceed 2^d, not merely to exceed it, and the tree's constant factors
mean it must prune substantially just to break even.

Brute force, by contrast, grows only linearly in d, from 3.984 ms at d = 2 to 12.521 ms at d = 14, exactly as
O(nd) predicts. It has no geometric assumption to lose. The grid degrades faster than brute force and crosses
it between d = 12 and d = 14, for the related reason that its cells stop isolating neighbourhoods once every
cell is wide along every axis.

9.5 Grid cell size sensitivity

Figure 4: Grid cell size sensitivity on the real KOI data

Measured on the real KOI data, 100 queries at k = 10, sweeping the cell width while holding everything else
fixed. The horizontal reference lines are brute force and the k-d tree, neither of which has a parameter to
tune. All values in this section come from the same run, so they are directly comparable to each other;
section 9.1 was a separate 300-query run, which is why its absolute timings differ by a few percent.

Reference for this run: brute force 16.261 ms/query, k-d tree 5.423 ms/query.

Cell width Occupied cells Points in busiest cell ms per query

0.0100 5,736 12 11.604
0.0200 3,244 47 7.048
0.0350 1,841 238 5.127
0.0500 1,211 629 4.232
0.0725 702 1,403 4.334
0.1000 399 2,470 5.395
0.1500 193 4,875 9.979
0.2000 105 3,426 7.844
 0.2500 76 4,013 9.209
0.3500 38 6,519 13.779
0.5000 19 7,146 15.759

This is the justification for section 6.5. The grid's performance varies by a factor of 3.7x across the swept
range, from 4.232 ms at its best to 15.759 ms at its worst. At the largest widths it is barely better than brute
force's 16.261 ms, because 19 enormous cells reject nothing while still paying for the filter, and the busiest of
them holds 7,146 of the 7,361 training points. At the smallest widths the 5,736-cell filter loop itself becomes
the bottleneck. Both predicted failure modes appear, and the optimum lies between them.

The curve is not perfectly monotonic on the coarse side: 0.15 is slower than 0.20 despite having larger cells.
This is a cell-boundary alignment effect. What matters for the query is not the nominal width but how many
points land in the cells the query actually has to scan, and for clustered data a slightly different width can split
or merge a dense cluster in a way that changes the busiest-cell occupancy non-monotonically, as the 4,875
against 3,426 column shows.

tune_cell_size selected 0.0725, which measures 4.334 ms against the sweep's best of 4.232 ms, so the
heuristic lands within 2.4 percent of the optimum without timing anything. The optimum is a broad basin
rather than a sharp point, which is fortunate, since it means the tuner does not need to be precise. The
comparison in section 9.1 is therefore against a well-tuned grid.

The asymmetry worth carrying into the discussion is that the tree has no such parameter. Its median-split
construction adapts to the data automatically, whereas the grid requires either domain knowledge or an
explicit search, and a poorly chosen width makes it worse than doing nothing clever at all.

9.6 A two-class variant, and what it does and does not show
The KOI table carries three dispositions, and every result above treats all three as classes to be predicted. A
common alternative in the literature is to restrict the problem to CONFIRMED against FALSE POSITIVE,
discarding CANDIDATE rows entirely. Because that choice changes the dataset, it is reported here explicitly
rather than adopted silently.

Both variants were run through the identical pipeline, differing only in whether CANDIDATE rows are kept.
[Link] can switch between them at runtime:

Variant Rows Train / test Accuracy Majority Lift

baseline
3-class 9,201 7,361 / 1,840 0.6522 0.5234 +12.9 pts
2-class 7,016 5,613 / 1,403 0.8432 0.6821 +16.1 pts

Taken at face value the two-class number looks dramatically better, 0.8432 against 0.6522. Two observations
stop that from being the right reading.

First, the baseline moves too. Removing CANDIDATE leaves FALSE POSITIVE holding 68.2 percent of the
remaining rows instead of 52.3 percent, so a classifier that predicts the majority class and nothing else
already scores 0.6821. Roughly a third of the apparent 19-point improvement is the easier baseline rather
than better classification. Measured as lift over the relevant baseline, the gap narrows from 19 points to 3.2.

Second, the residual 3.2 points is real, and it is the evidence for the argument in section 10.4. CANDIDATE
genuinely is the class the model handles worst, which is what the label semantics predict. CONFIRMED and
FALSE POSITIVE record a conclusion reached about an object. CANDIDATE records that no conclusion has
been reached yet, and whether a given KOI has been followed up depends on telescope allocation and target
priority rather than on the transit itself. None of that information is present in the 10 physical features, so the
boundary is partly unlearnable from this input in principle rather than merely difficult in practice.

The three-class result is retained as this report's headline for two reasons. It is the problem the dataset
actually poses, and discarding roughly 24 percent of the rows is a decision that needs the justification above
rather than an improved score to support it. The two-class figure is reported alongside it as a measurement
of how much of the difficulty CANDIDATE accounts for.

None of this affects any data-structure result. Accuracy is a property of k-NN and of the labels, not of the
index used to find neighbours, and in both variants the tree, the grid, and brute force agree unanimously:
1840/1840 rows in the three-class variant and 1403/1403 in the two-class variant.

10. Discussion
10.1 The curse of dimensionality, observed
The phrase "curse of dimensionality" is often quoted as a caveat. Figure 3 shows the mechanism concretely,
and it is worth stating why nearest-neighbour search specifically breaks down.

In high dimensions, distances concentrate. As d grows, the ratio between the distance to the nearest point
and the distance to the farthest point approaches 1, so "nearest" stops being distinguishable from "typical".
Every pruning rule in this report, the tree's plane-distance bound and the grid's box bound alike, depends on
the current best distance being small relative to the geometry of the partition. When all distances are similar,
no bound is ever comfortably exceeded, and every branch must be searched.

The tree does not merely stop helping at that point, it actively hurts, because it performs the same distance
computations as brute force plus recursion, list maintenance, and a pruning test that always fails. Figure 3
shows this as the tree curve crossing above the brute-force line and staying there.

The practical implication, consistent with Weber, Schek, and Blott (1998), is that above roughly 10
dimensions a sequential scan is competitive with or better than tree-based exact indexing, and the correct
response is either dimensionality reduction or accepting approximate answers.

10.2 Why the real dataset benefits at all

This raises the obvious question. The real data has d = 10, which Figure 3 places past the crossover, yet
section 9.1 measures the tree at 2.32x faster than brute force rather than slower. The two results appear to
contradict each other.

They do not, and the resolution is the central insight of the project. Figure 3 uses uniform data; the KOI
dataset is not uniform. Its 10 features are strongly correlated by physics rather than independent:
 koi_teq, equilibrium temperature, is determined largely by koi_period and koi_steff, since
temperature follows from orbital distance and stellar output.
 koi_insol, insolation flux, is essentially another expression of the same relationship.
 koi_steff, koi_slogg, and koi_srad jointly describe the host star and are tightly constrained by
stellar structure: main-sequence stars occupy a narrow locus in that space rather than filling it.
 koi_depth and koi_prad are related by construction, since planet radius is inferred from transit depth
and stellar radius.
The points therefore lie on a much lower-dimensional surface embedded in the 10-dimensional cube. The
intrinsic dimension is well below the nominal 10, and it is intrinsic dimension that governs whether pruning
works. The evidence is directly visible in the grid statistics: at a cell width of 0.5, the real data occupies just 19
of 1,024 available cells, which is what a low-dimensional structure sitting inside a high-dimensional box looks
like. Uniform data at the same width would occupy essentially all of them.

The clustered experiment in section 9.3 is the controlled version of this same effect, and the two agree:
clustered synthetic data at d = 10 gives 8.0x, real data at d = 10 gives 2.32x, uniform synthetic data at d = 10
gives 1.5x or worse. The real dataset sits between uniform and strongly clustered, which is exactly where a
physically correlated dataset should sit.

10.3 Tree versus grid

On the real data the grid is faster than the tree, 5.22 ms against 6.49 ms. Three points are needed to
interpret this fairly.

First, it is a real result and not noise. The grid genuinely wins by about 15 percent on this dataset. Constant
factors favour it: its inner loop is a flat iteration over a dict with a cheap box test, whereas the tree pays a
Python function call per node visited, and function calls are expensive in CPython.

Second, the grid does not scale as well. Its own asymptotic analysis in section 6.6 shows the filter loop is
O(nd/k), still linear in n. The measured slopes support this reading: on clustered data the grid's 0.798 is above
the tree's 0.721, and it is the tree that wins at n = 50,000 (13.912 ms against 20.804 ms). The grid improves
brute force's constant factor; the tree improves its growth rate, given data whose intrinsic dimension permits
pruning. The sub-linear slope measured for the grid should not be extrapolated, since it partly reflects the
tuner's inability to reach its occupancy target at the smallest n.

Third, the grid needs tuning and the tree does not. Figure 4 shows the grid spanning a wide range of
performance depending on a parameter with no principled default, and being worse than brute force at the
bad end. The tree has no such parameter. For a general-purpose structure this robustness is worth more than
15 percent on one dataset.

The honest summary is that on this specific dataset at this specific size the two are comparable, with the grid
slightly ahead on raw time and the tree ahead on scalability and robustness. Claiming a decisive k-d tree
victory would not be supported by the measurements.

10.4 Why accuracy is 65 percent and not higher

Accuracy of 0.6522 against a 0.5234 majority-class baseline is a modest gain, and several causes are
identifiable.
The CANDIDATE class is not a physical category. CONFIRMED and FALSE POSITIVE describe what a signal is.
CANDIDATE describes what has not yet been determined, and whether a KOI has been confirmed depends on
follow-up telescope time, target priority, and observational feasibility as much as on the transit's properties.
A classifier restricted to physical features cannot recover that, because the information is not in the features.
Some of the error is therefore irreducible given this label set. Section 9.6 quantifies this: removing
CANDIDATE raises the lift over the majority baseline from 12.9 to 16.1 points, so the class does account for a
measurable share of the difficulty, though less than its effect on raw accuracy alone suggests.

Class imbalance. FALSE POSITIVE at 51.3 percent means majority voting among 10 neighbours is biased
toward it in any mixed neighbourhood. The worked example in the CLI shows this: a genuine CANDIDATE was
classified FALSE POSITIVE on a 9-1 vote.

Equal feature weighting. Min-max scaling gives all ten features equal influence, which section 2.5 defends as
a better default than unit-driven weighting, but it is not the same as claiming all ten are equally informative.
koi_model_snr is a property of the detection and is plausibly more diagnostic of a false positive than
koi_srad, a property of the star. k-NN has no mechanism to learn such weights.

Unscaled outliers within a scaled range. Min-max scaling is sensitive to extreme values. koi_insol reaches
1.095e7 while its median is 140.7, so after scaling the vast majority of candidates are compressed into a tiny
interval near zero, and that feature contributes almost nothing to distances for typical points. A rank-based
or logarithmic transform would likely serve these heavy-tailed features better, and this is the single change
most likely to improve accuracy.

10.5 Threats to validity

 Timing is implementation-bound. As section 8.3 notes, wall-clock comparisons in CPython conflate
algorithm with interpreter overhead. Counting visited nodes and scanned points would give machine-
independent evidence and would directly measure pruning effectiveness rather than inferring it. This is
the most valuable extension.
 A single train/test split. All accuracy figures come from one seeded 80/20 split. k-fold cross-validation
would give confidence intervals.
 k is fixed at 10. k affects both accuracy and the pruning threshold, since a larger k means a looser bound
and less pruning. Sweeping k would characterise that interaction.
 The synthetic clustered generator is idealised. Isotropic Gaussians with equal variance are a crude
model of real astronomical structure. It is a controlled comparison against the uniform case, not a
simulation of the KOI dataset.
 The grid variant is not the textbook one. Section 6.4 documents why ring expansion was rejected. The
conclusions concern this min-distance variant, which is the stronger baseline of the two at d = 10.

11. Conclusion
A k-d tree was implemented from scratch in Python using only dicts, lists, and tuples, with median-split
construction and backtracking k-nearest-neighbour search with geometric pruning. It was verified exact
against brute force, with zero mismatches over 250 queries on the distance-based test of section 7 and
unanimous agreement with both baselines on all 1,840 test rows.
On the KOI dataset it delivers a 2.32x query speedup over brute force at identical accuracy of 0.6522, and a
tuned uniform spatial grid delivers 2.89x. Both are exact.

The more valuable outcome is the characterisation of when the structure helps. The experiments show that
the k-d tree's benefit is governed not by n but by the relationship between n and the intrinsic dimension of
the data:

 At d = 2 the tree is 44.8x faster than brute force.

 The advantage collapses as d rises and reverses near d = 9, past which the tree is slower than the
exhaustive scan.
 At a fixed d = 10, changing only the distribution from uniform to clustered moves the tree from 1.5x
slower-to-marginal to 8.0x faster.
 The real dataset benefits because its features are physically correlated, so its intrinsic dimension is well
below its nominal 10.
The single sentence worth carrying away is that a k-d tree is not a faster way to search a large dataset, it is a
faster way to search a dataset whose geometry permits pruning, and verifying that this precondition holds
matters more than the implementation itself. The project's most instructive measurement is the one where
the structure it set out to build was slower than the naive loop it set out to replace.

12. References
Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of
the ACM, 18(9), 509-517.

Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977). An algorithm for finding best matches in logarithmic
expected time. ACM Transactions on Mathematical Software, 3(3), 209-226.

Weber, R., Schek, H.-J., & Blott, S. (1998). A quantitative analysis and performance study for similarity-search
methods in high-dimensional spaces. In Proceedings of the 24th International Conference on Very Large Data
Bases (VLDB), 194-205.

NASA Exoplanet Archive. Kepler Objects of Interest cumulative table. NASA Exoplanet Science Institute.

Appendix A: pseudocode
A.1 Build
function build_kdtree(points, depth = 0):
if points is empty:
return None

d = number of features in points[0]

axis = depth mod d

sort points ascending by coordinate `axis`

mid = floor(length(points) / 2)

[Link] = features of points[mid]

 [Link] = label of points[mid]
[Link] = axis
[Link] = build_kdtree(points[0 .. mid-1], depth + 1)
[Link] = build_kdtree(points[mid+1 .. end], depth + 1)
return node

A.2 Insert and membership

function insert(tree, p, label, depth = 0):
if tree is None:
[Link] = p
[Link] = label
[Link] = depth mod d
[Link] = None
[Link] = None
return node

axis = [Link]
if p[axis] <= [Link][axis]:
[Link] = insert([Link], p, label, depth + 1)
else:
[Link] = insert([Link], p, label, depth + 1)
return tree

function exist(tree, p):

if tree is None:
return False
if [Link] equals p:
return True

axis = [Link]
if p[axis] < [Link][axis]:
return exist([Link], p)
if p[axis] > [Link][axis]:
return exist([Link], p)

return exist([Link], p) or exist([Link], p)

The final line is the tied-value case discussed in section 5.3. A point equal to this node on the split axis may
have been placed in either subtree by build_kdtree, so both must be searched.

A.3 k-nearest-neighbour search

function knn_search(root, q, k):
best = empty list # per query, holds (point, label, sq_distance)
search(root, q, k, best)
return best

function search(node, q, k, best):

if node is None:
return

# 1. descend into the side containing the query

if q[[Link]] <= [Link][[Link]]:
near, far = [Link], [Link]
else:
near, far = [Link], [Link]
 search(near, q, k, best)

# 2. consider this node while unwinding

append ([Link], [Link], sq_dist([Link], q)) to best
sort best ascending by distance
if length(best) > k:
remove last element of best

# 3. prune or search the far side

plane_gap = q[[Link]] - [Link][[Link]]
if length(best) < k or best[last].distance >= plane_gap^2:
search(far, q, k, best)

The two conditions in step 3 are both necessary. best[last].distance >= plane_gap^2 is the
geometric pruning rule. length(best) < k forces the far branch while the list is still filling, since with
fewer than k neighbours there is no meaningful threshold to prune against.

A.4 Grid query

function knn_grid(grid, cell_size, q, k):
best = empty list
home = cell_of(q, cell_size)

if home in grid:
scan_cell(grid[home], q, k, best) # seed a tight threshold first

for each (cell, points) in grid:

if cell == home:
continue
if length(best) == k and cell_min_sq_dist(cell, q, cell_size) >
best[last].distance:
continue # no point in this cell can qualify
scan_cell(points, q, k, best)

return best

function cell_min_sq_dist(cell, q, cell_size):

total = 0
for i in 0 .. d-1:
low = cell[i] * cell_size
high = low + cell_size
if q[i] < low: gap = low - q[i]
elif q[i] > high: gap = q[i] - high
else: gap = 0
total = total + gap^2
return total

Appendix B: files and reproduction

File Contents
cleaning_data.py CSV load, row cleaning, min-max scaling, scaler reuse
[Link] Squared Euclidean distance, train/test split, brute-force
k-NN, accuracy
 [Link] build_kdtree, insert, exist, knn_search,
_search, euclidean
[Link] build_grid, tune_cell_size,
cell_min_sq_dist, knn_grid
[Link] Exactness check of tree and grid against brute force
[Link] The four experiments and figures of section 9
[Link] Interactive CLI: classify, compare accuracy, benchmark;
owns predict
plots/ Generated figures and [Link] with all raw
numbers

To reproduce:
python [Link] # exactness check, prints 0 mismatches
python [Link] # regenerates all four figures and plots/[Link]
python [Link] # interactive classifier and benchmark

All randomness is seeded, so plots/[Link] reproduces exactly on the same machine. Absolute
timings will differ across machines; the crossover points and relative orderings are the reproducible findings.