This blog post is part of a series of blog posts about the new OSM file format “OMA”. This is the sixth post. At the end of the article you’ll find links to the other blog entries.

 

The Oma file format uses a set of bounding boxes to sort the data geographically. The default set used by the converter consists of three grids.

 

The Default Grids

The first grid uses a mesh size of 1 degree in both directions between -45° and 45° latitude. Towards the poles the mesh size increases and finally the area around the poles is put into a single bounding box.

The grid looks like this:

The second grid uses a mesh size of 10 degrees in both directions between -80° and 80° latitude. It does not include the areas around the poles.

This grid looks like this:

The third grid isn’t really a grid, it’s just the whole world as one big bounding box.¹

 

Data Distribution in Bounding Boxes

In practice, data isn’t evenly distributed around the globe. Large areas are covered by oceans where there is little data distribution, while other regions are densely covered.

Using identical bounding boxes everywhere results in a few large chunks and many small chunks. It would be better to balance the sizes. This would speed up data access.

As an example, look at the distribution of nodes in Germany:

The Ruhr area (centre, left) contains about 10% of Germany’s nodes. And the area around Berlin contains another 8.6%, while for example the area just north of Berlin contains only 1.4%.

Let’s see, how this affects the search times: I choose the street Bienenweg in Neubrandenburg for comparison. The search for this street takes 2.5 seconds. Compare this with the 4.7 seconds needed for the Viktorstraße in Wuppertal.

 

Improving Bounding Boxes

But how do you get a better set of bounding boxes? I tried some ad hoc algorithms, but could not find out, what really makes a good set of bounding boxes. Probably, this question could make a good master thesis (or even a PhD thesis).

Anyway, I’d like to take a quick look at what I tried with data distribution: The first idea led to this set of bounding boxes:

The nodes are still not evenly distributed, but the differences are somewhat smaller. Searching for the Bienenweg now takes 2.8 seconds, while searching for Viktorstraße has been reduced to 2.9 seconds. On average, this seems to be at least some improvement.

I wondered if overlapping bounding boxes were a problem. So I tried the same thing with (almost) non-overlapping bounding boxes. The result looks like this:

The distribution looks similar to before. Unfortunately, the search times are worse: still 2.8 seconds for the Bienenweg, but 3.5 seconds for the Viktorstraße.

I also tried to increase the number of bounding boxes. It seems that this improves the results slightly. Unfortunately, the more bounding boxes you use, the more difficult it is to create the Oma files (crashes happen more often). I fear that the algorithm for sorting data into bounding boxes will have to be improved before further experiments can be made with this.

In one of the comments to an earlier post Geonick pointed out a discussion about geoparquet.² In that discussion, GitHub user jiayuasu claims that an algorithm called KDB tree is optimal for geoparquet. I have not had the time to look into this, but it might also be a good choice for OMA files as well.

To summarise: The question of what makes a good set of bounding boxes for OMA files is still open.

See also

• A New File Format for OSM Data
• Using the Oma Library
• Getting Files in OMA File Format
• The OMA File Format
• Dealing with Relations in Oma Files
• About main keys and values
• Summary, Outlook and a Real-Life Example

---

1. There is also a last chunk without any bounding box. This is used for anything without geometry. In the current implementation, it’s all the collections. ↩

2. Geoparquet is a an approach similar to OMA files, based on parquet files. ↩