Contact Information:
Vassilis J. Tsotras
Dimitrios Gunopulos
Department of Computer
Science and Engineering
University of California,
Riverside, CA 92521
Phone: (909) 787-2888,
Fax : (909) 787-4643
Email: tsotras@cs.ucr.edu,
http://www.cs.ucr.edu/~tsotras
dg@cs.ucr.edu, http://www.cs.ucr.edu/~dg
WWW Page: http://www.cs.ucr.edu/~tsotras/spatiotemporal.html
List of Supported
Students:
Donghui Zhang, Marios
Hadjieleftheriou, Dimitris Papadopoulos.
Project Award Information:
Award Number: IIS-9907477.
Duration: Oct. 1, 1999-Sept.30, 2003
Title: Efficient Indexing
for Spatiotemporal Applications
Keywords: spatiotemporal databases, access methods, moving points, neighbor queries.
Project Summary:
Indexing spatiotemporal
data is an important problem for many applications (global change, transportation,
social and multimedia applications). The goal of this project is to provide
efficient access methods for data whose geometry changes over time. Two
time-varying spatial attributes are considered, the object position and
extent. Based on the rate by which these spatial attributes change, the
discrete and continuous spatiotemporal environments are identified. In
the discrete environment, spatiotemporal data changes in discrete steps.
Efficient ways to answer historical queries on any past state of such spatiotemporal
data are examined. In particular, selection, neighbor, aggregate, join
and similarity queries are addressed using a "partial persistence" methodology.
In the continuous spatiotemporal environment, data changes continuously.
Instead of keeping the data position/extent at discrete times (which would
result in enormous update/storage requirements) the functions by which
this data changes are stored. This introduces the novel problem of indexing
functions. Using this approach, selection, neighbor and aggregation queries
about future locations of moving objects in one and two dimensions are
addressed. The methods used in this project are expected to achieve at
least 30% improvement over traditional access methods. The applicability
of the completed work reaches multiple settings, including Geographic Information
Systems, multimedia databases and transportation systems.
Publications and
Products:
Journal/Conference
publications:
[1] D. Zhang, V.J.
Tsotras and D. Gunopulos, "Efficient Aggregation over Objects with Extent",
in PODS'02 (to appear), Madison, WI, June 2002.
[2] G. Kollios, V.J.
Tsotras, "Hashing Methods for Temporal Data", IEEE Trans. of Knowledge
and Data Engineering (to appear, July/Aug 2002).
[3] D. Zhang, D. Gunopulos,
V.J. Tsotras and B. Seeger, "Temporal Aggregation over Data Streams using
Multiple Granularities", in EDBT'02, Prague, Czech Republic, March 2002.
[4] G. Kollios, V.J.
Tsotras, D. Gunopulos, M. Hadjieleftheriou, "Efficient Indexing of
Spatiotemporal Objects", in EDBT'02, Prague, Czech Republic, March
2002.
[5] D. Zhang, V.J.
Tsotras, B. Seeger, "Efficient Temporal Join Processing using Indices",
in ICDE'02, San Jose, CA, Feb.-March 2002.
[6] D. Zhang, V.J.
Tsotras, "Index Based Processing of Semi-Restrictive Temporal Joins", in
TIME'02 (to appear), Manchester, UK, July 2002.
[7] D. Zhang, V.J.
Tsotras, "Improving Min/Max Aggregation over Spatial Objects", in GIS'01,
Atlanta, GA, Nov. 9-10, 2001.
[8]D. Zhang, A. Markowetz,
V. Tsotras, D. Gunopulos, B. Seeger: "Efficient Computation of Temporal
Aggregates with Range Predicates," in PODS'01, Santa Barbara, CA,
2001.
[9] G. Kollios, D.
Gunopulos, V.J.Tsotras, A. Delis, M. Hadjieleftheriou: "Indexing Animated
Objects Using Spatiotemporal Access Methods", IEEE Transactions of
Knowledge and Data Engineering,Sept/Oct 2001, Vol.13, No.5, pp 758-777.
[10] D. Gunopulos,
G. Kollios, V.J. Tsotras, C. Domeniconi: "Approximating Multi-Dimensional
Aggregate Range Queries over real Attributes", in SIGMOD'00, Dallas,
TX, May 2000.
[11] L. Tan, V.J.
Tsotras, G. Kollios, D. Gunopulos: "Multidimensional Membership Queries
for Temporal Databases", 12th Intl. Conference on Software and Knowledge
Engineering (SEKE'00), Chicago, IL, July 2000.
[12] D. Gunopulos,
G. Kollios, V. Tsotras, C. Domeniconi: "Using kernels to approximate
multi-dimensional aggregate range queries over real attributes.",
Workshop on New Perspectives in Kernel-Based Learning Methods, NIPS 2000.
[13] G. Kollios, D.
Gunopulos, V.J. Tsotras: "Nearest Neighbor Queries in a Mobile Environment",
in STDBM'99, Edinburgh, Scotland, September 10-11, 1999, LNCS 1678, pp:
119-134.
[14] D. Gunopulos,
G. Kollios, V.J. Tsotras: "All-Pairs Nearest Neighbors in a Mobile Environment",
7th Hellenic Conference on Informatics, Ioannina, Greece, August 26-29,
1999.
[15] G.Kollios, D.
Gunopulos, V.J. Tsotras: "Indexing Animated Objects", in Proceedings of
5th International Workshop on Multimedia Information Systems, MIS '99,
Indian Wells, CA, October 21-23, 1999.
[16] S-Y. Chien,
V.J. Tsotras, C. Zaniolo: "Multiversion Documents by Object Referencing.",
in VLDB 2001, Roma, Italy.
[17] S.-Y. Chien,
V.J. Tsotras, C. Zaniolo and D. Zhang, "Efficient Complex Query Support
for Multiversion XML Documents", in EDBT'02, Prague, Czech Republic, March
2002.
[18] S-Y. Chien, V.J.
Tsotras, C. Zaniolo: "Version Management of XML Documents: Copy-Based
versus Edit-Based Schemes." RIDE-DM 2001.
[19] S-Y. Chien, V.J.
Tsotras, C. Zaniolo: "Version Management of XML Documents". In WebDB
(Informal Proceedings) 2000: 75-80; an extended version appears in LNCS,
vol.1997, Springer, 2001.
Book:
[20] Y. Manolopoulos,
Y. Theodoridis, V.J. Tsotras,
Advanced Database Indexing, Kluwer
Academic Publishers, Boston, November 1999, 312 pages, ISBN 0-7923-7716-8.
Project Impact:
Dr. Kollios graduated
with a Ph.D. degree in Summer 2000, and is currently an Assistant
Professor in the Dept. of Computer Science, Boston University (advisor:
V.J. Tsotras). Donghui Zhang is graduating with a Ph.D. degree in June
2002. There are currently two Research Assistants working on this project,
Mr Hadjeleftheriou (advisor: V.J. Tsotras) and Mr. Papadopoulos (advisor:
D. Gunopulos). Parts of this research are used in a Database Graduate Seminar
course (CS267) taught at the University of California, Riverside (Winter
2000). For this project we have established a cooperation with ESRI (Environmental
Systems Research Institute). Our contact at ESRI is Dr. Erik Hoel. Through
this cooperation we expect to have access to real spatiotemporal datasets/applications.
We also cooperate with the Department of Defense.
Goals, Objectives,
and Targeted Activities:
The objective of this
proposal is to design efficient access methods for addressing spatiotemporal
queries. A spatiotemporal query specifies spatial/temporal predicates and
retrieves all objects that satisfy them. A spatial predicate is defined
in terms of a point or an extent while a temporal predicate can involve
a time instant or a time interval. In particular we are interested in:
(a) selection queries:
"find all objects contained in a given area S at a given time t,"
(b) neighbor queries:
"find which object became the closest to a given point s during
time interval T," or, "find the 5 closest ambulances to an accident
position in the next 10 minutes,"
(c) aggregate queries:
"find how many objects passed through area S during time interval
T,"
or, "find the fastest object that will pass through area S in the
next 5 minutes from now,"
(d) join queries:
"given two spatiotemporal relations R1 and R2, find pairs
of objects whose extents intersected during the time interval T,"
or "find pairs of planes that will come closer than 1 mile in the next
5 minutes,"
(e) similarity queries:
"given an area S find the time instants when there were more than
10 objects in S", or, "find objects that moved similarly to the
movement of a given object x over an interval T."
Project References:
Data and publications
are posted as they become available through the project's web page.
Area Background:
A spatiotemporal database
system manages data whose geometry changes over time. Spatiotemporal data
appear in global change (as in climate or land cover changes), transportation
(traffic surveillance data, intelligent transportation systems), social
(demographic, health, etc.), and multimedia (animated movies) applications.
We distinguish between discrete and
continuous updates. Traditional
databases assume that data stored in the database remains constant until
explicitly modified through an update. For example, if a price field is
$5, it remains $5 until explicitly updated. While this model serves well
many applications where data changes in discrete steps, it is not appropriate
for applications with continuously changing data (the dynamic attributes
of [SWCD97, WXCJ98]). Consider a database keeping the position of moving
objects (like automobiles). The primary goal of this database is to correctly
represent the real world while objects move. Continuous updating about
each object's position leads to serious performance overhead. Updating
the database only at given time instants limits query accuracy. A better
approach would be to represent the position of each moving object as a
function of time; then object positions change as time proceeds without
the need of explicit updates [SWCD97]. While spatiotemporal applications
and data abound the field has only recently attracted the efforts of database
researchers. While many temporal [ST99] and spatial indexes exist, very
few works have addressed the combination [SY91, TOW98, VTS98, KGT99]. Most
of research has concentrated to spatiotemporal database models and query
languages [EGSV98, CR99, W94, E93, SWCD97, WXCJ98]. [BGH97] examines spatiotemporal
structures for main memory. Due to the temporal component, spatiotemporal
databases need to manage large amounts of data accumulated over long periods
of time (historical data). It is thus important to develop efficient access
methods (indices) to access such databases.
Area References:
[BGH97] J. Basch,
L. Guibas and J. Hershberger, "Data Structures for Mobile Data", Proc.
ACM-SIAM SODA, pp. 747-756, Jan. 1997.
[CR99] J. Chomicki,
P. Revesz, "A Geometric Framework for Specifying Spatiotemporal Objects",
Proc. 6th International Workshop on Time Representation and Reasoning,
May 1999.
[E93] M.J. Egenhofer,
"What's Special about Spatial Database Requirements for Vehicle Navigation
in Geographic Space", Proc. SIGMOD Conference, 398-402 1993.
[EGSV98] M. Erwig,
R.H. Guting, M. Schneider and M. Vazirgianis, "Spatio-temporal Data Types:
An Approach to Modeling and Querying Moving Objects in Databases", ACM
GIS Symposium, pp. 131-136, 1998.
[KGT99] G. Kollios,
D. Gunopulos, V.J. Tsotras, "On Indexing Mobile Objects", in Proc. ACM
PODS, 1999.
[ST99] B. Salzberg,
V.J. Tsotras, "A Comparison of Access Methods for Time-Evolving Data",
ACM Computing Surveys, June 1999.
[SY91] S. Shekhar
and T.A. Yang, "Motion in a Geographical Database System", Proc. of 2nd
SSD, pp. 339-357, 1991.
[SWCD97] A. P. Sistla,
O. Wolfson, S. Chamberlain, S. Dao, "Modeling and Querying Moving Objects",
Proc. IEEE ICDE, pp. 422-432, Apr. 1997.
[TOW98] J. Tayeb,
O. Ulusoy, O. Wolfson, "A Quadtree-Based Dynamic Attribute Indexing Method",
The Computer Journal, Vol. 41, No. 3, pp. 185-200, 1998.
[VTS98] M. Vazirgiannis,
Y.Theodoridis, T.K. Sellis, "Spatio-Temporal Composition and Indexing for
Large Multimedia Applications", Multimedia Systems, 6(4): 284-298, 1998.
[W94] M. Worboys,
"A Unified Model for Spatial and Temporal Information", The Computer Journal,
37(1): 36-34, 1994.
[WXCJ98] O. Wolfson,
B. Xu, S. Chamberlain, L. Jiang, "Moving Objects Databases: Issues and
Solutions", Proc. SSDBM, pp. 111-122, Jul. 1998.
Potential Related
Projects:
We would like to cooperate
with colleagues working on spatial, geospatial, temporal and multimedia
databases.