CN113656670B - Flight data-oriented spatiotemporal trajectory data management and analysis method and device - Google Patents
Flight data-oriented spatiotemporal trajectory data management and analysis method and device Download PDFInfo
- Publication number
- CN113656670B CN113656670B CN202110965172.2A CN202110965172A CN113656670B CN 113656670 B CN113656670 B CN 113656670B CN 202110965172 A CN202110965172 A CN 202110965172A CN 113656670 B CN113656670 B CN 113656670B
- Authority
- CN
- China
- Prior art keywords
- target
- track
- point
- data
- time
- 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
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/907—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F16/909—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using geographical or spatial information, e.g. location
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2458—Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
- G06F16/2462—Approximate or statistical queries
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Databases & Information Systems (AREA)
- Probability & Statistics with Applications (AREA)
- General Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Fuzzy Systems (AREA)
- Computational Linguistics (AREA)
- Software Systems (AREA)
- Mathematical Physics (AREA)
- Library & Information Science (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a space-time trajectory data management analysis method and device for flight data, which are used for solving the problem that the existing system cannot well support space-time data range query. The method comprises the steps of obtaining space-time track data, establishing a space index, inquiring target data blocks of which all track points belong to a target polygon area in a target time period by using a space-time polygon range inquiring algorithm, wherein the space-time polygon range inquiring algorithm comprises the steps of calculating the minimum outsourcing rectangle of the target polygon area, screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the data blocks, adding a candidate result set, and determining the data blocks of which the track points in the target polygon area and the track time are in the target time period in the candidate set as the target data blocks.
Description
Technical Field
The invention belongs to the technical field of data management analysis, and particularly relates to a space-time trajectory data management analysis method and device for flight data.
Background
In recent years, with the wide application of positioning technology, application devices such as an internet of things sensor, a GPS wearable device, a smart phone, a satellite and the like are widely used, and massive space-time data is continuously generated from different application sources. The large amount of spatiotemporal data exceeds the storage, processing and analysis capabilities of the original system. The space-time data is closely related, large in volume, complex in structure, low in diversity and value density, and is difficult to store, manage and analyze efficiently. While traditional relational databases are limited to single-machine architecture and cannot cope with the scene of massive data, distributed query processing frameworks such as Spark, hadoop and the like lack effective space-time index and space-time analysis algorithms, so that it is difficult to efficiently process space-time data.
Therefore, aiming at the limitation of the existing data management system, based on the performance requirements of data management and analysis, researchers propose secondary development aiming at Spark, hadoop, noSQL and other platforms, spatial index and spatial query algorithms are embedded, and the MapReduce task is utilized to parallelize the spatial query algorithms, so that the data processing speed is improved. However, the method does not consider the time dimension or support the time-space index when processing the time-space data, so that a large amount of invalid data can be scanned when executing the time-space range query, and the query efficiency can not be ensured.
Aiming at a range query algorithm, the current research work only researches coarse-grained rectangular range query and does not consider the problem of polygonal range query under space-time injection conditions. In practice, the query scope of a polygon is a set of complex polygons that do not overlap, typically on the order of thousands, while the input is a large dataset containing hundreds of millions or even billions of points of space. Performing data analysis or computational aggregation tasks on these spatiotemporal data points adds additional CPU cost overhead, and as spatiotemporal data increases, the system may not scale well.
The information disclosed in this background section is only for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person of ordinary skill in the art.
Disclosure of Invention
The invention aims to provide a space-time trajectory data management analysis method for flight data, which is used for solving the problem that the existing system cannot well support space-time data range query.
In order to achieve the above object, the present invention provides a space-time trajectory data management analysis method for flight data, including:
Acquiring spatio-temporal trajectory data and establishing a spatial index comprising a plurality of data blocks, and
Querying a target data block of which all track points belong to a target polygonal area in a target time period by utilizing a space-time polygonal range query algorithm;
wherein the space-time polygon range query algorithm comprises:
calculating the minimum outsourcing rectangle of the target polygonal area;
screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the plurality of data blocks, and adding a candidate result set;
And determining the data blocks of which the candidate concentrated track points are positioned in the target polygon area and the track time is positioned in the target time period as target data blocks.
In one embodiment, the method further comprises counting the target airspace flow based on the space-time polygon range query algorithm, and specifically comprises the following steps:
dividing a target airspace sector into a plurality of regular cylinders;
Filtering out track points positioned in each column based on the space-time polygon range query algorithm and by using the upper limit and the lower limit of the height of each column as constraint conditions so as to be added into a counting queue;
and carrying out data deduplication on the track points in the counting queue to obtain the target airspace flow.
In an embodiment, performing data deduplication on the track points in the counting queue to obtain a target airspace flow, which specifically includes:
Defining a track id attribute and an affiliated column Vid for the track points in the counting queue;
When each column executes a space-time polygon range query algorithm, if the track point is in the column, marking the Vid of the track id attribute as the Vid of the current column to form a compound key < Trajid, vid >;
And carrying out data deduplication on the track points of the counting queue by utilizing the compound keys recorded in each row.
In one embodiment, the method further comprises calculating k track points adjacent to the target query point based on the KNN query algorithm, thereby capturing the space-time track data correlation, and specifically comprises the following steps:
Searching data blocks intersecting with the target query point in the plurality of data blocks, and adding the data blocks to a first priority queue;
Calculating the distance dist p between each data block in the first priority queue and the target query point;
Calculating the kth shortest distance dist k between the track point of each data block in the first priority queue and the target query point;
determining a data block corresponding to the track point meeting dist p＜distk as a candidate data block;
adding a track point, of which the track time is positioned in a target time period and the distance dist (i, q) from a target query point is smaller than dist k, in the candidate data block to a second priority queue;
Generating a test range which takes a target query point as a center and takes the distance between the target query point and a kth neighbor track point as a radius;
and determining k track points adjacent to the target query point based on the test result of the test range on the track points in the second priority queue.
In an embodiment, based on the test result of the test range on the trace points in the second priority queue, determining k trace points adjacent to the target query point specifically includes:
Judging whether the test range intersects with other data blocks or not, if not,
K track points in the test range are determined to be k track points close to the target query point, and if yes,
Calculating the distance dist between the track point in the data block intersected with the test range and the target query point, and adding the track point replacement with dist smaller than dist k in the second priority queue into the second priority queue.
In an embodiment, the query method for querying a target data block in which all track points in the plurality of data blocks belong to a target polygon area in a target time period by using a space-time polygon range query algorithm specifically includes:
Storing the abscissa of each track point of the target polygon area in an array X [ ], and storing the ordinate in an array Y [ ], and obtaining the maximum value X max and the minimum value X min of the array X [ ], and the maximum value Y max and the minimum value Y min of the array Y [ ];
Judging whether the track point is in the minimum outsourcing rectangle (x min,ymin)-(xmax,ymax) of the target polygon area, if not,
The trace point is determined not to belong to the target polygon area and if so,
The ray is led out from the track point to intersect with the target polygon area, and whether the track point belongs to the target polygon area is determined based on the intersecting point number.
In one embodiment, space-time trajectory data is acquired and a spatial index is established, where the spatial index includes a plurality of data blocks, and specifically includes:
Defining a space-time trajectory data set p= { p 1,p2,..,pn }, wherein each trajectory point p 1、p2、…、pn is expressed as (lng, lat, t), lng represents longitude, lat represents latitude, and t represents time attribute;
abstracting the longitude lng and the latitude lat of each track point into coordinates < x, y > of points on a two-dimensional plane, and defining two points on the two-dimensional plane The Euclidean distance of (2)
The invention also provides a space-time track data management analysis device facing the flight data, which comprises:
an index establishing module for acquiring the space-time track data and establishing a spatial index comprising a plurality of data blocks, and
The query module is used for querying a target data block of which all track points belong to a target polygonal area in a target time period by utilizing a space-time polygonal range query algorithm;
wherein the space-time polygon range query algorithm comprises:
calculating the minimum outsourcing rectangle of the target polygonal area;
screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the plurality of data blocks, and adding a candidate result set;
And determining the data blocks of which the candidate concentrated track points are positioned in the target polygon area and the track time is positioned in the target time period as target data blocks.
The present invention also provides a computing device comprising:
At least one processor, and
A memory storing instructions that, when executed by the at least one processor, cause the at least one processor to perform the method as described above.
The present invention also provides a machine-readable storage medium storing executable instructions that, when executed, cause the machine to perform a method as described above.
Compared with the prior art, according to the space-time trajectory data management analysis method for flight data, the target data blocks belonging to the target polygonal area in the constructed spatial index are rapidly inquired through the proposed space-time polygonal range inquiry algorithm, the problem that the existing space-time data platform does not support a space-time data structure is solved, the efficiency and the precision of space-time range inquiry are skipped, the space-time KNN inquiry algorithm is provided, the variety of space-time analysis operation algorithm is enriched, the space-time inquiry efficiency is improved, and meanwhile, a strategy for counting space flow is provided, and the inquiry efficiency and the function expandability are improved.
Drawings
FIG. 1 is a flow chart of one embodiment of a method for spatio-temporal trajectory data management analysis for flight data according to the present invention;
FIG. 2 is a system architecture diagram of an application scenario of a space-time trajectory data management analysis method for flight data according to the present invention;
FIG. 3 is a flow chart of a spatio-temporal polygonal range query algorithm in an embodiment of a spatio-temporal trajectory data management analysis method for flight data according to the present invention;
FIG. 4 is a flowchart of a spatiotemporal KNN query algorithm in an embodiment of a spatiotemporal trajectory data management analysis method oriented to flight data in accordance with the present invention;
FIG. 5 is a flow chart of a statistical airspace flow in an embodiment of a method for space-time trajectory data management analysis for flight data according to the present invention;
FIG. 6 is a block diagram of one embodiment of a spatio-temporal trajectory data management analysis device for flight data according to the present invention;
FIG. 7 is a hardware architecture diagram of one embodiment of a flight data oriented spatio-temporal trajectory data management analysis computing device in accordance with the present invention.
Detailed Description
The following detailed description of embodiments of the invention is, therefore, to be taken in conjunction with the accompanying drawings, and it is to be understood that the scope of the invention is not limited to the specific embodiments.
Throughout the specification and claims, unless explicitly stated otherwise, the term "comprise" or variations thereof such as "comprises" or "comprising", etc. will be understood to include the stated element or component without excluding other elements or components.
Referring to fig. 1 and 2, a specific embodiment of the space-time trajectory data management analysis method for flight data according to the present application will be described. In this embodiment, the method includes:
s11, acquiring space-time track data and establishing a spatial index.
First, a spatio-temporal trajectory dataset p= { p 1,p2,..,pn }, where each trajectory point p 1、p2、…、pn is denoted (lng, lat, t), lng denotes longitude, lat denotes latitude, and t denotes time attribute, is defined. In this embodiment, in order to locate the distance between the object and the calculation point in space, the distance is calculated using the euclidean space. The distance between two points in space is expressed by Euclidean distance, namely, the longitude lng and the latitude lat of each track point are abstracted into coordinates < x, y > of the points on a two-dimensional plane, and the two points on the two-dimensional plane are definedThe Euclidean distance of (2)Thus, the reading and storing of the spatiotemporal trajectory data is completed.
Then, a spatial index is established for the space track data, and each indexed data block is represented by a partition. Index type is represented by index, input data is represented by input, and output data is represented by output. There may be different ways of index establishment depending on the type of index.
S12, querying a target data block of which all track points belong to a target polygonal area in a target time period by utilizing a space-time polygonal range query algorithm.
With reference to fig. 3 in particular, the spatiotemporal polygonal range query algorithm includes:
S121, calculating the minimum outsourcing rectangle of the target polygon area.
Here, a set of spatio-temporal trajectory data sets p= { p 1,p2,..,pn } is first defined as a set of spatio-temporal trajectory data sets made up of spatio-temporal trajectory objects in E d (D-dimensional euclidean space), for each trajectory point i E D, i= (lng, lat, t), lng representing longitude, lat representing latitude, t representing time attribute.
And setting query range parameters, including a time dimension query range and a space dimension query range. The time query range is denoted by t=τ e (τ begin,τend), where τ begin denotes the start time and τ end denotes the end time. The polygonal query range q is composed of a set of spatial points that make up its boundary. The minimum envelope rectangle mbr of the polygon is calculated using a positive integer n, a set of X-axis coordinates x= { X 1,x2,…,xn }, a set of Y-axis coordinates y= { Y 1,y2,…,yn }, and a set of Y-axis coordinates y= { Y 1,y2,…,yn }.
S122, screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the data blocks, and adding a candidate result set.
For each index data block part obtained in the above steps, it may be first determined whether the part and the minimum package rectangle mbr intersect, if so, then determine whether the part intersects the polygon query range q, and if so, add the current part to the candidate result set. Otherwise, continuing to judge the next part until the screening of all parts is completed.
S123, determining the data blocks of which the candidate concentrated track points are located in the target polygon area and the track time is located in the target time period as target data blocks.
For each part in the candidate set, a PNPoly algorithm is called to judge whether each track point i is in the target polygon area, and meanwhile, the judgment of the time query range is carried out, and if yes, the time query range is returned and output.
Specifically, the abscissa of each trace point of the target polygon area is stored in an array X [ ], and the ordinate is stored in an array Y [ ], and the maximum value X max and the minimum value X min of the array X [ ], and the maximum value Y max and the minimum value Y min of the array Y [ ] are obtained;
The method comprises the steps of representing a queried track point by using a test x,testy, judging whether the track point (test x,testy) is in a minimum outsourcing rectangle (x min,ymin)-(xmax,ymax) of a target polygonal area, if not, determining that the track point does not belong to the target polygonal area, if so, leading out rays from the track point to intersect the target polygonal area, and determining whether the track point belongs to the target polygonal area based on the number of the intersected points.
Here, if the ray extracted from the trace point has an odd number of points intersecting the target polygon area, it is indicated that the trace point is located within the target polygon area, and if the ray extracted from the trace point has an even number of points intersecting the target polygon area, it is indicated that the trace point is located outside the target polygon area.
In some embodiments, the space-time trajectory data management analysis method for flight data of the present application further comprises:
S13, calculating k track points adjacent to the target query point based on the KNN query algorithm, and therefore capturing the space-time track data correlation.
In a specific process, referring to fig. 4, the method may first perform initialization, where q represents a certain target query point, and k represents a threshold value of q neighboring points to be queried. The time query range is denoted by t=τ e (τ begin,τend), where τ begin denotes the start time and τ end denotes the end time. Two priority queues, a first priority queue PQ and a second priority queue RQ, are defined, wherein PQ represents all the part sets intersecting the query point q, and the parts in the priority queues can be ordered by distance because the parts may not be unique. Each part in PQ is denoted by p, and candidate trace points satisfying knn conditions are denoted by RQ priority queue.
Next, an initial result is generated. The method comprises the steps of searching data blocks intersecting with a target query point in a plurality of data blocks, adding the data blocks to a first priority queue PQ, calculating the distance dist p between each data block in the first priority queue PQ and the target query point, calculating the kth shortest distance dist k (initialized to 0) between the track point of each data block in the first priority queue and the target query point, and determining the data blocks corresponding to the track points meeting dist p＜distk as candidate data blocks. At this time, the candidate data block that indicates that the condition is satisfied contains the initial result.
The first priority queue PQ here may be a queue in which each data block part is ordered according to a set rule. In one embodiment, for example, the data blocks are arranged in descending order according to the dist p size.
Next, performing time range matching on each track point i in the candidate data block, and adding a track point i with track time in the candidate data block being within the target time period and having a distance dist (i, q) from the target query point smaller than dist k to the second priority queue RQ, so as to obtain a second priority queue RQ composed of initial results.
The distance formula for calculating the data block part and the target query point q is as follows:
Where p represents each partirion in the PQ queue, i represents each trace point in p, q represents the target query point, and dist (i, q) represents the distance of trace point i from query point q.
Similarly, the second priority queue RQ may also be configured to order each data block therein according to a set rule. In one embodiment, for example, the data blocks are arranged in descending order according to the dist k size.
Finally, the initial results are tested to determine the final results. Specifically, a test range C (for example, a circle) centered on the target query point and having a radius from the kth neighboring trace point may be generated, and k trace points adjacent to the target query point may be determined based on a test result of the test range on the trace points in the second priority queue.
The method comprises the steps of judging whether a test range C is intersected with other data blocks, determining k track points in the test range as k track points close to a target query point if the test range C is not intersected with the other data blocks, calculating the distance dist between the track points in the data blocks intersected with the test range and the target query point if the test range C is not intersected with the other data blocks, and adding the track points of which the dist is smaller than the dist k in a second priority queue RQ to the second priority queue in a replacement mode.
During execution, the final result may be generated by m rounds of iteration under time constraints. The size of m depends on the distribution of trace points of the original dataset and the location of the target query point q. In each iteration, selecting a data block part, traversing all track points in the part, calculating the distance dist of a target query point q, comparing the selected target track point i and the dist corresponding to the target track point i with the tail element dist k of a second priority queue RQ (the data blocks in the RQ are arranged according to the descending order of dist k), if dist is less than or equal to dist k, indicating that i is more in line with a target result, writing the selected track point i and the dist corresponding to the selected track point i into the RQ, and if not, discarding and continuing to search for the next target point. And updating the elements in the second priority queue RQ according to the arrangement rule of the priority queue. After k rounds of iteration, k nearest results (trace points) are finally generated.
S14, counting the target airspace flow based on the space-time polygon range query algorithm.
Referring to fig. 5 in conjunction, specifically, the airspace sector parameters are first acquired. And counting the airspace flow, namely counting the number of all the aircrafts passing through in one sector. Dividing a target airspace Sector into a plurality of regular cylinders, wherein the cross section of each cylinder is a polygon formed by a plurality of points, defining a space query range of a three-dimensional Sector represented by a Sector, and the Sector is formed as follows:
Sector:<Sid,List<Volume>>
Volume:<Vid,lower,upper,List<Point>>
Point:<Pid,lng,lat>
Where Sid represents the unique id of the Sector, and List < Volume > represents that the Sector consists of a series of columns. The column is defined by Volume, the unique id of the column is represented by Vid, the lower column height bound is represented by lower, the upper column height bound is represented by upper, and the polygonal cross section of the column is represented by List < Point >. Point represents a plurality of vertices that make up the polygon. In addition, since the column is a three-dimensional space, the height attribute alt of the track point is introduced to represent the height of the track in the airspace.
Second, a Count queue is defined to record all the trace points of the aircraft passing through the sector. Based on the space-time polygonal range query algorithm, the flow passing through the single column is filtered by using the upper limit and the lower limit of the height of each column as constraint conditions. Namely:
PNPoly and τ start≤i.t≤τend and lower is less than or equal to i.alt is less than or equal to upper
Wherein, i is PNPoly that the track point i is in the polygon, tau start≤i.t≤τend that the time of the track point is in the constraint condition, lower is less than or equal to i.alt is less than or equal to upper, and the height of the track point is between the upper boundary and the lower boundary of the column. And judging whether the track point passes through the airspace sector or not based on the conditions. If yes, adding the data to a counting queue, otherwise, discarding the data. This step is performed in a loop until all columns of the sector have been traversed.
And finally, carrying out data deduplication on the track points in the counting queue to obtain the target airspace flow. Sector traffic may be represented by the record count res after de-duplication of the count queue. Taking an aircraft as an example, its time-space trajectory points may appear in more than one cylinder, so duplicate trajectory points need to be deduplicated to ensure that the trajectory points of the aircraft through a certain sector are counted only once, and finally returned to res.
In a specific de-duplication process, defining a track id attribute (Trajid attribute) and a column Vid (initialized to 0) of the track point in the counting queue, when each column executes a space-time polygon range query algorithm, if the track point i is in a column Volume, marking the Vid of the track id attribute as the Vid of the current column to form a compound key < Trajid, vid >, and performing data de-duplication on the track point of the counting queue by utilizing the compound key recorded in each row.
Referring to fig. 2, a space-time trajectory data system applied to the space-time trajectory data management analysis method for flight data proposed in the above embodiment is shown. Including storage and processing nodes, indexing layers, spatio-temporal operation algorithms, statistical airspace traffic, and user requests. The method comprises the steps of storing a space-time track data set in an HDFS file system of a Hadoop platform, establishing indexes on a data source by an index layer, supporting different space-time indexes (Grid indexes, rtree indexes, KDTree indexes and the like), performing a space-time operation algorithm, namely a space-time polygon range query algorithm and a space-time KNN algorithm, according to the space-time operation, realizing application service for counting space flow, storing a final result on the HDFS, and timely processing a request and returning the final result when an external space-time query request is accessed into the system. The user obtains the final result directly on the HDFS.
Referring to fig. 6, the embodiment of the application further provides a space-time trajectory data management analysis device facing the flight data. The system comprises an index establishment module, a query module, a flow statistics module and a capturing module.
An index establishing module for acquiring the space-time track data and establishing a space index, the spatial index includes a plurality of data blocks;
The query module is used for querying a target data block of which all track points belong to a target polygonal area in a target time period by utilizing a space-time polygonal range query algorithm;
wherein the space-time polygon range query algorithm comprises:
calculating the minimum outsourcing rectangle of the target polygonal area;
screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the plurality of data blocks, and adding a candidate result set;
And determining the data blocks of which the candidate concentrated track points are positioned in the target polygon area and the track time is positioned in the target time period as target data blocks.
The flow statistics module is used for counting the target airspace flow based on the space-time polygonal range query algorithm, and is specifically used for dividing a target airspace sector into a plurality of regular cylinders, filtering out track points positioned in each cylinder based on the space-time polygonal range query algorithm by using the upper limit and the lower limit of the height of each cylinder as constraint conditions to be added into a counting queue, and carrying out data deduplication on the track points in the counting queue to obtain the target airspace flow.
In one embodiment, the flow statistics module is specifically configured to define a track id attribute and a column Vid to which the track id attribute belongs for track points in the count queue, when each column executes a space-time polygon range query algorithm, if the track points are in the column, mark the track id attribute Vid as the current column Vid to form a compound key < Trajid, vid >, and perform data deduplication on the track points of the count queue by using the compound key recorded in each row.
The capture module is used for calculating k track points adjacent to a target query point based on a KNN query algorithm so as to capture space-time track data correlation, and is specifically used for searching data blocks which are intersected with the target query point in the plurality of data blocks and adding the data blocks to a first priority queue, calculating the distance dist p between each data block in the first priority queue and the target query point, calculating the k shortest distance dist k between the track point of each data block in the first priority queue and the target query point, determining the data block corresponding to the track point meeting dist p＜distk as a candidate data block, adding the track point which is positioned in a target time period and has the distance dist (i, q) smaller than dist k in the candidate data block to a second priority queue, generating a test range which takes the target query point as the center and has the distance with the k neighbor track point as the radius, and determining the k track points adjacent to the target query point in the second priority queue based on the test result of the test range on the track point.
In one embodiment, the capturing module is specifically configured to determine whether the test range intersects with other data blocks, if not, determine k track points in the test range as k track points close to a target query point, if so, calculate a distance dist between a track point in the data block intersected with the test range and the target query point, and replace and add a track point whose dist is smaller than dist k in the second priority queue to the second priority queue.
In one embodiment, the query module is specifically configured to store an abscissa of each track point of the target polygon area in the array X [ ], store an ordinate in the array Y [ ], and obtain a maximum value X max and a minimum value X min of the array X [ ], and a maximum value Y max and a minimum value Y min of the array Y [ ], determine whether the track point is in a minimum bounding rectangle (X min,ymin)-(xmax,ymax) of the target polygon area, if not, determine that the track point does not belong to the target polygon area, if so, extract a ray from the track point, intersect the target polygon area, and determine whether the track point belongs to the target polygon area based on the intersecting point.
In one embodiment, the building block is specifically configured to define a spatio-temporal trajectory dataset p= { p 1,p2,..,pn }, where each trajectory point p 1、p2、…、pn is expressed as (lng, lat, t), lng represents longitude, lat represents latitude, t represents time attribute, abstract the longitude lng and latitude lat of each trajectory point to coordinates < x, y > of a point on a two-dimensional plane, and define two points on the two-dimensional planeThe Euclidean distance of (2)
Fig. 7 shows a hardware block diagram of a computing device 30 for spatiotemporal trajectory data management analysis of flight data according to an embodiment of the present description. As shown in fig. 7, computing device 30 may include at least one processor 301, memory 302 (e.g., non-volatile memory), memory 303, and communication interface 304, and at least one processor 301, memory 302, memory 303, and communication interface 304 are connected together via bus 305. The at least one processor 301 executes at least one computer readable instruction stored or encoded in memory 302.
It should be appreciated that the computer-executable instructions stored in memory 302, when executed, cause at least one processor 301 to perform the various operations and functions described above in connection with fig. 1-5 in various embodiments of the present specification.
In embodiments of the present description, computing device 30 may include, but is not limited to, a personal computer, a server computer, a workstation, a desktop computer, a laptop computer, a notebook computer, a mobile computing device, a smart phone, a tablet computer, a cellular phone, a Personal Digital Assistant (PDA), a handset, a messaging device, a wearable computing device, a consumer electronic device, and the like.
According to one embodiment, a program product, such as a machine-readable medium, is provided. The machine-readable medium may have instructions (i.e., elements described above implemented in software) that, when executed by a machine, cause the machine to perform the various operations and functions described above in connection with fig. 1-5 in various embodiments of the specification. In particular, a system or apparatus provided with a readable storage medium having stored thereon software program code implementing the functions of any of the above embodiments may be provided, and a computer or processor of the system or apparatus may be caused to read out and execute instructions stored in the readable storage medium.
In this case, the program code itself read from the readable medium may implement the functions of any of the above embodiments, and thus the machine-readable code and the readable storage medium storing the machine-readable code form part of the present specification.
Examples of readable storage media include floppy disks, hard disks, magneto-optical disks, optical disks (e.g., CD-ROMs, CD-R, CD-RWs, DVD-ROMs, DVD-RAMs, DVD-RWs), magnetic tapes, nonvolatile memory cards, and ROMs. Alternatively, the program code may be downloaded from a server computer or cloud by a communications network.
It will be appreciated by those skilled in the art that various changes and modifications can be made to the embodiments disclosed above without departing from the spirit of the invention. Accordingly, the scope of protection of this specification should be limited by the attached claims.
It should be noted that not all the steps and units in the above flowcharts and the system configuration diagrams are necessary, and some steps or units may be omitted according to actual needs. The order of execution of the steps is not fixed and may be determined as desired. The apparatus structures described in the above embodiments may be physical structures or logical structures, that is, some units may be implemented by the same physical client, or some units may be implemented by multiple physical clients, or may be implemented jointly by some components in multiple independent devices.
In the above embodiments, the hardware units or modules may be implemented mechanically or electrically. For example, a hardware unit, module or processor may include permanently dedicated circuitry or logic (e.g., a dedicated processor, FPGA or ASIC) to perform the corresponding operations. The hardware unit or processor may also include programmable logic or circuitry (e.g., a general purpose processor or other programmable processor) that may be temporarily configured by software to perform the corresponding operations. The particular implementation (mechanical, or dedicated permanent, or temporarily set) may be determined based on cost and time considerations.
The detailed description set forth above in connection with the appended drawings describes exemplary embodiments, but does not represent all embodiments that may be implemented or fall within the scope of the claims. The term "exemplary" used throughout this specification means "serving as an example, instance, or illustration," and does not mean "preferred" or "advantageous over other embodiments. The detailed description includes specific details for the purpose of providing an understanding of the described technology. However, the techniques may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the concepts of the described embodiments.
The previous description of the disclosure is provided to enable any person skilled in the art to make or use the disclosure. Various modifications to the disclosure will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other variations without departing from the scope of the disclosure. Thus, the disclosure is not limited to the examples and designs described herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.
Claims (9)
1. A space-time trajectory data management analysis method facing to flight data is characterized by comprising the following steps:
Acquiring spatio-temporal trajectory data and establishing a spatial index comprising a plurality of data blocks, and
Querying a target data block of which all track points belong to a target polygonal area in a target time period by utilizing a space-time polygonal range query algorithm;
wherein the space-time polygon range query algorithm comprises:
calculating the minimum outsourcing rectangle of the target polygonal area;
screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the plurality of data blocks, and adding a candidate result set;
Determining a data block of which the track point is positioned in the target polygon area and the track time is positioned in a target time period as a target data block;
The method further comprises the step of calculating k track points adjacent to the target query point based on the KNN query algorithm so as to capture the space-time track data correlation, and specifically comprises the following steps:
Searching data blocks intersecting with the target query point in the plurality of data blocks, and adding the data blocks to a first priority queue;
Calculating the distance dist p between each data block in the first priority queue and the target query point, wherein p represents each data block in the first priority queue;
calculating the kth shortest distance dist k between the track point of each data block in the first priority queue and the target query point, wherein k represents the kth track point;
determining a data block corresponding to the track point meeting dist p＜distk as a candidate data block;
The track time in the candidate data block is positioned in the target time period and is distant from the target query point Trace points less than dist k are added to the second priority queue,Representing the distance from the track point i to the query point q, wherein q represents the target query point;
Generating a test range which takes a target query point as a center and takes the distance between the target query point and a kth neighbor track point as a radius;
and determining k track points adjacent to the target query point based on the test result of the test range on the track points in the second priority queue.
2. The method for managing and analyzing space-time trajectory data for flight data according to claim 1, further comprising the step of counting a target airspace flow based on the space-time polygon range query algorithm, and specifically comprising the steps of:
dividing a target airspace sector into a plurality of regular cylinders;
Filtering out track points positioned in each column based on the space-time polygon range query algorithm and by using the upper limit and the lower limit of the height of each column as constraint conditions so as to be added into a counting queue;
and carrying out data deduplication on the track points in the counting queue to obtain the target airspace flow.
3. The space-time trajectory data management analysis method for flight data according to claim 2, wherein the performing data deduplication on the trajectory points in the count queue to obtain a target airspace flow specifically comprises:
defining a track id attribute for track points in the counting queue, wherein the column V id,Vid to which the track id attribute belongs represents the unique id of the column;
When each column executes a space-time polygon range query algorithm, if the track point is in the column, marking the V id of the track id attribute as the V id of the current column so as to form a compound key;
And carrying out data deduplication on the track points of the counting queue by utilizing the compound keys recorded in each row.
4. The method for space-time trajectory data management analysis for flight data according to claim 1, wherein determining k trajectory points adjacent to the target query point based on the test result of the test range on the trajectory points in the second priority queue specifically comprises:
Judging whether the test range intersects with other data blocks or not, if not,
K track points in the test range are determined to be k track points close to the target query point, and if yes,
Calculating the distance dist between the track point in the data block intersected with the test range and the target query point, and adding the track point replacement with dist smaller than dist k in the second priority queue into the second priority queue.
5. The method for space-time trajectory data management analysis for flight data according to any one of claims 1 to 4, wherein the query for the target data blocks in which all the trajectory points in the plurality of data blocks belong to the target polygon area in the target time period by using a space-time polygon range query algorithm specifically comprises:
storing the abscissa of each track point of the target polygon area in an array X, and storing the ordinate in an array Y, and obtaining the maximum value of the array X And minimum valueMaximum value of array YAnd minimum value;
Judging whether the track point is in the minimum outsourcing rectangle of the target polygon areaIf the number of the groups is not equal to the number of the groups,
The trace point is determined not to belong to the target polygon area and if so,
The ray is led out from the track point to intersect with the target polygon area, and whether the track point belongs to the target polygon area is determined based on the intersecting point number.
6. The method for managing and analyzing spatio-temporal trajectory data for flight data according to any one of claims 1 to 4, characterized in that it comprises obtaining spatio-temporal trajectory data and creating a spatial index comprising a plurality of data blocks, comprising in particular:
Defining a spatiotemporal trajectory dataset Wherein each locus point p 1、p2、…、pn is represented as,Represents a longitude of the person in question,The latitude is indicated as such,Representing a time attribute;
Longitude of each track point And dimension(s)Abstracted as coordinates of points on a two-dimensional planeAnd defines two points on a two-dimensional planeThe Euclidean distance of (2)。
7. A space-time trajectory data management analysis device for flight data, comprising:
an index establishing module for acquiring the space-time track data and establishing a spatial index comprising a plurality of data blocks, and
The query module is used for querying a target data block of which all track points belong to a target polygonal area in a target time period by utilizing a space-time polygonal range query algorithm;
wherein the space-time polygon range query algorithm comprises:
calculating the minimum outsourcing rectangle of the target polygonal area;
screening data blocks which are intersected with the minimum outsourcing rectangle and the target polygon area in the plurality of data blocks, and adding a candidate result set;
Determining a data block of which the track point is positioned in the target polygon area and the track time is positioned in a target time period as a target data block;
The acquisition module is used for calculating k track points adjacent to the target query point based on a KNN query algorithm so as to acquire space-time track data correlation, and is particularly used for searching data blocks which are intersected with the target query point in the plurality of data blocks and adding the data blocks to a first priority queue, calculating the distance dist p between each data block in the first priority queue and the target query point, p represents each data block in the first priority queue, calculating the kth shortest distance dist k between the track point of each data block in the first priority queue and the target query point, k represents the kth track point, determining the data block corresponding to the track point meeting dist p＜distk as a candidate data block, and determining the track time in the candidate data block to be within a target time period and the distance between each data block and the target query point Trace points less than dist k are added to the second priority queue,The method comprises the steps of representing the distance between a track point i and a query point q, wherein q represents a target query point, generating a test range which takes the target query point as a center and takes the distance between the track point i and a kth neighbor track point as a radius, and determining k track points adjacent to the target query point based on the test result of the test range on the track points in the second priority queue.
8. A computing device, comprising:
At least one processor, and
A memory storing instructions that, when executed by the at least one processor, cause the at least one processor to perform the method of any of claims 1 to 6.
9. A machine-readable storage medium storing executable instructions that, when executed, cause the machine to perform the method of any one of claims 1 to 6.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110965172.2A CN113656670B (en) | 2021-08-23 | 2021-08-23 | Flight data-oriented spatiotemporal trajectory data management and analysis method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110965172.2A CN113656670B (en) | 2021-08-23 | 2021-08-23 | Flight data-oriented spatiotemporal trajectory data management and analysis method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113656670A CN113656670A (en) | 2021-11-16 |
| CN113656670B true CN113656670B (en) | 2024-12-06 |
Family
ID=78491919
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110965172.2A Active CN113656670B (en) | 2021-08-23 | 2021-08-23 | Flight data-oriented spatiotemporal trajectory data management and analysis method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113656670B (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114117260B (en) * | 2021-12-02 | 2022-09-23 | 中国人民解放军国防科技大学 | Spatiotemporal trajectory indexing and query processing method, device, equipment and medium |
| CN114610774B (en) * | 2022-02-10 | 2023-01-20 | 天津中远海运散运数字科技有限公司 | Method, device, electronic equipment and medium for analyzing ship passing through selected area |
| CN117648338B (en) * | 2024-01-29 | 2024-06-07 | 卡奥斯化智物联科技(青岛)有限公司 | Method, device, equipment and medium for optimizing space-time data range index filtration |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107423368A (en) * | 2017-06-29 | 2017-12-01 | 中国测绘科学研究院 | A kind of space-time data indexing means in non-relational database |
| CN112465199A (en) * | 2020-11-18 | 2021-03-09 | 南京航空航天大学 | Airspace situation evaluation system |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TWI581207B (en) * | 2016-04-28 | 2017-05-01 | 國立清華大學 | Computing method for ridesharing path, computing apparatus and recording medium using the same |
-
2021
- 2021-08-23 CN CN202110965172.2A patent/CN113656670B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107423368A (en) * | 2017-06-29 | 2017-12-01 | 中国测绘科学研究院 | A kind of space-time data indexing means in non-relational database |
| CN112465199A (en) * | 2020-11-18 | 2021-03-09 | 南京航空航天大学 | Airspace situation evaluation system |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113656670A (en) | 2021-11-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113656670B (en) | Flight data-oriented spatiotemporal trajectory data management and analysis method and device | |
| US10353742B2 (en) | Tracking large numbers of moving objects in an event processing system | |
| US10789231B2 (en) | Spatial indexing for distributed storage using local indexes | |
| CN107391554B (en) | Efficient Distributed Locality-Sensitive Hashing Method | |
| Yiu et al. | Clustering objects on a spatial network | |
| JP6032467B2 (en) | Spatio-temporal data management system, spatio-temporal data management method, and program thereof | |
| US9223801B2 (en) | Information management method and information management apparatus | |
| CN106649656A (en) | Spatial-temporal trajectory big data storage method for database | |
| Zhang et al. | Dart: A geographic information system on hadoop | |
| Gao et al. | An efficient and distributed framework for real-time trajectory stream clustering | |
| CN118964686A (en) | Vector retrieval method, device, equipment and storage medium | |
| Azri et al. | Review of spatial indexing techniques for large urban data management | |
| CN113312346B (en) | Index construction method, trajectory query method, device, equipment and readable medium | |
| US20130073550A1 (en) | Information management method and information management apparatus | |
| Cho et al. | A GPS trajectory map-matching mechanism with DTG big data on the HBase system | |
| US9436715B2 (en) | Data management apparatus and data management method | |
| CN119293276A (en) | Distributed tile slicing and object-based storage method of remote sensing images and its application | |
| Wu et al. | NEIST: A neural-enhanced index for spatio-temporal queries | |
| Dong et al. | GAT: A unified GPU-accelerated framework for processing batch trajectory queries | |
| Li et al. | gsstSIM: A high‐performance and synchronized similarity analysis method of spatiotemporal trajectory based on grid model representation | |
| CN118277494A (en) | Space and high-dimensional approximate nearest neighbor hybrid query method and system for electronic map | |
| Zhang et al. | U2sod-db: a database system to manage large-scale ubiquitous urban sensing origin-destination data | |
| Wang et al. | Grid‐Based Whole Trajectory Clustering in Road Networks Environment | |
| Aref et al. | ILX: intelligent" location+ x" data systems (vision paper) | |
| Wang et al. | Efficient spatial big data storage and query in HBase |
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 |