Spatial Databases (ECS 266) Spring 2008

M March 31	Organizational Issues, Introduction to Spatial Databases
W April 2	1.Introduction to Spatial Databases Additional reading: Ralf Hartmut Güting: An Introduction to Spatial Database Systems. The VLDB Journal, 3(4):357-399, 1994. http://www.acm.org/sigmod/vldb/journal/VLDBJ3/P357.pdf Shashi Shekhar et al.: Spatial Databases: Accomplishments and Research Needs. IEEE Transactions on Knowledge and Data Engineering, 11(1):45-55, 1999. http://www.cs.umn.edu/Research/shashi-group/paper_ps/tkde.ps
F April 5	2. Spatial Concepts and Representation of Spatial Objects (part 1) Additional Reading: •Markus Schneider: "Spatial Data Types: Conceptual Foundation for the Design and Implementation of Spatial Database Systems and GIS“, tutorial given at 6th International Symposium on Advances in Spatial Databases (SSD'99), 1999. http://www.cise.ufl.edu/~mschneid/Service/Tutorials/TutorialSDT.html
M April 7	2. Spatial Concepts and Representation of Spatial Objects (part 2) Additional Reading: Ralf Hartmut Güting, Markus Schneider: Realm-Based Spatial Data Types: The ROSE Algebra. VLDB Journal 4(2): 243-286 (1995). http://www.informatik.fernuni-hagen.de/import/pi4/papers/ROSEAlgebra.pdf
W April 9	2. Spatial Concepts and Representation of Spatial Objects (part 3) (spatial abstract data types and operators)
F April 11	Finished section on operators
M April 14	3. Computational Geometry Interval Tree, Convex Hull, and Sweep Line Methods
W April 16	Polygon Partitioning and line segment intersection problems
F April 18	Polygon intersection
M April 21	4. Spatial Access methods (part 1) Introduction, fixed Grid, Grid File Additional Reading: Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Computing Surveys 30(2): 170-231 (1998). http://portal.acm.org/citation.cfm?id=280279 •
W April 23	K-d Trees
F April 25	4. Spatial Access methods (part 2) Quadtrees
M April 28	Quadress, PM Quadtress, Region Quadtrees
W April 30	4. Spatial Access methods (part 3) Introduction to R-Trees Additional reading Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees Have Grown Everywhere. http://www.rtreeportal.org/pubs/MNPT03.pdf The R-Tree Portal. http://www.rtreeportal.org/
F May 2
M May 5
W May 7
F May 9
M May 12
W May 14
F May 16
M May 19	5. Spatio-temporal databases and Moving Objects (all on blackboard) Introduction Temporal databases, valid-time / transaction-time Reading: Survey of Spatio-Temporal Databases by T Abraham, JF Roddick - GeoInformatica, 1999 - Springer
W May 21	5. Spatio-temporal databases and Moving Objects (all on blackboard) moving objects, space/time concepts, requirements, types of queries applications
F May 23	Class canceled

M March 31

Organizational Issues, Introduction to Spatial Databases

W April 2

1.Introduction to Spatial Databases
Additional reading:

Ralf Hartmut Güting: An Introduction to Spatial Database Systems. The VLDB Journal, 3(4):357-399, 1994. http://www.acm.org/sigmod/vldb/journal/VLDBJ3/P357.pdf
Shashi Shekhar et al.: Spatial Databases: Accomplishments and Research Needs. IEEE Transactions on Knowledge and Data Engineering, 11(1):45-55, 1999. http://www.cs.umn.edu/Research/shashi-group/paper_ps/tkde.ps

F April 5

2. Spatial Concepts and Representation of Spatial Objects (part 1)
Additional Reading:

•Markus Schneider: "Spatial Data Types: Conceptual Foundation for the Design and Implementation of Spatial Database Systems and GIS“, tutorial given at 6th International Symposium on Advances in Spatial Databases (SSD'99), 1999.

http://www.cise.ufl.edu/~mschneid/Service/Tutorials/TutorialSDT.html

M April 7

2. Spatial Concepts and Representation of Spatial Objects (part 2)
Additional Reading:

Ralf Hartmut Güting, Markus Schneider: Realm-Based Spatial Data Types: The ROSE Algebra. VLDB Journal 4(2): 243-286 (1995).

http://www.informatik.fernuni-hagen.de/import/pi4/papers/ROSEAlgebra.pdf

W April 9

2. Spatial Concepts and Representation of Spatial Objects (part 3)
(spatial abstract data types and operators)

F April 11

Finished section on operators

M April 14

3. Computational Geometry
Interval Tree, Convex Hull, and Sweep Line Methods

W April 16

Polygon Partitioning and line segment intersection problems

F April 18

Polygon intersection

M April 21

4. Spatial Access methods (part 1)
Introduction, fixed Grid, Grid File
Additional Reading:

Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Computing Surveys 30(2): 170-231 (1998).
http://portal.acm.org/citation.cfm?id=280279

•

W April 23

K-d Trees

F April 25

4. Spatial Access methods (part 2)
Quadtrees

M April 28

Quadress, PM Quadtress, Region Quadtrees

W April 30

4. Spatial Access methods (part 3)
Introduction to R-Trees
Additional reading

Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees Have Grown Everywhere. http://www.rtreeportal.org/pubs/MNPT03.pdf
The R-Tree Portal. http://www.rtreeportal.org/

F May 2

M May 5

W May 7

F May 9

M May 12

W May 14

F May 16

M May 19

5. Spatio-temporal databases and Moving Objects (all on blackboard)

Introduction
Temporal databases, valid-time / transaction-time

Reading: Survey of Spatio-Temporal Databases
by T Abraham, JF Roddick - GeoInformatica, 1999 - Springer

W May 21

5. Spatio-temporal databases and Moving Objects (all on blackboard)

moving objects, space/time concepts, requirements, types of queries
applications

F May 23

Class canceled

Back to the top

Assignments

There will be four assignments; the assignments together with the
final count 55% towards the final grade (40% + 15%).

W April 9	Assignment 1
W April 23	Assignment 2
F May 9	Assignment 3
Sa May 24	Assignment 4

1.Philippe Rigaux, Michel Scholl, Agnès Voisard: Spatial Databases with Applications to GIS. Morgan Kaufman, 2002. [RVS02]

2.Shashi Shekhar, Sanjay Chawla: Spatial Databases – A Tour. Prentice Hall, 2003. [SC03]

3.Hanan Samet: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, 2006. [Sam06]

4.Mark de Berg, Marc van Krefeld, Mark Overmars, Otfried Schwarzkopf: Computational Geometry – Algorithms and Applications. Springer, 2000. [BKO00] Note that there is now a third edition!

5.Paul A. Longley, Michael F. Goodchild, David J. Maguire, David W. Rhind: Geographic Information Systems and Science. Wiley, 2001. [LGM01]

Several supplementary papers will be provided on this class Web site in the context of the lecture notes.

Conference and workshop papers mentioned in class can be obtained through:

Computer Science Bibliography http://www.informatik.uni-trier.de/~ley/db/
ACM Digital Library http://portal.acm.org/dl.cfm
IEEE Xplore http://ieeexplore.ieee.org

Instructor	Dr. Michael Gertz
Location	1062 Bainer
Time	MWF 2:10-3:00 pm
Final	A take home final will be handed out on Monday 6/2; due Friday 6/6

ECS 266 Spatial Databases - Spring 2008