Mining the Data in Programming Assignment

Assignment Task

The purpose of this project is to create a symbol table data type whose keys are two-dimensional points. We’ll use a 2dTree to support efficient range search (find all the points contained in a query rectangle) and k-nearest neighbor search (find k points that are closest to a query point). 2dTrees have numerous applications, ranging from classifying astronomical objects to computer animation to speeding up neural networks to mining data to image retrieval.

Geometric Primitives, We will use the data types dsa.Point2D and dsa.RectHV to represent points and axis-aligned rectangles in the plane.

Corner Cases

• The put() method should throw a NullPointerException() with the message "p is null" if p is null and the message "value is null" if value is null.
• The get(), contains(), and nearest() methods should throw a NullPointerException() with the message "p is null" if p is null.
• The rect() method should throw a NullPointerException() with the message "rect is null" if rect is null.

Develop a data type called KdTreePointST that uses a 2dTree to implement the above symbol table API.

A 2dTree is a generalization of a BST to two-dimensional keys. The idea is to build a BST with points in the nodes, using the x- and y-coordinates of the points as keys in strictly alternating sequence, starting with the x-coordinates.

• Search and insert. The algorithms for search and insert are similar to those for BSTs, but at the root we use the x-coordinate (if the point to be inserted has a smaller x-coordinate than the point at the root, go left; otherwise go right); then at the next level, we use the y-coordinate (if the point to be inserted has a smaller y-coordinate than the point in the node, go left; otherwise go right); then at the next level the x-coordinate, and so forth.

The prime advantage of a 2dTree over a BST is that it supports efficient implementation of range search, nearest neighbor, and k-nearest neighbor search. Each node corresponds to an axis-aligned rectangle, which encloses all of the points in its subtree. The root corresponds to the infinitely large square from [(−∞, −∞),(+∞, +∞)]; the left and right children of the root correspond to the two rectangles split by the x-coordinate of the point at the root; and so forth.

Range search

To find all points contained in a given query rectangle, start at the root and recursively search for points in both subtrees using the following pruning rule: if the query rectangle does not intersect the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). That is, you should search a subtree only if it might contain a point contained in the query rectangle. ˆ Nearest neighbor search. To find a closest point to a given query point, start at the root and recursively search in both subtrees using the following pruning rule: if the closest point discovered so far is closer than the distance between the query point and the rectangle corresponding to a node, there is no need to explore that node (or its subtrees). That is, you should search a node only if it might contain a point that is closer than the best one found so far. The effectiveness of the pruning rule depends on quickly finding a nearby point. To do this, organize your recursive method so that when there are two possible subtrees to go down, you choose first the subtree that is on the same side of the splitting line as the query point; the closest point found while exploring the first subtree may enable pruning of the second subtree.

This IT and Computer Science has been solved by our PHD Experts at My Uni Paper.