UWT/TCSS 590B- ANALYSIS OF DATA IN GEOGRAPHIC INFORMATION SYSTEMS.
Autumn 2012

Instructors: Mohamed Ali, Ph.D.
Class sessions:
Tues/Thurs 6:30- 8:30 pm

The class has been completed and the PROJECT DEMOS has been posted. Please click here to get a tour with demo videos! Many thanks my geospatial students and well done!

Course Overview:

This course is an advanced level computer science elective in the areas of Geographic Information Systems (GIS). The course addresses spatial databases, in general, and focuses on their applications in GIS, in particular.

While traditional information systems deal with objects that are of numeric or alphanumeric data types, a wide set of applications deal with objects that have spatial extent (e.g., points, lines and polygons) or that are geographic in nature (i.e., representable on a map). "Are spatial data types special?" YES and NO! This course addresses how to represent, store, index, and process spatial objects and focuses on their application in the field of Geographic Information Systems (GIS).

With the growing interest in spatial databases (e.g., Microsoft SQL Server Spatial Library, IBM Spatial Solutions, Oracle Spatial ), with the ability to access a wealth of digitized maps  (e.g., Google maps, Bing maps, Navteq), with the availability of rich Geographic Information Systems (e.g., ESRI ArcGis), and with the advances in GPS devices (e.g., Garmin, TomTom) and smart phones(e.g., iPhones, Androids, and Windows Phones), geospatial data management and location based services have been crucial to industry at all scales.

 This course provides a good stretch to the students in the GIS field starting from theoretical basic concepts and ramping up quickly to provide a hands-on experience with various commercial GIS systems. The course is intended to motivate the next generation of geospatial researchers and, meanwhile, is geared up to plant the seed of an engineer who leads a career in Geographic Information Systems.

 If you want to know what the Wi-2011 GIS students have done in their project, please read:

http://www.springerlink.com/content/q6q6354014l59458/

Or watch:

http://www.youtube.com/watch?v=9dC7OQcs7Yc

Prerequisites:

TCSS 342 DATA STRUCTURES. We also recommend that all students have prior experience with programming languages such as C/C++/C#/Java. Students with no programming experience should not take this course.

Readings:

The links to readings will be made available on Moodle during the term. Please bring your readings to each class session so that you can refer to them during discussion. We will use a set of research papers. Your mentors or instructor may assign specific readings to individual students. We will also cover topics in the following textbook:
“Spatial Databases: With Application to GIS (The Morgan Kaufmann Series in Data Management Systems) by Philippe Rigaux, Michel Scholl, and Agnes Voisard (Jun 1, 2001)”

 

Course Contents:

For detailed and up-to-date course contents, please check the class Moodle website: https://moodle.insttech.washington.edu/course/view.php?id=412

Week #

Topic

Paper/ Project presentation

1

9/25

·          Course overview

 

9/27

·          Introduction to Spatial Databases Systems

·          Introduction to database support for spatial objects

·          Application of Spatial Databases to GIS

Textbook (Chapter 1)

 

 

 

2

10/2

Spatial Access Methods :

·          k-d tree

·          Grid files

·          Textbook (Ch 6)

·          BENTLEY, J. L. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9, 509–517.

·          NIEVERGELT, J., HINTERBERGER, H., AND SEVCIK, K. C. 1984. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9, 1, 38–71.

10/4

Spatial Access Methods:

·          Quad trees

·          Space filling curves &
z-ordering trees

·          Textbook (Ch 6)

·          SAMET, H. 1984. The quadtree and related hierarchical

data structure. ACM Comput. Surv.16, 2, 187–260.

·          16.Mohamed F. Mokbel, Walid G. Aref, and Ibrahim Kamel. "Analysis of Multi-dimensional Space-Filling Curves". GeoInformatica 2003, 7(3), pp. 179-209, Sep., 2003.

 

 

 

 

3

10/9

Spatial Access Methods:

·          R-trees

·          Space driven versus data driven index structures

·          GIST

 

 

·          R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING

·          Textbook (Chapter 6)

·          Generalized Search Trees for Database Systems

10/11

Spatial Access Methods:

·          R+ tree, R-trees Packing, R* tree

·          The dimensionality curse and dimensionality reduction

 

 

·          The R*-tree: an efficient and robust access method for points and rectangles

·          The R+Tree: A Dynamic Index for MultiDimensional Objects

·          On Packing R Trees  

·          Dimensionality Reduction for Similarity Searching in Dynamic Databases

 

 

 

4

10/16

Spatial Access Methods:

·          SP-GIST

·          Demo of various multidimensional index structures

 

 

·          An Extensible Database Index for Supporting Space Partitioning Trees

·         http://donar.umiacs.umd.edu/quadtree/

 

 

 

10/18

 

 

·          Spatiotemporal access methods:Survey of spatiotemporal index structures

Query Processing:

·          I/O algorithms for Spatial Data

·          Spatial Join

 

 

 

 

 

 

·          Mohamed Mokbel, et al. Spatiotemporal access methods

 

 

 

 

 

·          Textbook 7.2

 

·          Textbook 7.3

 

 

 

 

 

5

10/23

·          Nearest neighbor search

 

·          Computational Geometry

·          N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries.

·          Textbook 5.1,5.2,5.3

10/25

·          Computational Geometry

·          Representation of Spatial Objects

·          Textbook 5.4, 5.5

 

·          Textbook 2.1,2.2,2.3

 

 

 

6

10/30

·          Logical Models and Query Languages

·          The constraint data model

·          Textbook 3.1,3.2,3.1,3.4

 

·          Textbook Chapter 4

11/1

·          Map Matching

·          Map generation from GPS traces

·          Hidden Markov Map Matching Through Noise and Sparseness

·          From GPS Traces to a Routable Road Map

 

 

 

7

11/6

Learning to Think Spatially: GIS as a Support System in the K-12 Curriculum

·          The Incorporation of Geographic Information Science Across the K-12 Curriculum, Committee on Geography, National Research Council

11/8

Location based recommendation systems

·          HyperLocal, DirectionsBased Ranking of Places

·          Collaborative Location and Activity Recommendations with GPS History Data

 

 

 

8

11/13

Project presentations- checkpoint

 

11/15

Privacy preserving location based services

 

 

 

 

9

11/20

·          Data Stream Systems and GeoStreaming

 

11/22

Thanksgiving Holiday

 

 

 

 

1011/27

Project presentations – dry run

 

11/29

Commercial systems

Textbook (Chapter 8)

 

 

 

11

12/4

Final Project Presentations

 

12/6