Question

Suppose we store a relation R (x,y) in a grid file. Both attributes have a range of values from 0 to 1000. The partitions of this grid file happen to be uniformly spaced; for x there are partitions every 20 units, at 20, 40, 60, and so on, while for y the partitions are every 50 units, at 50, 100, 150, and so on.
Required:
a. How many buckets do we have to examine to answer the range query?
b. We wish to perform a nearest-neighbor query for the point (110, 205). We begin by searching the bucket with lower-left corner at (100, 200) and upper-right corner at (120, 250), and we find that the closest point in this bucket is (115, 220). What other buckets must be searched to verify that this point is the closest?

Answer 1

Answer:

For (a) The total number of buckets from the given query for the relation is 25 buckets (b) the nearest neighboring query is (80, 200) (80, 150), (100, 150), (120,150) and (120, 200)

Explanation:

From the question stated, we need to define what a Grid file is

Grid File it is a structure of data that are used to divide the total space into a grid non-periodic, where set of point (small) are defined by more than one cells of the grid.

(a)Finding buckets for the query

The relation is divided into two parts which ranges from 0 to 1000, the first part is partitioned in every 20 units, at 20, 40, 60 etc; a second part is partitioned into every 50 units at 50, 100, 150 etc.

The total number of buckets from the given query for the relation is 25 buckets

(b)Finding the closest point or nearest point

The closest point discovered in the distance is little above 15

These points are are the points closer to the point target (110, 205) which can be found in five neighboring rectangles with left corners lower is stated as follows:

(80, 200) (80, 150), (100, 150), (120,150) and (120, 200)