How to convince your lead that quad trees are awesome? Make a bulky geo lookup 100x faster

This article may as well be named "How to 100x a bulk geographic lookup." Or perhaps "How to speed [it] up from twenty to two minutes." In one of my projects, we need to keep up with hundreds of high priority targets moving around the globe and being tracked relatively regularly via GPS trackers. All that, in order to track where they go, and more importantly: are they in particular user-defined areas?

Initial implementation

A very simple and straightforward way you would implement it would be to take the list of target positions you need to check, take the list of areas and the coordinates that make them up, and match them together. We end up with a complexity of $O(np)$, where $n$ is the number of positions to process, and $p$ the number of areas to match them with. At least, it's not quadratic... sure. Now, this doesn't sound too bad, does it? It makes sense that the complexity would scale like that. After all, those are the two main factors of the entire operation.

You would be right. But, how ever you look at it, it poorly scales as $n$ gets larger. By our measurements, matching one position against all areas was taking around three to four seconds. If you have one hundred targets, then the entire operation would take around six minutes. This already restricts you from real-time or minute-by-minute monitoring. Sure, this might not be your usecase anyway. Perhaps you need it every half hour, or every hour. Let's say that your business expand, and you start having to monitor upwards to two, three, or four hundred, you soon reach a point where the next batch arrives before you finished processing the previous one.

Sure, you could increase the specs of your machine and whatnot, or parallelise the operations. But there is a "simple" and quite elegant solution to all these issues!

The Solution

Looking at how our problem scales, the only way we could lower the load and improve the performance would be to lower $n$, the number of positions to process, or $p$, the number of areas to match. Now, we can't lower $n$. After all, we need to process every position! And you might think we can't lower $p$ either, but it's not entirely infeasible. A lot of the time spent matching a position is spent on areas that would have no chance at all to even match. Even if a position is in Russia, we still spend precious time looking into areas focused in the UK or France! This is a huge waste of CPU resources!

You could think that if we knew if an area has a chance to match with a position, or none at all, then this would lead to the same scalability issues. This would be true if we were to think to terms of absolute certainty. In our first implementation, we are making sure that there is no area that wasn't properly matched in order to rule them out. What if there was a way to trustworthily rule out a swath of areas with minimal effort?

This is where quad trees come into play.

What's a quadtree?

A quad tree is a tree data structure used in computer science, particularly in computer graphics, geographic information systems (GIS), and image processing. It is a hierarchical tree structure in which each node has four children, hence the name. The primary purpose of a quad tree is to partition a two-dimensional space into smaller regions (quadrants) to efficiently organise and search data. This hierarchical subdivision allows for efficient spatial indexing and retrieval of information. Quad trees are commonly used in applications where spatial data needs to be efficiently organised and queried, such as in image compression, collision detection, and spatial databases.

The basic idea is to recursively subdivide a space into four quadrants until a certain condition is met. Each node in the quad tree represents a rectangular region, and it either contains data or further subdivides its region into four smaller quadrants. There are different types of quad trees, including:

• Point: Each node represents a point in space, and the subdivision is based on the spatial location of points.
• Region: Each node represents a region or area of space, and the subdivision is based on the spatial extent of these regions.
• Hybrid: A combination of point and region quadtree, where nodes can represent either points or regions.

Quad trees provide an efficient way to perform spatial queries, such as range searches, nearest neighbour searches, and intersection tests, by exploiting the hierarchical structure and organising data based on spatial proximity. For our use, we need a Region quad tree (subsequently referred to as tree) where each Region (also referred to as a node) will contain a list of the areas that are (entirely or partially) within it.

Before processing the positions, we build said tree. We start at the root node, which is the entire map that contains all areas. When instantiated, this node will subsequently split itself into four quadrants and compute which areas intersect with each quadrant. Each of them becomes a node and the process repeats itself, each quadrant splitting itself into more quadrants and so on and so forth until a maximum deepness threshold (noted d) is reached.

The number of nodes at a specific deepness level $d'$ with $d\le d'$ is $4^{d'}$. The total number of nodes in the entire tree is $\sum^d_i{4^i}$ which is, using a geometric series formula, simplified to $\frac{4^d-1}{3}$. Thus, the complexity of building such a tree is $O(\frac{4^d-1}{3}p)$.

How do we use it?

Once built, we can query the areas at a given coordinate by giving the root node a coordinate. The root node will then determine which of its quadrants contains the coordinate and ask it recursively until we reach a leaf node (a node without subnodes). When we reach the leaf node, we retrieve its list of areas and return it recursively giving us which areas are intersecting with the region of the leaf node.

As you can see, this doesn’t give us EXACTLY what we want, which is the position’s areas. It only gives us the areas in the surroundings of the position we are processing. But that is still quite useful for us, since we are precisely trying to minimize the number of areas we need to process.

As we said previously, to decrease the processing time, we need to minimize $p$. We minimized $p$ by giving us only those who are intersecting, partially if not exactly, the position. And reading the tree costs only $O(4d)$ (simplified by equivalence to $O(d)$) which is to say that for each layer of the tree, we check 4 quadrants until we reach the leaf and return.

Thus, instead of needing to check all $p$ areas in $P$, we only need to check a subset $M$ where $M\subseteq P$, and the number of areas inside the leaf node where $m=|M|$ the length of $M$ with $m\le p$.

Is it actually better?

As long as the cost of a) building the tree, b) reading it, and c) checking collisions on $M$ is lower than the cost of checking collisions on $P$, then it will stay a better solution. In mathematical expression, our quadtree will be better if: $O(\frac{4^d-1}{3}p) + O(nd) + O(nm) \le O(np)$

While this might look like the quadtree implementation is worse than the current implementation, we can observe the following points:

• The first term is not dependent on the number of positions we need to process. Therefore, it will stay constant as $n$ increases.
• The second term is not dependent on the number of areas we need to process. Therefore, it will stay constant as $p$ increases.
• Also note that, as previously stated, $d$ is a constant equal or lower than five, meaning that we could safely reduce: $O(nd) \simeq O(n)$. Which can be then integrated with the third term:
  $\simeq O(n)+O(nm)$
  $\simeq O(n+nm)$
  $\simeq O(2nm)$
  $\simeq O(nm)$

Which gives us this simplified expression: $O(\frac{4^d-1}{3}p)+O(nm) \le O(np)$

Let’s name the first term of the inequality as NEW, and the right one ($O(np)$) as OLD. Keeping in mind that if $NEW>OLD$, this means that the new method costs more and thus is less performant.

We know already that $m \le p$, this means that $O(nm) \le O(np)$ will always be true and thus lets us know that querying the tree will never be worse than the current implementation. However, the tree building term ($O(\frac{4^d-1}{3}p)$) poses an issue.

This expression demarks itself from $O(np)$ as it scales exponentially with d which shouldn’t be higher than 5. This means that in practice, $\frac{4^d-1}{3}\le 341$. In addition, we also need to take into consideration the $O(nm)$ term that scales with $m$ which itself depends on the spatial distribution of $P$. Taking the median number of areas per leaf node that we will note $\alpha$, the closer $\alpha$ comes to $p$, the less spatially distributed $P$ is. Noting that we can measure the spatial distribution of $P$ by how close $m$ is to $p$.

More formally: $\lim_{\alpha\to p} m=p$, and thus that $\lim_{\alpha\to p} O(nm)=O(np)$.

Conclusion

As previously stated, in our case $m=6$ (on average) and let's say we have 108 user-defined areas to match, so $p=108$. This gives us: $\frac{-341p}{m-p}=\frac{-341 \times 108}{6 \times 108}=\frac{361.058824}{102}=3.53979239$

This indicates that for the quadtree to be more performant than the current implementation with a deepness of 5, a total of 108 areas to check, and an average number of area per leaf node of 6, we need at least ~4 coordinates to process. Less than that and the quadtree solution becomes slower.

In other words, building the tree takes around the same time as it would take to process four coordinates using the initial implementation.

Knowing in our case, we have hundreds of them, this requirement is easily fulfilled. In fact, we have thousands of them which further emphasizes the point.