educative.io

Confused by QuadTree Index

Courses
,
#1

My understanding is that QuadTree server will respond with what locationIDs for the given query will contain. The QuadTree Index description is confusing. It says “We will need to build a HashMap where the ‘key’ is the QuadTree server number and the ‘value’ is a HashSet containing all the Places being kept on that QuadTree server” My guess is the following

  1. QuadTree knows nothing about locationIds
  2. QuadTree will query Index to get a list of locationIds based on latitude and longitude
  3. The purpose of QuadTree Index is to speed up the look up of locationIds
  4. The purpose of the DB behind QuadTree Index to provide a persistent store of the index mapping as well as the target data of locations such as the whole meta data of locations.
  5. There should be separate micro service API that does the inverse look up based on the name to return the latitude/longitude of the interested location before QuadTree is being queried. And this step should be embedded in the search() API work flow.
    Can someone comment and confirm?
#2

Hi, @J1m!

The statement below corresponds to the distributed QuadTree servers. The Places data will be partitioned between all QuadTree servers, and we need to create a reverse index that maps the Places to the quad servers.

We will need to build a HashMap where the key is the QuadTree server number, and the value is a HashSet containing all the Places being kept on that QuadTree server.

We create a QuadTree to store this reverse mapping between places and the quad servers on top of the forward index.