CN118445318A

CN118445318A - Road network indexing method supporting multi-type query

Info

Publication number: CN118445318A
Application number: CN202410439901.4A
Authority: CN
Inventors: 曹春; 徐经纬; 曹卓
Original assignee: Nanjing University
Current assignee: Nanjing University
Priority date: 2024-04-12
Filing date: 2024-04-12
Publication date: 2024-08-06

Abstract

The invention discloses a road network indexing method supporting multi-type inquiry, which comprises the following steps: 1) Defining a road network and shortest path distance query, k neighbor query and range query; 2) A tree structure with shortcuts (shortcuts) for hierarchical index SCG-tree for multi-type queries in road network; 3) A method for constructing an SCG-tree index on a given road network through an iterative graph dividing method and a shortcut selection strategy based on an evaluation index; 3) Based on the SCG-tree index structure, the query methods of shortest path query, k neighbor query and range query can be efficiently performed by using the distance matrix pre-calculated and stored in the index and the shortcut distance matrix; the invention can efficiently support three kinds of inquiry including shortest path inquiry, k neighbor inquiry and range inquiry in a large-scale road network, overcomes the defect that the existing index only supports single kind of inquiry, has small storage cost in a layering structure, and can obtain higher inquiry speed by utilizing shortcut in the index structure.

Description

Road network indexing method supporting multi-type query

Technical Field

The invention relates to the technical field of space data query under the constraint of a road network, in particular to a road network index technology capable of supporting multi-type query

Background

In recent years, with the popularity of mobile terminals, there is an increasing demand for location-based services, in which users can quickly acquire relevant latest information according to their current location and personal preferences. A large number of location-based services are each day required to respond to a vast variety of road network-based spatial queries, such as navigation systems, map services, point-of-interest searches, and the like. Three basic query types are used in a large number, including shortest path distance query, k-nearest neighbor query, and range query. For example, in urban taxi taking services, there are millions of query demands per day, and there are hundreds of thousands of query tasks per second at peak. However, classical road network searching methods (e.g., dijkstra, a, etc.) are not able to respond to dense query loads in time, and therefore use of road network indexing techniques is necessary.

There are many existing technologies for road network indexes for shortest path distance query, k-nearest neighbor query and range query respectively, wherein indexes for shortest path distance query are mainly classified into two major categories of hierarchical indexes and label-based indexes. The hierarchical indexing method is balanced in terms of construction time, storage space overhead and query efficiency, and the query is performed on a hierarchical structure, so that a plurality of unnecessary search spaces are reduced, and the query efficiency is high. The label-based index pre-calculates a label set for each node in the road network, and only the corresponding label set is required to be searched during query, so that the query efficiency is higher, but the storage cost is huge, and the method is difficult to effectively use on the large-scale road network. The index for k-nearest neighbor query is searched by gradually expanding the search space, or the query is accelerated by using extra space to maintain the nearest target node, however, as the road network scale increases, the storage cost is very huge. The index for range query is often extended based on the k-nearest neighbor query problem, but there is still much redundant computational overhead, making the query process inefficient.

However, the existing indexing method is designed for a single type of query, and is rarely capable of supporting multiple query problems at the same time and with high efficiency. Constructing a separate road network index for each query problem can result in a significant amount of additional storage overhead that is not economical and efficient. Therefore, the design of the efficient road network index technology supports various query tasks at the same time, and meets the requirements of the existing application based on the location service, so that the application can respond to the query requirements more quickly, and the user experience is improved. The hierarchical indexing technology has a certain potential in supporting multi-type query, has smaller construction time and storage space cost, and can be efficiently applied to a large-scale road network. However, since the query is performed in a hierarchical structure, as the distance between query locations increases, particularly as long-distance query increases, the search space increases significantly, and the query efficiency decreases, it is difficult to perform efficient query in a large-scale road network.

Disclosure of Invention

The invention aims to: aiming at the problems and the defects in the prior art, the invention provides a hierarchical road network indexing technology which supports multi-type query and is enhanced by using shortcut, and aims to solve the defect that the prior indexing technology only supports single-type query, and simultaneously solve the problem that the efficiency of hierarchical indexing is poor in long-distance query. According to the invention, a small amount of shortcut is introduced into the hierarchical structure by using the evaluation index and the optimization strategy, so that the query algorithms for carrying out shortest path distance query, k neighbor query and range query by fully using the shortcut are respectively designed, and the search cost during query is effectively reduced, thereby realizing the efficient support of multi-type query, and simultaneously having smaller construction time and storage space cost.

The technical scheme is as follows: a road network indexing method supporting multi-type queries, comprising the following:

(1) Concepts related to the road network model and the query model are defined, wherein the concepts comprise the road network represented as a weighted undirected graph, the road network divided representation, the boundary node definition and the query model in three road networks: shortest path distance query Q _spsp(v_i,v_j), k neighbor query Q _knn(v_q, C, k), range query Q _range(v_q, C, d);

(2) Defining a structure of a road network index SCG-tree according to the definition of the road network, the representation of road network division and the definition of boundary nodes, wherein the structure is a hierarchical tree structure, a plurality of shortcuts exist in the tree, each node corresponds to a subgraph in the road network, each node in the tree is provided with a boundary node set, a joint boundary node set or subgraph node set, a shortcut set and a distance matrix, and each shortcut corresponds to a shortcut distance matrix;

(3) Giving a road network according to the structure of the road network index SCG-tree defined in the step (2), constructing a tree structure through iterative graph division, evaluating and selecting a shortcut through a plurality of indexes of benefits, use frequency, return and storage space, and finally calculating a distance matrix and a shortcut distance matrix respectively, and completing the construction of the index SCG-tree through the processes;

(4) Given a shortest path distance query Q _spsp(v_i,v_j based on the structure of the road network index SCG-tree), firstly, finding a query path of a start position v _i and a stop position v _j in the index SCG-tree, namely a path formed from a leaf node containing v _i to LCA to a leaf node containing v _j or a path formed from a leaf node containing v _i to a shortcut to a leaf node containing v _j, and then using a dynamic programming method to obtain a result of the shortest path distance query according to the query path;

(5) Giving a k neighbor query Q _knn(v_q, C and k) based on the structure of a road network index SCG-tree, firstly identifying nodes with target objects in the tree, then gradually expanding the search range by using a two-stage expansion strategy from bottom to top and from near to far, only searching the nodes with target objects in the process, excluding the nodes without target objects until the nearest k objects are found, and finally returning a query result;

(6) Based on the structure of the road network index SCG-tree, a range query Q _range(v_q, C and d) is given, firstly, the node with the target object in the tree is identified, then the search range is gradually increased by using a two-stage expansion strategy from bottom to top and from near to far, when the distance from the search position to one node is greater than the distance condition d in the search, pruning is carried out on the node and all sub-nodes thereof, namely the node and all sub-nodes thereof are not searched, when the minimum distance from the search position to the boundary of the current search area is greater than the distance condition d, early stop is carried out so as to reduce unnecessary search expenditure, and finally the query result meeting the condition is returned.

Further, in step (1), the following concepts are modeled:

(11) The road network model is represented as a weighted undirected graph G= { V, E }, w- & gtR ⁺, wherein G is a road network, V is a node set in the road network, E is a set of edges in the road network, E is a weight function of the edges, the distance or the transit time of the road is represented, the edge connecting two nodes V _i and V _j is represented as E _i,j, the shortest path between the nodes V _i and V _j is represented as sp _i,j, and the distance of the shortest path is represented as |sp _i,j |;

(12) Given a road network g= { V, E }, w→r ⁺, a graph-partitioning definition by edge-cutting divides the set of nodes in G into n disjoint subsets { V ₁,…,V_n }, and One of the subgraphs is denoted as G _i＝{V_i,E_i, the neutron atlas E _i＝{e_j,k∈E|v_j,v_k∈V_i;

(13) One node v _i in the subgraph is denoted b _i when it is a boundary node, satisfying the following

(14) The shortest path distance query is denoted Q _spsp(v_i,v_j), where v _i and v _j represent the start node and the end node, respectively, the query returns the result of the shortest path distance |sp _i,j |;

(15) The k-nearest neighbor query is denoted Q _knn(v_q, C, k), where v _q denotes the query location, Representing a target object set of the query, k representing the number of the latest objects to be queried, and the returned result of the query is represented as R, satisfying the following conditionsAnd

(16) The range query is denoted Q _range(v_q, C, d), where v _q denotes the query location,A target object set representing the query, d representing the distance condition to be queried, the returned result of the query being represented as R, satisfyingAnd v _i∈R,|sp_q,i < d for all, v _j∈C\R,|sp_q,j > d for each. C\R represents the element set left after the elements in the R set are removed from the elements in the C set.

Further, in step (2), the structure of the road network index SCG-tree includes:

(21) Each node in the tree corresponds to a subgraph in the road network, the root node corresponds to the whole road network, each non-leaf node has N _f child nodes, and the number |V _i | of the nodes in the node set V _i of the subgraph corresponding to each leaf node N _i is smaller than or equal to a given construction parameter N _τ;

(22) Each leaf node stores a boundary node set in a corresponding sub-graph, a joint boundary node set of all child nodes or all node sets in the corresponding sub-graph, all shortcut sets connected with the leaf nodes, and a distance matrix;

(23) Each shortcut is connected with two non-brothers nodes located on the same layer, each shortcut corresponds to a shortcut distance matrix, and the total memory space overhead of all the shortcuts is smaller than or equal to a given construction parameter n _λ.

Further, in step (3), the construction process of the road network index SCG-tree includes:

(31) Determining an input road network G and construction parameters n _f、n_τ and n _λ;

(32) Starting from a root node of the SCG-tree, performing iterative graph division, dividing each time into n _f sub-graphs until the number of nodes in node sets of all leaf nodes is less than or equal to n _τ, constructing corresponding tree nodes for each sub-graph according to a division process, constructing a boundary node set and a joint boundary node set, and constructing a complete tree structure;

(33) Determining the lowest layer l in the layers capable of completely building the shortcuts according to N _λ and the storage overhead of the possible shortcuts in each layer, building all the possible shortcuts among tree nodes of the layer, and evaluating the possible shortcuts by using several indexes of profit, use frequency, return and storage space for the unsatisfied layer l+1, wherein the profit of the shortcut connecting two nodes N _i and N _j is defined as:

Where TP _i,j represents the path of every two consecutive nodes in the tree from nodes N _i to N _j, the path being a combination of the sub-path of N _i to LCA and the sub-path of N _j to LCA, (N _x,N_y) for each pair represents two consecutive pairs of nodes in the path TP _i,j, |B _x | and |B _y | represent the number of elements in the set of boundary nodes of nodes N _x and N _y, respectively, |B _i | and |B _j | represent the number of elements in the set of boundary nodes of nodes N _i and N _j, respectively;

The frequency of use of shortcut connecting two nodes N _i and N _j is:

wherein |V _i | and |V _j | respectively represent the number of nodes in the subgraph corresponding to the nodes N _i and N _j, and |V| represents the number of nodes in the whole road network;

the return of shortcut connecting two nodes N _i and N _j is:

r_i,j＝g_i,j·p_i,j

Where g _i,j represents the benefit of shortcut connecting two nodes N _i and N _j, and p _i,j represents the frequency of use of shortcut connecting two nodes N _i and N _j;

The memory space of the shortcut connecting the two nodes N _i and N _j is:

w_i,j＝|B_i|·|B_j|

Wherein |b _i | and |b _j | represent the number of elements in the boundary node sets of nodes N _i and N _j, respectively;

by evaluating all possible shortcuts of the unsatisfied layer, constructing the following optimization strategy and sequentially selecting the shortcuts to be constructed according to the order of unit values from high to low in a greedy manner until the space overhead constraint n _λ is met;

Where K represents the total number of all possible shortcuts for the unsatisfied level, r _k represents the return indicator for the kth shortcut, x _k represents whether the kth shortcut is selected, delta _l represents the total storage overhead for all shortcuts built in level l, n _λ represents the total storage overhead constraint parameter for the shortcuts in a given SCG-tree, and n _λ-δ_l represents the total storage overhead available in the unsatisfied level l+1.

(34) Calculating distance values in all distance matrixes and distance matrixes corresponding to shortcuts in a full layer by a Folyd method, calculating distance values in all shortcuts in the full layer by a dynamic programming method, and arranging the shortcuts in all nodes in ascending order according to the minimum value in the corresponding shortcuts distance matrix.

Further, in step (4), the shortest path distance query process includes:

(41) Given two nodes v _i and v _j, the highest level node in the tree where nodes v _i and v _j are located is calculated using the highest level node function, and the highest level node hn (v _i, l) of node v _i is defined as:

Where l is a given hierarchical constraint, leaf (v _i) is the leaf node where node v _i is located, B _j is the set of boundary nodes for node N _j, N _j. Level is the layer where node N _j is located;

Finding the lowest common ancestor node LCA corresponding to the hn (v _i, l) and the hn (v _j, l) and available shortcuts, if the LCA is located in a lower layer than the available shortcuts, using the LCA to connect two tree nodes to a sub-path of the LCA as a query path in a tree, otherwise using the shortcuts to connect two tree nodes to the sub-path of the LCA as a query path in the tree, and using the shortcuts to effectively reduce the search overhead in an upper node;

(42) On the obtained path in the tree, the shortest path distance between the nodes v _i and v _j is obtained by using a dynamic programming method, and the specific process is to calculate and cache the shortest path distance between the node v _i and all boundary nodes of the next node in the path each time until the shortest path distance between the node v _i and the node v _j is calculated finally.

Further, in step (5), the k-nearest neighbor query procedure includes:

(51) According to a given target object set C, identifying leaf nodes containing target objects in the tree and ancestor nodes of the leaf nodes as candidate nodes;

(52) Starting from the leaf node where the query position v _q is located, a bottom-up expansion mode is used first, the search range is expanded to a child region corresponding to a father node each time, only the region containing the target object is searched during expansion, and the region not containing the target object is skipped. When reaching the layer of the fully built shortcut, the expansion is performed based on the shortcut from near to far according to the distance between nodes, and the distance between the nodes is defined as:

Where |b _i | and |b _j | denote the number of elements in the set of boundary nodes of nodes N _i and N _j respectively, Representing the shortest path distance of boundary nodes b _i and b _j;

The nearest node is selected according to the distance between nodes from small to large, and the distance between the query position and the node is calculated and expressed as:

Then find out the satisfaction from near to far In the formula (I)Ancestor nodes in the full-built shortcut layer, denoted v _q, are added to the search area at the same time if they further satisfy Dist (v _q,N_j)≤Dist(v_q,N_i), and the search process is repeated until the search area is not expandable again when the search area is the whole road network, and the search is ended when k target objects are contained in the result set in the search process.

Further, in step (6), the range query process includes:

(61) According to a given target object set C, identifying leaf nodes containing target objects in the tree and ancestor nodes of the leaf nodes as candidate nodes;

(62) Starting from the leaf node where the query position v _q is located, using a two-stage expansion strategy from bottom to top and from near to far, discarding the region when the distance from the query position to a sub-graph is greater than the search distance condition during expansion, stopping searching when the whole search range is greater than the search distance condition, and finally returning all the found target objects.

A road network indexing system supporting multiple types of queries, comprising:

Definition module of the concept related to the road network model and the query model, wherein the definition module comprises a road network represented as a weighted undirected graph, a road network divided representation, a boundary node definition and query models in three road networks: shortest path distance query Q _spsp(v_i,′_j), k neighbor query Q _knn(v_q, C, k), range query Q _range(v_q, C, d);

The definition module of the road network index SCG-tree structure defines the structure of the road network index SCG-tree according to the definition of the road network, the representation of road network division and the definition of boundary nodes, wherein the structure is a hierarchical tree structure, a plurality of shortcuts exist in the tree, each node corresponds to a subgraph in the road network, each node in the tree is provided with a boundary node set, a joint boundary node set or subgraph node set, a shortcut set and a distance matrix, and each shortcut corresponds to a shortcut distance matrix;

The road network definition module is used for giving a road network according to the structure of a defined road network index SCG-tree, constructing a tree structure through iterative graph division, evaluating and selecting a shortcut through a plurality of indexes of benefits, use frequency, return and storage space, and finally calculating a distance matrix and a shortcut distance matrix respectively, and constructing the index SCG-tree through the processes;

The shortest path distance query module, based on the structure of the road network index SCG-tree, gives a shortest path distance query Q _spsp(v_i,v_j), firstly finds the query path of the starting position and the ending position in the index SCG-tree, namely the path formed from the leaf node containing v _i to LCA to the leaf node containing v _j or the path formed from the leaf node containing v _i to a shortcut to the leaf node containing v _j, and then uses a dynamic programming method to obtain the shortest path distance query result according to the query path;

The k-nearest neighbor query module is used for giving a k-nearest neighbor query Q _knn(v_q, C and k based on the structure of a road network index SCG-tree, firstly identifying nodes with target objects in a tree, then gradually expanding the search range by using a two-stage expansion strategy from bottom to top and from near to far, only searching the nodes with target objects in the process, excluding the nodes without target objects until the nearest k objects are found, and finally returning a query result;

The range query module, based on the structure of the road network index SCG-tree, gives a range query Q _range(v_q, C, d), firstly identifies the node with the target object in the tree, then uses a two-stage expansion strategy from bottom to top and from near to far to gradually increase the search range, and in the search, when the distance from the search position to one node is greater than the distance condition d, pruning the node and all the sub-nodes thereof, namely not searching the node and all the sub-nodes thereof, and when the minimum distance from the search position to the boundary of the current search area is greater than the distance condition d, early stopping is carried out to reduce unnecessary search expenditure, and finally, the query result meeting the condition is returned.

The implementation process and method of the system are the same and will not be described again.

A computer device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, the processor implementing a road network indexing method supporting multi-type queries as described above when executing the computer program.

A computer readable storage medium storing a computer program for executing the road network indexing method supporting multi-type queries as described above.

The beneficial effects are that: compared with the prior art, the invention has the following advantages:

(1) The method can efficiently support shortest path distance query, k neighbor query and range query simultaneously, does not need to construct a separate index for each query, is more efficient and economical, and meets the application requirements of location-based services;

(2) The construction process is efficient, the storage cost is low, and the method can be used for efficient expansion on a large-scale road network;

(3) By evaluating the index and optimizing the strategy, the shortcut which is more beneficial to the query task can be selected, the query efficiency can be effectively accelerated, and the storage cost is saved.

(4) The shortest path distance query algorithm based on the shortcut can realize microsecond query response, and the k-nearest neighbor query and range query algorithm based on the two-stage expansion search strategy can realize microsecond to millisecond query response, so that the method has a faster query speed for long-distance query.

Drawings

FIG. 1 is an overall workflow diagram of a method of an embodiment of the invention;

FIG. 2 is a schematic diagram of a road network index structure according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of a query process according to an embodiment of the present invention.

Detailed Description

The present application is further illustrated below in conjunction with specific embodiments, it being understood that these embodiments are meant to be illustrative of the application and not limiting the scope of the application, and that modifications of the application, which are equivalent to those skilled in the art to which the application pertains, fall within the scope of the application defined in the appended claims after reading the application.

A road network index method supporting multi-type query is characterized in that on a given road network model, an index SCG-tree corresponding to the road network is constructed through three processes of iterative graph division, evaluation and selection of shortcut and calculation of distance matrix values, an index structure comprises three parameters n _f、n_τ and n _λ, each node corresponds to a subgraph in the road network, shortcut (shortcut) exists in a tree, and the three query methods of shortest path distance query, k neighbor query and range query can be fully used for carrying out efficient calculation. The method specifically comprises the following steps:

(1) The method comprises the steps of defining a concept related to a road network model and a query model, wherein the concept comprises the steps of representing the road network as a weighted undirected graph, representing road network division, defining boundary nodes and querying models in three road networks, wherein the querying models in the three road networks are respectively: shortest path distance query Q _spsp(v_i,v_j), k neighbor query Q _knn(v_q, C, k), range query Q _range(v_q, C, d);

(11) The road network model is expressed as a weighted undirected graph G= { V, E }, w- & gtR ⁺, wherein G is a road network, V is a node set in the road network, E is a set of edges in the road network, w is a weight function of the edges, the edge connecting two nodes V _i and V _j is expressed as E _i,j, the shortest path between the nodes V _i and V _j is expressed as sp _i,j, and the distance of the shortest path is expressed as |sp _i,j |;

(12) Given a road network g= { V, E }, w→r ⁺, graph partitioning by edge-cutting is defined as partitioning the set of nodes in G into n disjoint subsets { V ₁,…,V_n }, and One of the subgraphs is denoted as G _i＝{V_i,E_i, the neutron atlas E _i＝{e_j,k∈E|v_j,v_k∈V_i;

(16) The range query is denoted Q _range(v_q, C, d), where v _q denotes the query location,A target object set representing the query, d representing the distance condition to be queried, the returned result of the query being represented as R, satisfyingAnd for all v_i ε R, |sp_ { q, i } |d, for each' _j∈C\R,|sp_q,j | > d.

(2) Defining a structure of a road network index SCG-tree according to the definition of the road network, the representation of road network division and the definition of boundary nodes, wherein the structure is a hierarchical tree structure, a plurality of shortcuts exist in the tree, and each shortcut corresponds to a shortcut distance matrix;

(21) Each node in the tree corresponds to a subgraph in the road network, the root node corresponds to the whole road network, each non-leaf node has n _f child nodes, and the number of nodes in the node set of the subgraph corresponding to each leaf node is less than or equal to n _τ;

(22) Each non-leaf node stores a boundary node set in the corresponding sub-graph, a joint boundary node set of all child nodes or all node sets in the corresponding sub-graph, all shortcut sets connected with the node and a distance matrix, and the shortcut sets are arranged in ascending order according to the minimum value in the distance matrix of the corresponding shortcut;

(23) Each shortcut is connected with two non-brothers nodes positioned on the same layer, each shortcut corresponds to a shortcut distance matrix, and the total memory space overhead of all the shortcuts is less than or equal to n _λ.

(32) Starting from a root node, carrying out iterative graph division, dividing each time into n _f sub-graphs until the number of nodes in node sets of all leaf nodes is less than or equal to n _τ, constructing corresponding tree nodes for each sub-graph according to a division process, constructing a boundary node set and a joint boundary node set, and constructing a complete tree structure;

(33) Determining a layer capable of completely building the shortcuts according to N _λ and the storage overhead of the possible shortcuts in each layer, building all the possible shortcuts in the layer, and evaluating the possible shortcuts by using several indexes of profit, use frequency, return and storage space for the unsatisfied layer, wherein the profit of the shortcuts connecting two nodes N _i and N _j is defined as:

The frequency of use of shortcut connecting two nodes N _i and N _j is:

the return of shortcut connecting two nodes N _i and N _j is:

r_i,j＝g_i,j·p_i,j

The memory space of the shortcut connecting the two nodes N _i and N _j is:

w_i,j＝|B_i|·|B_j|

(4) Giving a shortest path distance query Q _spsp(v_i,v_j based on the structure of a road network index SCG-tree), firstly finding a query path of a starting position and a termination position in the index SCG-tree, wherein the path comprises a combination of two sub paths from leaf nodes containing v _i and v _j to LCA or a shortcut respectively, and then obtaining a result of the shortest path distance query by using a dynamic programming method according to the query path;

(52) Starting from the leaf node where the query position b _q is located, a bottom-up expansion mode is used first, the search range is expanded to a child region corresponding to a father node each time, only the region containing the target object is searched during expansion, and the region not containing the target object is skipped. When reaching the layer of the fully built shortcut, the expansion is performed based on the shortcut from near to far according to the distance between nodes, and the distance between the nodes is defined as:

(6) Based on the structure of the road network index SCG-tree, a range query Q _range(v_q, C, d) is given, the node with the target object in the tree is firstly identified, then the search range is gradually increased by using a two-stage expansion strategy from bottom to top and from near to far, pruning is carried out when the distance from the search position to one node is greater than the distance condition d in the search, early stopping is carried out when the minimum distance from the search position to the boundary of the current search area is greater than the distance condition d, so that unnecessary search expenditure is reduced, and finally the query result meeting the condition is returned.

FIG. 1 depicts an overall workflow diagram of the method of the present invention, including the following:

(1) Given a road network, an indexed tree structure is constructed by iterating the graph partitioning of the road network.

(2) And evaluating and selecting the shortcut through the evaluation index and the optimization strategy.

(3) And calculating the values of distance matrixes in all nodes, and calculating the values of all shortcut distance matrixes.

(4) And constructing an index SCG-tree of the corresponding road network through three processes of iterative graph division, evaluation and selection of shortcut and calculation of distance matrix values.

(5) Given shortest path distance query, k-nearest neighbor query, range query workload, query results can be obtained quickly by using the index.

FIG. 2 depicts a schematic diagram of the road network index structure of the present invention, including the following:

(1) Each node corresponds to a subgraph in the road network, and the root node corresponds to the whole road network.

(2) Each node has n _f child nodes, the number of nodes in the node set of the subgraph corresponding to each leaf node is less than or equal to n _τ, and the total memory space overhead of all shortcut matrixes is less than or equal to n _λ.

(3) There are some shortcuts in the tree, each shortcut connecting two non-sibling nodes at the same level.

(4) Each non-leaf node includes a set of boundary nodes, a set of joint boundary nodes, a set of shortcut, and a distance matrix.

(5) Each leaf node includes a set of boundary nodes, a set of child nodes, a set of shortcut, and a distance matrix.

(6) Each shortcut in the tree corresponds to a shortcut distance matrix, and all the shortcuts distance matrices form a shortcut matrix set.

FIG. 3 depicts a schematic diagram of the query process of the present invention, including the following:

(1) The index structure can efficiently support multiple query types, including three types of shortest path distance query, k-nearest neighbor query and range query.

(2) When the shortest path distance query is carried out, the query path in the tree is a complete path formed by connecting the highest-layer node in the tree where the nodes v _i and v _j are positioned to the two sub-paths of the ancestor node of the full shortcut layer through the shortcut.

(3) When the shortest path distance query is carried out, the shortest path distance between the starting node v _i and boundary nodes of all nodes in the path is sequentially calculated and stored on the query path in the tree by using a dynamic programming method, and finally the shortest path distance between the starting node v _i and the target node v _j is obtained.

(4) When the k neighbor is queried, starting from a leaf node where the query position v _q is located, expanding according to a bottom-up mode, then expanding according to a near-to-far mode based on shortcut until the nearest k target objects are found, and finally returning a query result.

(5) And when the range is searched, searching is carried out according to a two-stage expansion strategy combining from bottom to top and from near to far, pruning is carried out if the distance from the searching area is greater than the distance condition in the process, and searching is stopped when the minimum boundary distance of the whole searching area is greater than the distance condition of the query.

It will be apparent to those skilled in the art that the steps of the method for indexing a road network supporting multiple types of queries or the modules of the system for indexing a road network supporting multiple types of queries in the embodiments of the invention described above may be implemented by general purpose computing devices, they may be centralized on a single computing device, or distributed across a network of multiple computing devices, or alternatively, they may be implemented in program code executable by computing devices, such that they may be stored in a memory device for execution by computing devices and, in some cases, the steps shown or described may be performed in a different order than what is shown or described herein, or they may be separately fabricated into individual integrated circuit modules, or multiple modules or steps within them may be fabricated into a single integrated circuit module for implementation. Thus, embodiments of the invention are not limited to any specific combination of hardware and software.

Claims

1. A road network indexing method supporting multi-type inquiry is characterized by comprising the following steps:

(4) Giving a shortest path distance query Q _spsp(v_i,v_j based on the structure of a road network index SCG-tree), firstly finding a query path of a starting position v _i and a termination position v _j in the index SCG-tree, wherein the path comprises a combination of two sub paths from leaf nodes containing v _i and v _j to LCA or a shortcut respectively, and then obtaining a result of the shortest path distance query by using a dynamic programming method according to the query path;

2. The road network indexing method supporting multiple types of queries according to claim 1, wherein in step (1), the following concepts are modeled:

(11) The road network model is represented as a weighted undirected graph g= { V, E }, w→r ⁺, wherein G is a road network, V is a node set in the road network, represents a target object in the road network, E is a set of edges in the road network, represents a road, w is a weight function of the edges, represents a distance or a transit time of the road, an edge connecting two nodes V _i and V _j is represented as E _i,j, a shortest path between the nodes V _i and V _j is represented as sp _i,j, and a distance of a shortest path is represented as |sp _i,j |;

(12) Given a road network g= { V, E }, w→r ⁺, a graph-partitioning definition by edge-cutting divides the set of nodes in G into n disjoint subsets { V ₁,...,V_n }, and One of the subgraphs is denoted as G _i＝{V_i,E_i, the neutron atlas E _i＝{e_j,k∈E|v_j,v_k∈V_i;

(15) The k-nearest neighbor query is denoted Q _knn(v_q, C, k), where v _q denotes the query location, Representing a target object set of the query, k representing the number of the latest objects to be queried, and the returned result of the query is represented as R, satisfying the following conditions|R|=k, and month|sp_q,i|≤|sp_q,j|；

(16) The range query is denoted Q _range(v_q, C, d), where v _q denotes the query location,A target object set representing the query, d representing the distance condition to be queried, the returned result of the query being represented as R, satisfyingAnd v _i∈R,|sp_q,i < d for all, v _j∈C\R,|sp_q,j > d for each.

3. The road network indexing method supporting multiple types of queries according to claim 1, wherein in step (2), the structure of the road network index SCG-tree comprises:

4. The road network indexing method supporting multiple types of queries according to claim 1, wherein in step (3), the construction process of the road network index SCG-tree comprises:

The frequency of use of shortcut connecting two nodes N _i and N _j is:

the return of shortcut connecting two nodes N _i and N _j is:

r_i,j＝g_i,j·p_i,j

The memory space of the shortcut connecting the two nodes N _i and N _j is:

w_i,j＝|B_i|·|B_j|

5. The road network indexing method supporting multiple types of queries according to claim 1, wherein in step (4), the shortest path distance query procedure comprises:

Finding the lowest common ancestor node LCA corresponding to the hn (v _i, l) and the hn (v _j, l) and available shortcuts, if the LCA is located in a lower layer than the available shortcuts, using the LCA to connect two tree nodes to a sub-path of the LCA as a query path in a tree, otherwise using the shortcuts to connect two tree nodes to the sub-path of the LCA as a query path in the tree;

6. The road network indexing method supporting multiple types of queries according to claim 1, wherein in step (5), the k-nearest neighbor query procedure comprises:

7. The road network indexing method supporting multiple types of queries according to claim 1, wherein in step (6), the range query process comprises:

8. A road network indexing system supporting multiple types of queries, comprising the following modules:

Definition module of the concept related to the road network model and the query model, wherein the definition module comprises a road network represented as a weighted undirected graph, a road network divided representation, a boundary node definition and query models in three road networks: shortest path distance query Q _spsp(v_i,v_j), k neighbor query Q _knn(v_q, C, k), range query Q _range(v_q, C, d);

The shortest path distance query module, based on the structure of the road network index SCG-tree, gives a shortest path distance query Q _spsp(v_i,v_j, firstly finds a query path of a starting position and a termination position in the index SCG-tree, wherein the path comprises a combination of two sub paths from leaf nodes containing v _i and v _j to LCA or a shortcut respectively, and then obtains a result of the shortest path distance query by using a dynamic programming method according to the query path;

The range query module, based on the structure of the road network index SCG-tree, gives a range query Q _range(v_q, C, d), firstly identifies the node with the target object in the tree, then uses a two-stage expansion strategy from bottom to top and from near to far to gradually increase the search range, pruning the node when the distance from the search position to the node is greater than the distance condition d in the search, early stopping when the minimum distance from the search position to the boundary of the current search area is greater than the distance condition d, and finally returning the query result meeting the condition.

9. A computer device, characterized by: the computer device comprising a memory, a processor, and a computer program stored on the memory and executable on the processor, the processor implementing the road network indexing method supporting multiple types of queries as claimed in any of claims 1-7 when the processor executes the computer program.

10. A computer-readable storage medium, characterized by: the computer readable storage medium stores a computer program for performing the road network indexing method supporting multi-type queries as claimed in any one of claims 1-7.