Searching OSM Planet with Context-Aware Spatial Relations
Daniel Bahrdt

Stefan Funke

Universität Stuttgart
Germany

Universität Stuttgart
Germany

Rick Gelhausen

Sabine Storandt

Universität Freiburg
Germany

ABSTRACT
We consider the problem of indexing the complete OpenStreetMap
planet data set (> 500GB of raw data) to support complex queries
involving both text search as well as context-aware spatial relations.
This requires (a) formalization of spatial relations like ’north of’,’between’, ’near’ depending on the context, and (b) the developmentof suitable data representations to integrate textual and spatial
information for efficient query performance.

CCS CONCEPTS• Information systems → Information retrieval;

KEYWORDS
OpenStreetMap, proximity queries, textual spatial search
ACM Reference Format:
Daniel Bahrdt, Stefan Funke, Rick Gelhausen, and Sabine Storandt. 2017.
Searching OSM Planet with Context-Aware Spatial Relations. In Proceedingsof 25th ACM SIGSPATIAL International Conference on Advances in Geographic
Information Systems (SIGSPATIAL’17). ACM, New York, NY, USA, 4 pages.
https://doi.org/10.1145/3139958.3140000

1

INTRODUCTION AND RELATED WORK

Directional relations are frequently used to select data in spatial
databases (SDB) and are fundamental to spatial data queries, analysis and reasoning [1, 6]. They are not only used widely in geographic
information systems, but also in areas like artificial intelligence[8], computer vision [9], and multimedia [12]. Consequently there
has been a significant amount of effort to determine directional
relations automatically.
A commonly used indicator for the directional relation between
two regions is the direction between their centroids [11], possibly
snapped to one of the 8 cardinal directions. As an advantage, thisindicator is symmetric and once the centroids are (pre)computed,
efficient to evaluate for a pair of regions. Yet, sometimes asymmetricanswers make more sense, which the popular direction-relation
matrix model [5] allows for. It subdivides the space around thebounding box of the reference region into nine direction tiles andclassifies other regions according to the cell of the subdivision they
Permission to make digital or hard copies of part or all of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
SIGSPATIAL’17, November 7–10, 2017, Los Angeles Area, CA, USA© 2017 Copyright held by the owner/author(s).
ACM ISBN 978-1-4503-5490-5/17/11.
https://doi.org/10.1145/3139958.3140000

Universität Würzburg
Germany
lie in. [3] introduce a splitting line model to decide on the relationof two geometric entities. The goal of all these approaches is tocompute a directional indicator between two given regions, whereas
for our concrete application of a SDB we want to determine regions
fulfilling a certain directional relation. Moreover we also need toderive the extent of a region for the matches, not only a direction.
[10] and [7] propose non-trivial spatial queries and respective
implementations in the context of a SDB system. In [10] nearest
neighbors and range search primitives, amongst others, are implemented both for Euclidean and network connectivity constraints.
For example, for the nearest neighbor primitive, they employ geometric search structures and a network traversal to collect matching
results. [7] on the other hand design rather complex surrounder
queries with the main application domain being in location based
services. The reported experiments are of rather small scale (a database of a few thousand elements). While these approaches yieldexact nearest neighbors or report exactly all entities in a given
range, we want to emphasize that they are hardly feasible for large
data-sets. Queries like “All McDonald’s branches world-wide which
do not have a Burger King branch within 2km radius” would haveto be executed on each McDonald’s branch world-wide (more than
30,000).

Our contribution
This work is based on the freely-available OpenStreetMap (OSM)
data set. In [2] we have proposed an efficient framework to accessall entities of the OSM planet data set with their implicit and explicit
informations, supporting substring search on the key-value tags
as well as all common set operations like intersection, union, ordifference. This work builds upon this framework, extending it
to allow for the efficient support of adaptive spatial relations. We
provide actual semantics of spatial relations based on context andtheir implementation in our framework. Experiments as well as a
web-based demonstrator on www.oscar-web.de show the efficiencyof our approach even on a planet scale with hundreds of millions
of elements.

2

OSM CELL ARRANGEMENTS

The key concept behind OSCAR is a so-called cell arrangement of
OSM regions. Consider a set of simple polygons P, each corresponding to an OSM region. Each single polygon P ∈ P divides the plane
into two regions, the interior of the polygon and the exterior. The set
P naturally induces a subdivision of the plane into cells, we call thisthe cell arrangement A = A(P) of P. All points within a single cellc ∈ A have the property that they behave identically with respect

SIGSPATIAL’17, November 7–10, 2017, Los Angeles Area, CA, USA

1

3
2

D. Bahrdt et al.

10

1

11
12
4

9

2

4

3

9

5
6

7
8

12

7

8

11
10
6
5

Figure 1: Left: Cell arrangement – Points in the gray cell 11
have the property of being contained in the brown, purple,
orange, and red region, but not in the others. Right: Corresponding inclusion-DAG.
to containment in the set of polygons, in particular inheriting thesame information associated with the respective OSM regions.
The efficiency of OSCAR is based on the fact that the numberof cells in our cell arrangement A is considerably smaller than the
total number of items. The basic idea for our query data structureis then as follows:(1) create cell arrangement A induced by OSM regions(2) associate with each cell c ∈ A all tags of OSM regions
containing c(3) build search structure on ’tagged’ cells and individuallytagged nodes
So for a single query string such as Stuttgart our data structure returns all cells which have an associated tag with substring ’Stuttgart’
as well as all individual nodes whose tag set contains the substring’Stuttgart’. If several search terms are specified as part of a complex
search query, the set operations take place at the cell level as longas possible. Only at the very end, a conversion to items takes place.
The inclusion-relation of the regions creating the cell arrangement induces a natural clustering which we use for presenting theresult and calculation of candidate regions and items. See Figure 1,
left, for a cell arrangement with 12 cells induced by 8 regions. In
Figure 1, right, we see the induced Directed Acyclic Graph – we callit Inclusion-DAG. There is a directed edge (v, w ) from a cell/region
node v to a region node w in the DAG, if and only if the cell/regionv is fully contained in the region w and there exists no other regionw ′ ⊂ w in which it is fully contained. For a cell the set of regions it
is contained in can be easily determined via breadth- or depth-firstsearch in the inclusion-DAG starting from the respective node.

Refining the OSCAR Cell Complex
For implementations of Adaptive Spatial Relations, it is desirable tohave a cell arrangement with well-shaped cells. This is typically not
given for the cell arrangement induced by the OSM regions, e.g.,
many cells have very irregular shapes. Hence we perform a refinement step to make cells of the arrangement look nice, both in termsof shape, topology, and complexity. We first compute a Constrained
Delaunay Triangulation (CDT)[4] of the original arrangement. Keeping these triangles as cells would increase the complexity of thesearch structure too much, so in a second step we merge triangles
to form larger, yet simple and nice cells. See Figure 2 for a schematicof the refinement process. While the refinement process increases
the complexity of the arrangement, the blow-up is still limited andallows for the easy implementation of adaptive spatial relations.

Figure 2: Schematic of the refinement process. Left: Original
Cell Arrangement. Center: Constrained Delaunay Triangulation thereof. Right: After merging of triangles.

3

ADAPTIVE SPATIAL RELATIONS VIA A
REFINED CELL COMPLEX (OSCAR-RCC)

In the following we define adaptive spatial relations through polygons of interest. Inspecting all items within such a polygon is particularly costly. Yet, the cell-centered representation and processingin OSCAR strongly suggests also a cell-based implementation ofadaptive spatial relations. In particular larger regions of interest
will benefit considerably from cell-based processing.
For generality let us assume a given decomposition of the map
into tiles/cells and a data structure D which for a given query Q:• computes all tiles containing a match for Q• for a given tile C known to contain matches for Q, outputs
all matches
Note that depending on the implementation of D, computing theset of tiles containing at least one match might be much cheaper
than outputting all matches. OSCAR provides such a tiling, but thefollowing scheme applies to any cell- or tile-based representation.
For some query Q (e.g., searching for the string Burger King)the assumed data structure D can compute all tiles containing atleast one match, and for each tile also output the actual matches, if
necessary (at higher cost).
Neighborhood. The probably most natural spatial relation is aboutproximity, but there are considerable differences in terms of semantics depending on the objects referenced. The extent of the reference
object (the Eiffel Tower or the city of Paris) typically also determines
the extent of the region of interest. To keep things simple, we compute a minimum enclosing rectangle for the reference object and let
d be the extent of the smaller dimension (breadth or width). Then
we define as neighborhood of a reference object all locations whichhave distance at most max(d, 500m) to the reference object. We use
the maximum of d and 500m to also define neighborhoods of 0- or
1-dimensional entities (e.g., a mailbox is typically not considered tohave any real ’extent’).
A simple cell-based approximation of the neighborhood semantics as defined before distinguishes between two cases. If the extent
of the reference object is small, we simply define as relevant neighborhood the cell containing the reference object and neighboring
cells within the desired distance. This often leads to a larger regionof interest than intended, but a precise pruning with respect todistance can be part of a post-processing step. For larger reference
objects, we use the occupied cells to estimate the extent and thendetermine the respective cells.
Cardinal Directions. A user issuing a query like “hotels northof the Empire State Building” probably expects accommodations

Searching OSM Planet with Context-Aware Spatial Relations

SIGSPATIAL’17, November 7–10, 2017, Los Angeles Area, CA, USA
between the bounding boxes to the next nodes of the reference object on the bounding box border in the respective direction (whichmust be well-defined).
We can use this polygon to simply mark all cells between thereference objects, see Figure 3.
Path Corridors. When looking for ’hotels along the route from
Stuttgart to Berlin’ one typically refers to a much smaller area thanin ’hotels between Stuttgart and Berlin’. So given a (precomputed)
path we define as the area of interest as all locations with distanceof at most 1 kilometer from the route. In our implementation we
simply mark all cells traversed by the route, see Figure 3.
We want to note, though, that for all discussed relations othertoolboxes than the ones described here (or with different parameterchoices) could be plugged in our framework as well.

Figure 3: Relations Nearby/SpatialJoin, NorthOf, Between
and AlongPath.
within a distance of 500m north of the Empire State Building. For
larger entities, a larger region is of interest – “hotels north of Paris”
probably refers to a region up to a distance of 20km north of Paris.
We formalize this as follows: For 0-dimensional reference objects
a simple triangle in the cardinal direction is used. As we cannot infer the size of the region of interest from the extent of the reference
object and use a triangle of height 500m. If additional context information is available, the size of this triangle can easily be adjusted.
For 1-dimensional reference objects, we first determine the northernmost point of the polygonal line as well as the midpoint of thebounding box. We then construct a temporary point with latitude of
the northernmost point and longitude of the center of the boundingbox. We then pass this point to the cardinal direction function tocreate an intermediate triangle. Finally, the region of interest is theconvex hull of this triangle together with the polygonal line.
For 2-dimensional reference objects we first create a boundingbox and an isosceles trapezoid of twice the height of the boundingbox, the base is equal to the horizontal axis of symmetry of thebounding box and a parallel opposing side of double that length.
We can compute the result of a query “hotels north of Paris” basedon cells by first determining the cells/tiles that are (fully or partially)
covered by the city limits of Paris (via a search for “Paris”). We thenapproximate the extent of Paris by inspection of the respective tiles(computationally inexpensive, as there are only few tiles). Using
this approximate extent we mark tiles north of these tiles, see Figure
3, for a schematic illustration.
Betweenness. As for cardinal directions, the region referred toby a ’between’ relation depends on the reference regions and inparticular their distance apart.
To compute polygons bounding the region of interest for the
betweenness relation we again distinguish between the dimension of the reference objects. If we need the region between two
0-dimensional reference objects, we construct a diamond shapewith two opposing corners being the two reference objects and awidth of half the distance between the two reference objects. In allother cases we construct the convex hull of the bounding boxes ofboth reference objects. We use the area of the convex hull without
the bounding boxes as region of interest, as well the part of thebounding boxes that is formed by connecting the convex hull edges

Spatial Joins. A considerably more complex query arises in thefollowing scenario: Assume we are looking for residential areas
where both kindergarten and school are nearby. Querying for“kindergarten with school within 500m” should yield all kindergarten
for which there exists a school not too far away. The neighborhoods of such kindergartens then presumably constitute desirable
residential areas. The challenge here is that there are more than
300k tagged kindergartens in the OSM data set.
How could we use our query structure D together with thetiling to efficiently compute the result set? We first search for school
resulting in a set of tiles containing schools and mark neighboring tiles depending on our notion of ’nearby’. Then we search forkindergarten but only outputting the respective matches in tiles
that were marked previously.
Some queries have much higher nesting depths, e.g., “supermarkets which have an ATM, a pharmacy, and a car repair shop nearby”.

4

EXPERIMENTAL EVALUATIONIn the following we present some benchmarks to outline the performance of OSCAR. The hardware specifications of the test environments together with information about the data set as well as
an overview of resource usage of the pre-processing stage and theimpact of the cell refinement processes are listed in Table 1.
We have picked a number of representative queries with increasing complexity and analyzed their query processing. Figure
4 lists the queries, their sizes and computation time. It also shows
the impact of loading data from disk which usually increases thequery time by a factor of 10. The cell time is the time it takes to
do all the set operations. The subgraph time is the time needed
to compute the subgraph of the region hierarchy. The former isof course higher for queries with many and large set operations- the latter takes longer for results with many different regions.
This is especially true for all single query terms since these justdo a look-up in our text search data structure. Queries 1,2,13 and14 mostly select single items and as a consequence the numberof cells does not differ very much from the number of items. The
creation of the subgraph of the Inclusion-DAG does of course takelonger since the items are scattered around the world. Queries 3,7
and 9 select a mixture of items and cells with paris selecting many
full-match cells of Paris. Query 4 has large intermediate resultswith a small result mostly reduced to items in Paris. Query 5 adds

SIGSPATIAL’17, November 7–10, 2017, Los Angeles Area, CA, USA
Data set statistics# Items
500M
2.78M# Cells
Database
64.5 GB
Text search 33.4 GB
40.4 GB
Index

Cell size
Avg. unrefined353
189
Avg. refined
Max unrefined 2.13M
Max refined
578k

CPU
RAM
Disk

D. Bahrdt et al.

Hardware statistics
Query
Preprocessing
2 x Intel E5-2630v2 2 x Intel E5-2650v4
384 GiB
768 GiB
2 SSD raid0
3 HDD raid0

Pre-processing ressource usage
db
ts
15:14
34:17
Time [h:m]Ram [GiB]
17.8 GB 39.8 GB
Load avg. [%]
1516
298

Table 1: From left to right: Information about the dataset with all tags stored, prefix search for tags, substring search forimportant tags. Impact of the cell refinement. Statistics of our test environments. Resource usage to compute the data base(db) and the text search (ts) with 32 GiB allocated for out-of-memory algorithms.
the :north-of operation to query 4 returning some full-match cells
in Paris. Adding @tourism:attraction to query 5 further reduces
the number of items while not increasing the computation much
more since the former query mostly consists of full-match cells.
Queries 10 and 11 use the region query to query for Munich andGermany. The results of these are fed to the between operator to
get the rather large region between Munich and Frankfurt/Main.
This operation takes quite some time which is mostly due to the notyet fully optimized polygon-query. Finally, query 15 uses the celldilation operator turning partial-matched cells into fully-matchedcells and intersecting these with another set of partial-match cells.
Moverover, the query times can be improved by using multiple
threads and our implementation in fact parallelizes the executionof the set operations. Consider for example the query @highway@building @amenity where each operand selects a large amount ofpartial-match cells. Computing the set operations should in theory
scale linearly in the number of processors with a speed-up of 1,
however, in practice we get an efficiency ratio of 0.5 to 0.7:
Threads [1]
1
2
4
8
12
16
Time [ms] 2165 1450 830 470 330 290
Efficiency
10.74 0.65 0.58 0.55 0.47

5

No.
1
2
3
4
5
6

Cells
79.9k
54.8k
41.4k
1
8
1

Items
259k
205k
4.23M
2
3.43k
3

7
8
9
10
11
12
13
14
15

1.16k
14
714
261k
824
3.90k
63.7k
208k
48.5k

491k
15.8k
209k
50.7M
487k
946k
175k
836k
505k

Query
@tourism:hotel@tourism:attraction
paris
eiffel tour paris @tourism:attraction:north-of (eiffel tour paris @tourism:attraction)@tourism:hotel :north-of (eiffel tour paris@tourism:attraction)
Munich:north-of MunichFrankfurt am Main
#Germany#Germany #Munich("Frankfurt am Main") < - > (#Munich #Germany)@amenity:kindergarten@amenity:school(%@amenity:kindergarten @amenity:school) +(@amenity:kindergarten %@amenity:school)

CONCLUSIONSIn this paper we have shown that it is possible to develop efficient
data representations and algorithms that allow for complex string
search with spatial relation queries even for massive data sets like
OSM planet. The key ingredient for efficiency is the cell-centeredprocessing within the data structure with well-shaped cells thatfacilitate the implementation of adaptive spatial relations. Our webbased demonstrator can answer queries on a global scale whicheven involve adaptive spatial relations not available in common
search engines like Google/Bing Maps. Future work includes thehandling of dynamic update of the underlying data set as well as
more parallelization to reduce the time for precomputation.
Acknowledgements This work was in part supported by theDeutsche Forschungsgemeinschaft (DFG) within the priority program 1894: Volunteered Geographic Information: Interpretation,
Visualization and Social Computing.

REFERENCES[1] Alia I. Abdelmoty and Chris B. Jones. 1997. Towards Maintaining Consistencyof Spatial Databases. In Proc. 6th Int. Conference on Information and Knowledge
Management (CIKM ’97).
[2] Daniel Bahrdt and Stefan Funke. 2015. OSCAR: OpenStreetMap Planet at Your
Fingertips via OSm Cell ARrangements. In WISE (1) (LNCS), Vol. 9418. Springer.
[3] Kevin Buchin, Vincent Kusters, Bettina Speckmann, Frank Staals, and Bogdan
Vasilescu. 2011. A Splitting Line Model for Directional Relations. In Proc. 19th
ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems.
[4] L. P. Chew. 1987. Constrained Delaunay Triangulations. In Proc. 3rd Annual
Symposium on Computational Geometry (SCG ’87).

Figure 4: Top: Result sizes for various queries issued on theplanet data set. Bottom: The same queries with hot cache(red) and cold cache (blue) timings for cell (left) and subgraph (right) computation. Note that the total time of all
queries except one is well below the 1 second mark.
[5] Roop Kishor Goyal. 2000. Similarity Assessment for Cardinal Directions Between
Extended Spatial Objects. Ph.D. Dissertation. University of Maine. AAI9972143.
[6] Roop K. Goyal and Max J. Egenhofer. 2001. Similarity of Cardinal Directions. In
Proc. 7th Int. Symp. on Advances in Spatial and Temporal Databases (SSTD ’01).
[7] Xi Guo, Baihua Zheng, Yoshiharu Ishikawa, and Yunjun Gao. 2011. Directionbased Surrounder Queries for Mobile Recommendations. The VLDB Journal 20, 5(Oct. 2011).
[8] A. Klippel, C. Dewey, M. Knauff, K.-F. Richter, D. R. Montello, C. Freksa, and E.-A.
Loeliger. 2004. Direction Concepts in Wayfinding Assistance Systems. In Proc.
Workshop on Artificial Intelligence in Mobile Systems (AIMS’04) (SFB 378).
[9] Pascal Matsakis and Laurent Wendling. 1999. A New Way to Represent theRelative Position Between Areal Objects. IEEE Trans. Pattern Anal. Mach. Intell.
21, 7 (July 1999).
[10] Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. 2003. Query
Processing in Spatial Network Databases. In Proc. 29th Int. Conference on Very
Large Data Bases - Vol.29 (VLDB ’03).
[11] D. J. Peuquet and Ci-Xiang Zhang. 1987. An Algorithm to Determine the Directional Relationship Between Arbitrarily-shaped Polygons in the Plane. Pattern
Recogn. 20, 1 (Jan. 1987).
[12] Stephen S.-T. Yau and Qing-Long Zhang. 2004. On Completeness of Reasoning
about Planar Spatial Relationships in Pictorial Retrieval Systems. Commun. Inf.
Syst. 4, 3 (2004).