CN114817772B

CN114817772B - A segmented parallel expansion method for keyword optimal path query

Info

Publication number: CN114817772B
Application number: CN202210510076.3A
Authority: CN
Inventors: 牛保宁; 刘蒙蒙; 杨茸
Original assignee: Taiyuan University of Technology
Current assignee: Taiyuan University of Technology
Priority date: 2022-05-11
Filing date: 2022-05-11
Publication date: 2025-06-27
Anticipated expiration: 2042-05-11
Also published as: CN114817772A

Abstract

The present invention belongs to the field of spatial data query technology, and specifically is a segmented parallel expansion method for keyword optimal path query. It includes the following steps. S100: Calculate the minimum cost value between any two vertices in the query graph, the target value corresponding to the minimum cost value, the minimum target value, and the cost value corresponding to the minimum target value, and record the minimum cost value and the minimum target value in the query graph at the same time. S200: Keyword inverted list construction: Combine all keyword information of the vertex into a non-overlapping keyword set, construct a keyword inverted list of the form {w _i :v _j }, and record the vertices corresponding to the keyword. S300: Skip vertices that are not related to the query keyword, and construct the keyword vertex path with the smallest target value, recorded as And the keyword vertex path with the smallest cost value is recorded as S400: Divide the keyword vertex path, and expand the divided path in segments in parallel.

Description

Segmentation parallel expansion method for keyword optimal path query

Technical Field

The invention belongs to the technical field of space data query, and particularly relates to a segmentation parallel expansion method for keyword optimal path query.

Background

With the diversification of the demands of people on travel paths, the path query is not just a common shortest path query, and people often comprehensively consider other factors such as path time overhead and interest points of path coverage. Consider the scenario where a user wants to travel to a certain location, and wants to find a path from a specified location, through a path meeting a point of interest specified by the user, and finally to an end point, where the shorter and better the time the path takes is on the premise of meeting the tourist's travel budget (hereinafter referred to as cost threshold). The above-mentioned query is called Keyword-aware Optimal Route Query (KOR) best path query. KOR is a path query that satisfies the keyword full coverage, cost threshold (path length) and minimum target value (time overhead). The query is typically used for travel planning, path navigation, and other applications.

Shortening the execution time is an important goal for KOR optimization, but two challenges now exist. The first challenge is to reduce the search size. The most advanced technology in the prior art uses adjacent edge expansion, which essentially traverses from the starting point one by one, or uses keyword vertex expansion, skips the vertex irrelevant to the keyword to continuously expand the keyword vertices except the adjacent vertex, but the method needs to calculate the simplified Skyline path in preprocessing, and has huge space-time overhead. Although the two methods adopt various pruning strategies to shorten the execution time during expansion, such as approximate dominant pruning, global priority expansion, feasible solution target value pruning, minimum cost value pruning and the like, the search scale of the two methods increases exponentially with the increase of the path length or the search depth, and the execution time is still unacceptable.

The second challenge is to combine existing path expansion methods with pruning strategies to further shorten execution time. The most advanced technology at present is essentially serial expansion, i.e. expanding one vertex at a time in the query phase or the preprocessing phase, but the method has reached its performance barrier. Parallel expansion paths may be a good choice. Related studies have demonstrated the feasibility of shortest path parallel path expansion under single constraint, such as expanding single source shortest paths and full source shortest paths in parallel. However, the current research on parallel expansion of the multi-constraint shortest paths is not related.

The prior art has the following problems:

(1) When searching long paths, the searching scale of the existing algorithm increases exponentially along with the increase of the path length or the searching depth, and the execution time is too long.

(2) Parallel expansion technology is mostly applied to shortest path query under single constraint condition, and research on multi-constraint path query such as KOR problem is not involved yet. In order to realize the parallel expansion of the KOR problem, the invention needs to explore how to parallelize the serial multi-constraint expansion.

Disclosure of Invention

The invention aims to solve the problems and provides a segmentation parallel expansion method for keyword optimal path query.

The invention adopts the following technical scheme that the segmentation parallel expansion method for the keyword optimal path query comprises the following steps.

S100, calculating a minimum cost value b (V _i,v_j) between any two vertexes in the query graph and a target value o _σ(v_i,v_j corresponding to the minimum cost value, and a minimum target value o (V _i,v_j) and a cost value b _τ(v_i,v_j corresponding to the minimum target value, and simultaneously recording the minimum cost value b _min and the minimum target value o _min in the query graph G= (V, E).

And S200, constructing a keyword inverted list, namely combining all keyword information { v.w ₁,v.w₂, & gt } of the vertexes into a non-coincident keyword set, constructing a keyword inverted list in the shape of { w _i:v_j }, and recording the vertexes corresponding to the keywords.

S300, skipping the vertex irrelevant to the query keyword, constructing the keyword vertex path with the minimum target value asThe keyword vertex path with the minimum cost value is marked as

S400, dividing the keyword vertex paths, and expanding the divided paths in a segmented parallel manner.

The step S300 includes the steps of,

S310, giving a queryv_s、v_t、And delta respectively represents a query starting point, a query end point, a keyword set which needs to be covered by a query path and a cost threshold value, and is hidden and not containedThe method comprises the steps of (1) reserving a starting point, an ending point and keyword vertexes, constructing a simplified keyword vertex query graph G ', directly acquiring the keyword vertexes according to a keyword inverted list in S200 in the implementation process, and then adding the query starting point and the query ending point to form the query graph G ', wherein the query graph G ' contains information including (1) weights b(v_i,v_j)、o_σ(v_i,v_j)、o(v_i,v_j)、b_τ(v_i,v_j) between any two vertexes acquired in a preprocessing stage, a minimum cost value b _min and a minimum target value o _min in the query graph, and (2) querying the starting point, the ending point and the keyword vertexes.

S320, in the keyword vertex query graph G', keyword vertices are arranged and combined, traversed through breadth-first search, and finally returned to meet the keyword full coverage and cost threshold valueWherein the method comprises the steps ofThe vertex path of the keyword comprising the smallest target value is recorded asThe keyword vertex path with the minimum cost value is marked as

Step S320 includes the steps of giving a queryWherein the method comprises the steps ofw_i＝{v_k,v_m},w_j＝{v_x,v_y}。

S321, first construct an initial tag at v _s Placing it in a priority queue.

S322, expanding from the starting point to all keyword vertexes, and constructing labels from v _s to each keyword vertexAnd calculating a global priority enqueue, wherein the smaller the global priority, the higher the global priority.

S323, selecting the label with highest global priorityDequeuing at this timeHas included the keyword w _j, directionVertex v _i、v_j related to keyword w _i which is not contained is expanded, and new label is constructedAnd judging whether the new label meets the cost threshold and the approximate dominant condition, if so, calculating the global priority and then enqueuing, otherwise, discarding.

S324, continuing to select the label with the highest priority level for expansion, repeating the process S323 until the label is expanded to a terminal v _t, and selecting a path corresponding to the label meeting the full coverage of the keyword and having the minimum cost threshold and the target value as a mark

S325, continuing to select the label expansion with the highest priority level, repeating the process S323 until the label expansion reaches the terminal v _t, and selecting a path corresponding to the label meeting the full coverage of the keyword, the cost threshold and the minimum cost value as the path

In step S322, the tagIs expressed as global priority ofThe minimum target value from v _s to v _t is o (v _s,v_t), the priority factor β is set, 1< β <2, and the smaller the global priority of the tag is, the higher the global priority of the tag is.

Before step S400 is performed, the keyword vertex path with the smallest target value constructed in step S300 is selectedKeyword vertex path with minimum cost valueThe selection is carried out, and the specific selection process is as follows:

in construction of In the process of (2), the returned target value is the smallestIs marked asSimultaneously recording the corresponding target value O _min and cost value B _max, and returning the minimum cost valueIs marked asSimultaneous recording of B _min and O _max, availability of [ B _min,B_max ] and [ O _min,O_max ], for assuranceThe effective path is returned for the path expansion, and O _max is taken as the upper bound of the target value, namely, the path target value returned in the worst case is O _max, namelyTo expand the path of the basis, byAndThe key word vertex path boundaries are shared by the following cases;

1) Is not the air-conditioner and is not the air-conditioner, Not null, and B _min≤B_max、O_min≤O_max, in the path-segment parallel expansion, toTaking O _max as the upper boundary of the target value,The local cost threshold in (a) constrains the expansion of each path segment.

2)Is in the form of a hollow body,Not empty, path segment expansionTo be accurate.

3)Is in the form of a hollow body,For null, it is indicated that the cost threshold is too low, and the keyword vertex path with the smallest reconstruction target value for improving the cost threshold is recorded asThe keyword vertex path with the minimum cost value is marked as

Step S400 specifically includes the following steps,

And S410, setting parallelism, dividing the keyword vertex path into a plurality of sections, wherein all vertices except for the head vertex and the tail vertex in the keyword vertex path are keyword vertices, and dividing the path by using the keyword vertices.

And S420, carrying out parallel expansion on path segments, judging whether cost values of all paths from the initial point vertexes to the target vertexes of each path through the non-keyword vertexes are smaller than or equal to a local cost threshold value at the target vertexes when the path segments are expanded, if yes, carrying out feasible solution target value pruning strategy comparison applicable to parallel expansion, if yes, calculating global priority, and then queuing, otherwise, discarding.

In step S410, the principle of parallelism setting is to make the keyword vertexes in each path segment as uniform as possible so that the number of vertexes in each path segment is similar when expanding, thereby achieving the purpose of the close expansion time of each path segment.

In step S420, the judgment inequality of comparison of the feasible target value pruning strategy is:

Wherein, the AndRepresenting the vertices of the keywords,Is fromExpansion to v _k,v_k is fromTo the point ofA label of one vertex passing in the middle, if the constraint is satisfiedEnqueue continues expanding, otherwise discard

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

(1) The invention provides a thought for converting a multi-constraint KOR problem into a limited shortest path problem, namely, firstly constructing a keyword vertex path meeting the full coverage and cost threshold of keywords, and then considering the minimum constraint of a target value in detailed expansion to segment the problem.

(2) Aiming at the problem of long execution time of long path search, the invention provides a segmentation parallel expansion method (PSE-KOR) for keyword optimal path query, which is characterized in that a keyword vertex path is constructed, then the keyword vertex is taken as a boundary to divide the path into a plurality of sections, the search scale (depth) during long path search is reduced, and then the execution time of the long path KOR is further shortened by adopting a parallel expansion mode.

(3) And for path expansion of each segment, local cost threshold pruning is provided to restrict expansion direction and search depth, and meanwhile, the association degree between the segmented paths is reduced. And meanwhile, the practical solution target value pruning strategy of approximate dominant pruning, global priority expansion and applicable parallel expansion is utilized to accelerate the expansion.

Drawings

FIG. 1 is a diagram of a query graph;

FIG. 2 is a schematic diagram of a keyword vertex path;

FIG. 3 is a schematic diagram of the construction of a keyword vertex path;

FIG. 4 is a keyword vertex path example.

Detailed Description

Aiming at the problems, the invention provides a segmentation parallel expansion method for keyword optimal path query, which comprises the steps of firstly skipping vertexes irrelevant to query keywords, expanding the vertexes of the keywords only, constructing keyword vertex paths, dividing the paths into multiple sections by taking the vertexes of the keywords as boundaries, expanding the paths in parallel, and finally splicing the paths into a complete path. In order to reduce the association degree among all road sections and the search scale, the invention also provides a local cost threshold and feasible solution target value pruning suitable for parallel expansion, and the local cost threshold and the feasible solution target value pruning are matched with the parallel expansion.

Before further explanation, the KOR definition will be explained first:

KOR is based on a road network, which can be abstracted into a query graph as shown in fig. 1.

Definition 1 query graph g= (V, E) is made up of vertex set V and edge set E. Any V epsilon V represents the interest point, the geographic position of V is represented by longitude and latitude, and the keyword set marked as v.loc and V is represented asThe path (v _i,v_j) connecting the neighbors v _i and v _j is called a edge, denoted as E, E. Each edge has two attributes, cost value b (v _i,v_j) and target value o (v _i,v_j).

As shown in FIG. 1, the typical cost value is represented by the value outside the brackets, and the target value is represented by the time required to pass the edge, represented by the value inside the brackets. Table 1 lists the keyword sets corresponding to the vertices in fig. 1.

Table 1 vertex keyword information

Definition 2 Path p= (v ₀,v₁,....v_n) represents a path from v ₀ through v ₁,…v_n-1 to v _n, and p-overlaid keywords are expressed as

According to definition 2, the cost value and the target value of path p are respectively:

definition of 3KOR A KOR query Q is a four-tuple v_s、v_t、And delta represents the query start point, end point, the covered keyword set, and cost threshold, respectively. Let p _s,t denote the set of paths from v _s to v _t, and p _cand denote the set of possible paths p that meet the keyword full coverage and cost threshold, i.eOptimal path of KOR

The technical scheme of the invention is further described as follows:

S100, calculating a minimum cost value b (V _i,v_j) between any two vertexes in the query graph and a target value o _σ(v_i,v_j corresponding to the minimum cost value, a minimum target value o (V _i,v_j) and a cost value b _τ(v_i,v_j corresponding to the minimum target value by using a Floyd algorithm, recording the minimum cost value b _min and the minimum target value o _min in G= (V, E), and storing the minimum cost value b _min and the minimum target value o _min in a memory.

And 200, constructing a keyword inverted index, namely combining all keyword information { v.w ₁,v.w₂..degree } of the interest points into a non-coincident keyword set, constructing a keyword inverted index table, and recording the interest points corresponding to the keywords, wherein the table 2 is shown.

TABLE 2 keyword inverted index Table

Definition 4 keyword vertices givenFor keywordsIf a certain vertexCovering keywords w _i, i.eThen call forIs a vertex covering the keyword w _i.

Definition 5 keyword vertex Path givenContinuously checking uncovered keywords from v _s, expanding the keywords to corresponding vertexes to obtain paths which are expanded from v _s to v _t and meet the full coverage and cost threshold of the keywords, and marking the paths asWeighing scaleIs a keyword vertex path.

Step S300 includes the steps of:

S310, giving a query v_s、v_t、And delta respectively represents a query starting point, a query end point, a keyword set which needs to be covered by a query path and a cost threshold value, and is hidden and not containedThe method comprises the steps of (1) reserving a starting point, an ending point and keyword vertexes, constructing a simplified keyword vertex query graph G ', directly acquiring the keyword vertexes according to a keyword inverted list in S200 in the implementation process, and then adding the query starting point and the query ending point to form the query graph G ', wherein the query graph G ' contains information including (1) weights b(v_i,v_j)、o_σ(v_i,v_j)、o(v_i,v_j)、b_τ(v_i,v_j) between any two vertexes acquired in a preprocessing stage, a minimum cost value b _min and a minimum target value o _min in the query graph, and (2) querying the starting point, the ending point and the keyword vertexes.

A simplified keyword vertex query graph G' is shown in fig. 2. The broken lines connect the keyword vertices to form a keyword vertex query graph.

S320, in the keyword vertex query graph G', keyword vertices are arranged and combined, traversed through breadth-first search, and finally returned to meet the keyword full coverage and cost threshold valueWherein the method comprises the steps ofThe vertex path of the keyword comprising the smallest target value is recorded asThe keyword vertex path with the minimum cost value is marked asAs shown in fig. 3, the keyword vertex path with the smallest target value may be returned.

S321, first construct an initial tag at v _s Placing it in a priority queue.

Label (Label)Is expressed as global priority ofThe minimum target value from v _s to v _t is o (v _s,v_t), the priority factor β is set, 1< β <2, and the smaller the global priority of the tag is, the higher the global priority of the tag is.

Cost threshold-the path is meeting the guest's travel budget.

The approximation governs that given a parameter a, a slightly greater than 1 (e.g., a=1.1), if the start and end points of path p _i、p_j are the same,B (p _i)≤b(p_j) andPath p _i approximately dominates that p _j,p_j is pruned.

Target correction given a query graph g= (V, E) and a queryKnown tagsMinimum cost value b _min, minimum target value o _min, which is corrected to target value of Is referred to as a correction ratio, where 0< epsilon <1.

S325, continuing to select the label expansion with the highest priority level, repeating the process S323 until the label expansion reaches the end point _v t, and selecting a path corresponding to the label meeting the full coverage of the keyword, the cost threshold and the minimum cost value as a mark

The expansion result is shown in G' of FIG. 4, v ₂、v₄ is in constructionKeyword vertices that were discarded.

The keyword vertex path with the smallest target value constructed in step S300Keyword vertex path with minimum cost valueThe selection is carried out, and the specific selection process is as follows:

in construction of In the process of (2), the returned target value is the smallestIs marked asSimultaneously recording the corresponding target value O _min and cost value B _max, and returning the minimum cost valueIs marked asB _min and O _max were recorded simultaneously. [ B _min,B_max ] and [ O _min,O_max ] can be obtained. To ensure toReturns the effective path for the underlying path extension, as represented by O _max (i.e) As an upper bound to the target value, the worst case return path target value is O _max, i.e.To expand the path of the basis. In the expansion stage, byAndThe key vertex path boundaries that make up share the following:

(1) Is not the air-conditioner and is not the air-conditioner, Not empty, and B _min≤B_max、O_min≤O_max, in path segment expansion, toTaking O _max as the upper boundary of the target value,The local cost threshold in (a) constrains the expansion of each path segment.

(2)Is in the form of a hollow body,Not empty, path segment expansionTo be accurate.

(3)Is in the form of a hollow body,For null, it is indicated that the cost threshold is too low, and the keyword vertex path with the smallest reconstruction target value for improving the cost threshold is recorded asThe keyword vertex path with the minimum cost value is marked as

The keyword vertex path with the smallest target value, therefore, has the smallest target value O _min, since the solution is being performedWhen the target value is minimum, the path cost value is required to meet the cost threshold value, so that the contractThe path cost value of (3) is B _max.

The keyword vertex path with the smallest cost value has the smallest target value B _min because the solution is being carried outWhen the target value cost value is minimum, there is no constraint on the target value, so the contractThe path cost value of (3) is O _max.

And (3) the minimum target value of the whole road network diagram and the minimum cost value of the whole road network diagram are respectively represented by o _min and b _min.

From the above, it can be seen that in constructionAnd obtaining two keyword vertex paths with the minimum target value and the minimum cost value, and selecting a specific expansion basis according to the three conditions in the actual expansion process.

S400, dividing the keyword vertex paths, and expanding the divided paths in a segmented parallel manner. The method comprises the following specific steps:

All vertices in the keyword vertex path except the head and tail vertices are keyword vertices, so the path can be segmented by using the keyword vertices. As shown in fig. 4, the pathCan be divided into three sections v _s→v₁、v₁→v₃、v₃→v_t or two sections v _s→v₁→v₃、v₃→v_t.

The principle of setting the parallelism is that the keyword vertexes in each path segment are uniform as much as possible so that the number of vertexes in each path segment is similar when expanding, thereby achieving the purpose of the approaching expanding time of each path segment.

Feasible solution target value pruning when obtaining a feasible path p _i(p_i∈p_cand), taking the target value o (p _i) as pruning condition, if the target value of the path p _j(p_j∈p_cand) is larger than o (p _i), namely o (p _i)＜o(p_j), then p _j is pruned.

Local cost threshold value-known keyword vertex pathTotal cost value for the pathVertex for any two adjacent keywordsAndWhen the path is expanded, the methodAs a slaveTo the point ofThe local cost threshold of the path expansion is calculated.

When the keyword vertex path is constructed, two constraint conditions of keyword full coverage and cost threshold are satisfied, and the local cost threshold of each path segment is recorded, so that the local cost threshold can be used for replacing global cost threshold constraint when each path segment is expanded in parallel. The local cost threshold value only constrains each path and is independent from other paths, so that the association degree between paths can be reduced. The judgment inequality of comparison of the viable solution target value pruning strategy is as follows:

Claims

1. A segmented parallel expansion method for keyword optimal path query, characterized by comprising the following steps:

S100: Calculate the minimum cost value b(v _i ,v _j ) between any two vertices in the query graph, the target value o _σ (v _i ,v _j ) corresponding to the minimum cost value, the minimum target value o(v _i ,v _j ) and the cost value b _τ (v _i ,v _j ) corresponding to the minimum target value, and record the minimum cost value b _min and the minimum target value o _min in the query graph G=(V,E);

S200: constructing a keyword inverted list: combining all keyword information {vw ₁ ,vw ₂ ,...} of the vertices into a non-overlapping keyword set, constructing a keyword inverted list of the form { _wi : _vj }, and recording the vertices corresponding to the keywords;

S300: Skip vertices that are not related to the query keyword and construct the keyword vertex path with the smallest target value, recorded as And the keyword vertex path with the smallest cost value is recorded as

S400: dividing the keyword vertex path, and expanding the divided path in segments in parallel; step S400 includes the following steps:

S410: setting the degree of parallelism, dividing the keyword vertex path into multiple segments, all vertices except the first and last vertices in the keyword vertex path are keyword vertices, and the keyword vertices are used to segment the path;

The principle of setting the degree of parallelism is to make the keyword vertices in each path segment as uniform as possible so that the number of vertices in each path segment is close during expansion, thereby achieving the purpose of close expansion time for each path segment; in actual parallelism, the degree of parallelism can be set according to the number of keyword vertices in the keyword vertex path or by measuring the size of the local cost threshold of each segment;

S420: Expand the path segments in parallel. When expanding the path segments, determine whether the cost values of all paths from the starting point vertex through the non-keyword vertex to the target vertex of each path segment are less than or equal to the local cost threshold at the target vertex. If so and not dominated by the approximation, compare the target value pruning strategy of feasible solutions applicable to parallel expansion. If the judgment condition is met, calculate the global priority and enter the queue, otherwise it will be discarded.

The judgment inequality for the comparison of feasible solution target value pruning strategies is:

in, and Represents the keyword vertex, is from Expand to v _k , v _k is from arrive The label of a vertex in the middle; if the constraint is satisfied, then Enter the team and continue to expand, otherwise discard

2. The segmented parallel expansion method for keyword optimal path query according to claim 1 is characterized in that: the step S300 comprises the following steps:

S310: Given a query v _s 、v _t 、 and Δ represent the query starting point, query end point, and keyword set and cost threshold that the query path needs to cover, respectively. The vertex of any query keyword in S200 is retained, and the starting point, end point and keyword vertex are retained to construct a simplified keyword vertex query graph G′. In the implementation process, the keyword vertex is directly obtained according to the keyword inverted list in S200, and then the query starting point and query end point are added to form the query graph G′; the query graph G′ contains the following information: (1) the weights b(v _i ,v _j ), o _σ (v i ,v j ), o(v _i ,v _j ), b _τ (v _i ,v _j ) _between any two vertices obtained in the preprocessing stage, as well as the minimum cost value b _min and the minimum target value o _min in the query graph; (2) the query starting point, end point and keyword vertex _;

S320: In the keyword vertex query graph G′, the keyword vertices are arranged and combined, and they are traversed through breadth-first search, and finally the ones that meet the keyword full coverage and cost threshold are returned. in The path including the keyword vertex with the smallest target value is recorded as The keyword vertex path with the smallest cost value is recorded as

3. The segmented parallel expansion method for keyword optimal path query according to claim 2 is characterized in that: the step S320 comprises the following steps: given a query in w _i ={v _k , v _m }, w _j ={v _x , v _y };

S321: First construct the initial label at _vs Put it into the priority queue;

S322: Expand from the starting point to all keyword vertices and construct labels from _vs to each keyword vertex And calculate the global priority and enter the queue, where the smaller the global priority, the higher the global priority;

S323: Select the label with the highest global priority Out of the team, at this time Already contains the keyword w _j , to Expand the vertices v _i and v _j related to the keyword w _i that has not yet been included and construct a new label And determine whether the new label meets the cost threshold and approximate dominance conditions. If so, it is added to the queue after calculating the global priority, otherwise it is discarded;

S324: Continue to select the label with the highest priority to expand, repeat the process S323 until the end point v _t is reached, and select the path corresponding to the label that satisfies the full coverage of keywords, the minimum cost threshold and the target value, and record it as

S325: Continue to select the label with the highest priority to expand, repeat the process S323 until the end point v _t is reached, and select the path corresponding to the label that meets the keyword full coverage, cost threshold and minimum cost value, and record it as

4. The segmented parallel expansion method for keyword optimal path query according to claim 3 is characterized in that: in the step S322, the tag The global priority is expressed as The minimum target value from _vs to _vt is o( _vs , _vt ), and the priority factor β is set, 1＜β＜2. The smaller the global priority of the label, the higher the global priority of the label.

5. The segmented parallel expansion method for keyword optimal path query according to claim 4 is characterized in that: before the step S400, the keyword vertex path with the smallest target value constructed in step S300 is And the keyword vertex path with the smallest cost value Make a selection. The specific selection process is as follows:

In construction In the process, the target value returned is the smallest Recorded as At the same time, the corresponding target value O _min and cost value B _max are recorded; the one with the smallest cost value is returned. Recorded as Record B _min and O _max at the same time; [B _min , B _max ] and [O _min , O _max ] can be obtained; to ensure The path expansion based on will return a valid path, with O _max as the upper bound of the target value, that is, the path target value returned in the worst case is O _max , that is, To expand the path based on and There are several situations for the composed keyword vertex path boundaries;

1) is not null, is not empty, and B _min ≤ _{B max} , O _min ≤ O _max , then in the path segmentation parallel expansion, and O _max is used as the upper limit of the target value. The local cost threshold in constrains the expansion of each path;

2) is empty, Not empty, the path segment is extended to shall prevail;

3) is empty, If it is empty, it means that the cost threshold is too low. Increase the cost threshold to reconstruct the keyword vertex path with the smallest target value and record it as And the keyword vertex path with the smallest cost value is recorded as