Towards Modeling Locations as Poly-Hierarchies

Abstract

Location models are formal descriptions of locations (i. e., named sets of geographical positions) as well as of semantic relationships among locations. There exist various location models that vary in the considered location information, their level of detail, the kind of modelled relations and the used formal representation. In fact, more complex location models cover more aspects required for implementing location-aware or location-dependent systems, but also require more complex algorithms. As each application domain requires only a limited set of features, limiting a model to those features helps to improve system performance. In this paper, we discuss a novel location model called location poly-hierarchies that models the belonging of one location to one ore more other locations. Furthermore, we present an approach for creating location poly-hierarchies from a given set of locations.

INTRODUCTION AND MOTIVATION

In February 2004, the authors of [ 5 ] stated: “The widespread deployment of sensing technologies will make location-aware applications part of every day life.” Nowadays, location-awareness has become a key feature in a broad range of mobile information systems. Navigation systems, social network apps, tourist information systems, event information systems, shop finders and many more heavily rely on position data of their users. Consequently, almost all modern smartphones supply positioning techniques. However, a position determination, e.g, by the use of the Global Positioning System (GPS), enables a smartphone to calculate coordinates and accuracy, only. As, from the perspective of the user, a semantic location is more understandable than coordinate information, location-aware or location-based systems map position information to semantically meaningful locations. For example, the GPS coordinates 50:972 797 and 11:329 18 are precise but likely not meaningful for humans. They belong to the building which is placed in the Bauhausstraße 11 in Weimar, Germany and the assumption being that such information is usually more meaningful to the user. Hence, we should use a service that maps positions to locations. However, location-based applications differ in their required precision [ 10 ]. While the name of the city in which a user and/or a device is currently located might be appropriate for handling locationaware data processing in an event information system, a navigation system demands for exact coordinates, or street names at least.

The aforementioned example also illustrates another issue that is common for locations. In many cases, semantic locations form hierarchical structures. For example, in a hierarchical location model, earth is divided into continents, continents into countries, countries into states, states into cities, cities into streets and streets into street numbers, and so on. However, modelling locations as monohierarchies oversimplifies the reality and does not support multiple belongings. While, e. g., Weimar is part of Germany, Germany of Europe, etc., Istanbul is part of Turkey, but also of Europe and Asia. Please note, we focus on geographic belongs-to-relationships (subset and overlap) rather than on geopolitical ones. Location hierarchies benefit from the fact that determining low-level location information determines upper levels, too. Location poly-hierarchies cure the mentioned model incompleteness while keeping the benefit of a “fast” lookup of the correct path within the poly-hierarchy (cf., [ 11 ]). The research question addressed in this paper is: How can one algorithmically create location poly-hierarchies from a given set of locations?

The remainder of this paper is structured as follows: Section 2 surveys related work. Section 3 introduces the concept of location poly-hierarchies. Section 4 presents our approach for creating them. Section 5 discusses implementation aspects. Section 6 summarises the paper and gives an outlook on future research. 2.

RELATED WORK

There has been a lot of active research on suitable models and representations for location data in the field of location models. Location models are a core component of location-based applications. They represent not only location information, but also spatial (or even spatio-temporal [ 7 ]) relationships in the data, help to express relative locations, proximity, and allow users to determine containment of locations or connectedness of relationships.

The authors of [ 13 ] present in great detail the broad variety of location models that has been developed in recent years of active research. A key factor for distinguishing and characterising location models is their way of representing spatial relationships. According to [ 1 ], they can be categorised into set-based, hierarchical, and graph-based models. Hybrid models that combine several aspects exist as well. Figure 1 presents an overview of the three main loreturn only single points. However, we can interpret Tanja’s current GPS coordinate as a set of positions of cardinality 1. As discussed in Section 1 it is a common understanding that locations have a hierarchic nature. The train station is located within a city, the city is located in a state, the state within a country, and so on. Using this subset-based location interpretation, LTanja Lts LWeimar LThuringia LGermany LEurope LEarth represents the location of Tanja as path in a location mono-hierarchy.

However, there exist various real-world issues that require a polyhierarchical representation of locations. For example, Istanbul as the capital of Turkey, belongs to the continents Europe and Asia. Hence, LIstanbul 6 LEurope and LIstanbul 6 LAsia hold. The same issue holds for Russia, which is located in Europe and in Asia, too. Another problem results from enclaves. Kaliningrad, e.g., is part of Russia, but this information is insufficient to decide whether Kaliningrad is part of Europe or part of Asia. The solution for these problems is the use of set overlaps in combination with containment relationships that form a location poly-hierarchy. cation model concepts. In the illustrated examples, the set-based approach is the least expressive one, as it only models the fact that there are two distinct locations within a set of locations, and a set of coordinates is assigned to each location. The hierarchical model adds containment information, and the graph-based model adds connectedness and distance in the form of edge weights.

Hierarchical location models as a special case of set-based models represent containment relationships between different levels of the model and are widely used as basis for location-based applications [ 6, 2, 4 ]. Hierarchical models cannot represent distance information or directly encode proximity, but they have great advantages in traversal and for containment queries. They are also very close to the common human understanding of locations. As already stated in Section 1, the widely acknowledged segmentation of locations into administrative regions (country, state, city, street, and so on) is also a hierarchical model that heavily relies on containment information. On a city level, a lot of implicit information can be derived through the top-level relationship to a state or country (e.g., administrative language, local cuisine, prevalent religions).

LOCATION POLY-HIERARCHIES

The authors of [ 12 ] define the term “location” as follows: “Location of an object or a person is its geographical position on the earth with respect to a reference point.” From our point of view, this definition is too restrictive, because geographic positions are points within a reference system. In contrast to a point, a location has a spatial extent. Another definition is given in [ 3 ]: “Geographic location is the text description of an area in a special confine on the earth’s surface.”. From a more theoretical point of view, an area is a set of geographical positions. So, we use a set-oriented definition: A location is a named set of geographical positions on earth with respect to a reference point.

For example, in a two-dimensional coordinate system1, the location of a building, lets say a train station (ts), is given as set Lts = f(x1; y1); : : : ; (xn; yn)g, where each position (point) (xi; yi); 1 i n belongs to the train station building’s area. We discuss the calculation of the point set in Section 5.1. Consequently, we can characterise the location of an object or a person as a relationship between sets. A person, lets say Tanja, is located at the train station if LTanja Lts holds. Recent positioning technologies like GPS 1For simplification purposes, we use two-dimensional coordinates in this paper. However, the formalism can easily be adapted to three dimensions.

Figure 2 illustrates the simplified poly-hierarchies for Istanbul and Kaliningrad. From the definition of poly-hierarchies, we know that they can be represented by a directed acyclic graph LP H = (V; E). Each node v 2 V is a location and each directed edge e = (v1; v2) with v1; v2 2 V represents that the child node v2 belongs (semantically) to the parent node v1. Each location poly-hierarchy has an unique root node vr 2 V with :9vx 2 V j(vx; vr), because the entire coordinate system is closed in case of locations (all considerable positions are elements of the set of all positions on earth). Finally, for each leaf node vl 2 V that must not have any child node :9vx 2 V j(vl; vx) holds.

From an implementation point of view, each node in the polyhierarchy graph has the structure (n; P; C) where n is the name of the location Ln, P is a set of edges to the parent nodes and C is a set of edges to child nodes. The root node r = (earth; P; C) is the only node in LP H for which P = ; ^ C 6= ; must hold. For leaf nodes P 6= ; ^ C = ;, and for inner nodes P 6= ; ^ C 6= ; hold. For the concept described in the remainder of this paper, it is required to know the level of each node within this graph. The level level(m) of a node m is defined as the number of nodes on the longest direct path from r to m, plus one. As illustrated in Figure 2(b), level(Russia) = 2 and level(Kaliningrad) = 3.

In a location mono-hierarchy each edge between a parent node and a child node represents the fact that all points of the location that corresponds to the child node are also elements of the location that corresponds to the parent node. However, as discussed before, For each parent node p 2 V referenced in Pc having level(p) with :9p0 2 Pcjp0 6= p ^ level(p) = level(p0) the edge (p; c) 2 E represents the subset relationship Lnc Lnp .

For each (parent) node p 2 V referenced in Pc having level(p) with 9p0 2 Pcjp0 6= p ^ level(p) = level(p0) the edge (p; c) 2 E represents the overlapping relationship Lnc \ In other words this means that per hierarchy level each edge between a single parent node and the child node means an subset relationship. If a child node has more than only one parent node in the same level, then those links represent an overlap relationship. Furthermore, we know that the in the latter case, due to the directed nature of the edges, the child node must be a subset of the union of the respective parent nodes (i. e., the conjunction of the overlap relationships per level holds).

Europe   level=1  

Asia   level=1  

Europe   level=1  

Asia   level=1  

Figure 3 illustrates the link semantics for the Istanbul and the Kaliningrad examples. As one can see in Subfigure 3(a), LIstanbul LTurkey as Turkey is the only parent node of Istanbul at level two. Since Istanbul has two parent nodes on level one (i. e., Europe and Asia), these links represent the overlaps LIstanbul \ LEurope 6= ; and LIstanbul \ LAsia 6= ;. The facts that (in addition) LTurkey \ LEurope 6= ; ^ LTurkey \ LAsia 6= ; holds, also implies LIstanbul LEurope \ LAsia. We could use this “transitive” conclusion in a similar way for the Kaliningrad example, too. However, as show in Subfigure 3(b) it would reduce the expressivity of this LP H. Kaliningrad is only part of Europe but not of Asia. Hence, the Europe node is the only parent node of the Kaliningrad node at level one.

4. LPH CREATION

As discussed in Section 3 one could create an LP H using overlap relationships only. We already pointed out that, in order to be as expressive as possible, an LP H must use as many subset relationships as possible. Algorithm 1 creates the LP H from a given set L = fL1; : : : ; Lkg of locations. For illustration purposes, we assume that names of locations are unique. However, one could also use location IDs instead of the names to guarantee uniqueness.

Our algorithm uses four main steps. In the first step (lines 7-24), it creates two subgraphs, one (V ; E ) containing all subset reAlgorithm 1 Creating a location poly-hierarchy from a location set

Input:

L = fL1; : : : ; Lkg // location set

Output:

LP H = (V; E)

// location poly-hierarchy 01 def naive_lph_create(L): 02 V = ; // init of the node set for subset relations 03 V \ = ; // init of the node set for overlap relations 04 E = ; // init the edge set for subset relations 05 E\ = ; // init the edge set for overlap relations 06 LV = ; // init set of already analysed locations — STEP 1: FINDING OVERLAP AND SUBSET RELATIONSHIPS — 07 for each Lname1 2 L do 08 for each Lname2 2 L fLname1 g LV do 09 if Lname2 Lname1 then 10 V = V [ fname1; name2g 11 E = E [ f(name1; name2)g 12 fi 13 elif Lname1 Lname2 then 14 V = V [ fname1; name2g 15 E = E [ f(name2; name1)g 16 fi 17 elif Lname2 \ Lname1 6= ; then 18 V \ = V \ [ fname1; name2g 19 E\ = E\ [ f(name2; name1)g 20 E\ = E\ [ f(name1; name2)g 21 fi 22 done 23 LV = LV [ fLname1 g 24 done 25 if E == ; then return(FALSE) fi // no root node found — STEP 2: CLEANING UP E\ (REMOVING LOOPS) — 26 for each name1 2 V \ do 27 Lt = ;; Et = ; // temporary location and edge sets 28 for each e 2 V \ do 29 if e == (name1; x) then 30 Lt = Lt [ fLxg; Et = Et [ f(name1; x)g 31 fi 32 done 33 if Lname1 Lt then E\ = E\ Et fi 34 done — STEP 3: CLEANING UP E (TRANSITIVITY) — 35 for each name1 2 V do 36 if 9x; y 2 V $ f(x; name1); (y; x)g \ E 37 V t = fzjz 6= x ^ (z; name1) 2 V g 38 E = E Sz2V t f(z; name1)g 39 fi 40 V t = fxj(x; name1) 2 E g // all parents of name1 41 for each x 2 V t do 42 V c = fyj(x; y) 2 E ^ y 2 V t fname1gg 43 if Lname1 Sc2V c Lc then 44 E = E f(x; name1)g 45 fi 46 done 47 done — STEP 4: MERGING E\ WITH E AND V \ WITH V — 48 V = V \ [ V ; E = E\ [ E 49 return(V , E) 6= ; then lationships and one (V \; E\) for all (additional) overlap relationships. Figure 4 illustrates these subgraphs for the Istanbul and the Kaliningrad examples. Obviously, step 1 might generate redundant edges (cf., Figure 4(c)) earth!Russia!Kaliningrad and earth!Kaliningrad) or (later on) unnecessary edges (cf., Figure 4(a) earth!Turkey). Furthermore, it generates loops in the overlap subgraph as overlap relations have a symmetric nature (cf., Figure 4(b) and Figure 4(d)). We illustrated those needless edges using dotted arrows.

Step 2 (lines 26-34) of the algorithm cleans up the overlap subgraph, i. e., it breaks the loops. Therefore, each node of this subgraph is analysed (cf. Figure 5). If the location represented by a node is a subset of the union of all its direct child nodes, then we remove the outgoing edges.

checking  Europe   Europe  Asia 

Russia 

checking  Asia   Europe  Asia 

Russia 

checking  Russia   Europe  Asia 

Russia  The same procedure removes the edges Istanbul!Europe and Istanbul!Asia.

Step 3 (lines 35-47) cleans up the subset subgraph using the transitivity property of subset relationships. In contrast to many graph optimisation approaches, we do not aim for reducing the number of edges in general, but for finding the minimal number of edges necessary for representing correct semantics (cf. Section 3). For the first optimisation (lines 36-39), we first calculate for each node the set of parent nodes having parent nodes themselves. Afterwards, we remove all direct edges from grandparents nodes as they can be reached through the parents. In our examples, this removes the edges earth!Istanbul and earth!Kaliningrad. A second optimisation (lines 40-46) checks whether a node is contained in the union of its sibling locations. If this is the case, we can remove the edge from the parent node (in our examples earth!Turkey and earth!Russia), even if this fragments the subgraph (cf. Figure 7).

Joining the subset subgraph(s) with the overlap subgraph, as it is done in the final step 4 (line 48), results in a connected LP H. The fragmentation, that might have happened in step 2, is cured as the removed edges resulted from an overlap relationship between the involved nodes. For our examples, Algorithm 1 therefore creates the location poly-hierarchies shown in Figure 3.

Limiting factors Algorithm 1 requires a complete and closed set of locations. Without the location Asia, the Kaliningrad example graph would loose the LP H properties discussed in Section 3 as removing the Asia node also removes the edge Asia!Russia. Without this edge, the relationship Europe!Russia would be semantically wrongly interpreted as subset relationship. In fact, Algorithm 1 could be adapted in order to recognise this case through topologic sorting as the condition in line 33 would evaluate to false. Consequently, E\ would still contain loops after step 2. Furthermore, the algorithm does not support differently named locations with equal sets of position points (i. e., La Lb ^ Lb La holds). Step 1 would missinterpret this case as overlap relationship. Consequently, step 2 would nondeterministically remove one of the edges. A solution to this problem would be a cleanup phase that unifies those locations before starting Algorithm 1.

IMPLEMENTATION ASPECTS

As the “towards” in the title of this paper denotes, the presented results are subject to ongoing research. We were not able to finish the import of the evaluation database before the deadline. In fact, importing the OpenStreetMap database containing data about Europe (http://download.geofabrik.de/osm) using an slightly adapted version of the osm2postgresql_05rc4.sh script, which can be downloaded from http://sourceforge. net/projects/osm2postgresql, is still in progress. So far it took more than two weeks (PosgreSQL 9.1 [ 9 ] with PostGIS 1.5.1 [ 8 ] running on an iMac Intel Core 2 Duo 3:06 GHz, 4 GB 1067 MHz RAM, OS X 10.7.3). However, there are certain implementation issues that we find worthwhile to be discussed. 5.1

Point sets of locations

The formal definition of locations and location poly-hierarchies as discussed in Section 3 is based on set theory. From a theoretical point of view, those sets are infinite. A common approach to handle this infinity problem is to decrease the precision of set elements through quantisation. However, it would not be useful or even possible to physically store (materialise) all points of all locations. Hence, for the implementation of our approach we decided to use a polygon-based representation of locations, where a set of polygons describes the boundaries of the locations. In principal, all points that are inside of one of these polygons belong to the location. The OpenStreetMap data model provides an additional multipolygon relation (cf., http://wiki.openstreetmap.org/ wiki/Multipolygon_relation) for representing more complex areas. It allows, e. g., for areas within a location that do not belong to this particular location. Hence, from an implementation point of view, a location is represented as a database view. The location name corresponds to the name of the view and the point set is defined by a database query resulting in the location outline (multi)polygon. 5.2

Set operations

Interpreting locations as (multi)polygons necessitates a different interpretation of the used set operations, too. As discussed in Section 4, Algorithm 1 has to check subset and set overlap relationships. Remember, a location La contains another location Lb if and only if Lb La holds. Hence, La must contain all points (xb; yb) 2 Lb. For the polygon-based locations, the subset relation means that the (multi)polygon describing La must cover those of Lb completely. Similarly, an overlap relation of two locations implies that the boundary (multi)polygons overlap (and vice versa). Most geographical information system extensions, such as PostGIS, provide the corresponding operators (cf. [ 8 ]).

SUMMARY AND OUTLOOK

We presented a novel approach to model (geographical) relationships among locations. We extended the effective, but not complete location hierarchy approach in order to support enclaves and overlapping locations. We formally introduced the new location polyhierarchy model and presented an algorithm for creating a location poly-hierarchy from a given (closed and complete) set of locations. We discussed limitations of the algorithm and also pointed out potential solutions to handle them. Finally, we discussed some issues that need to be considered for the implementation of our strategy. However, there are many open issues that lead to future research directions. First of all we plan to evaluate the algorithm with real world data. We expect that the algorithm works properly, but we are aware of the huge amount of data that needs to be processed. Hence, we will have to optimise the algorithm in order to avoid unnecessary (database) operations. Furthermore, we will research whether it would be better to explicitly keep the information about the type of the relationships. This extended graph model would, of course, ease the interpretability of the final location poly-hierarchy, but it would also increase the complexity of the model.

References

[1] C. Becker and F. Dürr . On Location Models for Ubiquitous Computing. Personal and Ubiquitous Computing , 9 ( 1 ): 20 - 31 , 2005 .

[2] M. Beigl , T. Zimmer , and C. Decker . A Location Model for Communicating and Processing of Context. Personal Ubiquitous Computing , 6 : 341 - 357 , Jan. 2002 .

[3] Z. Dongqing , L. Zhiping , and Z. Xiguang . Location and its Semantics in Location-Based Services . Geo-spatial Information Science , 10 ( 2 ): 145 - 150 , June 2007 .

[4] F. Dürr and K. Rothermel . On a Location Model for Fine-Grained Geocast . In A. K. Dey , A. Schmidt , and J. F. McCarthy , editors, UbiComp '03 Proceedings , volume 2864 of LNCS , pages 18 - 35 , Berlin / Heidelberg, 2003 . Springer.

[5] M. Hazas , J. Scott , and J. Krumm . Location-Aware Computing Comes of Age . IEEE Computer, 37 ( 2 ): 95 - 97 , Feb. 2004 .

[6] C. Jiang and P. Steenkiste . A Hybrid Location Model with a Computable Location Identifier for Ubiquitous Computing . In G. Borriello and L. E. Holmquist, editors, Ubicomp '02 Proceedings , volume 2498 of LNCS , pages 246 - 263 , London, UK, 2002 . Springer.

[7] T. Kauppinen , R. Henriksson , R. Sinkkilä , R. Lindroos , J. Väätäinen , and E. Hyvönen . Ontology-based Disambiguation of Spatiotemporal Locations . In IRSW '08 Proceedings. CEUR-WS.org , 2008 .

[8] OSGeo Project . PostGIS 1.5.1 Manual . http://postgis.refractions.net/download/ postgis-1.5.1.pdf.

[9] The PostgreSQL Global Development Group. PostgreSQL 9.1.3 Documentation . http://www.postgresql. org/ docs/9 .1/static/index.html.

[10] B. N. Schilit , A. LaMarca, G. Borriello, W. G. Griswold , D. McDonald , E. Lazowska , A. Balachandran , J. Hong , and V. Iverson . Challenge: ubiquitous location-aware computing and the “place lab” initiative . In WMASH '03 Proceedings , pages 29 - 35 , New York, NY, USA, 2003 . ACM.

[11] M. Schirmer and H. Höpfner . Towards Using Location Poly-Hierarchies for Energy-Efficient Continuous Location Determination . In GvD '12 Proceeding. CEUR-WS.org , 2012 . forthcoming.

[12] A. Y. Seydim , M. H. Dunham , and V. Kumar . Location dependent query processing . In MobiDE '01 Proceedings , pages 47 - 53 , New York, NY, USA, 2001 . ACM.

[13] J. Ye , L. Coyle , S. Dobson , and P. Nixon . A Unified Semantics Space Model . In LoCA '07 Proceedings, LNCS , pages 103 - 120 , Berlin / Heidelberg, 2007 . Springer.