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

Contact Information

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

Teaching Assistant:    Mike Lieberman   <codepoet{at}>
AVW, Room 4431

Course Information

Class Time: Tue-Thu 12:30pm - 1:45pm
Location: CSI 3120
Instructor's Office Hours:   Tue 10:00am - 11:00am at AVW 4425


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. "Foundations of Multidimensional and Metric Data Structures", Morgan Kaufmann, San Francisco, CA, 2006.

  3. 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.


Mid-term: TBA
Final: TBA (Coverage

Homework & Projects

Project Topics


Spatial Data Structure Applets
Course Outline
Textbooks for the course


Missing Slides cm24 and cm25
GIS Graphics Transformation Slides (Pages 50-118 of cl Slides)
Laths Slides
Critique of Tomlin's book
Incremental Nearest Neighbor Finding Slides (2009 ICDE Tutorial)
Scalable Network Distance Browsing in Spatial Databases Slides (2008 SIGMOD Paper)
Fieldtrees (Loose Quadtrees) Slides
Loose Quadtree Paper
Quadtree Building Slides
Point Data Slides
Ranking in Spatial Databases Slides
Range Tree and Priorty Search Tree Slides

Final Exam Coverage

Fractals (fr)
Quadtree Background (bg)
Data Structure Conversion (qb)
Alternative Representations (ar)
Tessellations (ts)
Neighbor Finding Methods in Quadtrees (nf)
Geometric Properties in Quadtrees (gp)
Transformations on Quadtree (tf)
Region Expansion (bf)
Hierarchical Representations of Point Data (hp up to slide hp24)
Range Tree And Priority Search Trees (rt)
Slides nn16 and nn17 from Ranking in Spatial Databases
Loose quadtrees (cover fieldtree, partition fieldtree)
Shortest path quadtree and finding nearest neighbors in spatial networks (like road networks - called scalable network distance browsing)

For the Scalable network distance browsing you are not responsible for the whole set. Just look at slides 1-104. This represents what we discussed in class.

There is also a set of slides called "Incremental Nearest Neighbor Finding". Here slides 212-230 are relevant to the class. They are similar to the designated Ranking in Spatial Databases slides but not the same.


All graded materials (examinations and programming assignments and homework) must be strictly individual efforts. Cooperation on homework programming assignments is limited to general discussion of the problem (not its solution), and assistance with errors. Additional cooperation is considered academic dishonesty. Transmitting a copy of a solution (in either hardcopy or electronic form), falsely representing the correctness of a program or homework, or delaying other members of the class from completing a programming assignment are considered forms of academic dishonesty.

The instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment for missing a Major Scheduled Grading Events unless the failure to perform was due to an excused absence. A valid excused absence will need to be granted through the student presenting documentation from the Health Center or from an outside health care professional. This documentation must be submitted within one week of returning to classes and must include dates of incapacitation as well as the name and phone number of the health care provider. No diagnostic information shall be given. Once the period of incapacitation is over, the student must meet the missed academic responsibilities at according to the requirements and specifications set forth by the instructor. The Major Scheduled Grading Events for this course include:
  1. Exam 1 (Midterm): TBA
  2. Exam 2 (Final): TBA
  3. Course Project: TBA

Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.