{'fraction_non_alphanumeric': 0.02527020855533567, 'fraction_numerical': 0.003272948698432029, 'mean_word_length': 4.831779849090102, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hierarchical spatial reasoning and case of way-finding

Human beings use hierarchies to simplify their conceptual models of reality and to perform reasoning more efficiently. Hierarchical structures are conceptually imposed on space and allow performance of complex tasks in very large contexts easily. Hierarchical spatial reasoning is an important method for solving spatial problems. This paper briefly discusses the definition and frame of hierarchical spatial reasoning and its application to way-finding of road networks.


Introduction
The noted cognitive linguist Langacker once said, "Hierarchy plays a very important role in human being's spatial cognition." Human being's conceptual model of reality demonstrates significant hierarchical spatial characteristics. During their mental processing, they usually do not consider the whole problem with all its trivialities but tend to divide the problem into several parts or simplify it while neglecting its trivialities first and then go deep into these trivialities hierarchically. This kind of technique, solving the problem from the general to the details, or from its whole to the partial, is the so-called hierarchical method. Hierarchical spatial reasoning applies hierarchy in a spatial situation, which can help human beings grasp the essences of complex Geo-Science theories from the surface to the deep with different spatial scales. It can be used not only in simple spatial computation, such as the area of region and spatial relations [1] , but also in the complex tasks like planning of routes, shortest path [2][3][4][5] , allocation of re-sources etc. One model of its use is way-finding, which means to find the shortest distance between two nodes in road networks. Until now, the non-hierarchical way-finding methods, which are widely used in GIS, including the Dijkstrs's and A* algorithm , evolved from the field of computer science and operational research and only take the topology characteristics of abstract network into account while neglecting the concrete spatial characteristics of those road networks. Thus, the performance of this way-finding method declines with the enlargement of the network's size. Under this situation, it is very necessary to find out a new way for road networks' calculation. In this paper, we will pay more attention to its application to way-finding of road networks on the basis of a brief discussion on the definition and framework of hierarchical spatial reasoning.

Basics of general hierarchy theory
Hierarchy is one of the most common forms of constructing and organizing complex systems. It di-vides the whole system into smaller ones, and this division can continue recursively as long as it is meaningful. Spatial information science is complex in nature, and its research is mainly around the generalization of space. We often use our own experience or cognition to understand spatial concepts, such as spatial objects and the relations between them.
There are two types of spatial hierarchies. One is called top-down, which means to define the framework of the concept first and then to thin it step by step: divide a N-dimension space into several neighboring spatial objects, which are of the same dimension, e.g. the hierarchical structure of quad-tree; The other way is called the bottom-up, in which the conceptual models of each partial are defined and then those models are collected together to form the conception of the whole item: choose one subset from the whole to form the neighboring hierarchy of higher level, e.g. graph -sub-graph structure. According to the methods of hierarchy, we can also divide space into functional hierarchies and structural hierarchies. The functional spatial hierarchy is based on the task-subtask model and is mainly used in artificial space process. In the functional hierarchies of one task, each subtask stands for one hierarchy of structure. Different sub-tasks usually need different types of objects, which form a structure in different ways, and each hierarchy has its own spatial operation on its object, and that's why each hierarchy has its own ontology. While the structural spatial hierarchy divides the space into the hierarchies of point, line and surface. The spatial objects form different hierarchies, each hierarchy shares the same structure, the same object type; and the relations between objects also share the same tube, same operation, i.e. the same ontology. Each hierarchy is distinct from each other through its resolution and details with its resolution increasing gradually from highest to lowest. The division of the spatial objects, which are of the same hierarchical structure, is on the basis of different hierarchies and districts. All hierarchies and sub-districts are of the same structure, same patterns, and same operating relations between objects and their operations, only get related with the same tasks of different hierarchies and have nothing to do with different tasks. The hierarchy of the road networks in way-finding is just a kind of structural hierarchy.

Hierarchical spatial reasoning
Hierarchical spatial reasoning (HSR) is a method for solving spatial problems, which uses hierarchy to infer spatial information and draw conclusions [2] . Human being's conceptual model of reality demonstrates a very significant feature of spatial hierarchy; each hierarchy embodies necessary information for solving some special problems. The hierarchy, as an abstraction mechanism, usually unburdens human beings' cognitive load through two ways: one is to lower the complexity of the question domain by decreasing the question space; the other is to divide the problem into small parts and then to solve it. Both of these two methods can let the solution become much more efficient, because processing only the necessary information definitely can save more time. The HSR is suitable for human being's cognitive model: selecting proper partial hierarchy and doing calculation, then evaluating the quality of the outcome and comparing it to the data that are needed by the process. If the quality of the outcome is enough for decision-making, the processing should be stopped. If the quality of the outcome is not sufficient, the continuing analysis of the next hierarchy will be carried out.
To define HSR, we need the following factors.
(1) The hierarchical structure, which includes a hierarchy structure and a method for transforming the data space into the equivalent hierarchy space, i.e. transforming the non-hierarchical structure into equivalent hierarchical structure .The criteria for successful transformation is allocating each object to every hierarchy and establishing the relations between the objects of different hierarchies.
(2) Rules. Defining a series of rules on how to carry out reasoning on hierarchical structure, i.e. when and how to carry out the transformation between different hierarchies, and how to transform the partial results of each hierarchy into final results.
(3) The comparison of the results. Compare the results in terms of their accuracy and the degree of improvement.
HSR is a kind of spatial reasoning which uses the hierarchy to sub-divide the task or space. The application of HSR gives attention to the spatial structural hierarchies of the road network. Spatial structural hierarchy is a kind of independent level. No matter what the hierarchies are, the structure of each remains the same, and only has something with the same tasks of different hierarchies. Way-finding is trying to find out the shortest path between two nodes. The choice of the shortest path is carried out according to the hierarchies of the roads (Express high way, main road, secondary road, avenue and small road). This kind of solving method is quite different from that of the tasks, and we call it hierarchical way-finding.

Spatial hierarchical structure of road network
Our hierarchical spatial reasoning is based on the following cognitive hypotheses: (1) Human begins have classified the main road hierarchically, and these hierarchies are based on the level of the roads, traffic volume or the speed while aiming at different improvement criteria.
(2) The hierarchies increase successively from the higher level to the lower one; the higher level is the subset of the lower one.
(3) The whole road network is divided by those main roads. When we are reading the traffic map of a city, we can find that the main roads and express ways form a network, and the main roads divide the whole network into several smaller districts naturally, which we call natural grid.
(4) The networks of hierarchies are connected. On the basis of the knowledge of road network, we adopt a hierarchical way of processing great amounts of data. Taking the road network of Wuhan as an example, we would divide the original road network into two hierarchies: the hierarchy of main roads (higher level) and the hierarchy of sub-main roads (lower level). The main road level only includes the network that is formed by express highways and main roads; the secondary road level includes the network formed by express highways, main roads and the common roads, avenue and small roads of the natural grid.

Representation of hierarchical road network
The representation of hierarchical road network means how the road networks are represented and stored in the computer. It is the basis of the calculation method of way-finding. The whole road network is displayed as a graph that consists of all the nodes and arcs of the same single hierarchy. The whole network is expressed as G = (N, E), in which N={N 1 , N 2 ,…, N n }is the set of all the nodes of the network; and E={e ij | N i , N j ∈N} is the set of the edges of the network, where e ij is the edge that connects the nodes of N i and N j . The edges between two nodes are regarded as bi-directional, and each edge has a non-negative weight. In order to divide the road network into higher hierarchical network and lower hierarchical network, we have defined two arrays which are used to record the nodes and edge of the two hierarchical networks.

Rules of hierarchical way-finding
Given the origin point O and the destination point D, supposing the road network has been divided into hierarchies, the hierarchical calculation of the optimal path can be described as: (1) Decide the hierarchies that points O and D belong to; (2) If both point O and point D are in the higher hierarchy, turn to (5); if not, decide the natural grid that points O and D belong to; (3) If the two grids are the same or adjacent to each other, then we will apply the non-hierarchy algorithm to compute the optimal path between these two points; (4) Search the shortest path that leads to the higher hierarchical network respectively in the natural grid that points O and D belong to, and find out the corresponding points O 1 and D 1 of higher network, since these two points are the entrance or exit points of going to the higher hierarchy; (5) In the higher hierarchical network, use the non-hierarchy algorithm to search the optimal path between point O (or its corresponding point O 1 ) and point D (or its corresponding point D 2 ); (6) The output is the optimal path between points O and D.

Experiment and conclusion
To make a comparison between hierarchical algorithm and non-hierarchical algorithm, we use visual C++ to perform the optimal path computation simulations on the Wuhan city network. The whole road network was organized as a two-level hierarchical representation, the main roads are the higher hierarchy marked by bold lines, and secondary roads are the lower one, marked by the fine lines. The flat network consists of 10 794 arcs and 6 879 nodes. Fig.1 demonstrates the traditional algorithm to compute the shortest path that is simply operated on the single hierarchy, in which almost all the roads are common roads. Fig.2 demonstrates the hierarchical algorithm of the networks. Although the optimal path that we get with the latter method cannot be regarded as the shortest in theory, it is a kind of sub-short paths, and over 85% of them are on the main roads. The result of the experiment has proved that the length of the best computed by the hierarchical method is about 10% longer than that computed by the non-hierarchical algorithm, and this finding is reasonable according to former analyses of calculation theories.
Meanwhile, the hierarchy has greatly reduced the searching space and has greater efficiency than the non-hierarchical algorithm, which helps to significantly reduce the running time, costing only about 15% of the time needed by traditional algorithm. Hierarchical algorithm tries to divide the whole network into three sub-networks and compute the shortest path in these smaller sub-networks, as each sub-network is just one part of the whole network. This method has greatly decreased the running time. Applying the hierarchical spatial reasoning in large size city road networks to find the shortest path can greatly reduce the cost of time and space; it is also suitable for human being's reasoning model, and is easily acceptable.