CN109902139B - R-tree-based track data compression method - Google Patents
R-tree-based track data compression method Download PDFInfo
- Publication number
- CN109902139B CN109902139B CN201910184005.7A CN201910184005A CN109902139B CN 109902139 B CN109902139 B CN 109902139B CN 201910184005 A CN201910184005 A CN 201910184005A CN 109902139 B CN109902139 B CN 109902139B
- Authority
- CN
- China
- Prior art keywords
- tree
- position point
- node
- track data
- data
- 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
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention relates to a track data compression method based on an R tree, which comprises the following steps: initializing a track data sequence; constructing a tree index structure for the track data by adopting the existing R tree index method, and automatically creating a hierarchical model by means of the hierarchical structure of the R tree; sequentially taking out 2 position point data from the k-th track data sequence and judging whether the 2 position point data need to be stored in an R tree or not; and acquiring paired position point data stored in leaf nodes of the R tree by adopting the conventional R tree query method, and constructing a compressed track path in a map model according to the paired position point data. The invention realizes the compression storage of a plurality of discrete track data by utilizing the index structure of the R tree, and has the advantages of high reliability, strong accuracy and the like.
Description
Technical Field
The invention relates to the field of computer software and Geographic Information System (GIS) application, in particular to a track data compression method based on an R tree.
Background
With the technical progress and the continuous maturity of the market, more and more intelligent devices with the geographic positioning function are provided, and the intelligent devices can be GPS (global positioning system) track recording devices or Beidou navigation equipment. The geographical location trajectory data is usually obtained by using a smart device with a geographical positioning function to collect a series of location points of outdoor activities, and each location point includes information such as time, longitude, latitude, altitude and the like. With the popularity of smart devices, more and more people are used to record and share track records. In the process, the intelligent equipment is responsible for collecting the geographical position track data, and the collected geographical position track data is analyzed, transmitted and stored and finally applied to a specific service system.
With the development of traffic, the living standard of people is improved day by day, and trips, tourism, outdoor exercises and the like become faster and more convenient. Outdoor activity track recording is interesting and meaningful, at present, some intelligent devices can form complete track identification on a path going out every day, have the functions of recording daily life and motion tracks, form a daily moving map, write and store track logs, and facilitate future viewing and recall. The daily trace data is more and more saved due to the fact that the user accumulates in the month, and sometimes the user wants to see the trace data synthesized in the month or the year so as to remember the good life of the intravenous drip. In a company engaged in field work, the company or leader wants to view a comprehensive record of the annual track of one or more field workers for decision-making at the decision-making level.
The R tree is a balanced tree-like hierarchical structure, all leaf nodes have the same depth, a leaf node directly contains a target, its parent node contains several leaf nodes, and they are sequentially nested upwards, the root node at the uppermost layer indirectly contains all targets, the root node range is the minimum bounding box containing all targets, the whole tree has only one root node, usually the entry of various operations, such as space query and update operation, etc. In real life, the R tree can be used to store spatial information on a map, such as restaurant addresses, or polygons on a map used to construct streets, buildings, lake edges, and coastlines, and the R tree can also be used to implement compressed storage of trajectory data.
The basic idea of the existing off-line trajectory data compression algorithm is to estimate the importance of each point in a target according to index parameters such as geometric distance, angle, speed and the like from the compression control precision, and delete other secondary points while keeping important feature points (such as end points, local extreme points, inflection points and the like). Taking the Douglas-Peucker algorithm with the highest frequency of use in the application as an example, the original line target is recursively segmented through the maximum offset distance relative to the current datum line (head-to-tail point connecting line), and when the maximum offset distance corresponding to a certain segmentation part is smaller than the set geometric accuracy epsilon, the segmentation part is fitted into the corresponding datum line.
The method can better process a track data sequence containing complete track data, but the effect of compressing and storing a plurality of discrete track data sequences is not ideal, and the redundant stored track data is more.
Disclosure of Invention
In order to solve the technical problem, the invention provides a track data compression method based on an R tree.
The technical scheme of the invention is as follows: comprises the following steps of (a) carrying out,
step 1, initializing a track data sequence;
step 2, constructing a tree-shaped index structure for the track data by adopting the existing R tree index method, and automatically creating a hierarchical model by means of the hierarchical structure of the R tree;
step 3, sequentially taking out 2 position point data from the k (k =1,2,3, \ 8230;, n) th track data sequence, and judging whether the 2 position point data need to be stored in an R tree;
and 4, acquiring paired position point data stored in leaf nodes of the R tree by adopting the conventional R tree query method, and constructing a compressed track path in the map model according to the paired position point data.
The specific mode of the above step 1 of the present invention includes the following steps,
step 1.1, discrete track data sequences are input, namely n track data sequences are input, and the numbers are as follows: 1,2,3, \ 8230;, k, k +1, \ 8230;, n;
step 1.2, i-th position point p of k-th track data sequence ki The longitude value and the latitude value of (c) form a coordinate (x) ki ,y ki ). Wherein x is ki Represents the longitude value, y, of the ith position point of the kth track data sequence ki Representing the latitude value of the ith position point of the kth track data sequence. Ith position point coordinate (x) of kth track data sequence ki ,y ki ) And the (i + 1) th position point coordinate (x) k(i+1) ,y k(i+1) ) Form a rectangle R h (h =1,2,3, \8230;), the ith and i +1 th coordinate point data to be saved are shown as a rectangle R h Is stored in a leaf node of the R-tree.
The specific mode of the step 3 of the present invention includes the following steps,
step 3.1, for the k (k =1,2,3, \8230;, n) th trajectory data sequence, from the 1 st position point p k1 Initially, the R-tree is searched to determine the coordinates (x) of the 1 st position point k1 ,y k1 ) And coordinates (x) of the 2 nd position point k2 ,y k2 ) Rectangular R contained in leaf node of R tree h In, if (x) k1 ,y k1 ) And (x) k2 ,y k2 ) Rectangular R contained in the leaf nodes of the R-tree h Entering step 3.2; if (x) k1 ,y k1 ) Or (x) k2 ,y k2 ) Rectangular R not included in leaf nodes of R-tree h In step (4), entering step 3.3;
step 3.2, the data of the two position points do not need to be stored, namely the 1 st position point p k1 Latitude and longitude coordinates of and 2 nd position point p k2 The longitude and latitude coordinates of (a) need not be stored in the R tree;
step 3.3, the data of the two position points needs to be stored, namely the 1 st position point p k1 Latitude and longitude coordinates and 2 nd position point p k2 The longitude and latitude coordinates of the R tree are stored in a rectangular form;
step 3.4, processing 2,3 rd paired position point data in sequence, 8230, i, i +1 th paired position point data, 8230;
and 3.5, sequentially processing the (k + 1) \ 8230;, n track data sequences.
In the above step 3.1 of the present invention, the R tree is searched, and it is determined whether the coordinates of a certain position point are contained in the rectangular R of the leaf node of the R tree h The specific means in (1) includes the steps of,
step 3.1.1, starting from the root node, judging whether the current node m is a leaf node, and if the current node m is the leaf node, entering step 3.1.2; if not, go to step 3.1.3;
step 3.1.2, sequentially judging the rectangle R pointed by the node item of the current leaf node m h Whether or not the position point p is included ki Coordinate (x) of (2) ki ,y ki ) If yes, returning a true value; if not, returning a false value;
step 3.1.3, sequentially judging the rectangle R pointed by the node item of the current non-leaf node m h Whether or not the position point p is included ki Coordinate (x) of (2) ki ,y ki ) If yes, entering step 3.1.4; if not, judging the next node item of the current non-leaf node m;
step 3.1.4, entering a child node c of the node m according to the node item pointer of the non-leaf node m, and if the child node is a leaf node, entering step 3.1.2; if the child node is not a leaf node, step 3.1.3 is entered.
Compared with the prior art, the invention has the beneficial effects that:
the invention realizes the compression and storage of a plurality of discrete track data by utilizing the index structure of the R tree, can ensure higher track compression quality, and has the advantages of high reliability, strong accuracy and the like. Meanwhile, the method has wide market prospect in the application and popularization of database, data analysis, data mining, track data query and analysis and track data mining.
Drawings
FIG. 1 is a schematic diagram of 2 trace data sequences according to the present invention.
FIG. 2 is a schematic diagram of a rectangle formed by the 1 st track data sequence according to the present invention.
FIG. 3 is a schematic diagram of the R-tree based trace data compression according to the present invention.
FIG. 4 is a diagram of an R-tree structure according to the present invention.
FIG. 5 is a diagram illustrating the output of data compression results according to the present invention.
Detailed Description
The invention will now be further described with reference to the accompanying drawings, which illustrate and describe embodiments.
Referring to FIG. 1, the invention is a schematic diagram of 2 track data sequences, wherein the 1 st track data sequence comprises { p } 11 ，p 12 ，p 13 ，p 14 ，p 15 The 2 nd trace data sequence comprises { p } 21 ，p 22 ，p 23 ，p 24 ，p 25 ，p 26 The sequence of position points. The longitude value and the latitude value of the ith position point of the kth track data sequence form coordinate (x) ki ,y ki ). Wherein x is ki Representative position point p ki Longitude value of (a), y ki Representative position point p ki The latitude value of (a). For example: p is a radical of formula 11 The longitude value and the latitude value of the position point form coordinate (x) of the coordinate point 11 ,y 11 )。
Referring to fig. 2, the 1 st track data sequence of the present invention constitutes a rectangular schematic diagram. Paired position points p ki And p k(i+1) Coordinate (x) of ki ,y ki ) And (x) k(i+1) ,y k(i+1) ) Form a rectangle R h Location points p to be saved ki And p k(i+1) Is represented by a rectangle R h Is stored in a leaf node of the R-tree. For example: paired position point p 11 And p 12 Coordinate (x) of 11 ,y 11 ) And (x) 12 ,y 12 ) Form a rectangle R 1 ；p 12 Position point coordinates (x) 12 ,y 12 ) And p 13 Position point coordinates (x) 13 ,y 13 ) Form a rectangle R 2 。
Referring to fig. 3, the R-tree based trace data compression scheme of the present invention is shown. Let the compression algorithm start from the 1 st track data sequence, and from the 1 st position point p 11 Initially, look up the R tree, determine p 11 Coordinates (x) of the location point 11 ,y 11 ) And 2 nd position point p 12 Coordinate (x) of (2) 12 ,y 12 ) Whether or not to include a rectangle R stored at a leaf node of the R-tree h In (c), the result is (x) 11 ,y 11 ) And (x) 12 ,y 12 ) All do not include a rectangle R held at a leaf node of the R-tree h Of (2), the two location point data p 11 And p 12 Need to be preserved, i.e. p 11 Latitude and longitude coordinates and p of location point 12 The longitude and latitude coordinates of the location point are in a rectangle R 1 The form of (d) is stored in the R tree. Sequential treatment of p 12 And p 13 Location point data, p 13 And p 14 Location point data, p 14 And p 15 Position point data having longitude and latitude coordinates in a rectangular R h The form of (d) is stored in the R tree.
Next, the 2 nd track data sequence, p, is processed 21 The location point being contained in the rectangle R 1 In, p 22 The location point being contained in the rectangle R 2 In, so p 21 And p 22 The location point data need not be saved into the R-tree. p is a radical of 22 And p 23 The location point data also need not be saved into the R-tree. Next process p 23 And p 24 Location point data, albeit p 23 The location point being contained in the rectangle R 3 In but p 24 Position point has noLeaf node rectangle R contained in R tree h In, so p 23 And p 24 The location point data needs to be saved into the R-tree. p is a radical of 24 And p 25 Position point data and p 25 And p 26 The location point data needs to be saved into the R-tree.
Referring to fig. 4, the R-tree structure of the present invention is schematically illustrated. The example R-tree contains 4 nodes, where node 1, node 2 and node 3 are leaf nodes whose node entries point to the rectangle R h Rectangular R h Containing the position point p ki Coordinate (x) ki ,y ki ) And p k(i+1) Position point coordinates (x) k(i+1) ,y k(i+1) ). Node 4 is the root node of the R-tree. In view of FIG. 3, the node item of node 4 points to its child node, and each node item represents a rectangle R h A rectangle containing child nodes. For example, node item rectangle R for node 4 8 Rectangle R containing node 1 1 ，R 2 And R 3 ；R 9 Rectangle R containing node 2 4 ，R 5 ；R 10 Rectangle R containing node 3 6 ，R 7 。
Searching the R tree, and judging whether the coordinates of a certain position point are contained in a rectangle R of a leaf node of the R tree or not h Examples of (a) are as follows. Let p be 25 And p 26 If the position point data has not been processed, then rectangle R 7 Is absent, R 10 Containing only rectangles R 6 . Now it is necessary to judge p 26 Whether the location point is contained in a leaf node of the R-tree. First, the node items from the root node 4 are compared in order, rectangle R 8 Does not contain p 26 At a point of position, R need not be compared again 8 Child node 1; rectangle R 9 Nor p 26 Position point, at this time, R 10 Nor p 26 A location point. Thus, p 25 And p 26 The location point data needs to be saved into the R-tree.
Referring to fig. 5, a schematic diagram of data compression result output according to the present invention is shown. And acquiring paired position point data stored in leaf nodes of the R tree by adopting the conventional R tree query method, and constructing a compressed track path in a map model according to the paired position point data.
In summary, after reading the present disclosure, those skilled in the art can make various other corresponding changes without creative mental work according to the technical solutions and concepts of the present disclosure, and all of them are within the protection scope of the present disclosure.
Claims (1)
1. A track data compression method based on an R tree is characterized in that: comprises the following steps of (a) carrying out,
step 1, initializing a track data sequence;
the specific mode of the step 1 comprises the following steps,
step 1.1, discrete track data sequences are input, namely n track data sequences are input, and the number of the sequences is as follows: 1,2,3, \ 8230;, k, k +1, \ 8230;, n;
step 1.2, i-th position point p of k-th track data sequence ki The longitude value and the latitude value of (c) form a coordinate (x) of the coordinate point ki ,y ki ) (ii) a Wherein x is ki Representing the longitude value, y, of the ith position point of the kth track data sequence ki Representing the latitude value of the ith position point of the kth track data sequence;
step 2, constructing a tree-shaped index structure for the track data by adopting the existing R tree index method, and automatically creating a hierarchical model by means of the hierarchical structure of the R tree; ith position point coordinate (x) of kth track data sequence ki ,y ki ) And the (i + 1) th position point coordinate (x) k(i+1) ,y k(i+1) ) Form a rectangle R h (h =1,2,3, \8230;), the ith and i +1 th coordinate point data to be saved are shown as a rectangle R h Is stored in a leaf node of the R tree;
step 3, sequentially taking out 2 position point data from the k (k =1,2,3, \ 8230;, n) th track data sequence, and judging whether the 2 position point data need to be stored in an R tree;
the specific mode of the step 3 comprises the following steps,
step 3.1, for the k (k =1,2,3, \8230;, n) th trajectory data sequence, from the 1 st position point p k1 Initially, the R-tree is searched to determine the coordinates (x) of the 1 st position point k1 ,y k1 ) And coordinates (x) of the 2 nd position point k2 ,y k2 ) Whether or not to include a rectangle R at a leaf node of the R-tree h In, if (x) k1 ,y k1 ) And (x) k2 ,y k2 ) Rectangles R all contained in leaf nodes of the R-tree h Entering step 3.2; if (x) k1 ,y k1 ) Or (x) k2 ,y k2 ) Rectangle R not included in leaf node of R tree h Entering step 3.3;
step 3.2, the data of the two position points do not need to be stored, namely the 1 st position point p k1 Latitude and longitude coordinates of and 2 nd position point p k2 The longitude and latitude coordinates of (a) need not be stored in the R tree;
step 3.3, the data of the two position points needs to be stored, namely the 1 st position point p k1 Latitude and longitude coordinates of and 2 nd position point p k2 The longitude and latitude coordinates of the tree are stored in an R tree in a rectangular form;
step 3.4, processing 2,3 rd paired position point data in sequence, 8230, i, i +1 th paired position point data, 8230;
step 3.5, processing the (k + 1) \ 8230;, n track data sequences in sequence;
in the step 3.1, the R tree is searched, and whether the coordinate of a certain position point is contained in the rectangle R of the leaf node of the R tree or not is judged h The specific means in (1) comprises the steps of,
step 3.1.1, starting from the root node, judging whether the current node m is a leaf node, and if the current node m is the leaf node, entering step 3.1.2; if not, go to step 3.1.3;
step 3.1.2, sequentially judging the rectangle R pointed by the node item of the current leaf node m h Whether or not to include the position point p ki Coordinate (x) of ki ,y ki ) If yes, returning a true value; if not, returning a false value;
step 3.1.3, sequentially judging the rectangle R pointed by the node item of the current non-leaf node m h Whether or not the position point p is included ki Coordinate (x) of ki ,y ki ) If yes, entering step 3.1.4; if not, judging the next node item of the current non-leaf node m;
step 3.1.4, entering a child node c of the node m according to the node item pointer of the non-leaf node m, and if the child node is a leaf node, entering step 3.1.2; if the child node is not a leaf node, entering step 3.1.3;
and 4, acquiring paired position point data stored in leaf nodes of the R tree by adopting the conventional R tree query method, and constructing a compressed track path in the map model according to the paired position point data.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910184005.7A CN109902139B (en) | 2019-03-12 | 2019-03-12 | R-tree-based track data compression method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910184005.7A CN109902139B (en) | 2019-03-12 | 2019-03-12 | R-tree-based track data compression method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109902139A CN109902139A (en) | 2019-06-18 |
| CN109902139B true CN109902139B (en) | 2022-10-28 |
Family
ID=66946937
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910184005.7A Active CN109902139B (en) | 2019-03-12 | 2019-03-12 | R-tree-based track data compression method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109902139B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110553661B (en) * | 2019-09-16 | 2023-02-03 | 湖南科技大学 | R-tree-based user position-to-target area path recommendation method |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102646070A (en) * | 2012-02-29 | 2012-08-22 | 武汉大学 | Space-time trajectory data storage method based on area |
| CN106095802A (en) * | 2016-05-31 | 2016-11-09 | 南京邮电大学 | Full-time state Indexing for Moving Object based on R tree on city road network |
| KR20160135907A (en) * | 2015-05-18 | 2016-11-29 | 동아대학교 산학협력단 | An extended System and Method for searching nearest spatial entity based on tree index |
| CN109241126A (en) * | 2018-06-29 | 2019-01-18 | 武汉理工大学 | A kind of space-time trajectory accumulation mode mining algorithm based on R* tree index |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10088324B2 (en) * | 2016-05-02 | 2018-10-02 | International Business Machines Corporation | Trajectory data compression |
-
2019
- 2019-03-12 CN CN201910184005.7A patent/CN109902139B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102646070A (en) * | 2012-02-29 | 2012-08-22 | 武汉大学 | Space-time trajectory data storage method based on area |
| KR20160135907A (en) * | 2015-05-18 | 2016-11-29 | 동아대학교 산학협력단 | An extended System and Method for searching nearest spatial entity based on tree index |
| CN106095802A (en) * | 2016-05-31 | 2016-11-09 | 南京邮电大学 | Full-time state Indexing for Moving Object based on R tree on city road network |
| CN109241126A (en) * | 2018-06-29 | 2019-01-18 | 武汉理工大学 | A kind of space-time trajectory accumulation mode mining algorithm based on R* tree index |
Non-Patent Citations (2)
| Title |
|---|
| OCT: A Novel Opportunistic Compression and Transmission Approach for Private Car Trajectory Data;Jie Chen;《2018 Data Compression Conference》;20180723;全文 * |
| 一种集成R树、哈希表和B*树的高效轨迹数据索引方法;龚俊;《测绘学报》;20150531;第44卷(第5期);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109902139A (en) | 2019-06-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US9880012B2 (en) | Hybrid road network and grid based spatial-temporal indexing under missing road links | |
| CN112182410B (en) | User travel mode mining method based on space-time track knowledge graph | |
| US10140324B2 (en) | Processing spatiotemporal data records | |
| CN103294790B (en) | A kind of space and time order towards GPS track data indexes and search method | |
| CN106649656A (en) | Spatial-temporal trajectory big data storage method for database | |
| CN102375879A (en) | Mobile GIS (Geographic Information System) system based on intelligent mobile phone and application thereof | |
| CN102915326A (en) | Mobile terminal scenery identifying system based on GPS (Global Positioning System) and image search technique | |
| Li et al. | Robust inferences of travel paths from GPS trajectories | |
| CN111522892B (en) | Geographic element retrieval method and device | |
| Lin et al. | Noise filtering, trajectory compression and trajectory segmentation on GPS data | |
| CN111475746B (en) | Point-of-interest mining method, device, computer equipment and storage medium | |
| CN113656477A (en) | Method for verifying and fusing multi-source heterogeneous data of homeland space | |
| CN106326448A (en) | GIS (geographic information system) information collecting method and system | |
| Ladner et al. | Mining Spatio-Temporal Information Systems | |
| CN111427976B (en) | Road freshness obtaining method and device | |
| CN109902139B (en) | R-tree-based track data compression method | |
| CN110542914A (en) | 3S seamless integrated land law enforcement field dynamic patrol method | |
| CN110555174B (en) | R-tree-based track path recommendation method | |
| CN107092611A (en) | A kind of determination of positional information, information-pushing method and equipment | |
| Rashid et al. | Challenging issues of spatio-temporal data mining | |
| Li et al. | Spatial Data Science | |
| CN110553661B (en) | R-tree-based user position-to-target area path recommendation method | |
| Sasaki et al. | Thematic geo-density heatmapping for walking tourism analytics using semi-ready GPS trajectories | |
| Mariescu-Istodor | Efficient management and search of GPS routes | |
| CN107544079B (en) | Track route recording method and system applied to soil environment monitoring |
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 |