How to search point-of-interest (POI) markers on a map efficiently

At Booking.com we’re passionate about making the life of our users easier by providing the best property search capabilities. We want our users to have all the information to choose the best accommodation. It’s probably no secret that the location of the property is one of the most important criteria when choosing an accommodation, as it’s a major part of the trip experience.

Booking.com map feature is a powerful tool as it provides location information in a very visual way. In just a few seconds users can determine whether or not the property is in their preferred location. However, usually it’s not enough just to see the location of the property itself. It’s also important to show the location of the most interesting places to visit during the trip. How far are they? How easy is it to get to them from the property?

To help our users answer these questions, besides the property markers we also display so-called point-of-interest (POI) markers. As the name suggests, these markers highlight places of interest for travelers, such as beaches, ski resorts, landmarks, as well as cities and airports, all of which give a better understanding of the property’s location to the user.

City, attraction and airport markers on map

How to search on the map?

When a user opens the map, usually a specific area, called a bounding box (BBox), is visible. Technically speaking, a BBox is a rectangle, the corners of which are represented by 4 geo points:

• North-West (NW);
• North-East (NE);
• South-East (SE);
• South-West (SW).

Since it’s a rectangle, it’s enough to know just 2 geo points located diagonally from each other to derive a BBox. For example NE and SW.

Bounding box — the visible map area.

Logically, it’s enough to display only those POI markers which are inside of this BBox, because the rest of the world is not visible to a user. Thus, we can use a BBox as our search key when searching for the map contents.

Users might change the visible area by panning and zooming the map and the number of such interactions might be relatively high. We want to provide the best user experience and we want to supply information that is displayed on the map as soon as possible, which would require an efficient search mechanism that can work with the unusual search key of BBox.

When we’re talking about searching by a key, search trees are a classic solution, and of course this case is no exception! But first we need to find a way to utilize such a tree and to figure out how a BBox can be used as a key. To solve this problem, we will use a quadtree.

Quadtree

A quadtree is a search tree in which each internal node has exactly four children. Why four, you ask? A simple search tree with two child nodes usually divides the search set by two on each level. A map is a two-dimensional structure consisting of latitude and longitude, on each level we need to divide each dimension into two pieces, which results in four quadrants. Each node of this tree would be a BBox too. The root node would be the BBox that contains the whole world, each child node would be a quadrant of the parent BBox.

Search with a quadtree.

As our main goal is to find markers to show on the map, each node of the tree will also contain some (usually a relatively small) amount of markers. Code representation of the simplest quadtree node will look like this:

class QuadTreeNode {
private Set<Marker> markers;
private BoundingBox bbox;
private QuadTreeNode[] children;
private final int maxEntryCount; …

}

Search

Let’s see how we can use the quadtree to find, for example, five landmarks that are contained in the BBox. Assume that each node of our tree contains 10 landmarks that are inside of the BBox which represents the current node. We apply a BFS and, as usual, we start with the root node:

1. Iterate over all markers in this node and check if any of those intersect the BBox, which is a search key. It’s very simple to do knowing the coordinates of the landmark, we just need to check if these coordinates are inside the BBox rectangle. If the condition
   _(SW lat <= Marker lat <= NE lat) && (SW lon <= Marker lon <= NE lo_n)
   is true, then the marker is inside the BBox. We consider markers on the edge of the BBox as intersecting.
2. Save markers which do intersect.
3. If we found five landmarks, our search is over.
4. If we need to find more landmarks, we check which child nodes intersect with the given search key BBox and save them in the queue for further check. It might be from one to four nodes.
5. Pick the next node from the queue and go to step 1.

In the code we can express search process in this way:

class QuadTree {
private QuadTreeNode root; …

public Set<Marker> findMarkers(BoundingBox bbox, int n) {

Set<Marker> foundEntries = new HashSet<>();
Queue<QuadTreeNode> nextNodesToCheck = new LinkedList<>(); nextNodesToCheck.add(root);

while (foundEntries.size() < n && !nextNodesToCheck.isEmpty()) {

int stillToFind = n - foundEntries.size();
QuadTreeNode nodeToCheck = nextNodesToCheck.poll(); List<Marker> currentEntries = nodeToCheck.getIntersectingEntries(bbox, stillToFind); foundEntries.addAll(currentEntries);

if (foundEntries.size() < n) {

nextNodesToCheck.addAll( nodeToCheck.getIntersectingChildren(bbox) ); } }

return foundEntries;

}

}

When we search for X markers, we search from top to bottom of the tree. It means that markers which are the closest to the root node will be found first. As we want to show our users the most relevant markers for their search, we need to regard the markers’ importance too.

The most important markers will be kept in the root node, you will see them if you decrease the map scale to the level when the whole world is visible. When the user zooms the map, they will see markers which are the most important for the visible area, even though they might not have been visible at the lower zoom level.

The importance of a marker is based on custom criteria which can be defined by business requirements. For example, we might base landmark markers’ importance on user reviews.

Edge Case

There’s also one interesting edge case we should mention. Imagine what the simplistic paper world map looks like: it’s a rectangle, the side edges of which are 180th meridian on the right and -180th meridian on the left. So imagine that the user searches for property here.

Bounding box intersects the “edges” of the map.

In this case, the SW longitude of the BBox will be larger than NE longitude. We need to regard this case when checking the marker inside the BBox rectangle. For example:

• Let’s say BBox coordinates are SW (160, 60), NE (-160, 70) . It’s a valid BBox.
• Marker with coordinates (-162, 62) won’t be considered as intersecting with BBox, as _SW lon_ > _Marker lon_.

One way to solve this problem is to split our BBox into 2 BBoxes if we know that SW lon > NE lon. We can split our BBox into two, using -180/180 meridian as a delimiter:

• BBox1: SW (160, 60), NE (180, 70)
• BBox2: SW (-180, 60), NE (-160, 70)

Our marker (-162, 62) will match BBox2 now.

Split BBox into two parts.

Quadtree building

Luckily, search trees do not materialize out of thin air, so that’s one of the reasons why software engineers still have their jobs. Let’s see how we can implement a quadtree that would satisfy our use case.

At first, our tree will only have a root node which is the entire world and it won’t contain any markers, it will be empty.

To populate the tree with markers, we need to iterate over all markers we have and insert every marker into the tree. Let’s say each node can contain up to 10 markers. Then, on each insertion we do:

1. Put the current marker into the set of markers of the current node.
2. If the size of markers set <= 10, we are done — the marker found its place. Iterate to the next marker.
3. If the size of markers set > 10, we need to get the least important marker of this node and push it to one of the children. (Remember: the closer the node to the root, the higher the importance of markers in the node).

• Create children of the current node if they weren’t created yet by splitting the BBox of the node into four sub-BBoxes.
• Search for the child BBox which intersects with the lowest-priority marker.
• Recursively put this marker into the child node (ie go to step 1 above with least important marker and child node as inputs).

To make sure that we can find the least important marker of the node, we can use PriorityQueue for the markers’ container. Markers in this set will be sorted by importance, so we can easily find the least important ones. It also means that on markers lookup we will find the most important markers of the node first.

This is what insert implementation might look like:

class QuadTreeNode {

private PriorityQueue<Marker> markers;

private BoundingBox bbox;
private QuadTreeNode[] children;
private final int maxEntryCount; …

public void insert(Marker marker) {

markers.add(marker);

if (markers.size() > maxEntryCount) {

if (children == null) { children = initializeChildren(); }

Marker entryToPassToChild = markers.poll();

List<QuadTreeNode> intersectingChildren = getIntersectingChildren(entryToPassToChild.getBoundingBox());

for (QuadTreeNode intersectingChild : intersectingChildren) {

intersectingChild.insert(entryToPassToChild); } } } …

}

We build the quadtree during the markers search service start-up and keep it in memory, refreshing it from time to time. Luckily, new cities are not established too often, likewise for airports, landmarks, etc. However, the importance of markers might change, so it’s advisable to periodically refresh the tree.

Conclusion

A quadtree is a relatively simple and (at the same time) powerful concept that perfectly solves markers search by BBox task. We also find this solution as highly scalable, because all we need to do to cope with the increasing load is to horizontally scale our service.

For example, a quadtree which stores more than 300k markers, (depending on the service load) lookup takes less than 1 to ~5.5ms for 99%, which is extremely fast for our purposes.

Lookup time in the quadtree which stores at least 300k markers

Thank you for reading this article and happy searching!

Acknowledgments: thank you Gregory Zak for the post idea and technical editing and Al-Jerreau Davids for the beautiful illustrations.