1. 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 |d(Op, Q)-d(Or, Op)|>r(Q)+r(Or), then d(Or, Q) > r(Q) + r(Or) holds and node centered at Or with radius r(Or) can be safely pruned.
2、Read the lecture slides about the pruning conditions for Simple Point Method (SPM) of GNN queries, and prove the pruning condition below (Hint: you may need to read the original paper of GNN and use the triangle inequality for the proof) [30 points]
3、Given an aR-tree (as mentioned in the reference below) I and a hyperrectangular query region Q, please write the pseudo code of retrieving the number of objects in Q by traversing the aR-tree. [30 points]
I. Lazaridis and S. Mehrotra. Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure. In SIGMOD, 2001.