BIG DATA

3. Please read the lecture slide of Chapter 5, "Range Queries Over M-Tree", and prove the pruning strategy for the range query below (Hint use the triangle inequality) [30 points]: If Id(O,, Q)-d(O,, 1>r(Q)+r(O,), then d(Or, Q) > r(Q) + r(Or) holds and node centered at Or with radius O) can be safely pruned. Or d(Op.Q) r(Q Op Note LB Idistq, p)-dist(p, o) and UB dist g p)+ dis p, o),p is apivot Given a data set D, and a set of query points Q={q, q2, , q"), a data object a can be safely pruned if there exists an object ok such that UBy S LB, for all 1 SjSn dist(a^, -) 1S O k o k dist 3. Please read the lecture slide of Chapter 5, "Range Queries Over M-Tree", and prove the pruning strategy for the range query below (Hint use the triangle inequality) [30 points]: If Id(O,, Q)-d(O,, 1>r(Q)+r(O,), then d(Or, Q) > r(Q) + r(Or) holds and node centered at Or with radius O) can be safely pruned. Or d(Op.Q) r(Q Op Note LB Idistq, p)-dist(p, o) and UB dist g p)+ dis p, o),p is apivot Given a data set D, and a set of query points Q={q, q2, , q"), a data object a can be safely pruned if there exists an object ok such that UBy S LB, for all 1 SjSn dist(a^, -) 1S O k o k dist