CN103323018A - Time-interval-based feature identification and fast search method for hotspot path - Google Patents

Abstract

Translated fromChinese

本发明公开了一种基于轨迹大数据的热点路径特征识别与快速搜索方法。本发明涉及一种网络路径搜索的方法，尤其涉及利用历史轨迹大数据在路网中进行热点路径识别和搜索的方法。本发明提供了热点路径的一套核心特征，及热点路径的特征识别方法，包括路径热度的矢量标示法和基于路径热度的排名机制；并提出了一种索引机制，以减少对轨迹大数据的查询和获取过程中的磁盘I/O开销；并提出了基于时段的热点路径快速查询方法，包括确定出发地、目的地、感兴趣时段，利用历史轨迹大数据计算满足条件的热点路径。本发明给出了热点路径的合理定义，并提供基于任意时段的热点路径查询，不仅是对传统路径查询方法的重要补充，也能更好的为各类基于位置的服务提供核心技术支持。

The invention discloses a hot path feature recognition and fast search method based on trajectory big data. The invention relates to a method for searching a network path, in particular to a method for identifying and searching a hotspot path in a road network by using big data of historical trajectories. The present invention provides a set of core features of hotspot paths, and a feature identification method of hotspot paths, including a vector labeling method of path heat and a ranking mechanism based on path heat; and an index mechanism is proposed to reduce the need for large track data Disk I/O overhead during the query and acquisition process; and a time-based fast hotspot path query method is proposed, including determining the departure point, destination, and time of interest, and using historical trajectory big data to calculate hotspot paths that meet the conditions. The invention provides a reasonable definition of hotspot paths and provides hotspot path queries based on any time period, which is not only an important supplement to traditional path query methods, but also better provides core technical support for various location-based services.

Description

Feature identification and method for fast searching based on the focus path of period

Technical field

The present invention relates to a kind of method of network path search, relate in particular to the method for utilizing the large data of historical track in road network, to carry out focus Path Recognition and search.

Background technology

In network path search, optimal path typically refers in from origin to destination all paths, the shortest one of cum rights path.According to the difference of weights implication in highway section in the road network, that optimal path inquiry can develop is the shortest for path, the enforcement time is minimum, paying price is optimum, and the calculating in the path such as energy resource consumption is minimum.In comparatively complicated application, optimal path can also be the optimum after multiple weighing value (as considering simultaneously enforcement time and paying price) considers.

Yet in many application scenarioss, these can't satisfy user's trip requirements based on the path query technology of weights optimum.For example, people tend to consider factors at a strange city whilst on tour, as road closed whether, road conditions complexity, pavement quality quality, traffic safety whether, and how etc. landscape on the way.These conditions are not only numerous and diverse, and temporal evolution is indefinite, are difficult to as concrete pathfinding standard.At this moment, select from origin to destination, the most normal path of being used by the user, namely the focus path is that more traditional method for searching is better selected.Except the application in recommend in the path, the focus path also is that city planning, space-time data excavate, and the gordian technique of the important application such as all kinds of location-based services.For example, we can be by checking within the different periods, the focus path is whether identical between identical source point and the destination, and analyze people and whether change in the trip custom of different times (such as working day and weekend), and the auxiliary generation of surveying unusual and major event.

In recent years, along with the fast development of position acquisition technology (such as Global Positioning System:GPS), people begin to collect and process the historical movement trace information of the objects such as increasing relevant vehicle, people, animal.For example, from 2007 to 2012, collected vehicle GPS position record and has reached about 1,000 hundred million Beijing.The appearance of magnanimity track data, for the identification in focus path and inquiry provide may.

In brief, the focus path refers in all paths from the source point to the destination, the path that the most often is used.This concept is easily understood, and its principal character but is difficult to extract.Patent documentation 1(number of patent application 201110357525.7) general routes and the focus path implication that propose are similar.Specifically, general routes refers in all paths from the source point to the destination, through the path of historical track number greater than certain preset value.The subject matter of the method is, the optimal path that obtains does not thus possess the characteristic of suffix subpath optimum.This characteristic refers to, supposes path P=v₁→ v₂→ ... → v_nFrom source point v₁To destination v_nThe focus path, v_i(1≤i≤n) is the node in the road network, so the suffix subpath v of P_i→ ... → v_nAlso should be v_iTo v_nThe focus path.Otherwise in the reality navigation, the every crossroad of user (is v_i), just needing the again focus path of the remaining route of inquiry, this obviously is discontented with the demand that use on full border.Secondly, track data possesses the space-time multi-dimensional nature, and existing large data processing technique can't be supported effective storage and the quick-searching of the large data of track.The method does not provide the solution of effective storage and the large data of inquiry track.At last, be subjected to the impact of the dynamic factors such as the magnitude of traffic flow, weather condition, road construction, anomalous event, the focus path possesses stronger ageing.But the method does not allow the user in when inquiry, selects the interested period, and the calculating in focus path is based on that all historical tracks finish.Because arbitrariness and the unpredictability of period, a lot of complicated operations (such as the track data inquiry) must be finished online, and this has proposed huge challenge for the fast query in path.

The scientific research personnel of University of Queensland has proposed the method in another definition focus path.They have designed a novel heat degree function, for assessment of the temperature from given source point to every paths the destination, and select the highest path of temperature as the focus path.The temperature value of one paths equals on this path the product that all highway sections arrive the probable value of destinations.Therefore, the highway section number is more, and the temperature value in path is lower.The road (such as the route by way of the urban district) that this obviously is unfavorable for those by way of more intersection and frequency of utilization is very high.Also have, the road that the method is found out may comprise the highway section that seldom is used, and such focus path does not have practical significance.In addition, the method does not allow the interested period of user selection yet, does not propose the solution of online query (such as the track data online query).

In sum, effective identification in focus path and fast search are problem demanding prompt solutions.。

Summary of the invention

In order to solve the deficiencies in the prior art, the invention provides the novel feature recognition strategy in a kind of focus path, a kind of focus path high-efficiency search method based on the period.Its purpose has 2 points: 1) focus Path Recognition mechanism reasonable in design, the footpath experience of seeking that accurately reflection is popular as far as possible; 2) the efficient track data storage and retrieval method of design realizes the fast search based on the focus path of period.

To achieve these goals, the invention provides the core identification feature in a cover focus path.Suppose P=v₁→ v₂→ ... → v_nFrom v₁To v_nThe focus path, v_i(1≤i≤n) is the node in the road network, and P should possess following core feature so:

Feature one: the suffix path is optimum, and namely any suffix subpath of P also should be a focus path;

Feature two: link length is irrelevant, and namely the temperature of P is only relevant with its number of times of once being used, and can't help its length decision;

Feature three: do not contain bottleneck road, namely P should not comprise and can be avoided the low temperature highway section of using.

In the feature one, the suffix subpath of P refers to, for any node v among the P_i, from v_iTo v_nSubpath.This subpath should be from v_iTo v_nThe focus path.

In the feature two, both the shown the way physical length in footpath of path, the footpath that also shows the way comprises the quantity on highway section (limit).In addition, the temperature in path is the function that the reflection path is used number of times, and it is more frequent that the path is used, and its temperature is higher.

In the feature three, bottleneck road refers to from v₁To v_nCan be avoided the low temperature highway section of using.In addition, the temperature in highway section is to reflect in order to arrive the destination, and this highway section is used the function of number of times.It is more frequent that the highway section is used, and its temperature is higher.The temperature in highway section must be based on given destination v_nOnly in order to reach v_nAnd select the track in this highway section, just the temperature in this highway section there is contribution.

The present invention also provides a kind of characteristic recognition method of the focus path based on the period.Comprise following step:

Step 1, the sign of track and filtration, every track all represents once significant travelling.Take taxi as example, a track has comprised the motion recording that the passenger gets off from getting on the bus to.Article one, typical track can be designated Y=((v₁, t₁) ..., (v_n, t_n)), wherein, (v₁..., v_n) be the paths in the road network, t_i(1≤i≤n) is that Y arrives node v_iTime.The interested period T of given user=[t_s, t_e], then every track will not be filtered in the part that T generated in the period.Particularly, suppose Y '=((v_k, t_k) ..., (v_h, t_h)) be the result's (sub-trajectory of Y) after track Y is filtered by T, so:

· t_s≤ t_k，t_h≤ t_e；

If k〉1, t then_K-1＜t_s

If h＜n, then t_H+1T_e

Step 2, the measuring of highway section temperature, particularly, the temperature of highway section e refers to arrive destination v by way of e_nThe track number.Every track is all filtered by T herein.Note the not necessarily terminal point of track of destination, as long as track had passed through e before arriving the destination.

Step 3, the vector of path temperature indicates, and namely adopts vector to indicate the temperature in path from origin to destination.Particularly, the temperature F of path P (P)=(f₁, f₂..., f_k) be exactly that P(is comprised k highway section) and in sort the from low to high sequence of rear generation of the temperature in all highway sections.F wherein_i(1≤i≤k) is exactly the temperature that temperature comes the highway section of i name reciprocal.

Step 4, the rank of path temperature, this rank is based on a kind of novel temperature relational calculus.Given two paths P and P ' and their temperature F (P)=(f₁, f₂..., f_m) and F (P ')=(f₁', f₂' ..., f_n'), if following any two conditions satisfy one, we think that the temperature of P is not less than P '.If the value of F (P) and F (P ') is different, the temperature that we say P is greater than P ':

Condition 1:F (P) is the prefix of F (P ');

Condition 2: exist q belong to set 1 ..., min (m, n) } so that: 1) for theset 1 ..., the arbitrary element i among the q-1} all has f_i=f_i', 2) f_qF_q'.

Use this relational calculus, can the temperature in path be sorted entirely, come first namely be the focus path.It all is the highest that attention may have the temperature of mulitpath, at this moment selects wherein any one to get final product.

The present invention also provides a kind of track data Indexing Mechanism CFMI(Containment-Based Footmark Index), be used for retrieval and in specified time period T, arrive certain node v_dAll historical tracks, and intercept them and arrive v_dBefore, and the part in T.Utilize this index can calculate the temperature in highway section, but the function of this index possesses versatility, be not limited to the focus path query.The feature of this Indexing Mechanism is can filter all not arrive v in T_dTrack.Owing to whenever reading a track, will produce the expense that disk reads at random, in order to reduce the I/O operation, the basic thought of this Indexing Mechanism is only to read leading track from disk, and by the reference position of other tracks of record in leading track, reduce the track route of other (satisfying querying condition) tracks.Suppose that track Y is by way of node v_i, use Y_{(*, vi)}Indicate track Y and arrive v_i(comprise v before_i) sub-trajectory, with Path (Y_{(*, vi)}) sign Y_{(*, vi)}The path of process.For other any one by way of v_iTrack Y ', if or Path (Y_{(*, vi)}) and Path (Y '_{(*, vi)}) identical, or Path is (Y_{(*, vi)}) be not Path (Y '_{(*, vi)}) suffix, we claim that Y is node v_iLeading track.By analysis and the research to the large data of real trace, the track quantity that we are found to destination (the especially focus in the city) is far longer than the leading track quantity on this ground.If track Y ' ' passes through v_i, and Path (Y ' '_{(*, vi)}) be Path (Y_{(*, vi)}) suffix (in other words, Y ' ' arrives v_iRoute covered by the route that Y arrives vi), we claim that Y is that Y ' ' is about node v so_iLeading track, we can reduce Y ' ' by only reading Y.The foundation of doing like this is because period T(such as several days, several week, some months) often be far longer than the time of a track (such as dozens of minutes, several hours.We think that a track is once significant trip, for example the track of taxi from upper visitor to lower visitor).Therefore for most of track, as long as they arrive the time of destination in T, its zero-time is also contained in the T naturally.We only do independent reading to the track on its time leap of only a few T border.

In index CFMI, we are each the node v in the road network_iCreate a B+ tree BT_ViBT_ViIndex track arrive v_iTime, and deposited the track number of this track.Each BT_ViLeaf node comprise five territories:

<tid, t_start, t_arrive, did, sloc>

Wherein tid is unique sign of track; t_StartIt is the zero-time of track tid; t_ArriveThat track arrives v_iTime; Did is tid number of the affiliated leading track of track tid; Sloc is the reference position of track tid in track did.Secondly, we are each BT_ViSafeguarded a table v_i-Dom has recorded vertex v in the table_iEvery leading track arrive v_iThe number of vertices of process before.In addition, we have safeguarded a form Table, are used for each node mapping to its corresponding B+ tree.

The present invention also provides a kind of method for quickly querying of the focus path based on the period.Given road network G=(V, E), departure place v_s, destination v_d, period T interested, the method comprises two steps: 1) generate based on (v_d, temperature figure G T)_f=(V_f, E_f).G_fThe cum rights subgraph of G, V_fComprised in time T, in order to arrive v_d, historical track the vertex set of process.E_fThe set on the limit (highway section) that temperature is non-vanishing.2) search the focus path, namely at G_fMiddle inquiry is from v_sTo v_dThe focus path.If v_sNot at G_fIn, perhaps G_fBe sky, then return null value, illustrate from v_sTo v_dThere is not the focus path to exist; Otherwise return lookup result.

Described generation temperature figure G_fThe specific implementation step as follows:

Step 1, FG represents based on (v with adjacency matrix_s, v_d, temperature figure G T)_f, all elements is initialized as 0 among the FG;

Step 2 is searched index CFMI and is returned two set: track record set TR and leading track set of records ends DOM.Wherein, set TR has deposited all through (v_d, (namely this track has not passed through v for sky T) to filter rear sub-trajectory_d, and arrive v_dBefore for some time in T) trace information, comprise (tid, t_Start, did, sloc), notice that tid is unique sign of track; Set DOM has deposited the information of the leading track of all tracks among the set TR, comprises (did, len), and wherein did is unique sign of leading track, and len is that leading track arrives v_dThe time the nodal point number of process (comprise v_d);

Step 3, one of initialization comprise the set DA of array for empty, and for every among DOM record (did, len), creating a length is the array DA.did of len, and its all elements of initialization is 0.Then data DA.did is incorporated among the set DA;

Step 4 is for every among the TR record (tid, t_Start, did, sloc), check t_StartWhether in period T, if do not exist, then according to track not the mode in T revise temperature figure matrix F G; If, the value of sloc the element of array DA.did is added 1;

Step 5 is revised temperature figure matrix F G according to the mode of track in T;

Step 6 is returned temperature figure matrix F G, FG[i wherein, j] in the expression road network from v_iTo v_jHave the highway section to link to each other, temperature is FG[i, j].Temperature figure G_fThen comprised all temperatures and be not 0 highway section, and their nodes of being connected.If the temperature in all highway sections that link to each other with node v among the attention road network G is 0, then v can not appear at temperature figure G_fIn.

In thestep 2 that generates temperature figure, the concrete steps of searching index CFMI are as follows:

1) original state, set TR and set DOM are sky;

2) in form Table, find B+ tree BT_VdThe deposit position of root node;

3) from BT_VdRoot node sets out, and finds in leaf node, greater than period T=[t_s, t_e] middle t_sMinimum t_ArriveThe element at place (tid, t_Start, t_Arrive, did, sloc), with element (tid, t_Start, did, sloc) and insert set TR, and at table v_iFind value corresponding to track did (to arrive v among the-Dom_dThe nodal point number of process) len if (did, len) do not exist in set DOM, then inserts;

4) along BT_VdPointer in the tree between the leaf node is from element (tid, t_Start, t_Arrive, did, sloc) set out, press t_StartThe order that increases, take out one by one to the right next element (tid ', t '_Start, t '_Arrive, did ', sloc '), if t '_ArriveIn T, then repeating step 3) in operation.

In the step 4 that generates temperature figure, if the departure time t of track tid_StartNot in period T, the concrete steps of revising temperature figure matrix F G are:

1) reads track tid from disk, take out first element (vid of track tid₁, t₁);

2) if t₁Not in T, then continue to get its following element, until take out the element (vid of first time of arrival in T_i, t_i);

3) take out element (vid_i, t_i) next first prime element (vid_I+1, t_I+1) (notice that this element is certain existence, because index CFMI only can return relevant (v_d, T) sub-trajectory is not empty track), and with matrix element FG[vid_i] [vid_I+1] value add 1;

4) repeat 3), until get destination v_dTill the element at place.Like this, among the track tid from (vid_i, t_i) to (v_d, t_Vd) the temperature in each highway section added 1 at FG.

In thestep 5 that generates temperature figure, if the departure time t of track tid_StartIn period T, the concrete steps of revising temperature figure matrix F G are:

1) value with sloc the element of array DA.did adds 1;

2) for each element (did, len) among the set DOM, be done as follows:

A) from disk, take out leading track did, and take out first node vid of track did process₁

B) two variable k=1 of initialization, w=0;

C) if vid₁Not v_d, then take out the next node vid of the process of track tid₂

D) if DA.did[k] be not 0 or w be not 0, then the value of w is increased DA.did[k], and with FG[vid₁] [vid₂] value increase w;

E) value with k adds 1;

F) repeat c), until take out destination node v_dTill.

Described search the focus path operations be input as starting point v_sWith based on (v_d, temperature figure G T)_f, concrete steps are as follows:

Step 1 is if temperature figure is G_fBe sky, illustrating does not have track to arrive v in period T_d, return from v_sTo v_dThe focus path be empty;

Step 2 is with temperature figure G_fCall in internal memory.If departure place v_sNot at G_fIn, illustrating does not have track once from v_sTo v_d, return the focus path for empty; Otherwise, continue to carry out following steps.

Step 3 is with F* (v_s, i) be illustrated under the prerequisite on maximum permission i bars limit, from v_sTo v_dThe focus path.For G_fIn each node u, represent the temperature of the F* (u, i) that up to the present finds with u. ￡, represent the immediate successor node of node u among the F* (u, i) with u.suc.Under the original state, if u is not equal to v_d, u. ￡=#(explanation focus path is set does not exist), u.suc=null; Otherwise u. ￡ is set is empty (illustrating that u does not comprise any highway section to the focus path of u).Unless this means u is exactly v_d, otherwise from u to v_dThe focus path that comprises 0 limit is non-existent.

Step 4 is to G_fIn every limit (u, v), with w (u, v) temperature of expression (u, v), and be done as follows: if (w (u, v) ‖ v. ￡)〉u. ￡ illustrates the temperature of F* (u, i), not from u through limit (u, v), pass through again F* (v, the temperature in path i) is high, therefore need to revise F* (u, i), order

u.￡ = w(u, v) ‖ v.￡；

u.suc = v；

Step 5, repeating step 4 be altogether | V_f|-1 time, | V_f| be temperature figure G_fThe sum on middle summit;

Step 6 is from v_sSet out, along the suc pointer to v_dThe path, namely be v_sTo v_dThe focus path.

In the step 4 of searching the focus path, the temperature in two kinds of paths is arranged: a kind of is the temperature in dead circuit footpath, and a kind of is the temperature # that does not have the path.In all path temperatures, temperature be the highest, the temperature of # is minimum.

In the step 4 of searching the focus path, operation " ‖ " is defined as follows:

1) if two non-decreasing sequences that input all is comprised of positive integer, " ‖ " is merged into a non-decreasing sequence with these two sequences.For example: (20) ‖ (5,20)=(5,20,20);

2) if one of them is input as empty sequence, another input will as a result of be returned so.If two inputs all are empty sequences, then as a result of return.For example: ‖ (5,20)=(5,20);

3) if one of them is input as #, then return #.For example: #+(5,20)=#.

Compared with prior art, the present invention has following advantage:

1) the present invention proposes a kind of new method for searching path: based on the focus route searching of period.The present invention allows the user when searching the focus path, selects the interested period.This meets the characteristic of in time dynamic change of focus path very much.Can not only provide accurately result for digital map navigation; Also can be by the variation in the different period focus paths of analysis and comparison, for the complicated applications such as city planning, space-time data excavation provide the core technology support;

2) the present invention has designed a kind of focus path identification method based on the period.The focus path that utilizes the method to find, satisfy the suffix subpath optimum, irrelevant with path, do not contain the good characteristic such as bottleneck road, meet people to the intuitivism apprehension in focus path, can better reflect in the past people's the footpath experience of seeking;

3) the present invention has designed a kind of simple, efficient track data Indexing Mechanism, can not only filter the track data that all and result have nothing to do, can also be by only reading the mode of leading track, reduction is dominated track and is included in other interior a large amount of tracks, can effectively reduce the random reading times of disk, have good extensibility, its space hold is also very low.Secondly, this index also possesses good versatility, can accelerate " in set period, arriving the track of any appointed place " inquiry, cut apart and obtain, be not limited to the search in focus path;

4) the present invention has designed a kind of simple, efficient focus path search algorithm.Fast focus path online query can be provided.Utilize the historical taxi data in more than 1,000 ten thousand Shanghai City, move the method at the separate unit server, (destination that namely arrives is focus, and a lot of track processes are arranged under worst case; Time is whole historical time), the time of searching in focus path is no more than 1 minute.Therefore should the very suitable focus path query based on the large data of historical track of invention.

Description of drawings

The present invention is further described below in conjunction with drawings and Examples.

Fig. 1 is the focus route characteristic identification process figure of first embodiment of the present invention.

Fig. 2 is the trace filtering method schematic diagram of first embodiment of the present invention.

Fig. 3 is the path temperature Relationship Comparison process flow diagram of first embodiment of the present invention.

Fig. 4 is the leading track structural representation of second embodiment of the present invention.

Fig. 5 is the index CFMI building-block of logic of second embodiment of the present invention.

Fig. 6 is the temperature figure visioning procedure figure of the 3rd embodiment of the present invention.

Fig. 7 is that the 3rd embodiment of the present invention searches process flow diagram in CFMI

Fig. 8 is the track departure time processing flow chart in T not among the 3rd embodiment of the present invention

Fig. 9 is the processing flow chart of track departure time in T among the 3rd embodiment of the present invention

Figure 10 is the search routine figure of focus path on temperature figure of the 4th embodiment of the present invention.

Embodiment

Below in conjunction with accompanying drawing, describe the embodiment of focus path identification method of the present invention and fast search mechanism in detail.Listed accompanying drawing for explanation, is not limitation of the present invention only.

Embodiment one

The embodiment of the invention provides a kind of characteristic recognition method in focus path, as shown in Figure 1.Input parameter comprises: road network G, historical track set, departure place v_s, destination v_d, and interested period T.Specifically comprise the steps:

A1. for every historical track, only keep it and arrive destination v_d(comprise v before_d), and the part in T.

A2. calculate the temperature in every highway section for arriving v through this highway section_d(filter after) historical track number;

A3. for every from v_sTo v_dThe path, calculate its temperature and be the non-decreasing arrangement of its institute through the temperature in highway section;

A4. with all from v_sTo v_dThe path entirely sort according to their temperature, what temperature was the highest is exactly in the period T, from v_sTo v_dThe focus path.

Historical track is according to (v_d, the method for T) filtering as shown in Figure 2.Article one, typical track can be designated Y=((v₁, t₁) ..., (v_n, t_n)), wherein, (v₁..., v_n) be the paths in the road network, t_i(1≤i≤n) is that Y arrives node v_iTime.The interested period T=[t of given user_s, t_e], then every track will not be filtered in the part that T generated in the period.Particularly, suppose Y '=((v_k, t_k) ..., (v_h, t_h)) be the result's (sub-trajectory of Y) after track Y is filtered by T, so:

· t_s≤ t_k，t_h≤ t_e；

If k〉1, t then_K-1＜t_s

If h＜n, then t_H+1T_e

Further, we only preserve and arrive v among the Y '_d(comprise v_d) before part.If Y ' is without v_d, Y ' is empty after then filtering.Note, because we suppose that every track all is once significant travelling, so we have reason to think that every track can not repeat through same place (node), so we do not consider to arrive the track part behind the destination.Concrete, 6 track Y1 are arranged to Y6 among Fig. 2.Result after they filter is respectively:

Y1 the path of process be (v₁→ v₂→ v₇→ v_d→ v₅), because v₁Not in T, v₅At v_dAfterwards, the result after therefore filtering is (v₂→ v₇→ v_d);

Y2 the path of process be (v₁→ v₂→ v₇→ v_d), and whole Y2 is in T, so Y2 remains unchanged after filtration.The situation of Y3 and Y4 is the same with Y2, and whole track also remains unchanged after filtering;

Y5 the path of process be (v₁→ v₂→ v₆→ v_d), but v₁Not in T, the result after therefore filtering is (v₂→ v₆→ v_d);

Y6 the path of process be (v₇→ v₆→ v₅), although whole Y6 is in T, because Y6 is without v_dSo the result after filtering is empty.

The comparative approach of path temperature is considered the temperature ofpath P 1 and P2 as shown in Figure 3:

F(P1) = (f¹₁, f¹₂, …, f¹_n)

F(P2) = (f²₁, f²₂, …, f¹_m)

Comparison procedure based on temperature relational calculus provided by the invention is specific as follows:

B1. count initialized device i equals 1;

If b2. i≤min (m, n) turns step b3, otherwise turn step b5;

If f b3.¹_i=f²_i, i is added 1, and turns step b2, otherwise turn step b4;

If f b4.¹_i＜f²_i, then export F (P1)＜F (P2), the temperature that reaches P1 is lower than P2, otherwise turns step b5;

B5. export F (P1) 〉=F (P2), namely the temperature of P1 is not less than P2.

Embodiment two

The embodiment of the invention provides ultimate principle and the logical organization of index CFMI.The ultimate principle of CFMI is to recover a large amount of tracks by reading a small amount of leading track, as shown in Figure 4.Suppose that track Y is by way of node v_i, use Y_{(*, vi)}Indicate track Y and arrive v_i(comprise v before_i) sub-trajectory, with Path (Y_{(*, vi)}) sign Y_{(*, vi)}The path of process.For other any one by way of v_iTrack Y ', if or Path (Y_{(*, vi)}) and Path (Y '_{(*, vi)}) identical, or Path is (Y_{(*, vi)}) be not Path (Y '_{(*, vi)}) suffix, we claim that Y is node v_iLeading track.In Fig. 4, v_iBe the black node in the road net.One has six tracks (Y1 to Y6) arrives this node.Note track Y2 and Y3 the path of process be comprised among the track Y1, track Y4 and Y5 the path of process be comprised among the track Y6, and Y1 and Y6 before arriving the black node the path of process, do not comprised through the path by any other track, so Y1 and Y6 are the leading tracks of black node.

Fig. 5 has described the logical organization of CFMI.In index CFMI, we are each the node v in the road network_iCreate a B+ tree BT_ViBT_ViIndex track arrive v_iTime, and deposited the track number of this track.Each BT_ViLeaf node comprise five territories:

<tid, t_start, t_arrive, did, sloc>

Wherein tid is unique sign of track; t_StartIt is the zero-time of track tid; t_ArriveThat track arrives v_iTime; Did is tid number of the affiliated leading track of track tid; Sloc is the reference position of track tid in track did.Secondly, we are each BT_ViSafeguarded a table v_i-Dom has recorded vertex v in the table_iEvery leading track arrive v_iThe number of vertices of process before.In addition, we have safeguarded a form Table, are used for each node mapping to its corresponding B+ tree.

The upper left corner of Fig. 5 is a road network example.We have indicated eight node (v₁To v₈).Historical track by this road network has 4, and is specific as follows:

Y1 arrives v₂Front part is: ((v₆, t_Y1-v6), (v₇, t_Y1-v7), (v₃, t_Y1-v3), (v₄, t_Y1-v4), (v₂, t_Y1-v2));

Y2 arrives v₁Front part is: ((v₃, t_Y2-v3), (v₄, t_Y2-v4), (v₂, t_Y2-v2), (v₅, t_Y2-v5), (v₁, t_Y2-v1));

Y3 arrives v₁Front part is: ((v₅, t_Y3-v5), (v₁, t_Y3-v1));

Y4 arrives v₁Front part is: ((v₈, t_Y4-v8), (v₁, t_Y4-v1));

Wherein, t_Yi-vjExpression track Yi arrives node v_jTime, and:

t_Y1-v2< t_Y2-v2< t_Y4-v1 < t_Y2-v1 < t_Y3-v1

With BT_V1Be example, its leaf node partial index Y2, Y3 and Y4 arrive node v₁Time, and according to time of arrival they having been carried out the non-decreasing arrangement, because t_Y4-v1＜t_Y2-v1＜t_Y3-v1, so node (Y4, t_Y4-v8, t_Y4-v1, Y4,1) and come Far Left, secondly be node (Y2, t_Y2-v3, t_Y2-v1, Y2,1), rightmost is node (Y3, t_Y3-v5, t_Y3-v1, Y2,1).With node (Y4, t_Y4-v8, t_Y4-v1, Y4,1) and be example, track tid=Y4, t_Start=t_Y4-v8The zero-time that Y4 is described is through v₈Time, t_Arrive=t_Y4-v1Indicated the time of Y4 arrival v1, the leading track that did=Y4 explanation comprises Y4 is exactly Y4 oneself, and sloc=1 explanation Y4 reference position in the leading track under it is 1, and namely the leading track under the Y4 namely is Y4 oneself.Notice that the leading track under the Y3 is Y2, because it arrives v₁Before do through the path be included in the Y2.In addition, table v₁-Dom has comprised two records, illustrates to arrive v₁Leading track have two, i.e. Y2 and Y4.Take Y2 as example, it before arriving v1 the nodal point number of process be 5, i.e. v₃, v₄, v₂, v₅And v₁

Embodiment three

The embodiment of the invention provides creation method and the flow process of temperature figure, as shown in Figure 6.Input road network G (V, E), destination v_dAnd interested period T, temperature figure G_fThe concrete steps that create are as follows:

C1. represent based on (v with adjacency matrix FG_s, v_d, temperature figure G T)_f, all elements is initialized as 0 among the FG;

C2. search index CFMI and return two set: track record set TR and leading track set of records ends DOM.Wherein, set TR has deposited all through (v_d, T) (namely this track has not passed through v in T for sky after the filtration_d) trace information, comprise (tid, t_Start, did, sloc), notice that tid is unique sign of track; Set DOM has deposited the information of the leading track of all tracks among the set TR, comprises (did, len), and wherein did is unique sign of leading track, and len is that leading track arrives v_dThe time the nodal point number of process (comprise v_d);

C3. create a set DA who comprises array, each element among the DA is an array DA.did, the record (did, len) among the corresponding DOM.The length of DA.did is len, and under the original state, all elements of DA.did is 0;

C4. judge that whether set TR is empty, if so, then turns step c8, otherwise turns step c5;

C5. take out element (tid, the t of TR_Start, did, sloc), and judge t_StartWhether in period T.If, turn step c6, otherwise turn step c7;

C6. with array element DA.did[sloc] value add 1, turn step c4;

C7. according to t_StartThe mode in period T is not revised adjacency matrix FG, turns step c4;

C8. according to t_StartMode in period T is revised adjacency matrix FG;

C9. export adjacency matrix FG, FG[i wherein, j] in the expression road network from v_iTo v_jHave the highway section to link to each other, temperature is FG[i, j].

Temperature figure G_fComprised all temperatures and be not 0 highway section, and their nodes of being connected.If the temperature in all highway sections that link to each other with node v among the attention road network G is 0, then v can not appear at temperature figure G_fIn.

Fig. 7 has provided the flow process of searching at index CFMI among the step c2, given input v_dAnd T=[t_s, t_e], concrete steps are as follows:

D1. initialization set TR and set DOM are sky;

D2. in form Table, find B+ tree BT_VdThe deposit position of root node;

D3. from BT_VdRoot node sets out, and finds in leaf node, greater than t_sMinimum t_ArriveThe element at place (tid, t_Start, t_Arrive, did, sloc);

D4. incite somebody to action wherein (tid, t_Start, did, sloc) and insert set TR, and at table v_iSearch track did and corresponding value (arrival v thereof among-the Dom_dThe nodal point number of process) len if (did, len) do not exist in set DOM, then inserts;

D5. along BT_VdPointer in the tree between the leaf node takes out (tid, t_Start, t_Arrive, did, sloc) next node;

If d6. this node exists and t_StartIn T, turn steps d 4, otherwise turn steps d 7;

D7. output set TR and the set DOM.

Fig. 9 has provided track departure time t among the step c7_StartIn the time of not in T, revise the flow process of adjacency matrix FG.Input element (tid, t_Start, did, sloc), period T and FG, concrete steps are as follows:

E1. read track tid from disk, take out first element (vid of track tid₁, t₁);

If t e2.₁Not in T, then continue to read next element (vid_i, t_i), until t_iTill in T;

If vid e3._i=v_d, then turn step e6, otherwise turn step e4;

E4. take out element (vid_i, t_i) next first prime element (vid_I+1, t_I+1);

E5. and with matrix element FG[vid_i] [vid_I+1] value add 1, and turn step e3;

E6. export adjacency matrix FG.

Fig. 8 has provided track departure time t among the step c8_StartIn the time of in T, revise the flow process of adjacency matrix FG.Input set DOM and FG, concrete steps are as follows:

F1. initializing variable k=1, w=0;

F2. take out the next element (did, len) of set DOM;

If f3. this element (did, len) does not exist, then turn step f11; Otherwise turn step f4;

F4. from disk, take out leading track corresponding to did, and take out first node vid of track did process₁

If vid f5.₁V_d, then turn step f2; Otherwise turn step f6;

F6. take out the next node vid of the process of track tid₂

If DA.did[k f7.] be not 0 or w be not 0, then turn step f8, otherwise turn step f10;

F8. the value with w increases DA.did[k];

F9. and with FG[vid₁] [vid₂] value increase w;

F10. the value with k adds 1, and with vid₂Value be assigned to vid₁, and turn step f5;

F11. export adjacency matrix FG.

Embodiment four

The embodiment of the invention provides the search routine of focus path on temperature figure, as shown in figure 10.Be input as starting point v_sWith based on (v_d, temperature figure G T)_f=(V_f, E_f), concrete steps are as follows:

If G g1._fBe sky, illustrating does not have track to arrive v in period T_d, EO; Otherwise turnstep g 2;

G2. with temperature figure G_fCall in internal memory, if departure place v_sNot at G_fIn, illustrating does not have track once from v_sTo v_d, the focus path is empty, EO, otherwise turn step g 3;

G3. use F* (v_s, i) be illustrated under the prerequisite on maximum permission i bars limit, from v_sTo v_dThe focus path.For G_fIn each node u, represent the temperature of the F* (u, i) that up to the present finds with u. ￡, represent the immediate successor node of node u among the F* (u, i) with u.suc.Under the original state, if u is not equal to v_d, u. ￡=#(explanation focus path is set does not exist), u.suc=null; Otherwise u. ￡ is set is empty (illustrating that u does not comprise any highway section to the focus path of u).Unless this means u is exactly v_d, otherwise from u to v_dThe focus path that comprises 0 limit is non-existent;

G4. count initialized device i is 0;

G5. the value with i adds 1.If the value of i is greater than greater than G_fTotal nodal point number | V_f|, EO then; Otherwise turn step g 6;

G6. count initialized device j is 0;

G7. the value with j adds 1, if the value of j is greater than G_fTotal limit number | E_f|, then turnstep g 5; Otherwise turn step g 8;

G8. take out G_fJ bar limit (u, v), with w (u, v) expression (u, v) temperature;

G9. (if w (u, v) ‖ v. ￡)〉u. ￡, F* (u is described, i) temperature, not from u through limit (u, v), pass through again F* (v, the temperature in path i) is high, therefore needs to revise F* (u, i), make u. ￡=w (u, v) ‖ v. ￡, then u.suc=v turns step g 7; Otherwise directly turn step g 7.

From v_sSet out, along the suc pointer to v_dThe path, namely be v_sTo v_dThe focus path.

In the step g 3 of searching the focus path, the temperature in two kinds of paths is arranged: a kind of is the temperature in dead circuit footpath, and a kind of is the temperature # that does not have the path.In all path temperatures, temperature be the highest, the temperature of # is minimum.

In the step g 9 of searching the focus path, operation " ‖ " is defined as follows:

1) if two non-decreasing sequences that input all is comprised of positive integer, " ‖ " is merged into a non-decreasing sequence with these two sequences;

2) if one of them is input as empty sequence, another input will as a result of be returned so.If two inputs all are empty sequences, then as a result of return;

If one of them is input as #, then return #.

Claims (10)

Translated fromChinese

1.基于时段的热点路径的特征识别与快速搜索方法，其特征是：热点路径的新型特征识别策略与基于时段的热点路径高效搜索方法结合，在给定出发地和目的地的情况下，从出发地到目的地最常被使用的热点路径具备后缀路径最优、道路长度无关、不含瓶颈路线的关键特征，给定道路网络，出发地与目的地，感兴趣的时段，以及历史轨迹大数据，利用历史轨迹大数据计算出每条路段的热度；再根据路段的热度，计算出从出发地到目的地的每条路径的热度；对从出发地到目的地的所有路径按照其热度进行非递减排序；热度最高的路径，即是在指定时段内，从出发地到目的地的热点路径；引入轨迹数据索引机制计算路段的热度。1. The feature recognition and fast search method of hotspot paths based on time period, which is characterized in that: the new feature recognition strategy of hotspot paths is combined with the efficient search method of hotspot paths based on time period. The most commonly used hotspot route from the departure point to the destination has the key characteristics of optimal suffix path, independent of road length, and no bottleneck route. Given the road network, departure point and destination, time period of interest, and large historical trajectories Data, use the big data of historical trajectory to calculate the heat of each road section; then calculate the heat of each path from the departure point to the destination according to the heat of the road section; calculate the heat of each path from the departure point to the destination according to its heat Non-decreasing sorting; the path with the highest popularity is the hotspot path from the departure point to the destination within a specified period of time; the trajectory data indexing mechanism is introduced to calculate the popularity of the road section.2.根据权利要求1所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：关键特征中所述后缀路径最优指的是，热点路径的任意后缀子路径，即从热点路径上任意结点到目的地的子路径，也是一条热点路径；道路长度无关指的是，热点路径的选取只和它曾经被使用的次数有关，而不由其长度决定；不含瓶颈路段指的是，热点路径不应包含可以避免的，在指定时段内很少被使用的瓶颈路段。2. the feature recognition and fast search method based on the hotspot path of time period according to claim 1, it is characterized in that: the optimal suffix path described in the key feature refers to any suffix subpath of the hotspot path, i.e. from the hotspot The sub-path from any node on the path to the destination is also a hotspot path; the length of the road is irrelevant, which means that the selection of the hotspot path is only related to the number of times it has been used, not determined by its length; Yes, hotspot routes should not contain avoidable bottlenecks that are rarely used during the specified time period.3.根据权利要求1所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：快速搜索方法包括以下步骤：轨迹的标识与过滤、路段热度的量度、路径热度的矢量标示、路径热度的排名；并结合用于检索在规定时段T内到达某结点vd的所有历史轨迹，并截取它们到达vd前，且在T内的部分的轨迹数据索引机制CFMI（Containment-Based Footmark Index）计算路段的热度。3. The feature recognition and fast search method based on the hotspot path of time period according to claim 1, characterized in that: the fast search method comprises the following steps: identification and filtering of the track, measurement of the heat of the road section, vector labeling of the heat of the path, The ranking of path popularity; combined with the CFMI (Containment-Based Footmark Index) mechanism for retrieving all historical trajectories that reach a certain node vd within a specified period of time T, and intercepting them before reaching vd and within T. ) to calculate the heat of the road segment.4.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：历史轨迹大数据中的每条轨迹都代表一次有意义的旅行，并不是物体行驶轨迹的任意序列，一条典型的轨迹可标识为Y = ((v₁, t₁), …, (v_n, t_n))，其中，(v₁, …, v_n)是路网中的一条路径，t_i(1 ≤ i ≤ n)是Y到达结点v_i的时间；每条轨迹进行过滤，即只考虑其在指定时段内的部分，其余的部分将被删除，不参与路段热度的计算。4. The feature recognition and fast search method based on the hotspot path of time period according to claim 3, characterized in that: each track in the historical track big data represents a meaningful trip, and is not an arbitrary track of the object's driving track. sequence, a typical trajectory can be identified as Y = ((v₁ , t₁ ), …, (v_n , t_n )), where (v₁ , …, v_n ) is a path in the road network, t_i (1 ≤ i ≤ n) is the time when Y reaches node v_i ; each trajectory is filtered, that is, only the part within the specified time period is considered, and the rest will be deleted and will not participate in the calculation of the heat of the road section.5.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：路段的热度是基于特定目的地的，即路段的热度是指途经该路段到达指定目的地的轨迹数，目的地不一定是轨迹的终点，只要轨迹在到达目的地之前经过了该路段即可。5. The feature recognition and fast search method based on the hotspot path of time period according to claim 3, characterized in that: the heat of a road section is based on a specific destination, that is, the heat of a road section refers to the number of people passing through the road section to reach a designated destination. The number of tracks, the destination is not necessarily the end of the track, as long as the track passes through the road segment before reaching the destination.6.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：路径的热度采用矢量进行标示，即路径中所有路段的热度由低到高排序后生成的非递减序列。6. The feature recognition and fast search method for hotspot paths based on time periods according to claim 3, characterized in that: the heat of the path is marked with a vector, that is, the non- descending sequence.7.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：路径基于热度的排名，基于一种新型的热度关系运算：给定两条路径P和P’及它们的热度F(P) = (f₁, f₂, …, f_m)和F(P’) = (f₁’, f₂’, …, f_n’)，如果以下任意两个条件满足一个，我们认为P的热度不小于P’，如果F(P)和F(P’)的值不同，我们认为P的热度大于P’：条件1：F(P)是F(P’)的前缀；条件2：存在q属于集合{1, …, min(m,n)}，使得：1) 对于集合{1, …, q-1}中的任意元素i，均有f_i= f_i’，2) f_q> f_q’。7. The feature recognition and fast search method for hotspot paths based on time periods according to claim 3, characterized in that: paths are ranked based on popularity, based on a new type of heat relationship calculation: given two paths P and P' and their degrees of heat F(P) = (f₁ , f₂ , …, f_m ) and F(P') = (f₁ ', f₂ ', …, f_n '), if any two of the following conditions Satisfies one, we think that the heat of P is not less than P', if the values of F(P) and F(P') are different, we think that the heat of P is greater than P': Condition 1: F(P) is F(P') Prefix of ; Condition 2: There exists q belonging to the set {1, ..., min(m,n)}, such that: 1) For any element i in the set {1, ..., q-1}, f_i = f_i ', 2) f_q > f_q '.8.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：轨迹数据索引机制CFMI（Containment-Based Footmark Index）只从磁盘读取少量的轨迹，并通过记录其他轨迹在这些少量轨迹中的起始位置，还原满足查询条件的其他轨迹的行走路线，该索引从磁盘读取的轨迹中，绝大部分是主导轨迹，即到达vi的路线不被任何其他到达vi的轨迹所覆盖的轨迹：假设轨迹Y途经结点v_i，用Y_(*,vi)标示轨迹Y到达v_i之前（包括v_i）的子轨迹，用Path(Y_(*,vi))标示Y_(*,vi)经过的路径；对于其他任意一条途经v_i的轨迹Y’，如果要么Path(Y_(*,vi))和Path(Y’_(*,vi))相同，要么Path(Y_(*,vi))不是Path(Y’_(*,vi))的后缀，我们称Y为结点v_i的主导轨迹；如果一条轨迹到达v_i的时间在T内，且到达v_i的路线被主导轨迹覆盖，那么可以通过只读取主导轨迹恢复该轨迹走过的路线，只有其时间在到达v_i前跨越T边界的轨迹，才需要单独从磁盘读取。8. The feature recognition and fast search method for time-based hotspot paths according to claim 3, characterized in that: the track data index mechanism CFMI (Containment-Based Footmark Index) only reads a small amount of tracks from the disk, and records The starting position of other trajectories in these small number of trajectories restores the walking routes of other trajectories that meet the query conditions. Most of the trajectories read by the index from the disk are dominant trajectories, that is, the route to vi is not reached by any other The trajectory covered by the trajectory of vi: Assuming that the trajectory Y passes through the node v_i , use Y_(*,vi) to mark the sub-trajectories of the trajectory Y before reaching_vi (including v_i ), use Path(Y_(*,vi) ) Mark the path passed by Y_(*,vi) ; for any other trajectory Y' passing through_vi , if either Path(Y_(*,vi) ) is the same as Path(Y'_(*,vi) ), or Path( Y_(*,vi) ) is not a suffix of Path(Y'_(*,vi) ), we call Y the dominant trajectory of node v_i ; if a trajectory reaches v_i within T, and the time to reach v_i If the route is covered by the dominant track, then the route taken by this track can be recovered by reading only the dominant track. Only the track whose time crosses the T boundary before reaching_vi needs to be read from disk alone.9.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：轨迹数据索引机制CFMI中路网中的每个结点v_i都对应一棵B+树BT_vi，BT_vi索引了轨迹到达v_i的时间，并存放了该轨迹的轨迹号，每个BT_vi的叶结点包含五个域：<tid, t_start, t_arrive, did, sloc>，其中tid是轨迹的唯一标示；t_start是轨迹tid的起始时间；t_arrive是轨迹到达v_i的时间；did是轨迹tid所属主导轨迹的tid号；sloc是轨迹tid在轨迹did中的起始位置。9. The feature recognition and fast search method based on the hotspot path of time period according to claim 3, characterized in that: each node v_i in the road network in the track data indexing mechanism CFMI all corresponds to a B+ tree BT_vi , BT_vi indexes the time when the track arrives at v_i , and stores the track number of the track. Each leaf node of BT_vi contains five fields: <tid, t_start , t_arrive , did, sloc>, where tid is The unique mark of the trajectory; t_start is the start time of the trajectory tid; t_arrive is the time when the trajectory reaches_vi ; did is the tid number of the dominant trajectory to which the trajectory tid belongs; sloc is the starting position of the trajectory tid in the trajectory did.10.根据权利要求3所述的基于时段的热点路径的特征识别与快速搜索方法，其特征是：轨迹数据索引机制CFMI中每个BT_vi维护了一张表v_i-Dom，表中记录了顶点v_i的每条主导轨迹在到达v_i之前经过的顶点个数；CFMI维护了一张表格Table，用于将每个结点映射到其对应的B+树上。10. The feature recognition and fast search method based on the hotspot path of time period according to claim 3, it is characterized in that: in the track data indexing mechanism CFMI, each BT_vi maintains a table v_i -Dom, records in the table The number of vertices that each dominant trajectory of vertex v_i passes before reaching v_i ; CFMI maintains a table Table, which is used to map each node to its corresponding B+ tree.

Images