Let D be a 2-dimensional point dataset and p = (x, y) a point in that set. The coordinates of all points are positive. Consider

Question

87 users unlocked this solution today!

Let D be a 2-dimensional point dataset and p = (x, y) a point in that set. The coordinates of all points are positive. Consider the function: f(p) : D R, where f(p) = a₁x + a₂y and a₁ + a₂ = 1. The values for a₁ and a₂ are given by the user. The idea is that each user gives different importance (weight) to different attributes. We want to find the point (or points) that maximize(s) this function. This type of queries are called preference queries. Now, assume that an R-tree is used to store the dataset D.

(a) Design an efficient search procedure that uses the R-tree to find the point(s) that maximize the function f. Give the pseudo-code of the algorithm and explain how it works.

(b) What is the property that allows the design and guarantees the correctness of your algorithm? Explain.