On-line data reduction and the quality of history in moving objects databases

ABSTRACT

In this work we investigate the quality bounds for the data stored in Moving Objects Databases (MOD) in the settings in which mobile units can perform an on-board data reduction in real time. It has been demonstrated that line simplification techniques, when properly applied to the large volumes of data pertaining to the past trajectories of the moving objects. result in substantial storage savings while guaranteeing deterministic error bounds to the queries posed to the MOD. On the other hand. it has also been demonstrated that if moving objects establish an agreement with the MOD regarding the (im)precision tolerance significant savings can be achieved in transmission when updating the location-in-time information. In this paper we take a first step towards analyzing the quality of the history in making in MOD by correlating the (impact of the) agreement between the server and the moving objects for on-line updates in real time with the error bounds of the data that becomes a representation of the past trajectories as time evolves.

REFERENCES

• 1: Charu C. Aggarwal , Dakshi Agrawal, On nearest neighbor indexing of nonlinear trajectories, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.252-259, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773178]
• 2: Helmut Alt , Christian Knauer , Carola Wenk, Comparison of Distance Measures for Planar Curves, Algorithmica, v.38 n.1, p.45-58, October 2003 [doi>10.1007/s00453-003-1042-5]
• 3: G. Barequet. D. Z. Chen. O. Deascu. M. T. Goodrich. and J. Snoeyink. Efficiently approximating polygonal path in three and higher dimensions. Algorithmica. 33(2). 2002.
• 4: M. Breunig. C. Türker. M. Böhlen. S. Dieker. R.H. Güting. C. Jensen. L. Relly. P. Rigaux. H.-J. Schek. and M. Scholl. Architectures and implementations of spatio-temporal database management systems. In Spatio.Temporal Databases - the Chorochronos Approach. 2003.
• 5: Hu Cao , Ouri Wolfson , Goce Trajcevski, Spatio-temporal data reduction with deterministic error bounds, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.211-228, September 2006 [doi>10.1007/s00778-005-0163-7]
• 6: W. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimal error. International Journal of Computational Geometry Applicaitons. 6. 1996.
• 7: Reynold Cheng , Sunil Prabhakar, Managing uncertainty in sensor database, ACM SIGMOD Record, v.32 n.4, December 2003 [doi>10.1145/959060.959068]
• 8: Hui Ding , Goce Trajcevski , Peter Scheuermann, OMCAT: optimal maintenance of continuous queries' answers for trajectories, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142575]
• 9: Managing Moving Objects on Dynamic Transportation Networks, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.287, June 21-23, 2004 [doi>10.1109/SSDBM.2004.48]
• 10: D. Douglas and T. Peuker. Algorithms for the reduction of the number of points required to represent a digitised line or its caricature. The Canadian Cartographer. 10(2):112-122. 1973.
• 11: S. E. Dreyfus. An appraisal of some shortest - path algorithms. Operations Research. 17(3). 1969.
• 12: Minos Garofalakis , Phillip B. Gibbons, Wavelet synopses with error guarantees, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564746]
• 13: B. Gedik and L. Liu. Mobieyes: Distributed processing of continuous queries on moving objects in a mobile system. In International Conference on Extending the Database Technology (EDBT). 2004.
• 14: B. Gedik and L. Liu. Mobieyes: A distributed location monitoring service using moving location queries. IEEE Transactions on Mobile Computing. 2006. (accepted. to appear).
• 15: R.H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann. 20045.
• 16: J. Hershberger and J. Snoeyink. Speeding up the douglas-peuker line-simplification algorithm. In International Symposium on Spatial Data Handling. 1992.
• 17: G.S. Iwerks. H. Samet. and K. Smith. Continuous k-nearest neighbor queries for continuously moving points with updates. In International Conference on Very Large Databases (VLDB). 2003.
• 18: G.S. Iwerks. H. Samet. and K. Smith. Maintenance of spatial semijoin queries on moving points. In International Conference on Very Large Databases (VLDB). 2004.
• 19: J.A.C. Lema. L. Forlizzi. R.H. Güting. E. Nardeli. and M. Schneider. Algorithms for moving objects databases. Computing Journal. 46(6). 2003.
• 20: Mohamed F. Mokbel , Xiaopeng Xiong , Moustafa A. Hammad , Walid G. Aref, Continuous Query Processing of Spatio-Temporal Data Streams in PLACE, Geoinformatica, v.9 n.4, p.343-365, December 2005 [doi>10.1007/s10707-005-4576-7]
• 21: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 22: Dieter Pfoser , Nectaria Tryfona , Christian S. Jensen, Indeterminacy and Spatiotemporal Data: Basic Definitions and Case Study, Geoinformatica, v.9 n.3, p.211-236, September 2005 [doi>10.1007/s10707-005-1282-4]
• 23: Sunil Prabhakar , Yuni Xia , Dmitri V. Kalashnikov , Walid G. Aref , Susanne E. Hambrusch, Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects, IEEE Transactions on Computers, v.51 n.10, p.1124-1140, October 2002 [doi>10.1109/TC.2002.1039840]
• 24: S. Saltenis and C. Jensen. Indexing of moving objects for location-based services. In International Conference on Data Engineering (ICDE). 2004.
• 25: Jochen Schiller , Agnès Voisard, Location Based Services, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 26: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 27: Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003 [doi>10.1145/777943.777944]
• 28: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 29: Goce Trajcevski , Peter Scheuermann, Reactive maintenance of continuous queries, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.3, July 2004 [doi>10.1145/1031483.1031488]
• 30: Goce Trajcevski , Ouri Wolfson , Klaus Hinrichs , Sam Chamberlain, Managing uncertainty in moving objects databases, ACM Transactions on Database Systems (TODS), v.29 n.3, p.463-507, September 2004 [doi>10.1145/1016028.1016030]
• 31: Robert Weibel, Generalization of Spatial Data: Principles and Selected Algorithms, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.99-152, September 16-20, 1996
• 32: Ouri Wolfson , Hu Cao , Hai Lin , Goce Trajcevski , Fengli Zhang , Naphtali Rishe, Management of Dynamic Location Information in DOMINO, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.769-771, March 25-27, 2002
• 33: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]
• 34: Xiaopeng Xiong , Walid G. Aref, R-trees with Update Memos, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.22, April 03-07, 2006 [doi>10.1109/ICDE.2006.125]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Keywords:
data reduction algorithms, dead-reckoning, moving objects databases, spatio-temporal data reduction, trajectories