1. Given the following geospatial map with ten data points (labelled 1 to 10), and the associated quad-tree data structure (shown as boxes over the geospatial map) with a maximum per-bucket load of 1, explain what happens when we insert an element 11 (labelled 11) at the position shown in the map? What does the resultant quad-tree look like? 

 

2. Explain how we can use the quad-tree structure to query for all points within the (x,y) region bounded by (10, 0) and (20, 10)? Which points will be returned?

3. Briefly discuss the concept of in-memory key-value stores as compared to traditional relational database management systems. Provide one possible use-case for an in-memory keyvalue store.
 

Transcribed Image Text:

y = 20 y = 10 y = 0 x = 0 1 2 3 4 x = 10 6 5 10 7 11 9 8 x = 20 y = 20 y = 10 y = 0 x = 0 1 2 3 4 x = 10 6 5 10 7 11 9 8 x = 20