CN114896480B - Top-K space keyword query method based on road network index - Google Patents

Abstract

The invention discloses a Top-K space keyword query method based on road network indexes, which comprises the following steps: 1) Defining related concepts of the road network; 2) Weighting calculation is carried out by using the shortest transit time and the TF-IDF model, so that a space text scoring function capable of measuring the space adjacency of the object and the similarity of the text is obtained; 3) Constructing a road network index TKG-tree by using edge and vertex information contained in the road network, wherein the road network index comprises a traffic time matrix recorded with space index information and an inverted document recorded with text index information; 4) Using the space text score as an index of Top-K result sequencing, and using the constructed road network index TKG-tree to find a space keyword object of ranking Top-K; the road network index is constructed in a sub-graph dividing mode, the problem that the index storage cost is too high is solved, the space text score of the node is used as an upper bound pruning object, and the speed of searching the Top-K space keyword object can be improved.

Description

Top-K spatial keyword query method based on road network index

Technical Field

The present invention relates to the technical field of road network index and Top-K query, and in particular to a Top-K spatial keyword query method based on road network index.

Background Art

The Top-k spatial keyword query problem is a hot topic in spatial database research. Its purpose is to query several objects that are close to the user's location and meet the user's query preferences, and its query intent is expressed by keywords. The Top-k spatial keyword query problem not only considers the matching degree between the object and the keyword, but also considers the spatial distance between the user and the query object. According to the difference in the measurement method of spatial distance, it can be divided into two different distances: Euclidean space and road network space. Euclidean space represents that the distance between two points is measured by straight-line distance, while the distance between two points in road network space is measured by the shortest distance on the road network.

However, it is very difficult to support efficient Top-K queries on road networks. The main bottleneck is that the cost of calculating the shortest path from point to point is extremely high, which is not as simple as calculating the Euclidean straight-line distance between two points. In addition, even if the shortest road distance can be obtained quickly, it is very time-consuming to calculate the Top-K results without efficient pruning algorithms and strategies. Although there is a lot of work studying the Top-K query processing problem on road networks. However, the existing methods cannot support large-scale road networks. The main problem with these methods is that the index will lead to too high storage cost or too high preprocessing time cost.

Summary of the invention

The purpose of the present invention is to overcome the shortcomings and deficiencies of the prior art, and proposes a Top-K spatial keyword query method based on road network index. The road network index is constructed by dividing the subgraph, which alleviates the problem of high index storage cost. The spatial text score of the node is divided into upper bound pruning objects, which can improve the speed of searching for Top-K spatial keyword objects.

To achieve the above object, the technical solution provided by the present invention is: a Top-K spatial keyword query method based on road network index, comprising the following steps:

1) Define the relevant concepts of the road network, including the spatial keyword object o, the road network graph G and the shortest travel time function τ ^* (t) between two vertices;

2) Use the shortest travel time function τ ^* (t) obtained in step 1) to measure the spatial proximity of the spatial keyword object o, and obtain the spatial score function, denoted as f _s (o); use the TF-IDF model to measure the text similarity of the spatial keyword object o, and obtain the text score function, denoted as f _d (o); use the text score function f _d (o) and the spatial score function f _s (o) to perform weighted calculation to obtain the spatial text score function, denoted as

3) Based on the road network defined in step 1), the road network index TKG-tree is constructed using the edge and vertex information it contains; TKG-tree is a balanced tree structure obtained by graph cutting, whose root node corresponds to the entire road network graph G, and has the following properties: each descendant node n _i of the root node corresponds to a subgraph G _i , and the bottom layer of nodes are called leaf nodes; TKG-tree has two hyperparameters f and μ, which represent the number of branches of non-leaf nodes and the upper limit of the number of vertices of leaf nodes respectively; each node n _i contains a travel time matrix M _i and an inverted document D _i that records the object keyword information o.key;

4) Using the spatial text score function obtained in step 2) As the indicator for sorting the Top-K results, starting from the query point _vq , the road network index TKG-tree constructed in step 3) is used to find the spatial keyword object o ranked Top-K.

Furthermore, in step 1), the following concepts are defined:

a. In the edge of the road network, the travel time is used to represent the length of the edge, and the travel time of the edge will change with the time t, so the travel time function of the edge is recorded as ω(t); in the vertices of the road network, some of the vertices carry text information in the form of keywords. The vertex with spatial position information and text keyword information is called spatial keyword object o, which is expressed as:

o＝(v _o ,o.key)

In the formula, v _o represents the vertex position of the object, and o.key represents the object keyword information;

b. Model the road network as an undirected graph, expressed as:

Wherein, G is a road network graph, representing an undirected graph road network structure composed of several intersecting edges; v ₁ represents the first vertex, v _n represents the nth vertex, V = {v ₁ ,v ₂ ,...v _n } represents the set of all vertices in the road network; e ₁ represents the first edge, e _n represents the nth edge, E = {e ₁ ,e ₂ ,...e _n } represents the set of edges in the road network; ω ₁ (t) represents the travel time function of the first edge, ω _n (t) represents the travel time function of the nth edge, and W = {ω ₁ (t),ω ₂ (t),...ω _n (t)} represents the set of travel time functions associated with the corresponding edges;

c. In a road network, a path ρ from the starting point to the end point is represented by a series of adjacent connected vertex sequences < _vi ,... _vj >, where _vi represents the i-th vertex, _vj represents the j-th vertex, and P is used to represent the set of all paths from the starting point to the end point; let the travel time function of the path ρ be τ(t), then the shortest travel time function from the starting point to the end point τ ^* (t) is defined as follows:

τ ^* (t) = min{τ(t)|ρ∈P}

In the formula, τ(t) represents the travel time function of path ρ starting at time t; τ ^* (t) represents the shortest travel time function among all paths from the starting point to the end point starting at time t.

Further, the step 2) comprises the following steps:

2.1) Define the query parameter query based on the Top-K spatial keyword of the road network space:

query = <v _q ,q.key,t,k>

In the formula, v _q represents the query point, q.key represents the query keyword phrase, t represents the search time, and k represents the number of spatial keyword objects o returned;

2.2) Use the shortest travel time function τ ^* (t) to measure the spatial proximity between the spatial keyword object o and the query point v _q , and define the spatial score function f _s (o) as follows:

In the formula, Represents the shortest travel time between the vertex v _o where the spatial keyword object o is located and the query point v _q ;

2.3) Use the TF-IDF model to measure the text similarity between the spatial keyword object o and the query keyword phrase q.key, and define the text score function f _d (o) as follows:

In the formula, key and q.key represent the keyword and the keyword phrase of the query respectively, tf(key) represents the number of times the keyword key appears in the spatial keyword object o, and idf(key) represents the inverse frequency of the keyword key in all spatial keyword objects o. The importance of the keyword key increases in direct proportion to the number of times it appears in the spatial keyword object o, but at the same time it decreases in inverse proportion to the frequency of its appearance in all spatial keyword objects o.

2.4) Use the text score function f _d (o) and the space score function f _s (o) to get the space text score function The calculation formula is as follows:

In the formula, α represents the weight factor, represents the spatial text score function, which is obtained by weighted calculation of the spatial score function _fs (o) and the text score function _fd (o).

Furthermore, in step 3), the road network index TKG-tree is constructed by a graph cutting method. First, the entire road network graph G is taken as the root node, and then G is cut into f subgraphs of the same size, and they are taken as child nodes of the root node. Then, these subgraphs are cut recursively until the number of vertices contained in the final subgraph does not exceed μ; according to the topological relationship of the road network, the Floyd algorithm is run to obtain the travel time matrix _Mi of the node n _i . The matrix _Mi records the shortest travel time function τ ^* (t) between each vertex in the subgraph _Gi corresponding to the node n _i ; the keyword information o.key of all spatial keyword objects o in the subgraph _Gi corresponding to the node n _i is taken as the union, and the inverted document _Di of the node n _i is obtained.

Further, in step 4), after entering the query parameters, the spatial text score function As the index for sorting Top-K results, we search for it; first, we define a maximum priority queue Q and result set R, start the search from the subgraph where the query point _vq is located, add all spatial keyword objects o in the subgraph to the priority queue Q, and then search according to the spatial text score function. Sorting; use n _x to record the highest level node currently visited on the TKG-tree, mark the current search range as the subgraph G _x corresponding to the node, and define the spatial text score of the node Prune as an upper bound:

Where _fs (node) represents the shortest travel time from the query point _vq to the current subgraph _Gx , which is calculated using the travel time matrix _Mi of the road network index TKG-tree; represents the maximum text score that the spatial keyword object o can achieve, which is calculated using the inverted document _Di of the road network index TKG-tree; the spatial keyword objects o in the queue Q are dequeued one by one, and the spatial text scores are greater than the upper bound. The high spatial keyword object o is added to the result set R; if the queue Q is empty and the result set R is less than k, n _x is updated to the parent node of the original node, and the current search range is expanded to the subgraph corresponding to the updated n _x node. Change to the updated spatial text score of n _x nodes, repeat the above operation until the result set R has k results, and the algorithm ends automatically; the maximum priority queue Q and the upper bound It is guaranteed that the query point v _q to the kth result is globally optimal, so the Top-K space keyword object o can be found correctly.

Compared with the prior art, the present invention has the following advantages and beneficial effects:

1. The present invention takes into account the influence of time factors on the Top-K road network distance and has more practical application value.

2. Compared with other Top-K query methods in road network space, the present invention has shorter preprocessing time and lower storage cost.

3. The present invention has a millisecond query response time on data sets of different sizes and has good versatility and scalability.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of a logic flow of the method of the present invention.

FIG. 2 is a schematic diagram of a road network index TKG-tree used in the present invention.

DETAILED DESCRIPTION

The present invention is further described in detail below in conjunction with embodiments and drawings, but the embodiments of the present invention are not limited thereto.

As shown in FIG1 , this embodiment provides a Top-K spatial keyword query method based on a road network index, and the specific details are as follows:

1) The spatial keyword object, road network diagram and shortest travel time are defined:

a. In the edge of the road network, the travel time is used to represent the length of the edge, and the travel time of the edge will change with the time t, so the travel time function of the edge is recorded as ω(t); in the vertices of the road network, some of the vertices carry text information in the form of keywords. The vertex with spatial position information and text keyword information is called spatial keyword object o, which is expressed as:

o＝(v _o ,o.key)

In the formula, v _o represents the vertex position of the object, and o.key represents the keyword information of the object;

b. Model the road network as an undirected graph, expressed as:

Wherein, G is a road network graph, representing an undirected graph road network structure composed of several intersecting edges; v ₁ represents the first vertex, v _n represents the nth vertex, V = {v ₁ ,v ₂ ,...v _n } represents the set of all vertices in the road network; e ₁ represents the first edge, e _n represents the nth edge, E = {e ₁ ,e ₂ ,...e _n } represents the set of edges in the road network; ω ₁ (t) represents the travel time function of the first edge, ω _n (t) represents the travel time function of the nth edge, and W = {ω ₁ (t),ω ₂ (t),...ω _n (t)} represents the set of travel time functions associated with the corresponding edges;

c. In a road network, a path ρ from the starting point to the end point can be represented by a series of adjacent connected vertex sequences <v _i ,...v _j >, where v _i represents the i-th vertex, v _j represents the j-th vertex, and P can be used to represent the set of all paths from the starting point to the end point. Let the travel time function of the path ρ be τ(t), then the shortest travel time function from the starting point to the end point τ ^* (t) is defined as follows:

τ ^* (t) = min{τ(t)|ρ∈P}

In the formula, τ(t) represents the travel time function of path ρ starting at time t; τ ^* (t) represents the shortest travel time function among all paths from the starting point to the end point starting at time t.

2) Using the shortest travel time function τ ^* (t) obtained in step 1) to measure the spatial proximity of the spatial keyword object o; using the TF-IDF model to measure the text similarity of the spatial keyword object o; using the text score function and the spatial score function to perform weighted calculation to obtain the spatial text score function, which includes the following steps:

2.1) Define the query parameter query based on the Top-K spatial keyword of the road network space:

query = <v _q ,q.key,t,k>

In the formula, v _q represents the query point, q.key represents the query keyword phrase, t represents the search time, and k represents the number of spatial keyword objects o returned;

2.2) Use the shortest travel time function τ ^* (t) to measure the spatial proximity between the spatial keyword object o and the query point v _q , and define the spatial score function f _s (o) as follows:

In the formula, Represents the shortest travel time between the vertex v _o where the spatial keyword object o is located and the query point v _q .

2.3) Use the TF-IDF model to measure the text similarity between the spatial keyword object o and the query keyword phrase q.key, and define the text score function f _d (o) as follows:

In the formula, key and q.key represent the keyword and the keyword phrase of the query respectively, tf(key) represents the number of times the keyword key appears in the spatial keyword object o, and idf(key) represents the inverse frequency of the keyword key in all spatial keyword objects o; the importance of the keyword key increases in direct proportion to the number of times it appears in the spatial keyword object o, but at the same time it decreases in inverse proportion to the frequency of its appearance in all spatial keyword objects o.

2.4) Use the text score function f _d (o) and the space score function f _s (o) to get the space text score function The calculation formula is as follows:

In the formula, α represents the weight factor, represents the spatial text score function, which is obtained by weighted calculation of the spatial score function _fs (o) and the text score function _fd (o).

3) Use the edge and vertex information defined in step 1) to construct the road network index TKG-tree; the road network index TKG-tree is constructed by graph cutting, as shown in Figure 2, we set the number of branches f of non-leaf nodes to 2, and the maximum number of vertices μ of leaf nodes to 4; first, take the entire road network graph G as the root node, then cut G into f subgraphs of the same size, and use them as child nodes of the root node, and then continue to recursively cut these subgraphs until the number of vertices contained in the final subgraph does not exceed μ; according to the topological relationship of the road network, run the Floyd algorithm to obtain the travel time matrix _Mi of the node n _i , the matrix _Mi records the shortest travel time function τ ^* (t) between each vertex in the subgraph _Gi corresponding to the node n _i ; take the union of the keyword information o.key of all spatial keyword objects o in the subgraph Gi corresponding to the node _{n i} , and obtain the inverted document _Di of the node n _i .

4) Using the spatial text score function obtained in step 2) As the index for sorting the Top-K results, starting from the query point _vq , the road network index TKG-tree constructed in step 3) is used to find the spatial keyword objects ranked Top-K; first define a maximum priority queue Q and result set R, start the search from the subgraph where the query point _vq is located, add all the spatial keyword objects o in the subgraph to the priority queue Q and sort them according to the spatial text score function Sorting; use n _x to record the highest level node currently visited on the TKG-tree, mark the current search range as the subgraph G _x corresponding to the node, and define the spatial text score of the node Prune as an upper bound:

Where _fs (node) represents the shortest travel time from the query point _vq to the current subgraph _Gx , which is calculated using the travel time matrix _Mi of the road network index TKG-tree; represents the maximum text score that the spatial keyword object o can achieve, which is calculated using the inverted document _Di of the road network index TKG-tree; the spatial keyword objects o in the queue Q are dequeued one by one, and the spatial text scores are greater than the upper bound. The high spatial keyword object o is added to the result set R; if the queue Q is empty and the result set R is less than k, n _x is updated to the parent node of the original node, and the current search range is expanded to the subgraph corresponding to the updated n _x node. Change to the updated spatial text score of n _x nodes and repeat the above operation until the Top-K spatial keyword object o is found correctly.

The above embodiments are preferred implementation modes of the present invention, but the implementation modes of the present invention are not limited to the above embodiments. Any other changes, modifications, substitutions, combinations, and simplifications that do not deviate from the spirit and principles of the present invention should be equivalent replacement methods and are included in the protection scope of the present invention.

Claims (5)

1. A Top-K spatial keyword query method based on a road network index, characterized in that it comprises the following steps: 1) Define the relevant concepts of the road network, including the spatial keyword object o, the road network graph G and the shortest travel time function τ ^* (t) between two vertices; 2) Use the shortest travel time function τ ^* (t) obtained in step 1) to measure the spatial proximity of the spatial keyword object o, and obtain the spatial score function, denoted as f _s (o); use the TF-IDF model to measure the text similarity of the spatial keyword object o, and obtain the text score function, denoted as f _d (o); use the text score function f _d (o) and the spatial score function f _s (o) to perform weighted calculation to obtain the spatial text score function, denoted as 3) Based on the road network defined in step 1), the road network index TKG-tree is constructed using the edge and vertex information it contains; TKG-tree is a balanced tree structure obtained by graph cutting, whose root node corresponds to the entire road network graph G, and has the following properties: each descendant node n _i of the root node corresponds to a subgraph G _i , and the bottom layer of nodes are called leaf nodes; TKG-tree has two hyperparameters f and μ, which represent the number of branches of non-leaf nodes and the upper limit of the number of vertices of leaf nodes respectively; each node n _i contains a travel time matrix M _i and an inverted document D _i that records the object keyword information o.key; 4) Using the spatial text score function obtained in step 2) As the indicator for sorting the Top-K results, starting from the query point _vq , the road network index TKG-tree constructed in step 3) is used to find the spatial keyword object o ranked Top-K. 2. The Top-K spatial keyword query method based on road network index according to claim 1 is characterized in that in step 1), the following concepts are defined: a. In the edge of the road network, the travel time is used to represent the length of the edge, and the travel time of the edge will change with the time t, so the travel time function of the edge is recorded as ω(t); in the vertices of the road network, some of the vertices carry text information in the form of keywords. The vertex with spatial position information and text keyword information is called spatial keyword object o, which is expressed as: o＝(v _o ,o.key) In the formula, v _o represents the vertex position of the object, and o.key represents the object keyword information; b. Model the road network as an undirected graph, expressed as: Wherein, G is a road network graph, representing an undirected graph road network structure composed of several intersecting edges; v ₁ represents the first vertex, v _n represents the nth vertex, V = {v ₁ ,v ₂ ,...v _n } represents the set of all vertices in the road network; e ₁ represents the first edge, e _n represents the nth edge, E = {e ₁ ,e ₂ ,...e _n } represents the set of edges in the road network; ω ₁ (t) represents the travel time function of the first edge, ω _n (t) represents the travel time function of the nth edge, and W = {ω ₁ (t),ω ₂ (t),...ω _n (t)} represents the set of travel time functions associated with the corresponding edges; c. In a road network, a path ρ from the starting point to the end point is represented by a series of adjacent connected vertex sequences < _vi ,... _vj >, where _vi represents the i-th vertex, _vj represents the j-th vertex, and P is used to represent the set of all paths from the starting point to the end point; let the travel time function of the path ρ be τ(t), then the shortest travel time function from the starting point to the end point τ ^* (t) is defined as follows: τ ^* (t) = min{τ(t)|ρ∈P} In the formula, τ(t) represents the travel time function of path ρ starting at time t; τ ^* (t) represents the shortest travel time function among all paths from the starting point to the end point starting at time t. 3. The Top-K spatial keyword query method based on road network index according to claim 1, characterized in that the step 2) comprises the following steps: 2.1) Define the query parameter query based on the Top-K spatial keyword of the road network space: query＝<v _q ,q.key,t,k＞ In the formula, v _q represents the query point, q.key represents the query keyword phrase, t represents the search time, and k represents the number of spatial keyword objects o returned; 2.2) Use the shortest travel time function τ ^* (t) to measure the spatial proximity between the spatial keyword object o and the query point v _q , and define the spatial score function f _s (o) as follows: In the formula, Represents the shortest travel time between the vertex v _o where the spatial keyword object o is located and the query point v _q ; 2.3) Use the TF-IDF model to measure the text similarity between the spatial keyword object o and the query keyword phrase q.key, and define the text score function f _d (o) as follows: In the formula, key and q.key represent the keyword and the keyword phrase of the query respectively, tf(key) represents the number of times the keyword key appears in the spatial keyword object o, and idf(key) represents the inverse frequency of the keyword key in all spatial keyword objects o. The importance of the keyword key increases in direct proportion to the number of times it appears in the spatial keyword object o, but at the same time it decreases in inverse proportion to the frequency of its appearance in all spatial keyword objects o. 2.4) Use the text score function f _d (o) and the space score function f _s (o) to get the space text score function The calculation formula is as follows: In the formula, α represents the weight factor, represents the spatial text score function, which is obtained by weighted calculation of the spatial score function _fs (o) and the text score function _fd (o). 4. The Top-K spatial keyword query method based on road network index according to claim 1 is characterized in that: in step 3), the road network index TKG-tree is constructed by a graph cutting method, firstly taking the entire road network graph G as the root node, then cutting G into f subgraphs of the same size, and taking them as child nodes of the root node, and then continuing to recursively cut these subgraphs until the number of vertices contained in the final subgraph does not exceed μ; according to the topological relationship of the road network, running the Floyd algorithm to obtain the transit time matrix _Mi of the node n _i , the matrix _Mi records the shortest transit time function τ ^* (t) between each vertex in the subgraph _Gi corresponding to the node n _i ; taking the union of the keyword information o.key of all spatial keyword objects o in the subgraph _Gi corresponding to the node n _i , and obtaining the inverted document _Di of the node n _i . 5. The Top-K spatial keyword query method based on road network index according to claim 1 is characterized in that: in step 4), after the query parameters are input, the spatial text score function is used to As the index for sorting Top-K results, we search for it; first, we define a maximum priority queue Q and result set R, start the search from the subgraph where the query point _vq is located, add all spatial keyword objects o in the subgraph to the priority queue Q, and then search according to the spatial text score function. Sorting; use n _x to record the highest level node currently visited on the TKG-tree, mark the current search range as the subgraph G _x corresponding to the node, and define the spatial text score of the node Prune as an upper bound: Where _fs (node) represents the shortest travel time from the query point _vq to the current subgraph _Gx , which is calculated using the travel time matrix _Mi of the road network index TKG-tree; represents the maximum text score that the spatial keyword object o can achieve, which is calculated using the inverted document _Di of the road network index TKG-tree; the spatial keyword objects o in the queue Q are dequeued one by one, and the spatial text scores are greater than the upper bound. The high spatial keyword object o is added to the result set R; if the queue Q is empty and the result set R is less than k, n _x is updated to the parent node of the original node, and the current search range is expanded to the subgraph corresponding to the updated n _x node. Change to the updated spatial text score of n _x nodes, repeat the above operation until the result set R has k results, and the algorithm ends automatically; the maximum priority queue Q and the upper bound It is guaranteed that the query point v _q to the kth result is globally optimal, so the Top-K space keyword object o can be found correctly.