A place graph is an abstract representation of human place knowledge, which models spatial references. A place graph can be used for various tasks that rely on reasoning and querying of the stored knowledge. In related work, place graphs were constructed from parsing natural language place descriptions using language processing techniques. In this research, we present an innovative approach to derive place graphs from information stored in spatial databases, with a demonstration using OpenStreetMap data. The approach provides a complementary way to generating place graphs from natural language descriptions.
descriptions can be di cult to collect for all desired environments, we seek alternative ways to generate place graphs.
As shown in Figure 2, a GIS, a place description, and a place graph are alternative representations of place knowledge. Most current approaches derive place graphs from NL descriptions and link places in the graphs to a GIS through georeferencing, as indicated by the three solid arrows. This research focuses on one of the missing links, as shown by the dashed arrows i.e., deriving place graphs from GIS. In the future, this can be combined with techniques to generate NL place descriptions from place graphs, thus resolving generating place descriptions from GIS. Completing the circle can smooth and simplify human-computer interaction in terms of translating place knowledge among di erent representations.
This research will investigate methods to derive place graphs from spatial databases (e.g., a GIS), where places are represented by features with either point, polyline, or polygon geometry. Accordingly, the hypothesis of this paper is that place graphs can be generated from information stored in spatial databases. The task is not trivial although computing qualitative spatial relationships (in the approach below, topological and directional ones) is straight-forward; the real challenge is to derive place graphs in a way that is similar to how people cognitively represent and communicate about place and their spatial relationships.
The rest of this paper is structured as follows: In Section 2 we review related work. In Section 3 our approach for deriving place graphs from spatial databases is presented. Section 4 explains the implementation and a case study using OpenStreetMap data, as well as a discussion of the obtained results. Section 5 concludes this work. 2
Place based research is an emerging eld in GIScience, and its importance has been widely acknowledged
Vasardani et al. (2013) focus on locative expressions | parts of NL descriptions that provide location
information of a place reference using a spatial relation to another place as landmark, e.g., \the lawn is in front
of the library". Each locative expression can be modeled by a triplet, and triplets can be extracted automatically
from place descriptions using existing NL parsers
This research is informed by human reasoning and communication about places and spatial relationships.
Richter et al. (2013) collected and analyzed NL place descriptions and found that people tend to describe places
in a hierarchical manner | a property that has also been observed in the organization of cognitive maps
Figure 3 shows the sequence of processing for creating place graphs from data stored in spatial databases. The proposed approach consists of three steps: (1) the extraction of a hierarchical structure based on containment relationships, (2) updating the hierarchy using a quad-tree strategy, and (3) the extraction of qualitative spatial relationships from quantitative data. Up till now, place graphs were the result of processed NL descriptions. The method suggested here is built upon cognitive studies in order to produce place graphs that resemble those from people's descriptions, i.e., not necessarily complete, but with relatively few, salient relationships between places. Compared to a complete, fully connected graph, the produced place graph is smaller in storage size (thus allowing for faster querying) and better captures the way people tend to describe places in a given environment. It is worth noting that using qualitative spatial reasoning non-stored relationships can be inferred. The rst step generates a hierarchical structure, represented by containment relationships between places. The hierarchy is created in two sequential steps using Algorithm 1. First, the containment relationships between each pair of polygons are checked, to form a containment network. Then, the containment network is pruned into a hierarchical structure. 3.2
After creating the hierarchical structure, a quad-tree strategy is applied to update the hierarchy by creating
intermediate nodes. The idea behind these intermediate nodes is cognitively motivated, based on the limited
human short-term memory span. As mentioned earlier, Miller (1956) argues that human capacity for processing
information is limited to approximately seven plus/minus two elements. Hence, if a node contains more than a
xed number of nodes ( ve in this research), the polygon associated with the node is divided into four polygons
based on its centroid, using a quad-tree. These polygons are linked to intermediate nodes that are placed between
a node and its contained nodes in the updated hierarchical structure. Then, the containment relationships
between the contained nodes and intermediate nodes are checked. Finally, the relationships will be pruned to
maintain the hierarchical structure. This process iteratively updates the hierarchy to a new version until each
node, including intermediate nodes, has no more than ve contained child nodes in the hierarchy. Algorithm 2
shows how the quad-tree strategy is used in updating the hierarchy.
Algorithm 1 generating the hierarchical structure
In this step, the updated hierarchical structure is used for further populating topological and directional
relationships. For each pair of sibling nodes in the hierarchy, their cardinal direction relationship, e.g., `north' or `east',
and topological relationship, e.g., `overlap' or `meet'
The proposed approach is implemented as a toolbox for creating place graphs using OpenStreetMap (OSM) data. Figure 4 shows the work ow of creating place graphs from OSM maps. First, by de ning the target area and using OSM API, the input data is gathered in XML format. Then, by parsing the XML le, polygons are extracted for further analysis. Next, the previously described approach is used to generate a place graph from the extracted polygons (in this research we do not consider places with polyline or point geometries). Finally, the results are stored in a graph-based place database. In this study, Neo4j Community version and Gephi are used as the graph-based database and graph visualizer, respectively. 4.2
Three experiments are designed to test the approach for creating place graphs in di erent map scales. Neighborhoods of Melbourne Cricket Ground, neighborhoods of Melbourne CBD, and the Greater Melbourne area are considered as geographic areas of interest. These experiments are conducted to show the e ectiveness of Algorithm 3 generating place graph the proposed approach for generating place graphs at di erent scales. The extracted polygons are processed to produce the place graphs. The geographic areas and the produced place graphs are shown in Figure 5.
The approach is compared to a baseline method that creates fully connected graphs. In a fully connected
graph, every pair of nodes is connected with two di erent edges, one for cardinal direction and the other for
topological relationships. Equation 1 allows to determine the number of edges in a fully connected graph. The
number of edges depends on how the graph is stored. Hence, equation 1 is held when topological and directional
relationships are stored separately. Figure 6 shows the number of edges and nodes for the proposed approach
and the fully connected graph method. The number of nodes in our method is slightly higher than the fully
connected graph due to the intermediate nodes resulting from the quad-tree strategy. However, the number
of edges is much lower in the proposed approach compared to the fully connected graph method. Hence, the
graphs resulting from our approach require comparatively less storage. It is worth noting that there is not any
information loss in the extracted place graph compared to the fully connected graph. This is because every
relationship in the fully connected graph either also exists in the extracted place graph, or can be inferred using
qualitative spatial reasoning. Moreover, the proposed method is based on cognitive constraints | the limitation
of short-term memory
numberOf Edges = numberOf N odes
(numberOf N odes
1)
(1)
This paper proposes an innovative approach to generate place graphs from spatial databases. In the place
graphs generated, containment relations are represented in a hierarchical structure, with topological and cardinal
direction relations captured between sibling nodes. The approach considers various cognitive factors of how
people think about and describe places, as well as their spatial relationships. It also considers the limitation
of human short-term memory and the hierarchical structure of places in human cognitive maps. It is the rst
attempt to derive place graphs from spatial databases. In future work, we plan to consider deriving qualitative
distance relationships, e.g., `near', from spatial databases, for example based on contrast set theory
The support by the Australian Research Council grant DP170100109 is acknowledged.