CMSC 725: Geographical Information Systems and Spatial Databases (Fall 2006)

Contact Information

Instructor:    Prof. Hanan Samet   <hjs{at}>
AVW, Room 4425

Teaching Assistant:    Jagan Sankaranarayanan  <jagan{at}>
AVW, Room 4431

Course Information

Class Time: Tue-Thu 2:00pm - 3.15pm
Location: CSI 3118
Instructor's Office Hours:   Tue 1:00 PM - 2:00 PM at AVW 4425
TA Office Hours: Tue-Thr 11:30 AM - 1:30 PM at AVW 4431


Please take a few moments to fill out the online class evaluation form.[LINK]

Nov 28: Slides for download - MaxNearestDist Estimator,Pk-trees,NN Slides

Nov 18: Slides for download - bf08-bf13

Nov 16: Slide for download - tl07 Slides

HW -5 due.
What is the advantage of doubly-linked lists over a singly-linked lists ?
Can you reduce the number of comparison tests (by half) when searching a binary search tree ?

Nov 9: QB Slides  NF Slides

Oct 24: HW -4 due. Problem description can be found here.

Oct 19: HW - 3 due.

HW-3: Description: Show that the partition of each of the cells of a restricted quadtree into two triangles does not remove the cracks ?

Oct 17: HW -2 due. Also, a short progress report on the project has to be submitted.

HW-2: Problem description:

What conditions must be satisfied by the bounding ellipses of two subarcs of an arc tree to guarantee that these two subarcs do indeed intersect? Prove that your answer is true.

Oct 5: HW-1 (which was described in class) is due today.

Sept 21: For your reading pleasure

Social processes and proofs of theorems and programs  (alternate link)
Manifold Destiny

Sept 19: Slides on Graph Representations

Sept 14: Project descriptions are due on Thur, Sept 28. You should provide us with a short write-up of your project for the course.

Sept 12:

Slides on Image Databases (UMD CS & UMIACS domain only).
Slides on Pictorial Query Specifications (UMD CS & UMIACS domain only).
Image Database Demo
ARCHIMEDES -- Similarity retrieval on a breast cancer database

Sept 7: List of possible projects for the class is available here (UMD CS & UMIACS domain only).

Sept 5: Required Reading - "Draft Summary of Geographic Information Systems and Cartographic Modeling", pages 789--800 of the slide set.

Information on the availability of the textbooks for the class
  1. Copy of lecture note slides titled ``GEOGRAPHIC INFORMATION SYSTEMS (GIS): A TECHNICAL APPROACH'' will be available for sale at the Engineering Copy Center.

  2. H. Samet. "Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS". Addison Wesley, Reading, MA, 1990. This book is out of print, but a spiral-bound version of the most recent version is available for sale at the University Book Center.

  3. H. Samet. "Foundations of Multidimensional and Metric Data Structures", Morgan Kaufmann, San Francisco, CA, 2006.

    Copies of Reference 3 should be available for sale at the University Book Center. Alternatively, Prof. Samet would be placing one bulk order for the book. You are welcome to place an order for the book with him to get a substantial discount as announced in class. This book lies somewhere between recommended and required in the sense that students who took CMSC420 will have much of the material covered in this book in the previously published book by Samet titled "The Design and Analysis of Spatial Data Structures". If you don't have the "Design" book, then you should get the "Foundations" book.

Aug 29: Class webpage created.


Mid-term: Thur October 26, 2006 in class
Final Examination

Homework & Projects

Possible List of Projects  (UMD CS and UMIACS domain only).


Spatial Data Structure Applets
Course Outline
Textbooks for the course
Slide Set errata

Class Calendar