• The University of Hong Kong

• COMP 3323

Department of Computer Science

The University of Hong Kong

COMP3323: Advanced Database Systems

Assignment 2 (10% of total marks)

Due date: Thursday, October 24, 2019, 4:00pm

Q1. [5%]

Consider a set of 10 hotels that are spatial points {a, b, c,…, i, j}. These hotel points are indexed by an Rtree as illustrated in the two figures of Figure 1. Table 2 shows the ratings of these hotels. Rating values

are integers in [1, 10].

Suppose you are at query point q in Figure 1 (left) and want to find a hotel that must have rating ≥ 7,

and as close to your position q as possible based on Euclidean distance.

(1). Fill the steps of finding your desired hotel using incremental Best First Nearest Neighbor Search

with the help of a priority queue Q into Table 1. Elements in Q are ordered by the distance to the query

point q in ascending order. (In each step, you need to specify which node to access, the content of Q

after access action at current step.)

(2). In the end, show the final result of the query. Show how many R-tree nodes are accessed during this

search.

(The first step of accessing root node of R-tree is provided for your reference. After accessing root, MBR

M1 (distance to q is 1) is at the front of Q, while M2 (distance to q is √2) and M3 (distance to q is 4) are

behind M1 sequentially.)