=Paper=
{{Paper
|id=None
|storemode=property
|title=Towards Modeling Locations as Poly-Hierarchies
|pdfUrl=https://ceur-ws.org/Vol-850/paper_hoepfner.pdf
|volume=Vol-850
|dblpUrl=https://dblp.org/rec/conf/gvd/HopfnerS12
}}
==Towards Modeling Locations as Poly-Hierarchies==
https://ceur-ws.org/Vol-850/paper_hoepfner.pdf
Towards Modeling Locations as Poly-Hierarchies
Hagen Höpfner and Maximilian Schirmer
Bauhaus-Universität Weimar
Media Department / Mobile Media Group
Bauhausstraße 11, 99423 Weimar, Germany
hoepfner@acm.org, maximilian.schirmer@uni-weimar.de
Keywords the Bauhausstraße 11 in Weimar, Germany and the assumption be-
Location, Location Modeling, Poly-Hierarchies, Enclave Problem, ing that such information is usually more meaningful to the user.
Multiple Belonging Hence, we should use a service that maps positions to locations.
However, location-based applications differ in their required preci-
sion [10]. While the name of the city in which a user and/or a de-
ABSTRACT vice is currently located might be appropriate for handling location-
Location models are formal descriptions of locations (i. e., named aware data processing in an event information system, a navigation
sets of geographical positions) as well as of semantic relationships system demands for exact coordinates, or street names at least.
among locations. There exist various location models that vary in The aforementioned example also illustrates another issue that is
the considered location information, their level of detail, the kind common for locations. In many cases, semantic locations form hi-
of modelled relations and the used formal representation. In fact, erarchical structures. For example, in a hierarchical location model,
more complex location models cover more aspects required for im- earth is divided into continents, continents into countries, coun-
plementing location-aware or location-dependent systems, but also tries into states, states into cities, cities into streets and streets into
require more complex algorithms. As each application domain re- street numbers, and so on. However, modelling locations as mono-
quires only a limited set of features, limiting a model to those fea- hierarchies oversimplifies the reality and does not support multiple
tures helps to improve system performance. In this paper, we dis- belongings. While, e. g., Weimar is part of Germany, Germany of
cuss a novel location model called location poly-hierarchies that Europe, etc., Istanbul is part of Turkey, but also of Europe and Asia.
models the belonging of one location to one ore more other loca- Please note, we focus on geographic belongs-to-relationships (sub-
tions. Furthermore, we present an approach for creating location set and overlap) rather than on geopolitical ones. Location hierar-
poly-hierarchies from a given set of locations. chies benefit from the fact that determining low-level location in-
formation determines upper levels, too. Location poly-hierarchies
cure the mentioned model incompleteness while keeping the bene-
1. INTRODUCTION AND MOTIVATION fit of a “fast” lookup of the correct path within the poly-hierarchy
In February 2004, the authors of [5] stated: “The widespread de- (cf., [11]). The research question addressed in this paper is:
ployment of sensing technologies will make location-aware appli-
How can one algorithmically create location poly-hierarchies
cations part of every day life.” Nowadays, location-awareness has
from a given set of locations?
become a key feature in a broad range of mobile information sys-
tems. Navigation systems, social network apps, tourist information The remainder of this paper is structured as follows: Section 2
systems, event information systems, shop finders and many more surveys related work. Section 3 introduces the concept of loca-
heavily rely on position data of their users. Consequently, almost tion poly-hierarchies. Section 4 presents our approach for creating
all modern smartphones supply positioning techniques. However, them. Section 5 discusses implementation aspects. Section 6 sum-
a position determination, e.g, by the use of the Global Positioning marises the paper and gives an outlook on future research.
System (GPS), enables a smartphone to calculate coordinates and
accuracy, only. As, from the perspective of the user, a seman-
tic location is more understandable than coordinate information,
2. RELATED WORK
location-aware or location-based systems map position information There has been a lot of active research on suitable models and
to semantically meaningful locations. For example, the GPS coor- representations for location data in the field of location models.
dinates 50.972 797 and 11.329 18 are precise but likely not mean- Location models are a core component of location-based applica-
ingful for humans. They belong to the building which is placed in tions. They represent not only location information, but also spatial
(or even spatio-temporal [7]) relationships in the data, help to ex-
press 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 lo-
cation models that has been developed in recent years of active re-
search. A key factor for distinguishing and characterising location
models is their way of representing spatial relationships. Accord-
ing to [1], they can be categorised into set-based, hierarchical, and
24th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. graph-based models. Hybrid models that combine several aspects
Copyright is held by the author/owner(s). exist as well. Figure 1 presents an overview of the three main lo-
cation model concepts. In the illustrated examples, the set-based return only single points. However, we can interpret Tanja’s current
approach is the least expressive one, as it only models the fact GPS coordinate as a set of positions of cardinality 1. As discussed
that there are two distinct locations within a set of locations, and in Section 1 it is a common understanding that locations have a hi-
a set of coordinates is assigned to each location. The hierarchical erarchic nature. The train station is located within a city, the city is
model adds containment information, and the graph-based model located in a state, the state within a country, and so on. Using this
adds connectedness and distance in the form of edge weights. subset-based location interpretation, LTanja ⊂ Lts ⊂ LWeimar ⊂
LThuringia ⊂ LGermany ⊂ LEurope ⊂ LEarth represents the loca-
tion of Tanja as path in a location mono-hierarchy.
Location A World Location A However, there exist various real-world issues that require a poly-
(1,2)
(1,2) (1,3) (2,3) (2,4) (1,2) hierarchical representation of locations. For example, Istanbul as
50
25 the capital of Turkey, belongs to the continents Europe and Asia.
60
Hence, LIstanbul 6⊂ LEurope and LIstanbul 6⊂ LAsia hold. The
Location B Location C
Location B Location A Location B same issue holds for Russia, which is located in Europe and in
(2,4) (1,3)
(1,2) (1,3) (2,3) (2,4)
Asia, too. Another problem results from enclaves. Kaliningrad,
(2,3)
25 100 e.g., is part of Russia, but this information is insufficient to decide
Location D Location E
whether Kaliningrad is part of Europe or part of Asia. The solution
Location c
(2,3)
10 (2,5)
for these problems is the use of set overlaps in combination with
(1,2)
containment relationships that form a location poly-hierarchy.
(a) (b) (c)
earth
earth
Figure 1: Examples for set-based (a), hierarchical (b), and
graph-based (c) location models. The edge weights in the
graph-based model represent distance information.
Europe
Asia
Europe
Asia
Hierarchical location models as a special case of set-based mod-
Turkey
Russia
els represent containment relationships between different levels of
the model and are widely used as basis for location-based applica-
tions [6, 2, 4]. Hierarchical models cannot represent distance infor-
mation or directly encode proximity, but they have great advantages Istanbul
Kaliningrad
in traversal and for containment queries. They are also very close to
the common human understanding of locations. As already stated (a) (b)
in Section 1, the widely acknowledged segmentation of locations
into administrative regions (country, state, city, street, and so on) is Figure 2: Examples for the Poly-hierarchical nature of loca-
also a hierarchical model that heavily relies on containment infor- tions: Istanbul (a), and Kaliningrad (b).
mation. On a city level, a lot of implicit information can be derived
through the top-level relationship to a state or country (e.g., admin-
istrative language, local cuisine, prevalent religions). Figure 2 illustrates the simplified poly-hierarchies for Istanbul
and Kaliningrad. From the definition of poly-hierarchies, we know
3. LOCATION POLY-HIERARCHIES that they can be represented by a directed acyclic graph LP H =
(V, E). Each node v ∈ V is a location and each directed edge e =
The authors of [12] define the term “location” as follows: “Lo- (v1 , v2 ) with v1 , v2 ∈ V represents that the child node v2 belongs
cation of an object or a person is its geographical position on the (semantically) to the parent node v1 . Each location poly-hierarchy
earth with respect to a reference point.” From our point of view, has an unique root node vr ∈ V with ¬∃vx ∈ V |(vx , vr ), because
this definition is too restrictive, because geographic positions are the entire coordinate system is closed in case of locations (all con-
points within a reference system. In contrast to a point, a location siderable positions are elements of the set of all positions on earth).
has a spatial extent. Another definition is given in [3]: “Geographic Finally, for each leaf node vl ∈ V that must not have any child
location is the text description of an area in a special confine on the node ¬∃vx ∈ V |(vl , vx ) holds.
earth’s surface.”. From a more theoretical point of view, an area is From an implementation point of view, each node in the poly-
a set of geographical positions. So, we use a set-oriented definition: hierarchy graph has the structure (n, P, C) where n is the name of
A location is a named set of geographical positions on earth with the location Ln , P is a set of edges to the parent nodes and C is
respect to a reference point. a set of edges to child nodes. The root node r = (earth, P, C) is
For example, in a two-dimensional coordinate system1 , the loca- the only node in LP H for which P = ∅ ∧ C 6= ∅ must hold. For
tion of a building, lets say a train station (ts), is given as set Lts = leaf nodes P 6= ∅ ∧ C = ∅, and for inner nodes P 6= ∅ ∧ C 6= ∅
{(x1 , y1 ), . . . , (xn , yn )}, where each position (point) (xi , yi ), 1 ≤ hold. For the concept described in the remainder of this paper, it
i ≤ n belongs to the train station building’s area. We discuss the is required to know the level of each node within this graph. The
calculation of the point set in Section 5.1. Consequently, we can level level(m) of a node m is defined as the number of nodes on
characterise the location of an object or a person as a relationship the longest direct path from r to m, plus one. As illustrated in
between sets. A person, lets say Tanja, is located at the train station Figure 2(b), level(Russia) = 2 and level(Kaliningrad) = 3.
if LTanja ⊂ Lts holds. Recent positioning technologies like GPS In a location mono-hierarchy each edge between a parent node
1
For simplification purposes, we use two-dimensional coordinates and a child node represents the fact that all points of the location
in this paper. However, the formalism can easily be adapted to three that corresponds to the child node are also elements of the location
dimensions. that corresponds to the parent node. However, as discussed before,
it is not sufficient to use subset relationships only. The semantics
of edges in the poly-hierarchical graph representation is as follows. Algorithm 1 Creating a location poly-hierarchy from a location set
Given a (child) node c = (nc , Pc , Cc ) the following relations hold:
• For each parent node p ∈ V referenced in Pc having level(p) Input: L = {L1 , . . . , Lk } // location set
with ¬∃p0 ∈ Pc |p0 6= p ∧ level(p) = level(p0 ) the edge
(p, c) ∈ E represents the subset relationship Lnc ⊂ Lnp . Output: LP H = (V, E) // location poly-hierarchy
• For each (parent) node p ∈ V referenced in Pc having level(p) 01 def naive_lph_create(L):
with ∃p0 ∈ Pc |p0 6= p ∧ level(p) = level(p0 ) the edge 02 V ⊂ = ∅ // init of the node set for subset relations
(p, c) ∈ E represents the overlapping relationship Lnc ∩ 03 V ∩ = ∅ // init of the node set for overlap relations
Lnp 6= ∅. 04 E ⊂ = ∅ // init the edge set for subset relations
05 E ∩ = ∅ // init the edge set for overlap relations
In other words this means that per hierarchy level each edge be-
06 LV = ∅ // init set of already analysed locations
tween a single parent node and the child node means an subset rela-
— S TEP 1: FINDING OVERLAP AND SUBSET RELATIONSHIPS —
tionship. If a child node has more than only one parent node in the
07 for each Lname1 ∈ L do
same level, then those links represent an overlap relationship. Fur-
08 for each Lname2 ∈ L − {Lname1 } − LV do
thermore, we know that the in the latter case, due to the directed
09 if Lname2 ⊂ Lname1 then
nature of the edges, the child node must be a subset of the union
10 V ⊂ = V ⊂ ∪ {name1 , name2 }
of the respective parent nodes (i. e., the conjunction of the overlap
11 E ⊂ = E ⊂ ∪ {(name1 , name2 )}
relationships per level holds).
12 fi
13 elif Lname1 ⊂ Lname2 then
earth
earth
14 V ⊂ = V ⊂ ∪ {name1 , name2 }
level=0
level=0
15 E ⊂ = E ⊂ ∪ {(name2 , name1 )}
16 fi
Europe
Asia
Europe
Asia
17 elif Lname2 ∩ Lname1 6= ∅ then
level=1
level=1
level=1
level=1
18 V ∩ = V ∩ ∪ {name1 , name2 }
19 E ∩ = E ∩ ∪ {(name2 , name1 )}
20 E ∩ = E ∩ ∪ {(name1 , name2 )}
Turkey
Russia
level=2
level=2
21 fi
22 done
23 LV = LV ∪ {Lname1 }
Istanbul
Kaliningrad
24 done
level=3
level=3
25 if E ⊂ == ∅ then return(FALSE) fi // no root node found
(a) (b) — S TEP 2: CLEANING UP E ∩ ( REMOVING LOOPS ) —
26 for each name1 ∈ V ∩ do
Figure 3: Examples for the semantics of edges in LP H, solid 27 Lt = ∅; E t = ∅ // temporary location and edge sets
lines represent subset relationships and dashed lines overlaps. 28 for each e ∈ V ∩ do
29 if e == (name1 , x) then
30 Lt = Lt ∪ {Lx }; E t = E t ∪ {(name1 , x)}
Figure 3 illustrates the link semantics for the Istanbul and the 31 fi
Kaliningrad examples. As one can see in Subfigure 3(a), LIstanbul ⊂ 32 done
LTurkey as Turkey is the only parent node of Istanbul at level two. 33 if Lname1 ⊂ Lt then E ∩ = E ∩ − E t fi
Since Istanbul has two parent nodes on level one (i. e., Europe and 34 done
Asia), these links represent the overlaps LIstanbul ∩ LEurope 6= ∅ and — S TEP 3: CLEANING UP E ⊂ ( TRANSITIVITY ) —
LIstanbul ∩ LAsia 6= ∅. The facts that (in addition) LTurkey ∩ LEurope 6= 35 for each name1 ∈ V ⊂ do
∅ ∧ LTurkey ∩ LAsia 6= ∅ holds, also implies LIstanbul ⊂ LEurope ∩ LAsia . 36 if ∃x, y ∈ V ⊂ ↔ {(x, name1 ), (y, x)} ∩ E ⊂ 6= ∅ then
We could use this “transitive” conclusion in a similar way for the 37 V t = {z|z 6= Sx ∧ (z, name1 ) ∈ V ⊂ }
Kaliningrad example, too. However, as show in Subfigure 3(b) it 38 E ⊂ = E ⊂ − z∈V t {(z, name1 )}
would reduce the expressivity of this LP H. Kaliningrad is only 39 fi
part of Europe but not of Asia. Hence, the Europe node is the only 40 V t = {x|(x, name1 ) ∈ E ⊂ } // all parents of name1
parent node of the Kaliningrad node at level one. 41 for each x ∈ V t do
42 V c = {y|(x,Sy) ∈ E ⊂ ∧ y ∈ V t − {name1 }}
43 if Lname1 ⊂ c∈V c Lc then
4. LPH CREATION 44 E ⊂ = E ⊂ − {(x, name1 )}
As discussed in Section 3 one could create an LP H using over- 45 fi
lap relationships only. We already pointed out that, in order to be 46 done
as expressive as possible, an LP H must use as many subset rela- 47 done
tionships as possible. Algorithm 1 creates the LP H from a given — S TEP 4: MERGING E ∩ WITH E ⊂ AND V ∩ WITH V ⊂ —
set L = {L1 , . . . , Lk } of locations. For illustration purposes, we 48 V = V ∩ ∪ V ⊂; E = E∩ ∪ E⊂
assume that names of locations are unique. However, one could 49 return(V , E)
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 re-
lationships and one (V ∩ , E ∩ ) for all (additional) overlap relation- The same procedure removes the edges Istanbul→Europe and
ships. Figure 4 illustrates these subgraphs for the Istanbul and the Istanbul→Asia.
Kaliningrad examples. Obviously, step 1 might generate redundant
a4er
a4er
a4er
edges (cf., Figure 4(c)) earth→Russia→Kaliningrad and checking
(1)
Europe,
(2)
Asia
checking
(3)
Turkey
checking
(4)
Istanbul
earth→Kaliningrad) or (later on) unnecessary edges (cf., Fig-
Europe
Asia
Europe
Asia
Europe
Asia
ure 4(a) earth→Turkey). Furthermore, it generates loops in the
overlap subgraph as overlap relations have a symmetric nature (cf., Turkey
Turkey
Turkey
Figure 4(b) and Figure 4(d)). We illustrated those needless edges
using dotted arrows. Istanbul
Istanbul
Istanbul
Figure 6: Step 2 for the Istanbul example.
earth
Step 3 (lines 35-47) cleans up the subset subgraph using the tran-
Europe
Asia
Europe
Asia
sitivity 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 nec-
Turkey
Turkey
essary 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
Istanbul
Istanbul
be reached through the parents. In our examples, this removes
(a) V ⊂ , E ⊂ (b) V ∩ , E ∩ the edges earth→Istanbul and earth→Kaliningrad. A
second optimisation (lines 40-46) checks whether a node is con-
tained in the union of its sibling locations. If this is the case,
earth
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).
Europe
Asia
Europe
Asia
earth
earth
Russia
Russia
Europe
Asia
Europe
Asia
Kaliningrad
(c) V ⊂ , E ⊂ (d) V ∩ , E ∩ Turkey
Russia
Figure 4: Intermediate graph(s) after step 1; (a,b) Istanbul,
(c,d) Kaliningrad. Istanbul
Kaliningrad
(a) Istanbul (b) Kaliningrad
Step 2 (lines 26-34) of the algorithm cleans up the overlap sub-
graph, i. e., it breaks the loops. Therefore, each node of this sub-
Figure 7: Intermediate graphs (V ⊂ , E ⊂ ) after step 3.
graph 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. Joining the subset subgraph(s) with the overlap subgraph, as it is
checking
Europe
checking
Asia
checking
Russia
done in the final step 4 (line 48), results in a connected LP H. The
Europe
Asia
Europe
Asia
Europe
Asia
fragmentation, that might have happened in step 2, is cured as the
removed edges resulted from an overlap relationship between the
Russia
Russia
Russia
involved nodes. For our examples, Algorithm 1 therefore creates
the location poly-hierarchies shown in Figure 3.
Figure 5: Step 2 for the Kaliningrad example; bold arrows
highlight the edges analysed for currently handled node that
Limiting factors
is marked gray. Algorithm 1 requires a complete and closed set of locations. With-
out the location Asia, the Kaliningrad example graph would loose
the LP H properties discussed in Section 3 as removing the Asia
Figure 6 illustrates step 2 for the Istanbul example. After check- node also removes the edge Asia→Russia. Without this edge,
ing the nodes for Europe and Asia, the node for Turkey is checked. the relationship Europe→Russia would be semantically wrongly
So far, it has the child nodes Europe and Asia. As all points of interpreted as subset relationship. In fact, Algorithm 1 could be
Turkey belong to Europe or Asia, both must not be represented adapted in order to recognise this case through topologic sorting
by child nodes of the Turkey node. So, these edges are removed. as the condition in line 33 would evaluate to false. Consequently,
E ∩ would still contain loops after step 2. Furthermore, the algo- poly-hierarchy from a given (closed and complete) set of locations.
rithm does not support differently named locations with equal sets We discussed limitations of the algorithm and also pointed out po-
of position points (i. e., La ⊆ Lb ∧ Lb ⊆ La holds). Step 1 would tential solutions to handle them. Finally, we discussed some issues
missinterpret this case as overlap relationship. Consequently, step 2 that need to be considered for the implementation of our strategy.
would nondeterministically remove one of the edges. A solution to However, there are many open issues that lead to future research
this problem would be a cleanup phase that unifies those locations directions. First of all we plan to evaluate the algorithm with real
before starting Algorithm 1. world data. We expect that the algorithm works properly, but we
are aware of the huge amount of data that needs to be processed.
5. IMPLEMENTATION ASPECTS Hence, we will have to optimise the algorithm in order to avoid
unnecessary (database) operations. Furthermore, we will research
As the “towards” in the title of this paper denotes, the presented whether it would be better to explicitly keep the information about
results are subject to ongoing research. We were not able to fin- the type of the relationships. This extended graph model would, of
ish the import of the evaluation database before the deadline. In course, ease the interpretability of the final location poly-hierarchy,
fact, importing the OpenStreetMap database containing data about but it would also increase the complexity of the model.
Europe (http://download.geofabrik.de/osm) using an
slightly adapted version of the osm2postgresql_05rc4.sh
script, which can be downloaded from http://sourceforge.
7. REFERENCES
[1] C. Becker and F. Dürr. On Location Models for Ubiquitous
net/projects/osm2postgresql, is still in progress. So
Computing. Personal and Ubiquitous Computing,
far it took more than two weeks (PosgreSQL 9.1 [9] with Post-
9(1):20–31, 2005.
GIS 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 imple- [2] M. Beigl, T. Zimmer, and C. Decker. A Location Model for
mentation issues that we find worthwhile to be discussed. Communicating and Processing of Context. Personal
Ubiquitous Computing, 6:341–357, Jan. 2002.
5.1 Point sets of locations [3] Z. Dongqing, L. Zhiping, and Z. Xiguang. Location and its
The formal definition of locations and location poly-hierarchies Semantics in Location-Based Services. Geo-spatial
as discussed in Section 3 is based on set theory. From a theoret- Information Science, 10(2):145–150, June 2007.
ical point of view, those sets are infinite. A common approach to [4] F. Dürr and K. Rothermel. On a Location Model for
handle this infinity problem is to decrease the precision of set el- Fine-Grained Geocast. In A. K. Dey, A. Schmidt, and J. F.
ements through quantisation. However, it would not be useful or McCarthy, editors, UbiComp ’03 Proceedings, volume 2864
even possible to physically store (materialise) all points of all loca- of LNCS, pages 18–35, Berlin / Heidelberg, 2003. Springer.
tions. Hence, for the implementation of our approach we decided [5] M. Hazas, J. Scott, and J. Krumm. Location-Aware
to use a polygon-based representation of locations, where a set of Computing Comes of Age. IEEE Computer, 37(2):95–97,
polygons describes the boundaries of the locations. In principal, all Feb. 2004.
points that are inside of one of these polygons belong to the loca- [6] C. Jiang and P. Steenkiste. A Hybrid Location Model with a
tion. The OpenStreetMap data model provides an additional multi- Computable Location Identifier for Ubiquitous Computing.
polygon relation (cf., http://wiki.openstreetmap.org/ In G. Borriello and L. E. Holmquist, editors, Ubicomp ’02
wiki/Multipolygon_relation) for representing more com- Proceedings, volume 2498 of LNCS, pages 246–263,
plex areas. It allows, e. g., for areas within a location that do not London, UK, 2002. Springer.
belong to this particular location. Hence, from an implementation [7] T. Kauppinen, R. Henriksson, R. Sinkkilä, R. Lindroos,
point of view, a location is represented as a database view. The J. Väätäinen, and E. Hyvönen. Ontology-based
location name corresponds to the name of the view and the point Disambiguation of Spatiotemporal Locations. In IRSW ’08
set is defined by a database query resulting in the location outline Proceedings. CEUR-WS.org, 2008.
(multi)polygon. [8] OSGeo Project. PostGIS 1.5.1 Manual.
http://postgis.refractions.net/download/
5.2 Set operations postgis-1.5.1.pdf.
Interpreting locations as (multi)polygons necessitates a differ- [9] The PostgreSQL Global Development Group. PostgreSQL
ent interpretation of the used set operations, too. As discussed in 9.1.3 Documentation. http://www.postgresql.org/
Section 4, Algorithm 1 has to check subset and set overlap rela- docs/9.1/static/index.html.
tionships. Remember, a location La contains another location Lb [10] B. N. Schilit, A. LaMarca, G. Borriello, W. G. Griswold,
if and only if Lb ⊂ La holds. Hence, La must contain all points D. McDonald, E. Lazowska, A. Balachandran, J. Hong, and
(xb , yb ) ∈ Lb . For the polygon-based locations, the subset relation V. Iverson. Challenge: ubiquitous location-aware computing
means that the (multi)polygon describing La must cover those of and the “place lab” initiative. In WMASH ’03 Proceedings,
Lb completely. Similarly, an overlap relation of two locations im- pages 29–35, New York, NY, USA, 2003. ACM.
plies that the boundary (multi)polygons overlap (and vice versa). [11] M. Schirmer and H. Höpfner. Towards Using Location
Most geographical information system extensions, such as Post- Poly-Hierarchies for Energy-Efficient Continuous Location
GIS, provide the corresponding operators (cf. [8]). Determination. In GvD ’12 Proceeding. CEUR-WS.org,
2012. forthcoming.
6. SUMMARY AND OUTLOOK [12] A. Y. Seydim, M. H. Dunham, and V. Kumar. Location
We presented a novel approach to model (geographical) relation- dependent query processing. In MobiDE ’01 Proceedings,
ships among locations. We extended the effective, but not complete pages 47–53, New York, NY, USA, 2001. ACM.
location hierarchy approach in order to support enclaves and over- [13] J. Ye, L. Coyle, S. Dobson, and P. Nixon. A Unified
lapping locations. We formally introduced the new location poly- Semantics Space Model. In LoCA ’07 Proceedings, LNCS,
hierarchy model and presented an algorithm for creating a location pages 103–120, Berlin / Heidelberg, 2007. Springer.