Compressing location data of moving objects

• US 20040158398A1
• Filed: 12/05/2003
• Published: 08/12/2004
• Est. Priority Date: 12/06/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Ying, Yu, Xiu Lan, Rao, Fang Yan
• Granted Patent: US 6,983,205 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Provides methods, apparatus and systems for compressing a large number of continuous location data of moving objects. A large number of continuous location data of moving objects sent from a mobile unit or a locating device are received, these location data are compressed and inserted the compressed location data into a database, so as to solve the problem that the database can not work under a high insertion frequency, and reduce the storage space of continuous locations while maintaining certain location query precision. An example apparatus for compressing the location data of moving objects, comprises: input interface for receiving current location data of a object moving continuously; data compressing means for compressing the location data received via said input interface; and output interface for outputting compressed location data of the moving object.

Claims

1. A method for compressing large number of location data of moving objects during a continuous time, comprising the steps of:

a) receiving current location data of a moving object;

b) determining whether the object was in motion of translation previously;

c) if determined in step b) the object was in translational motion, determining whether the object continues to move translationally after taking account of the current location, if yes, not updating the location data;

d) if determined in step c) the translational motion is no longer observed after taking account of the current location, updating the location data and returning to step a); and

e) if determined in step b) the object was not in translational motion, determining whether the object is moving randomly nearby, if yes, not updating the location data, otherwise updating the location data, setting the object in motion of translation and returning to step a).

2. The method according to claim 1, wherein the step of updating the location data includes selecting a location queue with variable length, storing the compressed location data of the moving object into the variable location queue, then from said location queue, inserting the location data of the moving object at different time into a database at an acceptable data insertion rate of the database.

3. The method according to claim 2, wherein the topology and physical structure and location data of roads are stored in advance, and the corrected location data of the moving object is obtained by a spatial index before step b).

4. The method according to claim 3, wherein step c) further comprises the sub-steps of:

c1) using several previous locations of the object to perform linear prediction to the current location of the object;

c2) computing a prediction error between the predicted current location and the received current location; and

c3) if the prediction error is within the range of a linear prediction threshold, confirming that the moving object continues to move translationally.

5. The method according to claim 4, wherein said linear prediction is a first order polynomial linear prediction of double points or a first order polynomial linear prediction of multiple points.

6. The method according to claim 2, wherein in the case of without stored topology and physical structure and location data of roads in advance, the step c) further comprises the sub-steps of:

c11) obtaining the time-location linear equation through fitting of the current location and previous locations where the object was in translational motion;

c12) substituting the current time point value and the previous time point values when translational motion was satisfied into the time-location linear fitting equation and estimating a fitting error at each time point; and

c13) if the fitting errors at all the time points are within the range of linear prediction threshold, confirming that the moving object continues to move translationally and setting the fitting location of the object at each time point as the corrected location.

7. The method according to claim 5, wherein the step d) further comprises the sub-steps of:

d1) if determined in step c) the translational motion is no longer observed after taking account of the current location, determining whether the object is moving randomly nearby, if yes, updating the location data and setting the object to be in a state of moving randomly nearby;

d2) if determined in step d1) the object is not in the state of moving randomly nearby, determining whether the prediction error or fitting error is larger than a specific error threshold of the object set according to a location query precision, if the prediction error or fitting error is larger than the specific error threshold of the object set according to location query precision, determining whether the last recorded location data on the database and the last corrected location data are identical, if yes, recording the current location data, otherwise recording the last corrected location data and the current location data;

d3) if the prediction error or fitting error is not larger than the specific error threshold of the object set according to the location query precision, determining whether the number of the points satisfying the linear prediction are larger than a threshold, if no, recording the current location data, and if yes, recording the last corrected location data and the current location data; and

d4) only retaining the current location data in a temporary storage space for locations satisfying the linear prediction.

8. The method according to claim 1, wherein step e) further comprises the sub-steps of:

e1) determining whether the last recorded location data is equal to the last corrected location data, if no, setting a translational motion flag and recording the current location data;

e2) if determined in step e1) the last recorded location data is equal to the last corrected location data, determining whether the location prediction error is larger than the specific threshold set according to the location query precision, if no, only recording the current location data;

e3) if determined in step e2) the location prediction error is larger than the specific threshold set according to the location query precision, determining whether the number of points satisfying moving randomly nearby threshold are larger than a threshold, if yes, recording the last corrected location data and the current location data, otherwise only recording the current location data; and

e4) resetting the number of points satisfying moving randomly nearby threshold to zero, clearing up the data of the previous location, and retaining the last corrected location data and the current location data in the temporary storage space for the locations satisfying linear prediction according to the translational motion flag.

9. The method according to claim 1, wherein said location queue resides in memories or exists in form of one or more files.

10. The method according of claim 1, wherein an initialization step is performed before the step a):

receiving and recording the first several location data of the moving object, and determining whether the object is in motion of translation or a state of moving randomly nearby according to the received first several location data.

18. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing compression of a large number of location data of moving objects during a continuous time, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

19. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compressing large number of location data of moving objects during a continuous time, said method steps comprising the steps of claim 1.

11. An apparatus for compressing location data of moving objects, comprising:

input interface for receiving current location data of a object moving continuously;

data compression means for compressing the location data received via said input interface; and

output interface for outputting compressed location data of the moving object,

wherein said data compressing means comprises;

linear model processing unit for determining, when the moving object was in motion of translation previously, whether the moving object continues to move translationally after taking account of the current location, if yes, not updating the location data, and if no, updating the location data; and

simple threshold model processing unit for determining, when the moving object is not moving translationally, whether the object is moving randomly nearby, if yes, not updating the location data, otherwise updating the location data.

12. The apparatus according to claim 11, further comprises storage means for storing the topology and physical structure, location data and the temporary results necessary for data compression.

13. The apparatus according to claim 12, wherein said linear model processing unit comprises:

linear prediction means for predicting the current location of the object with several previous locations of the object;

prediction error computing means for computing a prediction error between the predicted location and the current location; and

determination means for confirming the moving object continues to move translationally if the prediction error is within the range of linear prediction threshold.

14. The apparatus according to claim 13, wherein said linear prediction is a first order polynomial linear prediction of double points or a first order polynomial linear prediction of multiple points.

15. The apparatus according to claim 11, wherein said linear model processing unit comprises:

fitting means for performing the regression between time and locations including the current location and the previous locations satisfying translational motion to obtain a fitting time-location linear equation;

fitting error estimation means for substituting the current time value and the previous time values in which translational motion was satisfied into the fitting time-location linear equation and estimating a fitting error at each time point; and

determining means for confirming that the moving object continues to move translationally if the fitting errors at all the time points are within the range of linear prediction threshold.

16. The apparatus according to claims 11, wherein said output interface comprising a variable-length location queue which saves the compressed location data of the moving object to be inserted into a database and inserts the compressed location data of the moving object at different time into the database at an acceptable data inserting rate of the database.

17. The apparatus according to claim 11, wherein said location queue resides in memories or exists in form of one or more files.

20. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing compression of location data of moving objects, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 11.