Design Choices for Location Based Services / Part II
As we've seen, calculating locations in 2D space using latitude and longitude can be compute-intensive and time-consuming. However, queries and lookups in 1D are significantly faster. Therefore, we are exploring methods to map 2D coordinates (lat, long) to 1D space.
This can be achieved in two main ways: hash-based and tree-based methods. We've already examined hash-based approaches, namely Even Grid and GeoHash. In this blog post, we will be discussing Quad Tree.
Quad Tree
A Quadtree is a tree data structure used to efficiently organize and partition a two-dimensional space. It recursively divides a region into four quadrants (quads) until the content of a quadrant meets a certain condition (e.g., a maximum number of points). It is an effective method for spatial indexing, allowing for fast lookups and queries on data points (like latitude and longitude) that are clustered in a 2D plane.
A Quadtree is an in-memory data structure, not a database solution. It typically runs on a Location-Based Service (LBS) Server and is built during the server's startup time. The following steps detail the construction process:
The process begins with a single node (the root) that represents the entire 2D space being indexed (e.g., a city map).
A node is split into four child regions if it contains more data points or objects than a predefined maximum capacity (threshold).
The four child regions are typically designated as North-West, North-East, South-East, and South-West.
The points within the parent node are then redistributed into the new child quadrants based on their coordinates.
This same splitting rule is applied recursively to each of the four child nodes.
The process stops when a node (a leaf) satisfies the stopping condition—usually containing less than the maximum capacity of points or reaching a maximum defined depth.
The Quadtree follows adaptive precision, meaning the structure automatically adjusts to the data density. It saves computational resources by not over-dividing empty regions. It is due to this property that it is used for collision detection in games and Level of Detail (LOD) rendering in graphics.
While Quadtrees are excellent for spatial analysis, it is useful to compare them to alternative methods. For instance, Geohash is typically preferred for high-volume writes (like tracking moving objects) and simplicity, while Quadtrees excel for complex spatial analysis and non-uniform data distribution.
Additionally, as the server builds the Quadtree at startup, indexing millions of records can result in the Location-Based Service (LBS) taking a few minutes to become operational. This creates a period of service unavailability during the startup process. To mitigate this downtime, a deployment strategy of incremental rollout (or canary deployment) can be used, updating only a small subset of servers at a time while maintaining the availability of the others.
This deployment method, however, may result in some servers serving stale data for a short period. An alternative is to update the Quadtree as changes occur (on-the-fly). While this ensures data freshness, it significantly complicates the design because it necessitates implementing locking mechanisms within the Quadtree structure to ensure thread safety in a multi-threaded environment.
Additional Reads & Watch
