Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

K-D-Tree Splitting Algorithm

IP.com Disclosure Number: IPCOM000043969D
Original Publication Date: 1984-Oct-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 3 page(s) / 63K

Publishing Venue

IBM

Related People

Robinson, JT: AUTHOR

Abstract

K-D-B-tree algorithms have been implemented, and their performance investigated in terms of page accesses. This earlier implementation, however, was concerned only with page accesses and did not deal with the problem of efficiently searching the regions or points within the page: regions or points were stored and searched linearly within pages. Since non-leaf pages can be represented as K-D-trees in a natural way (Fig. 1), and the points within leaf pages can be inserted, deleted, and searched using a K-B-tree structure in the usual way, this suggests structuring each page as a K-D-tree. One problem with this approach is that the K-D-B-tree algorithms require splitting pages along an arbitrary value of an arbitrary domain (Fig.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

K-D-Tree Splitting Algorithm

K-D-B-tree algorithms have been implemented, and their performance investigated in terms of page accesses. This earlier implementation, however, was concerned only with page accesses and did not deal with the problem of efficiently searching the regions or points within the page: regions or points were stored and searched linearly within pages. Since non-leaf pages can be represented as K-D-trees in a natural way (Fig. 1), and the points within leaf pages can be inserted, deleted, and searched using a K-B-tree structure in the usual way, this suggests structuring each page as a K-D-tree.

One problem with this approach is that the K-D-B-tree algorithms require splitting pages along an arbitrary value of an arbitrary domain (Fig. 2), and that there does not seem to be any current algorithms for splitting K-D-trees in such a fashion. This article describes an algorithm for splitting a K-D-tree into two K-D-trees given an arbitrary value in an arbitrary domain so that each resulting K-D-tree lies entirely within each of the two half-K-spaces determined by this value and domain. Let the K domains be numbered 1, 2, 3, . . . , K, and let the splitting value be S in domain I. A K-D-tree node will be represented as (P1,X,J,P2), where P1 is either a pointer to another K-D-tree node in the same K-D-tree, or else some other type of data that the K-D-tree is being used to find (e.g., in the K-D-B-tree application mentioned above, in a non-leaf page P1 could be a pointer to another page), similarly for P2, and where X is a value in domain J. The input to the K-D-tree splitting algorithm is the original K-D-tree with root OTREE, the splitting value S, and the splitting domain I. The output will be two K-D-trees with roots LTREE and RTREE, where LTREE lies entirely within the left half-K-space determined by S and I, and RTREE lies entirely within the right half-K-space determined by S and I. The algorithm is defined recursively as follows (the steps flagged with an asterisk are referred to later): 1. (*) If OTREE is not a pointer, or if it is the null pointer, set LTREE and RTREE to OTREE, and terminate. 2. Otherwise, OTREE points to some node (P1,X,J,P2). There are four cases. a. Case 1: I J (Fig. 3). Create two new nodes (L1,X,J,L2) and (R1,X,J,R2), where L1,L2,R1,R2 are computed as follows. 1) (*) If P1 is not a pointer, or if it is the null pointer, set L1 and R1 to P1, and...