Efficient data structures play a crucial role in optimizing query performance when dealing with spatial data and computational geometry. One such structure that has gained significant attention is the BKD tree, which stands for "Block-K-Dimensional" tree. BKD is an improved variant of the K-D tree that offers better memory usage and query performance. In this blog post, we will delve into the workings of the BKD tree and its applications in range queries.

The Anatomy of a BKD Tree

A BKD tree is a binary tree that partitions data points in a multi-dimensional space. Each node in the tree represents a block of data points, where the block size is determined by a user-defined parameter. The tree structure is built by recursively splitting the data points along different dimensions, creating a balanced binary tree.

One of the key advantages of the BKD tree is its ability to efficiently handle range queries. When performing a range query, the tree is traversed to identify the blocks that intersect with the query range. This is achieved by comparing the query range with the bounding boxes associated with each node in the tree. By discarding irrelevant blocks during the traversal, the BKD tree significantly reduces the number of comparisons required for range queries, resulting in faster query times.

As a variation of a K-D Tree, BKD Trees have many substantial differences. BKD Trees are designed for disk-based operations and excel in scenarios where the dataset is too large to fit into main memory. On the other hand, traditional K-D Trees are typically used for in-memory operations.

Another significant innovation introduced by BKD Trees is immutability. BKD trees are often constructed in an immutable manner, which means that once a part of the tree is written to disk, it remains unchanged. This is particularly suitable for scenarios where data is written once and read multiple times, and it simplifies concurrency and transactional semantics. On the other hand, K-D trees, being primarily an in-memory structure, are typically mutable.

One significant advantage of choosing BKD Trees over other data structures is their space efficiency. When serialized to disk, BKD trees occupy less space because they group points into blocks at the leaves, minimizing the need for tree pointers and node metadata. In contrast, K-D trees usually require more space due to the additional overhead of pointers for each node and leaf.

Applications of the BKD Tree

The BKD tree has various applications in domains that use spatial or multi-dimensional data. One of its primary use cases is in Geographic Information Systems (GIS), where the tree can be utilized to index and query spatial data, including points, lines, or polygons. The BKD tree's primary advantage is that it allows for efficient retrieval of data points within a specified range, which makes it possible for users to carry out fast spatial analysis and visualization.

In database systems that handle high-dimensional data, the BKD tree finds another useful application. Traditional indexing structures like B-trees face challenges with high-dimensional data due to the curse of dimensionality. However, the BKD tree partitions the data points based on their spatial proximity, making it possible to query efficiently even in high-dimensional spaces.

Furthermore, the BKD tree has shown promise in similarity search tasks, where the goal is to find data points that are similar to a given query point. By leveraging the tree's partitioning nature, the BKD tree can effectively prune irrelevant branches during the search process, reducing the search space and improving the overall efficiency of similarity search algorithms.

Differences between BKD Trees, R-Trees, K-D Trees, and Quadtrees

When implementing spatial queries, the most common data structures to consider are R-trees and quadtrees.

At Orama, we decided to implement our Geosearch APIs using BKD Trees, because they offer superior query performance and memory usage compared to R-trees and quadtrees. But how do they do that? Let’s find out more.

BKD Tress vs R-Trees

R-trees are specifically designed to handle bounding rectangles and are commonly used in geographical information systems for spatial data queries. For example, they are used to search for all points within a given region. R-trees group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree. The "R" in R-tree stands for rectangle. This process is recursive and builds a hierarchy, with each node containing entries that represent aggregations of its child nodes.

R-trees are optimized for bounding box queries, such as finding all objects within a geographic region. They are particularly efficient for datasets where objects vary in size and overlap. By minimizing the number of bounding box intersection checks during search queries, R-trees improve performance.

When comparing it to BKD Trees, the splitting strategy of R-Trees is more complex and aims to minimize overlap between bounding rectangles. Various strategies such as linear, quadratic, or exponential splits can be used to determine how to create new nodes while ensuring that the minimum bounding rectangles (MBRs) do not overlap. On the other hand, in BKD Trees, the space is split along specific dimensions, usually in a round-robin manner or based on the dimension with the highest variance. Points are then divided into blocks that fall on either side of the split.

Other key factors play a role in differentiating the two data structures. For example, node capacity impacts how the tree is split or re-balanced. R-trees have nodes that contain a variable number of entries, bounded by a minimum and maximum count. This allows for more adaptive space utilization but can result in more complex tree-balancing operations. Additionally, balancing and reinsertions, as well as overall structure and organization, also contribute to the differences between the two data structures.

In that sense, there is no "winner" between these two data structures. As always, you have to choose depending on your very specific use case and needs.

BKD Trees vs K-D Trees

As mentioned in the introduction of this blog post, BKD Trees are a variation of K-D Trees and may initially appear very similar. However, there are some important distinctions between them. We have already mentioned that BKD Trees are optimized for disk-based operations, unlike K-D Trees which are primarily designed for in-memory operations. Another difference is in how balancing is managed: K-D Trees often require balancing for efficiency, while BKD Trees, being often immutable, do not support traditional balancing.

Speaking of Orama, this was one of the key factors that led to the decision to use BKD Trees. The constraints imposed by edge networks, such as limited memory, also played a role in this decision, along with the ability to easily serialize and read trees from disk to contribute to optimal performance.

BKD Trees vs Quadtrees

BKD Trees and quadtrees are quite different, particularly in terms of their organization and query performance. Quadtrees are specifically designed for two dimensions (while Octrees are designed for three dimensions), dividing the space into four parts or quadrants with each division. On the other hand, BKD Trees are designed for multi-dimensional data (k-dimensional) and are commonly used for higher dimensions.

When comparing the composition of nodes in these two data structures, a significant difference becomes apparent. In Quadtrees, the node is divided evenly into four child nodes or quadrants, regardless of the distribution of data. On the other hand, in BKD Trees, nodes are split into two based on a chosen dimension and split point, often the median, effectively separating the point data. Depending on the specific use case, the Quadtree splitting strategy can highlight some problems. They are less adaptive to point distributions due to uniform quadrant divisions, potentially resulting in many empty or sparsely populated nodes. In contrast, BKD Trees are more adaptive as they partition based on the actual point distribution, often resulting in a more balanced distribution of points.

BKD Trees in Orama

In Orama, we have chosen to implement our Geosearch APIs using a highly optimized BKD Tree implementation. This implementation has been developed specifically for Orama, with scalability and performance as the primary considerations.

The decision was influenced by the ability to quickly access partitions from disk, external memory, or services. Additionally, the ease of managing multi-dimensional data was an important factor, as we may need it to optimize our custom vector storage engine in the future.

You can test its capabilities by using the following live demo. Simply visit https://orama-examples-geosearch-airports.vercel.app/, where you can draw a polygon on a map and retrieve all the airports within the designated range.

You can find the complete implementation in our repository at https://github.com/oramasearch/orama/blob/main/packages/orama/src/trees/bkd.ts.