CSci 5980: From GPS and Google Earth to Spatial Computing

Instructor: Prof. Shashi Shekhar
Contact:, (612) 624-8307, 5-203, EE/Csci Building
Credits: 3
Class Time and Place: tbd.
Class Webpage:
To Register: Contact Computer Science reception in 4-192 EE/Csci. Bldg. (Phone 612-625-4002).
Pre-requisites: Course work in database management or geographic information science.
Text: GIS: A Computing Perspective , M. Worboys et al., CRC Press, 2004. ( amazon ), Slides .
Supplementary Material: Encyclopedia of GIS and selected articles.
Links: Sample Schedule from Fall 2010 , Homeworks from Fall 2010, Textbook Problems from Fall 2010, TA-announcements from Fall 2010 , Instructor Announcements from Fall 2010 ,

Long Title: Spatial Computing: How Global Positioning Systems, Geo-Social Media and Cell-phone based Location Based Services are transforming computing ?
Motivation: Over the last decade, geo-informatics has become an important part of our everyday life. Google Earth, a popular web-based virtual globe, is widely used for mash-ups to publish a variety of information. Navigation devices and cell-phone/web-based location based services (e.g., check-in models on foursquare and facebook) are used for finding close by friends, and nearby businesses and routes. Large organizations value it for site-selection, logistics and customer relationship management. Emergency managers turn to it to prepare for, respond to, and recover from disasters; police to identify crime hot-spots for patrol planning and social interventions, earth scientists to understand climate change, and epidemiologists to track spread of infectious diseases. Interested readers are encourage to review a short 2011 congression report (23 pages) to see many recent examples of great societal importance ranging from California wildfires (2008) to Japanese Earthquake and Tsunami (2011).

Topics: This course introduces the fundamental ideas underlying the geo-spatial services, systems, and sciences. These include mathematical concepts (e.g. Euclidean space, topology of space, network space), geo-information models (e.g. field-based, object-based), representations (e.g. discretized, spaghetti, tessellation, vornoi diagram), algorithms (e.g. metric and Euclidean, topological, set-based, triangulation, graph-based), data-structures and access methods (e.g. space filling curves, quad-trees, R-tree), analysis (e.g. spatial query languages, spatial statistics, spatial data mining), architectures (e.g. location sensor, location based services), interfaces (e.g. cartography, Geo-visualization), reasoning (e.g. data quality, approaches to uncertainty), and time (e.g. valid time, events and processes).

Note: UCGIS GIST Body of Knowledge domains of "Analytical Methods", "Data Modeling" and "Conceptual Foundations" are explored including the subdomains of AM2: Query Operations and query languages, AM3: Geometric Measures, AM11: Network Analysis, CF4: Elements of geographic information, CF5: Relationships, DM1: basic storage and retrieval structures, DM2: Database Management Systems, DM3: Tessellation data models, DM4: Vector and object data models, and DM5: Modeling 3D, uncertain and temporal phenomena.

Required Work: Course has a set of four assignments and two examinations. The weighting scheme used for grading is: Midterm exam. - 25%, Final exam. - 25%, Assignments including a project - 40%, Class participation - 10%. Examinations will emphasize problem solving and critical thinking. Assignments will include pen-and-paper problems and computer based laboratory experiments/projects to reinforce concepts uncovered in the classroom. Class participation includes spatial-news presenting and active group learning. Participants will take turn to review current spatial news and present selected news items in the class. During active learning, participants will work in small groups on exercises provided in the class meeting. After this, a randomly chosen group will be invited to summarize the discussion in his/her group. Other groups in the class may critique constructively.

Career Opportunities: Major computer science employers looking for geospatial knowledge and skills include ESRI, Facebook, Google, IBM, Microsoft, Nokia, Oracle, Yahoo, and many government agencies related to public health, public safety, transportation, etc. As per a recent article in the Nature magazine “ the US Department of Labor identified geotechnology as one of the three most important emerging and evolving fields, along with nanotechnology and biotechnology. Job opportunities are growing and diversifying as geospatial technologies prove their value in ever more areas. ”

Auxiliary Information: Representing geo-spatial information services include virtual globes (e.g. Google Earth, Bing Maps , World Wind ), location based services (e.g. Apple iPhone location services, Google Android location and maps, Nokia Ovi and Location-based services , foursquare, mapquest ), enterprise consulting (e.g. IBM smarter planet). Representative application programming interfaces include HTML 5 Geolocation API , Google Maps API , Bing Maps API , Yahoo Maps Web Services , Flickr Flickr Maps , Twitter location API

Geo-spatial systems include GIS (e.g. Open Source GIS , ESRI ArcGIS family , ), Database Management Systems (e.g. Oracle Spatial & Locator , IBM Spatial Offerings , MS SQL Server Spatial ), spatial data mining platforms (e.g. R , Splus , Crimestat), and standards , ISO TC 211 etc.

Geo-spatial information science includes relevant branches of computer sciences (e.g. spatial databases, spatial data mining, computational geometry, computational cartography), mathematics (e.g. topology, geometry, graph theory, spatial statistics), physical sciences (e.g. geodesy and geoPhysics), and social sciences (e.g spatial cognition), etc. Web-based resources include Encyclopedia of GIS , Proceedings of the ACM SIG-Spatial Conf. on GIS , Proceedings of the Intl. Symposium on Spatial and Temporal Databases , IEEE Transactions on Knowledge and Data Eng. , and GeoInformatica: An International Journal on Advances in Computer Science for GIS.

Non-intuitive geo-spatial concepts include map projections , scale , auto-correlation , heterogeneity and non-stationarity etc. First two impact computation of spatial distance, area, direction, shortest paths etc. Spatial (and temporal) autocorrelation violates the omni-present independence assumption in traditional statistical and data mining methods. Non-stationarity violates assumptions underlying dynamic programming, a popular algorithm design paradigm in Computer Science. This course will also explore these concepts particularly in context of the gap between traditional Computer Science (CS) paradigms and the computational needs of spatial domains. We will examine current approaches to address these new challenges possibly via talks from prominent geospatial thinkers at our university.