CSE 555: Introduction to Spatial Computing

Instructor: Dr. Viswanath Gunturi
Contact: gunturi@iiitd.ac.in, B-402 Academic Block
Office hours: Tuesday and Thursday 11:00 -- 12:00pm
Credits: 4
Class Time and Place: Tu and Thu: 9:30am - 11:00am :: Room num: C12
Teaching Assitants
  • Karishma Tirthani (karishma15027@iiitd.ac.in) (Office hours: Wednesday 3:00pm -- 4:00pm Library ground floor)
  • Neeti Arora (neeti15039@iiitd.ac.in) (Office hours: Wednesday 2:00pm -- 3:00pm CDX)
  • Ananya Harsh Jha (ananyaharsh12018@iiitd.ac.in) (Office hours: Monday 2:30pm -- 3:30pm CDX glass room)

    • To Register: Contact academic affairs office
    Pre-requisites: Basic knowledge of data structures (e.g., CSE102 Data Structures and Algorithms) and databases (e.g., CSE202 Fundamentals of Database Systems), basic understanding of mathematics and programming skills.
    Post-Condition: By the end of the course:
  • Student is able to distinguish between traditional relational data and spatial data by pointing out some of the unique challenges of handling spatial data. For example, by being able to defend the need for operators beyond the traditional select, project and join of traditional relational databases
  • The student is able to define and interpret basic terminology of spatial data, e.g., field vs object data models, field operators, OGIS operators, spatial query languages, index structures for spatial data etc.
  • The student is able to apply basic spatial query processing algorithms such as Voronoi diagrams, convex hulls, and search algorithms on spatial index structures and basic spatial data mining algorithms (co-location and hotspot detection).

    • Textbooks: GIS: A Computing Perspective , M. Worboys et al., CRC Press, 2004. ( amazon link ), Spatial Databases: A Tour, Shashi Shekhar et al., Prentice Hall, 2003. ( amazon link )

    Important Links Homeworks, Schedule, Interesting Readings

    Background: Spatial computing encompasses a set of ideas, solutions, technologies, and systems that transform our lives and society by creating a new understanding of locations; how we know, communicate, and visualize our relationship to locations; and how we navigate through those locations. Spatial Computing has had a transformative impact. Large organizations (e.g., logisitics companies) use spatial computing for site selection, asset tracking, facility management, navigation and logistics. Scientists use Gobal Positioning systems to track endangered species and better understand animal behavior, while farmers use these technologies for precision agriculture to increase crop yields and reduce costs. Government agencies also use spatial computing technologies for a wide range of applications which include transportation and urban planning, disease monitoring and epidemiology (e.g., public health), census blocks, weather modelling, mapping terrains etc.

    Topics: This course introduces fundamental ideas underlying geo-spatial science, systems and services. These include spatial concepts and data models (e.g, field vs object based), spatial query languages, fundamental spatial algorithms (e.g., space filling curves, vornoi diagrams, etc.), spatial storage and indexing (e.g., Grid files, Quadtrees and R-trees), query processing (e.g, join strategies) and optimization, spatial networks (conceptual, logical and physical level design issues), spatial data mining (classification, association and clustering). Some future research trends in spatial computing would also be covered.

    Required Work: This course would have four homeworks, two exams and a quiz. Homeworks may have both written and programming components. Programming component of the homework would include questions requiring SQL or a high-level language. Following is the distribution of weightage of these deliverables:

  • Homework assignments..... 12% each
  • Mid-term exam............ 17%
  • Final exam............... 22%
  • Quiz..................... 13%

    • Group formation policies All homeworks should be done in a team. Following policies would be enforced with regards to the team configuration.

  • Teams of size one, two and three are allowed.
  • All teams (irrespective of their size) would have a common deadline by which the homework needs to be submitted.
  • Teams of size one and two would be doing the same amount of work and for the same deadline.
  • Teams of size three would be given some extra questions which need to completed by the same deadline and for the same 12% weightage.

    • Other Policies Makeup Exam or Quiz Policy: Makeup exams or quizzes will not be offered except in case of critical travel (e.g., paper presentation at a conference) that cannot be reschedules or medical emergency as documented by a doctor. Makeup exams or quizes would given only before the scheduled day of exam or quiz for the entire class. For example, if a quiz (or an exam) is scheuled on date X (which you cannot attend), then a makeup quiz (or an exam) would be given only before the date X. Post scheduled-day makeups would be given only in case of documented medical emergencies.
    Late submission policy on homeworks: All homeworks must be submitted within the specified deadline. However, we understand that it may not always be possible on part of students to do so. In order to accomodate this, we would allow at grace period of 24 hours where the students are allowed to submit with a score reduction of 30%. Within 24 hours and 48 hours, there would be a score reduction of 60% byond which the submission would not receive any score.
    Policies from TAs:

  • All queries relating to the course must be resolved only through emails, designated office hours and forums on usebackpack page.
  • Emails and posts on usebackpack forum will be replied each day between 1:00pm --- 6:00pm. Emails received after 6:00pm would be responded on the next day.
  • No questions relating to homeworks or exam-related material would be answered during the last 12 hours before the particular deliverable is due.

    • Note: Academic dishonesty polcies of IIIT Delhi apply. Visit this link for more information.

    Auxiliary Information: Representing 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, 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 , Flickr location API , Twitter location API

    Spatial computing systems include Geographic Information Systems (e.g. Open Source GRASS GIS , ESRI ArcGIS family , ), Database Management Systems (e.g. PostgreSQL PostGIS , Oracle Spatial & Graph , IBM DB2 Spatial Extender , MS SQL Server Spatial ), Spatial data mining platforms (e.g. R , and standards opengeospatial.org , ISO TC 211 etc.

    Spatial computing 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.

    Resources research literature 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.