kdtree

What it is and what it does

kdtree is a pure-Python implementation of kd-trees, a data structure that partitions points in k-dimensional space to accelerate spatial queries. It lets you build a tree from any collection of indexable objects (tuples, lists, namedtuples, or custom classes that support indexing), then search for the nearest neighbor to any query point in logarithmic time. The tree supports standard operations: insertion, deletion, traversal (inorder and level-order), and rebalancing.

You'd use this when you need to find the closest point(s) in a dataset to a given location—common in machine learning, computational geometry, clustering, and spatial analysis. The package is straightforward: create a tree, add or remove points as needed, and query for nearest neighbors. It handles any number of dimensions and works with any objects that look like tuples to the tree, so you can attach metadata (a payload) to each point without needing a separate index.

Use it for:

• Find the nearest landmark, location, or object in a spatial dataset given a query coordinate
• Implement k-nearest-neighbor search for machine learning or clustering algorithms
• Build a spatial index for collision detection or proximity queries in games or simulations
• Store and query multi-dimensional data (e.g., feature vectors) with fast nearest-neighbor lookup
• Attach metadata to spatial points and retrieve both the point and its associated data in one query

Worth the install?

AI-flagged interpretation of the facts on this page — verify before relying

Constructs, modifies, and searches kd-trees—spatial data structures for organizing points in multi-dimensional space to enable efficient nearest-neighbor queries.

Yes, if you need a lightweight, dependency-free kd-tree for nearest-neighbor queries in Python. The package is stable (ISC-licensed, no known vulnerabilities) and suitable for small to medium datasets. However, the last release was 2017-10-19 and maintenance is aging; for production use at scale or with modern Python versions, verify compatibility and consider whether a more actively maintained alternative (such as scipy.spatial.KDTree) better fits your needs.

Install

kdtree on PyPI

pip install kdtree

uv add kdtree

poetry add kdtree

Installing kdtree

Before you install

Low install friction; pure Python wheel. Maintenance is aging—last release was 2017-10-19 and last commit 2025-05-27, so the codebase is stable but not actively developed. No runtime dependencies.

License in practice

ISC license is permissive; you can use, modify, and distribute this package with minimal restrictions, including in commercial software.

Quickstart

import kdtree

# Create tree from list of points (tuples, lists, or indexable objects)
tree = kdtree.create([(2, 3, 4), (4, 5, 6), (5, 3, 2)])

# Find nearest neighbor to point (1, 2, 3)
nearest = tree.search_nn((1, 2, 3))

# Add and remove points
tree.add((5, 4, 3))
tree = tree.remove((5, 4, 3))

Verify before relying

• Whether the package is actively maintained or if aging status poses a risk for future Python versions
• Performance characteristics (insertion/search time complexity) for large datasets
• Whether rebalancing is automatic or must be called manually to maintain tree efficiency

Package facts

Evidence: kdtree-0.16-py2.py3-none-any.whl

Tags

More Libraries packages