CN109840620B - Query method for k nearest neighbor node pairs in multi-attribute time sequence traffic network - Google Patents
Query method for k nearest neighbor node pairs in multi-attribute time sequence traffic network Download PDFInfo
- Publication number
- CN109840620B CN109840620B CN201811636467.XA CN201811636467A CN109840620B CN 109840620 B CN109840620 B CN 109840620B CN 201811636467 A CN201811636467 A CN 201811636467A CN 109840620 B CN109840620 B CN 109840620B
- Authority
- CN
- China
- Prior art keywords
- path
- node
- time
- constraint
- attribute
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 60
- 238000010586 diagram Methods 0.000 claims abstract description 24
- 238000004364 calculation method Methods 0.000 claims abstract description 11
- 238000013507 mapping Methods 0.000 claims abstract description 3
- 230000002441 reversible effect Effects 0.000 claims description 40
- 230000008569 process Effects 0.000 claims description 22
- 238000012545 processing Methods 0.000 claims description 5
- 238000006116 polymerization reaction Methods 0.000 claims description 3
- 230000000379 polymerizing effect Effects 0.000 claims description 3
- 230000004931 aggregating effect Effects 0.000 claims description 2
- 238000013138 pruning Methods 0.000 description 4
- 230000003068 static effect Effects 0.000 description 4
- 238000012546 transfer Methods 0.000 description 4
- 230000002457 bidirectional effect Effects 0.000 description 3
- 230000001186 cumulative effect Effects 0.000 description 3
- 238000013461 design Methods 0.000 description 3
- 238000005192 partition Methods 0.000 description 3
- NRNCYVBFPDDJNE-UHFFFAOYSA-N pemoline Chemical compound O1C(N)=NC(=O)C1C1=CC=CC=C1 NRNCYVBFPDDJNE-UHFFFAOYSA-N 0.000 description 3
- 238000004458 analytical method Methods 0.000 description 2
- 238000007796 conventional method Methods 0.000 description 2
- 238000011161 development Methods 0.000 description 2
- 238000010845 search algorithm Methods 0.000 description 2
- 230000002123 temporal effect Effects 0.000 description 2
- 241000221095 Simmondsia Species 0.000 description 1
- 235000004433 Simmondsia californica Nutrition 0.000 description 1
- 230000003044 adaptive effect Effects 0.000 description 1
- 230000002776 aggregation Effects 0.000 description 1
- 238000004220 aggregation Methods 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000010006 flight Effects 0.000 description 1
- 239000000446 fuel Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000012163 sequencing technique Methods 0.000 description 1
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/30—Computing systems specially adapted for manufacturing
Landscapes
- Navigation (AREA)
Abstract
The invention discloses a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network, which comprises the steps of mapping a multi-attribute time sequence diagram of the traffic network into a two-dimensional coordinate system; in a two-dimensional coordinate system, dividing all nodes in the traffic network map into two by using a straight line L parallel to a y axis, respectively calculating k nearest neighbor node pairs on the left side and the right side of the straight line L, and then selecting the whole k nearest neighbor node pairs; finding any grid c on the right side of the straight line L and on the left side of the straight line L 1 R neighbor grid c of (c) 2 Calculation grid c 1 Node v in (a) s To c 2 Node v in (a) d Is a multi-constraint timing path of (a); and calculate c 2 Node v in d To c 1 Node v in s Is a multi-constraint timing path of (a); slave node v s To node v d Multiple constraint timing path of (a) and node v d To node v s K nearest neighbor node pairs conforming to multiple constraints are selected from the multiple constraint timing paths. The invention can find out the path which accords with the constraint between two points in the traffic network and has the shortest distance, thereby meeting the travel requirement.
Description
Technical Field
The invention relates to the field of traffic networks, in particular to a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network.
Background
Along with the rapid development of social economy, traffic becomes more complex while being developed day by day, and along with the change of time sequence information, whether two points are communicated or not, the congestion condition of a road between the two points, the oil consumption of an automobile and the like can be changed, so that how to efficiently and reasonably conduct city planning and travel arrangement becomes one of the problems puzzling people. The present method is proposed to solve this problem. For example, a user may need to design a 2-day travel plan, consider factors in making hotel reservations, travel route planning [3], including the earliest departure time of the hotel, the latest arrival time at the attraction, the traffic cost budget from the hotel to the attraction, the run time, and the distance between the two points, among others. Thus, k nearest neighbor node pair queries (k-Closest-Pairs-Query, k-CPQ) in traffic networks have attracted attention. In a conventional sense, given two sets of points of interest P and Q on the road, then k-CPQ returns k node pairs of interest from P x Q, and the distance between these node pairs is the first k small. For this scenario of travel planning, P is the hotel set and Q is the attraction set. In addition, the traffic network has time sequence information, and the departure time of the vehicles is arranged according to the existing schedule, so that people need to consider the time sequence information when planning the travel route.
In public transportation networks, each vehicle has the attribute of travel distance, travel cost and the like from the departure place to the destination in addition to the time sequence information. Often people will also put some corresponding constraints on these properties when considering paths to indicate their requirements for the path. For example, a user may want to visit several attractions in a city of the ocean in three days, they want to be able to visit two attractions each day between 8:30 and 10:30 a.m., and want to visit the two attractions each day the distance between them is nearest, and the time from one attraction to the other is no more than 45 minutes, the cost of the lift is no more than 70 yuan, how should the travel group arrange the daily tour? The problem can be abstracted into how to solve the query problem of k nearest neighbor nodes meeting a plurality of constraints in the multi-attribute time sequence traffic network, which has important significance for various applications in real life.
The existing k-CPQ solving methods are mainly divided into two types, one is to solve the k-CPQ in Euclidean space, and the other is to solve the k-CPQ in other metric space. First, methods in Euclidean space are described, corral et al [ 1]]Assuming that R is already * Index the interest point set P and Q in the tree respectively, then utilize R * The hierarchical nature of the tree improves pruning capability. To quickly find the distance between node pairs, [2 ]][3]In addition, the scanning efficiency is further improved by selecting a good scanning axis and scanning direction. Yang and Lin [4 ]]A new index structure bRdnn-tree is proposed for tracking nearest neighbors in Q for each node in P. Next, methods in other metric spaces are described, gao et al [5]Three methods based on depth-first, best-first and combinations thereof are proposed, using M-tree [6 ]]And processing k-CPQ. Kurasawa et al [7]An adaptive multi-partition method based on divide-and-conquer method is proposed to solve the k-CPQ problem, the basic idea of which is to reduce the upper bound of the distance of the k-th nearest neighbor pair by continuous iteration.
In addition, the k-CPQ problem is often associated with similarity join queries, and the goal of the similarity join algorithm is to find node pairs that are no more than ε apart. Jacox et al [8] propose the basic idea behind the fast-ranking based approach, which recursively divides the data into smaller partitions. The method of Fredriksson et al [9] was modified as described in [8 ]. The similarity join problem was studied by Sarma et al [10] and Wang et al [11] based on the Map-Reduce method, which partitions the data space based on the underlying data distribution. As described above, a smaller value may lead to incomplete results, while a larger value may incur excessive overhead due to difficulty in selecting an appropriate epsilon value, so that the method of solving the similarity join cannot effectively deal with the k-CPQ problem.
In addition, the existing analysis methods have the following problems:
(1) The analysis method is based on static diagrams, and time sequence information is not considered. Traffic networks in real life tend to have time charts rather than static charts, for example, traffic roads in different time periods have different crowds, resulting in different running times, different prices for flights in different time periods, etc., whereas conventional methods only consider the situation on static charts and thus do not fit the real world situation well.
(2) Only one constraint on the path is simply considered. In view of the current research, most node distance studies consider only one target or a target under a single constraint, such as the classical Dijkstra algorithm, which considers only one target of path length, and many methods consider only the shortest path under the constraint of a given running cost. However, in real life, people often consider a plurality of factors in activities such as traveling, for example, total traveling time, total automobile fuel consumption budget and the like when starting from point a to point B, and after comprehensively considering the plurality of factors, a path which is most in line with the conditions is selected, so that the practical problem in life cannot be solved far enough if only one constraint is considered.
(3) The accuracy is not high and the running time is long. At present, no special study is made to deal with the multi-constraint k nearest neighbor node pair query problem on the timing diagram, and if the conventional method is applied to this aspect, the path between any two nodes in the diagram and the accumulated value of each attribute on the path need to be calculated, and then k node pairs with the shortest path conforming to the constraint are selected as a result set. And when calculating the path between each node pair, the shortest path meeting the attribute constraint needs to be calculated for each attribute, if W attributes exist, the W shortest paths need to be calculated, and then intersection sets are screened out from the W path sets, so that the method is not very high in both efficiency and accuracy.
[1]A.Corral,Y.Manolopoulos,Y.Theodoridis,and M.Vassilakopoulos.Algorithms for processing k-closest-pair queries in spatial databases.DKE,49(1):67–104,2004[2].
[2]H.Shin,B.Moon,and S.Lee.Adaptive multi-stage distance join processing.ACM SIGMOD Record,29(2):343–354,2000.
[3]H.Shin,B.Moon,and S.Lee.Adaptive and incremental processing for distance join queries.IEEE TKDE,15(6):1561–1578,2003.
[4]C.Yang and K.-I.Lin.An index structure for improving closest pairs and related join queries in spatial databases.In IEEE IDEAS,pages 140–149,2002.
[5]Y.Gao,L.Chen,X.Li,B.Yao,and G.Chen.Efficient k-closest pair queries in general metric spaces.VLDBJ,pages 1–25,2015.
[6]M.Patella,P.Ciaccia,and P.Zezula.M-tree:An efficient access method for similarity search in metric spaces.In VLDB,pages 1241–1253,1997.
[7]H.Kurasawa,A.Takasu,and J.Adachi.Finding the k-closest pairs in metric spaces.In Proc.of the 1st Workshop on New Trends in Similarity Search,pages 8–13,2011.
[8]E.H.Jacox and H.Samet.Metric space similarity joins.ACM TODS,33(2):7,2008.
[9]K.Fredriksson and B.Braithwaite.Quicker similarity joins in metric spaces.In Similarity Search and Applications,pages 127–140.2013.
[10]A.Das Sarma,Y.He,and S.Chaudhuri.Clusterjoin:a similarity joins framework using map-reduce.PVLDB,7(12):1059–1070,2014.
[11]Y.Wang,A.Metwally,and S.Parthasarathy.Scalable all-pairs similarity search in metric spaces.In ACM KDD,pages 829–837.ACM,2013.。
Disclosure of Invention
The invention aims to overcome the defects of the prior art, and provides a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network, which can quickly find k nearest neighbor nodes meeting the constraint under the constraint of a plurality of attributes on a traffic network diagram given by a user, namely find out paths which meet the constraint between two points in a traffic network and have the shortest distance, and meet travel requirements.
The invention adopts the following technical scheme:
a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network comprises the following steps:
mapping the multi-attribute time sequence diagram of the traffic network into a two-dimensional coordinate system;
in the two-dimensional coordinate system, dividing all nodes in the traffic network map into two by using a straight line L parallel to a y axis, respectively calculating k nearest neighbor node pairs on the left side and the right side of the straight line L, and then selecting the whole k nearest neighbor node pairs; the number of the nodes divided into two fingers at the left side and the right side of the straight line L is the same or the number of the nodes is different by 1;
constructing square grids by taking the kth distance r as a diagonal line, wherein a straight line L is on a grid line;
finding any grid c on the right side of the straight line L and on the left side of the straight line L 1 R neighbor grid c of (c) 2 Calculation grid c 1 Node v in (a) s To grid c 2 Node v in (a) d Is a multi-constraint timing path of (a); and calculates grid c 2 Node v in d To c 1 Node v in s Is a multi-constraint timing path of (a); slave node v s To node v d Multiple constraint timing path of (a) and node v d To node v s K nearest neighbor node pairs conforming to multiple constraints are selected from the multiple constraint timing paths.
Preferably, node v s To node v d The multi-constraint time sequence path calculation method comprises the following steps:
reverse search step: from the end point v d To the starting point v s Performing reverse search and calculating reverse search pathThen judging whether the reverse search path satisfies the corresponding W constraints by the value of the target equation, path +.>Is stored at node v i In (a) and (b);
forward expansion step: from the starting point v in combination with the information stored in the reverse search step s Toward the end point v d Searching to find the starting point v s To the end point v d The shortest timing path between which meets the constraint.
Preferably, the reverse search step includes:
step 301, for each edge e= (v) i ,v i+1 ,t i ,f W (e) Check in turn if the departure time and arrival time of the edge are within a given time interval t α ,t β ]Step 302 is executed; if the departure time is within the time interval t α ,t β ]In the interval, if the arrival time is not in the interval, the next edge is processed; otherwise, stopping the processing; wherein t is i Indicating the departure time of the strip;
step 302, from v d Initially, for edge e= (v i ,v i+1 ,t i ,f W (e) Let the corresponding running time be r i The method comprises the steps of carrying out a first treatment on the surface of the If v i+1 Is the end point, then updateBy->Information of->Update get->A piece of information->In particular toAnd (F)>Wherein (1)>Representing reverse timing path +.>From v i+1 Departure time of the point; />Representation->The current minimum objective function value; />Representing the cumulative value of the jth attribute, wherein j is greater than or equal to 1 and less than or equal to W;
for a pair ofAfter updating, delete->A pair of dominant elements;
step 303, ifIn addition->If->In addition-> Wherein (1)>The latest departure time of the reverse path is represented;
step 304: for each node, the minimum objective function value of the reverse path is returnedDeparture time of route for acquiring objective function value ∈>And the latest departure time of the reverse path +.>
Preferably, the step 301 further includes:
and ordering all time sequence edges in the multi-attribute time sequence diagram from big to small according to the departure time.
Preferably, the forward expansion step includes:
step 501, determining the currently scanned edge e= (v) i ,v i+1 ,t i ,f W (e) If the departure time is within the time interval given by the user, if not, stopping the processing; if the departure time is within the time interval t α ,t β ]In the interval, if the arrival time is not in the interval, the next edge is processed; if the departure time and arrival time are both within the given time range, then step 502 is performed;
step 502, aggregating attribute values of a first half path currently obtained and a second half path obtained in a reverse process, including:
step 5021, determining slave v i+1 To v d Minimum objective function value of timing path of (a)Whether greater than 1, if->Indicating from v i+1 To v d There is no path conforming to the constraint;
step 5022, ifJudging from v s Through e to v i+1 Is>Whether or not the arrival time of (a) is less than v i+1 To v d Is->If->Description->And all slave v i+1 To v d Is not able to join in time, from v s Cannot reach v through e d ；
Step 5023, ifHandle->And the minimum target equation value of the latter half path calculated in the reverse process +.>Polymerizing to obtain a polymerization path->And->Wherein j is more than or equal to 1 and is less than or equal to W; if->Indicating from v s Through e to v d Paths that do not meet constraints; if->Then use->Information in (1) to update->Delete->Is a dominant element in (a); wherein (1)>In the form of each element ofa vi Representing the forward timing path->To v i The arrival time of the point; />Representing an objective function value; />An accumulated value representing a j-th attribute; />Representing the path length from the origin to v;
step 503: at the position ofFind slave v s To v d The constrained shortest path is met and k node pairs are selected.
Preferably, the step 501 further includes:
and ordering all time sequence edges in the multi-attribute time sequence diagram from small to large according to the departure time.
Compared with the prior art, the invention has the following beneficial effects:
(1) The query method of k nearest neighbor node pairs in the multi-attribute time sequence traffic network considers the characteristics of a time sequence diagram of the traffic network, and is different from the traditional static diagram;
(2) The invention provides a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network, which provides a target equation composed of a plurality of attribute values and corresponding constraint values of a path, wherein the target equation is used for judging whether each attribute on the path meets the constraint given by a user or not, so as to judge whether the path is feasible or not;
(3) The invention relates to a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network, which provides an algorithm for carrying out bidirectional search (forward and reverse combination) on a traffic road network (multi-attribute time sequence diagram) to comprehensively consider a constraint value and a target value of a shortest path, thereby solving a multi-constraint shortest path between two nodes;
(4) The invention provides a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network, which provides a divide-and-conquer method for accelerating the calculation of the k nearest neighbor node pairs meeting the constraint, and pruning is carried out by adopting a grid division method in the calculation process.
The foregoing description is only an overview of the present invention, and is intended to provide a more clear understanding of the technical means of the present invention, so that it may be carried out in accordance with the teachings of the present specification, and to provide a more complete understanding of the above and other objects, features and advantages of the present invention, as exemplified by the following detailed description.
The above and other objects, advantages and features of the present invention will become more apparent to those skilled in the art from the following detailed description of the specific embodiments of the present invention when taken in conjunction with the accompanying drawings.
Drawings
FIG. 1 is a diagram of a multi-attribute time-series road network mapped into a two-dimensional coordinate system according to an embodiment of the present invention;
FIG. 2 is a multi-attribute timing road network with a mesh constructed in accordance with an embodiment of the present invention;
fig. 3 is a schematic diagram of an r-nearest neighbor grid according to an embodiment of the present invention;
FIG. 4 is a diagram of a multi-attribute timing network and corresponding bus route in accordance with an embodiment of the present invention; fig. 4 (a) is a multi-attribute time sequence road network diagram, and fig. 4 (b) is a corresponding bus route diagram.
Detailed Description
For the purpose of making the objects, technical solutions and advantages of the present invention more apparent, the embodiments of the present invention will be described in further detail with reference to the accompanying drawings.
The invention discloses a query method of k nearest neighbor node pairs in a multi-attribute time sequence traffic network, which is used for querying the k nearest neighbor node pair problems under multiple constraints on a time sequence diagram, and solves the problems by adopting a divide-and-conquer method as a whole. Firstly, in the coordinate system, all nodes are divided into two by a straight line L parallel to the y axis, k nearest neighbor node pairs on the left side and the right side of the L are calculated respectively, then the k nearest neighbor node pairs are selected as a whole, and a square grid is constructed by taking the k-th distance r as a diagonal line (namely, the side length of the square is) And straight line L is on the grid line. For any grid c on the left side of L 1 Find c on the right side of L 1 R neighbor grid c of (c) 2 Calculate c 1 Node v in s To c 2 Node v in d Is provided. Similarly, calculate c 2 Node v in d To c 1 Node v in s Is provided. Node v s To node v d The calculation mode of the time sequence path of (a) comprises the following steps: first from v d Direction v s Reverse search is performed to calculate v s To v d Path of (c) and intermediate node to v d The minimum target equation value and the latest departure time of the path of (2), and then from v s Start toForward expansion path, pruning is carried out by combining information reserved in reverse process in expansion process, thus speeding up query and finally obtaining the secondary v s To v d The shortest timing path between which the constraint is satisfied. And finally, outputting k nearest neighbor node pairs meeting multiple constraints as a result.
Specifically, the method comprises the following three steps:
first, a target equation is proposed that determines whether a plurality of attribute values on a path satisfy constraints given by a user through traffic network information, specifically as follows.
In daily output, the user often puts forward corresponding constraints on the attributes such as time and oil consumption spent on the journey according to own preference, so that a target equation is needed to be designed to judge whether the attribute aggregation value on the path meets the constraints. Secondly, because the traffic network is changed in real time in many cases, the information of each road in different time periods is acquired first. At present, with the rapid development of global positioning system, wireless communication and mobile internet technologies, road network information can be obtained more and more easily, for example, information such as path length and running time between two points can be obtained easily through a hundred-degree map. From these known information, it can be determined whether the path satisfies the constraint of the user.
The objective equation is composed of a plurality of attribute values of the path and corresponding constraint values, and is used for judging whether each attribute on the path meets the corresponding constraint. Given W constraints, lambda 1， λ 2 ,…λ W From the starting point v at time t s To the end point v t Is a path of (a)Is defined as:
wherein,wherein W is more than or equal to 1 and less than or equal to W, f 1 (e(v i ,v i+1 ,t i ,f W (e))),…，f W (e(v i ,v k ) Is edge e (v) i ,v i+1 ,t i ,f W (e) W attribute values on>Indicate path->The W constraints are met, which is a viable path that would otherwise not be viable.
Using the delta function described above, the objective equation for any two nodes in the traffic network can be represented.
In a traffic network, the W attributes may include the running time of the vehicle between two stops, the fare between two stops, the number of transfers of the user from the start point to the end point, and so on. If the user wants to go from about jojoba to about Yangzhou, he wants to run for no more than 3 hours on the road, the fare is no more than 80 yuan and the number of transfers is no more than 1. From the point of view of the transportation route, there are two schemes: (1) Directly from Suzhou to Yangzhou, the fare is 78 yuan, and the transfer frequency is 0; (2) The fare is 50 yuan from the Zhuzhou sitting cart to Zhenjiang, and then 30 yuan from the Zhenjiang sitting cart to Yangzhou, and the transfer frequency is 1. The invention aims to judge whether the attribute value of the path in a certain time period meets the constraint of a user or not through real-time road network information by utilizing the method.
And secondly, searching a path with the shortest distance between two points which meets the constraint through traffic network information, wherein the path is specifically as follows.
Since the final objective is to find k nearest neighbor points of interest in the traffic network that satisfy the constraints of the user, and by using the objective equation above, it can be already determined whether a path satisfies a plurality of constraints given by the user, it is further necessary to find a path that meets the constraints between two points and has the shortest distance in the traffic network.
Based on the above-mentioned object, the present invention proposes a pair ofStep algorithm, the algorithm carries out bidirectional search on traffic road network (multi-attribute time sequence diagram), the first search is from terminal point v d To the starting point v s The second search is from the starting point v s To the end point v d . In the algorithm, the reverse process of the first step first calculates a reverse search path (Backward Temporal Path)Then determines BTP (Backward Temporal Path) whether the corresponding W constraints are satisfied by the value of the target equation, in which process the path +.>Is stored at node v i May be used to accelerate the search for the second forward process. If->Indicating that from the starting point v s To the end point v d There is one possible path. Then, the following forward search process can be performed from the starting point v s Toward the end point v d A search is performed to find the shortest path that satisfies the constraint.
(a) Reverse search process
This process goes from endpoint v d To the starting point v s Searching is performed, mainly calculating two values: (1) Intermediate node v i To v d The minimum delta value of all timing paths of (a) is used delta min Expressed by the departure time of the corresponding path expressed asIntermediate node v i To v d The latest departure time of all timing paths of (a) by +.>And (3) representing. Thus, at each node v i On, store delta min 、/>And->This information stored on the nodes can help predict the feasibility of the path during the forward search. Furthermore, in the reverse search process, if node v i To node v d With two paths p 1 And p 2 If p 1 Departure time ratio p of (2) 2 Is early in departure time, and delta (p 1 ) Value ratio delta (p) 2 ) Large, then say p 2 Dominating p 1 Then path p can be taken 1 The removal is because the earlier the path departure time, the more difficult it is for the previous path to connect to the path, the greater the current delta value, and the more likely the final delta value will not satisfy the constraint.
The main process of reverse search is as follows: all timing edges in the timing diagram are first ordered from big to small according to departure time. Creating an L at each node v v To store from node v to endpoint v d Information about all paths of L v In the form of each element ofWherein d is v 、/>And->Respectively represent reverse timing path +.>And starting time, an objective function value and an accumulated value of a j-th attribute from the v point, wherein j is more than or equal to 1 and W is more than or equal to W. To facilitate the description of the algorithm, let edge e= (v i ,v i+1 ,t i ,f W (e) (ti here refers to the departure time of the edge) run-time r i To represent.
The reverse search process specifically includes the following steps:
step 301: for each edge e= (v) i ,v i+1 ,t i ,f W (e) Check in turn if the departure time and arrival time of the edge are within a given time interval t α ,t β ]If so, then go to step 302; if the departure time is within the time interval t α ,t β ]In the section, if the arrival time is not within the section, the next edge is processed (before searching, all edges are already ordered in the order from the big to the small according to the departure time, so the next edge is the next edge ordered from the big to the small according to the departure time); otherwise, the algorithm is terminated;
step 302: from v d Initially, for edge e= (v i ,v i+1 ,t i ,f W (e) Corresponding to a run time r i . If v i+1 Happens to be the endpoint, then the update(i.e. (t) i +r i 0, … 0) to +.>In, here->That is, information about the value from end point to end point, including the time t from end point i +r i The end-to-end objective function value 0, and the accumulated value of this attribute 0, are all 0 because there is virtually no run from end-to-end, which is simply a special case); then, based on->Update->Select->Element->Wherein->And->Is->Is the current minimum objective function value. Updating with the element to get->A piece of information in->Wherein the method comprises the steps ofAnd (F)>For a pair ofAfter the update, & gt, was deleted by the aforementioned pruning>A pair of dominant elements;
step 303: if it isUpdate->If->Updating node v i Delta of (2) mim And the departure time of the route corresponding to the value +.>
Step 304: for each node, return delta min ，And->Namely, the minimum objective function value of the reverse path, the departure time of the path for which the function value is obtained, and the latest departure time of the reverse path.
(b) Forward expansion process
The method comprises the steps of firstly sequencing all time sequence edges in a graph from small to large according to departure time, then traversing the edges to obtain a shortest path conforming to constraint, and predicting the feasibility of the path by combining a minimum target equation value obtained in the reverse direction and the latest departure time in the process. At initialization, an F is created on each node v v To store the starting point v s Information about all paths to node v, F v In the form of each element ofWherein a is v ，/>Respectively represent forward time sequence paths->Arrival time to v point, objective function value, cumulative value of jth attribute (1. Ltoreq.j. Ltoreq.W), path length from start point to v. For ease of description, e= (v i ,v i+1 ,t i ,f w (e) R) for runtime i To represent. The method specifically comprises the following steps:
step 501: determining the currently scanned edge e= (v) i ,v i+1 ,t i ,f w (e) If the departure time is within the time interval given by the user, if not, the algorithm is ended; if the departure time is within the time interval t α ,t β ]In the interval, if the arrival time is not in the interval, the next edge is processed; if the departure time and arrival time are both within the given time frame, then go to step 502;
step 502: the attribute values of the front half path which is currently calculated and the back half path which is calculated in the reverse process are calculated and aggregated, and the main process is as follows: (1) First judge from v i+1 To v d Minimum objective function value of timing path of (a)Whether greater than 1, if->Description from v i+1 To v d There is no path conforming to the constraint; (2) If->Judging from v s Through e to v i+1 Is>Whether or not the arrival time of (a) is less than v i+1 To v d Is->If->Indicate->And all slave v i+1 To v d Is not able to join in time, indicating that from v s Cannot reach v through e d The method comprises the steps of carrying out a first treatment on the surface of the (3) If it is/>Next, the->And the minimum target equation value of the latter half path calculated in the reverse process +.>Polymerizing to obtain a polymerization path->And-> Wherein j is more than or equal to 1 and W is more than or equal to W. If->Indicating from v s Through e to v d Paths that do not meet constraints; if->Then +.>Information in (1) to update->In particular +.> 1.ltoreq.j.ltoreq.W and, +.>Wherein->Representing the forward timing path->Arrive v i+1 Time of (2); />Representation->The current minimum objective function value; />Representing the cumulative value of the jth attribute, wherein j is greater than or equal to 1 and less than or equal to W; after the update is completed, delete->Is a dominant element in (a);
step 503: at the position ofFind slave v s To v d The shortest path that meets the constraint and returns.
Finally, the path (if any) with the shortest distance between any two points in the traffic network meeting the user constraint can be obtained through the bidirectional search algorithm.
Thirdly, searching the first k nearest neighbor interest point pairs meeting multiple constraints from the whole traffic network.
By the first and second, the path with the shortest distance between two points in the traffic network satisfying the constraint of the user can be obtained, but the whole traffic network is huge, and it is not realistic to enumerate all the point pairs, so how to effectively and efficiently solve the problem of the traffic network is a problem worth thinking and having practical significance. Therefore, the invention provides a k nearest neighbor calculation method based on a divide-and-conquer method, which is as follows.
Referring to fig. 1 to 3, since the entire traffic network can be abstracted into a multi-attribute timing diagram, each node has position information, and each side has attribute information, the entire traffic network timing diagram can be mapped into a two-dimensional coordinate system in which all nodes are divided into two by a straight line L parallel to the y-axis, the number of the divided nodes divided into two on the left and right sides of the straight line L is the same or the number of the divided nodes differs by 1. Let P 1 And P 2 Representing the nodes on the left side and the right side of L respectively, finding k node pairs which meet constraint and have the shortest paths on the left side and the right side of L respectively, then merging the results obtained from the two sides, namely taking the previous k node pairs, so far, only considering the case of one side, and not considering the case of two sides crossing (the case of one node on the left side of L and one node on the right side of L), so next calculating the case of two sides crossing by means of constructing a grid to obtain the whole k node pairs which meet constraint and have the shortest paths. The method comprises the following steps: with the current kth distance r as a diagonal, a square grid is constructed (i.e. square side length is) Ensuring that L is on the grid line when constructing the grid (the dotted line is the constructed grid as shown in FIG. 2, L is easy to calculate on the grid line), then for each grid cell c with a distance L less than r to the left of L 1 (requirement c here 1 The shortest distance to L is less than r because if c 1 The shortest distance to L is greater than r, then for any node to the right of L, c 1 The distance from the node to the node is necessarily larger than r, and the distance is not satisfactory, namely, the calculation is not continued, so that under the condition that the two sides of the calculation are crossed, all grids do not need to be traversed, only the distances are required to be traversed, and c) is found on the right side due to the existence of grids and r 1 R neighbor grid c of (c) 2 (if c 1 To c 2 Not exceeding r, then c 2 Namely c 1 May not be more than c2One, as shown in FIG. 3, c 1 To c 2 Is MinDist, if MinDist is less than or equal to r, c 2 Namely c 1 R neighbor grid of (c), similarly 1 Also c 2 R neighbor grid of (r) using the forward and reverse search algorithm described in the second above to calculate c 1 Any node v in s To c 2 Any node v in d Is provided. Similarly, calculate c 2 Any node v in d To c 1 Any node v in s Is provided. The first k constrained node pairs with the shortest paths are finally selected. From the above description, it can be seen that, every time a new kth small node pair is calculated, the diagonal length of the grid is reduced, and the more nodes can be filtered out, so that the algorithm efficiency is faster.
Accordingly, referring to fig. 1 to 4, in the traffic road network, let the set p= { a, c, d, k } represent a hotel set, the set q= { h, i, j } represent a scenic spot set, the weight on the edge represents the length of the road section, and the public traffic information on each road section is shown in the table of fig. 4, and includes the information of the start point, the end point, the departure time, the running time, the cost and the like of the road section. Given time interval [8:30AM,10:30AM]The running time on the road section is not more than 45 minutes, the total budget is not more than $10, two nearest-neighbor hotel-scenic spot pairs need to be found, two nearest-neighbor hotel-scenic spot pairs meeting the time interval and a plurality of attribute constraints can be obtained by using the method, one hotel-scenic spot pair is (c, j), the distance is 5km, and a user takes a lift b at 9:00AM near the point c 2 Then the corresponding run time is 24mins, the cost is $5, and at 9:24am reaches point f, at 9:45am at point f, pick-up b 2 Going to point j, the corresponding run time is 18mins and the cost is $4, then the user can reach point j at 10:03AM, and the sum of the time spent on the road segment is 42mins and the cost is $9 in the whole process. Another hotel-sight pair is (d, i), at a distance of 9km, and the user can ride vehicle b near point d at 9:00am 2 Then point e can be reached at 9:20am, then point e is transferred by b at 9:30am 3 To i, then the user canAt 9:55AM reaches i, the overall run time on the road segment is 45mins, at $9.
The foregoing is merely illustrative of specific embodiments of the present invention, but the design concept of the present invention is not limited thereto, and any insubstantial modification of the present invention by using the design concept shall fall within the scope of the present invention.
Claims (1)
1. A method for querying k nearest neighbor node pairs in a multi-attribute time-sequential traffic network, comprising:
mapping the multi-attribute time sequence diagram of the traffic network into a two-dimensional coordinate system;
in the two-dimensional coordinate system, dividing all nodes in the traffic network map into two by using a straight line L parallel to a y axis, respectively calculating k nearest neighbor node pairs on the left side and the right side of the straight line L, and then selecting the whole k nearest neighbor node pairs; the number of the nodes divided into two fingers at the left side and the right side of the straight line L is the same or the number of the nodes is different by 1;
constructing square grids by taking the kth distance r as a diagonal line, wherein a straight line L is on a grid line;
finding any grid c on the right side of the straight line L and on the left side of the straight line L 1 R neighbor grid c of (c) 2 Calculation grid c 1 Node v in (a) s To grid c 2 Node v in (a) d Is a multi-constraint timing path of (a); and calculates grid c 2 Node v in d To c 1 Node v in s Is a multi-constraint timing path of (a); slave node v s To node v d Multiple constraint timing path of (a) and node v d To node v s Selecting k nearest neighbor node pairs conforming to multiple constraints from the multiple constraint timing paths;
node v s To node v d The multi-constraint time sequence path calculation method comprises the following steps:
reverse search step: from the end point v d To the starting point v s Performing reverse search and calculating reverse search pathThen judging whether the reverse search path satisfies the corresponding W constraints by the value of the target equation, path +.>Is stored at node v i In (a) and (b);
forward expansion step: from the starting point v in combination with the information stored in the reverse search step s Toward the end point v d Searching to find the starting point v s To the end point v d A shortest timing path between which the constraint is met;
the reverse search step includes:
step 301, for each edge e= (v) i ,v i+1 ,t i ,f W (e) Check in turn if the departure time and arrival time of the edge are within a given time interval t α ,t β ]Step 302 is executed; if the departure time is within the time interval t α ,t β ]In the interval, if the arrival time is not in the interval, the next edge is processed; otherwise, stopping the processing; wherein t is i Indicating the departure time of the edge; wherein f W (e) Representing W attribute values on the edge;
step 302, from v d Initially, for edge e= (v i ,v i+1 ,t i ,f W (e) Let the corresponding running time be r i The method comprises the steps of carrying out a first treatment on the surface of the If v i+1 Is the end point, then updateBy->Information of->Update get->A piece of information->In particular toAnd (F)>Wherein (1)>Representing reverse timing path +.>From v i+1 Departure time of the point; />Representation->The current minimum objective function value; />An accumulated value representing a j-th attribute;
for a pair ofAfter updating, delete->Is a dominant element in (a);
wherein,representing the slave v d To the end point v i+1 Related information of (2);
step 303, ifLet->If->Let->Wherein (1)>The latest departure time of the reverse path is represented;
step 304: for each node, a minimum objective function value delta of the reverse path is returned min (v i ) Departure time of path for acquiring objective function valueAnd the latest departure time of the reverse path +.>
The step 301 further includes:
ordering all time sequence edges in the multi-attribute time sequence diagram from big to small according to the departure time;
the forward expansion step includes:
step 501, determining the currently scanned edge e= (v) i ,v i+1 ,t i ,f w (e) If the departure time is within the time interval given by the user, if not, stopping the processing; if the departure time is within the time interval t α ,t β ]In the interval, if the arrival time is not in the interval, the next edge is processed; if the departure time and arrival time are both within the given time range, then step 502 is performed;
step 502, aggregating attribute values of a first half path currently obtained and a second half path obtained in a reverse process, including:
step 5021, determining slave v i+1 To v d Minimum objective function value of timing path of (a)Whether or not it is greater than 1, ifIndicating from v i+1 To v d There is no path conforming to the constraint;
step 5022, ifJudging from v s Through e to v i+1 Is>Whether or not the arrival time of (a) is less than v i+1 To v d Is->If->Description->And all slave v i+1 To v d Is not able to join in time, from v s Cannot reach v through e d ；
Step 5023, ifHandle->And the minimum target equation value of the latter half path calculated in the reverse process +.>Polymerizing to obtain a polymerization path->And->λ j Representing constraints; if->Indicating from v s Through e to v d Paths that do not meet constraints; if->Then use->Information in (1) to update->Delete->Is a dominant element in (a); wherein F is vi In the form of each element ofa vi Representing the forward timing path->To v i The arrival time of the point; />Representing an objective function value; />An accumulated value representing a j-th attribute; />Representing from the origin to v i Is a path length of (a);
step 503: at the position ofFind slave v s To v d The shortest path conforming to the constraint and k node pairs are selected from the shortest paths;
the step 501 further includes:
and ordering all time sequence edges in the multi-attribute time sequence diagram from small to large according to the departure time.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811636467.XA CN109840620B (en) | 2018-12-29 | 2018-12-29 | Query method for k nearest neighbor node pairs in multi-attribute time sequence traffic network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811636467.XA CN109840620B (en) | 2018-12-29 | 2018-12-29 | Query method for k nearest neighbor node pairs in multi-attribute time sequence traffic network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109840620A CN109840620A (en) | 2019-06-04 |
| CN109840620B true CN109840620B (en) | 2024-03-08 |
Family
ID=66883471
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811636467.XA Active CN109840620B (en) | 2018-12-29 | 2018-12-29 | Query method for k nearest neighbor node pairs in multi-attribute time sequence traffic network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109840620B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114692352B (en) * | 2022-04-06 | 2023-02-03 | 中南大学 | Intelligent layout method for highway network in mountain railway construction |
| CN117236247B (en) * | 2023-11-16 | 2024-01-23 | 零壹半导体技术(常州)有限公司 | Signal shielding wire generation method for chip test |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20040042216A (en) * | 2002-11-13 | 2004-05-20 | 에스케이 주식회사 | System for route searching of car and method thereof |
| CN101819717A (en) * | 2010-03-05 | 2010-09-01 | 吉林大学 | Road network performance judgment method based on traffic state space-time model |
| CN102506849A (en) * | 2011-09-28 | 2012-06-20 | 浙江大学 | Method for optimizing shortest path with restraint |
| CN102880642A (en) * | 2012-08-20 | 2013-01-16 | 浙江工业大学 | Bus transfer method based on weighted directed network model |
| CN104317886A (en) * | 2014-10-23 | 2015-01-28 | 西北工业大学 | Method for retrieving and selecting neighbor conditional data points in grid node interpolation under fault constraint |
| CN109086302A (en) * | 2018-06-21 | 2018-12-25 | 苏州大学 | Skyline-based multi-constraint path query method under timing diagram |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8660789B2 (en) * | 2011-05-03 | 2014-02-25 | University Of Southern California | Hierarchical and exact fastest path computation in time-dependent spatial networks |
-
2018
- 2018-12-29 CN CN201811636467.XA patent/CN109840620B/en active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20040042216A (en) * | 2002-11-13 | 2004-05-20 | 에스케이 주식회사 | System for route searching of car and method thereof |
| CN101819717A (en) * | 2010-03-05 | 2010-09-01 | 吉林大学 | Road network performance judgment method based on traffic state space-time model |
| CN102506849A (en) * | 2011-09-28 | 2012-06-20 | 浙江大学 | Method for optimizing shortest path with restraint |
| CN102880642A (en) * | 2012-08-20 | 2013-01-16 | 浙江工业大学 | Bus transfer method based on weighted directed network model |
| CN104317886A (en) * | 2014-10-23 | 2015-01-28 | 西北工业大学 | Method for retrieving and selecting neighbor conditional data points in grid node interpolation under fault constraint |
| CN109086302A (en) * | 2018-06-21 | 2018-12-25 | 苏州大学 | Skyline-based multi-constraint path query method under timing diagram |
Non-Patent Citations (6)
| Title |
|---|
| Alberto Viseras .An asynchronous distributed constraint optimization approach to multi-robot path planning with complex constraints.ACM.全文. * |
| An asynchronous distributed constraint optimization approach to multi-robot path planning with complex constraints;Alberto Viseras;ACM;全文 * |
| Bi-BFS:一种新颖的基于时序图的可达性算法;刘凯洋;范新灿;;现代计算机(专业版)(第08期);全文 * |
| 动态图数据上查询与挖掘算法的研究综述;杨雅君;智能计算机与应用(第4期);全文 * |
| 动态网络可视化与可视分析综述;刘真;吴向阳;郑秋华;;计算机辅助设计与图形学学报(第05期);全文 * |
| 杨雅君.动态图数据上查询与挖掘算法的研究综述.计算机软件及计算机应用.2013,(第4期),全文. * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109840620A (en) | 2019-06-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Liao et al. | Incorporating space–time constraints and activity-travel time profiles in a multi-state supernetwork approach to individual activity-travel scheduling | |
| Thangaraj et al. | Xhare-a-ride: A search optimized dynamic ride sharing system with approximation guarantee | |
| Anwar et al. | Capturing the spatiotemporal evolution in road traffic networks | |
| CN110836675B (en) | Decision tree-based automatic driving search decision method | |
| Liao et al. | Multi-state supernetwork framework for the two-person joint travel problem | |
| CN100523735C (en) | Fast map matching method based on small lattice road network organization and structure | |
| CN111879329B (en) | Customized public transport passable shortest path calculation method based on A-x algorithm | |
| CN109840620B (en) | Query method for k nearest neighbor node pairs in multi-attribute time sequence traffic network | |
| CN109902711B (en) | K-nearest neighbor query algorithm for moving object on time-dependent road network | |
| CN114578848A (en) | Unmanned aerial vehicle routing inspection path planning method based on discrete point density and global planning | |
| Luo et al. | Dynamic taxi service planning by minimizing cruising distance without passengers | |
| CN106373384A (en) | Remote area passenger transport regular bus route real-time generation method | |
| Cai et al. | A novel vector-based dynamic path planning method in urban road network | |
| He et al. | Exploring public transport transfer opportunities for pareto search of multicriteria journeys | |
| Majumder et al. | MERIT: multi-itinerary tourist recommendation engine for industrial internet of things | |
| CN113808424B (en) | A method for obtaining K shortest paths in urban road network based on bidirectional Dijkstra | |
| CN112084609B (en) | Power supply partition dividing method for power industry | |
| Jensen et al. | Routing with Massive Trajectory Data | |
| Cici et al. | SORS: a scalable online ridesharing system | |
| Lu et al. | Trajectory splicing | |
| Mouhcine et al. | An improved swarm optimization algorithm for vehicle path planning problem | |
| CN110188254B (en) | Dynamic shortest path query and visualization | |
| CN115170171A (en) | Identification method, device, equipment and storage medium of shared bicycle silting area | |
| Constantinou et al. | A framework for continuous knn ranking of ev chargers with estimated components | |
| CN119201405B (en) | A streaming computing job scheduling method based on time and space awareness |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |