Question

k-d tree

Background

One generalization of binary trees is the k-d tree, which stores k-dimensional data. Every internal node of a k-d tree indicates the dimension d and the value v in that dimension that it discriminates by. An internal node has exactly two children, containing data that is less-than-or-equal and data that is greater than v in dimension d. For example, if the node distinguishes on dimension 1, value 107, then the left child is for data with y value less than or equal to 107, and the right child is for data with y value greater than 107. Leaf nodes represent a bucket containing no more than b elements of k-dimensional data. All data are found in the leaves.

For this assignment, k is 4; that is, we only deal with four-dimensional data. Dimension numbers are therefore 0, 1, 2, and 3.

There are several strategies for building k-d trees. The offline method (1) accumulates all the data in an array, (2) finds the best dimension to discriminate on, namely, the one with the widest range, (3) finds the best value of that dimension to discriminate on, namely, the median value in that dimension (typically using the QuickSelect algorithm with Lomuto's partitioning method), (4) separates the data into two subarrays based on that discriminant, (5) recurses back to step 2 on each subarray. Recursion terminates when an array has size b or smaller. One can also devise online methods that add to existing trees.

Requirements

Write a program called kd that (1) takes a parameter n, which should be a positive integer, indicating how many data points are to be placed in the tree, and a parameter p, indicating the number of probes into the tree; (2) reads from standard input a list of n 4-dimensional integer data points; (3) builds a k-d tree with those n values using the offline method, with b set to 10 (and ties going to the left subtree); (4) reads p 4-dimensional data values, called probes, and for each probe, lists all the data points stored in the bucket where the probe would be found if it were in the tree.

In step 3, you may assume that all integer data are distinct.

Answer 1

fast and secure web hosting at the lower possible price.

For ex: KD-tree is used in databases.

now you have the recoreds of employees like thier attributes .

query is to list the employees

age: 22 to 34

salary: $54,000 to $90,000

How will it  be done?

If data redundancy is not a problem for yo then you can sort the data separately, then do the range search with binary search to get the answers.

Data redundancy can be taken care by storing the original data in some hash map and storing the sorted list of indices.this will have the memory size.

If you really want the best memory and speed performance then KD-tree will be helpful.