CSCI 587 • Geospatial Information Management |

Course Description

In the past forty years, Geospatial Information Systems (GIS) have seen an increasing role in decision making tasks. However, it was not until early 2000’s that the power of digital geospatial information was brought to mass population through online map services such as Yahoo-map and later Google-Earth and Microsoft Virtual Earth. Nowadays, due to the proliferation of mobile devices with accurate positioning capabilities (e.g., GPS, Wi-Fi localization), a wide array of popular locationcentric applications, e.g., location-based services, geo-social networks and ride sharing have become commonplace. In return for sharing their locations with the service provider, users can find restaurants and shopping malls nearby, can plan their travel itinerary with ease, or can connect with nearby friends. While the benefits of personalized location services are clear, there are also increasing risks associated with the sharing of fine-grained individual locations. The uncontrolled sharing of users’ whereabouts can lead to a wide range of attacks, from stalking and assault, to various privacy breaches that may disclose sensitive personal details such as one’s health status, political or religious orientation, etc.

The focus of this course is on studying techniques to efficiently store, manipulate, index, query, and analyze geospatial information in support of real-world geographical and decision-making applications. In this course, students will become familiar with a variety of geospatial applications, such as location-based services, online maps, and ride sharing, and datasets including GPS points, road-network data, and 3D models. The course will cover both traditional methods and modern approaches incorporating machine learning (ML) and artificial intelligence (AI) for analyzing location and spatiotemporal data. Topics include:

Spatial Index Structures: Techniques such as Quadtrees, K-d Trees, One-dimensional Orderings, PK-Trees, R-Trees, and Voronoi-based indexes for efficient data management.
Spatial Queries: Methods for performing k-Nearest Neighbor (kNN), Reverse-NN, Skyline, and Spatial Skyline queries.
Non-Euclidean Spaces: Analysis of complex spaces like road networks and land surfaces.
Geo-Spatial Applications: Applications including Spatial Crowdsourcing, Geo-Social Networks, and Ride Sharing.
Geo-Spatial Data Privacy: Ensuring privacy and security in handling geospatial data.
Machine Learning for Geospatial Data: Utilizing supervised and unsupervised learning techniques for tasks such as clustering, classification, and anomaly detection in location data.
AI for Spatiotemporal Analysis: Implementing AI algorithms for predictive analytics, real-time traffic forecasting, and dynamic routing based on spatial and temporal data patterns.

This comprehensive coverage ensures that students will understand the foundational techniques of geospatial data handling but also stay up-to-date of cutting-edge methodologies in ML and AI that are transforming the field.

Recommended Preparation: The course assumes student familiarity with a conceptual data modeling tool such as EntityRelationship (ER) data model, a logical data model such as the relational data model, SQL query language, normal forms and logical data design, physical characteristics of mass storage devices such as magnetic disks and memory, physical data design and index structures such as B+-tree and hash indexes, concurrency control and crash recovery protocols. Familiarity with the fundamentals of machine learning, including supervised, unsupervised, and reinforcement learning, is also required. While CSCI-567 (Machine Learning) is recommended, it is not mandatory. Students will need to use C/C++ and Python programming languages for the class project.

Class Time: Mon - Wed, 2:00pm - 3:50pm PST
Class Location: THH 212

Instructor
Prof. Cyrus Shahabi
Email: shahabi@usc.edu
OH: Mon-Wed, 4-5pm, PHE-306a

Teaching Assistant
Arash Hajisafi
Email: hajisafi@usc.edu
OH: TBD

Teaching Assistant
Maria Despoina Siampou
Email: siampou@usc.edu
OH: TBD

Grading

The grading breakdown for this class is as follows:

Midterm 1: 30%
Midterm 2: 30%
Project: 30% (split in 3 deliverables – 10% each)
Participation: 10%

Lectures

Date	Lecture	Readings
08/26	Lecture 1 (Arash & Maria): Course Introduction [ slides ]	Readings 1-6
08/28	Lecture 2 (Arash & Maria): Fundamentals of Computational Geometry [ slides ]	Readings 1-6
09/02	Labor Day, No Class
09/04	Lecture 3 : Spatial Indexes [ slides ]	Spatial Data Structures by Hanan Samet
09/09	Lecture 4 : Spatial Indexes: R-Trees [ slides ]	R-Trees, A dynamic index for spatial searching R+-Trees, A dynamic index for multi-dimensional objects
09/11	Lecture 5 (Arash & Maria): Introduction to HW [ slides ]	To be added
09/16	Lecture 6 : Nearest Neighbor Queries [ slides ]	Nearest Neighbor Queries
09/18	Lecture 7 : Reverse k-Nearest Neighbor Queries [ slides ]	Reverse kNN Search in Arbitrary Dimensionality
09/23	Lecture 8 : Skyline Queries [ slides ]	An Optimal and Progressive Algorithm for Skyline Queries
09/25	Lecture 9 : Spatial Skyline Queries [ slides ]	The Spatial Skyline Queries Processing Spatial Skyline Queries in Both Vector Spaces and Spatial Network Databases
09/30	Lecture 10 : VoR Trees [ slides ]	VoR-Tree
10/02	Lecture 11 : Spatial Queries: Continuous Nearest Neighbor [ slides ]	Time-Parameterized Queries in Spatio-Temporal Databases
10/07	Lecture 12 : Spatial Queries: Continuous Nearest Neighbor [ slides ]	Continuous Nearest Neighbor Search
10/09	Lecture 13 : Spatial Queries on non-Euclidean Space: Road Networks [ slides ]	Query Processing in Spatial Network Databases
10/14	Lecture 14 : Spatial Queries on non-Euclidean Space: Road Networks II [ slides ]	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases Indexing Network Voronoi Diagrams
10/16	Midterm Exam 1
10/21	Lecture 15 : Spatial Queries on non-Euclidean Space: Road Networks III [ slides ]	Scalable Network Distance Browsing in Spatial Databases
10/23	Lecture 16 : Spatial Queries on non-Euclidean Space: Time-dependent Road Network [ slides \| slides (part b) ]	Online Computation of Fastest Path in Time-Dependent Spatial Networks Efficient K-Nearest Neighbor Search in Time-Dependent Spatial Networks
10/28	Lecture 17 (Maria): Trajectory-based Routing / Reachability Analysis [ slides ]	Time-Dependent Reachability Analysis; A Data-Driven Approach
10/30	Lecture 18 (Arash): Spatio-Temporal Forecasting Tasks [ slides ]	Semi-Supervised Classification with Graph Convolutional Networks Diffusion Convolutional Recurrent Neural Network; Data-driven Traffic Forecasting Learning Dynamic Graphs from All Contextual Information for Accurate Point-of-Interest Visit Forecasting
11/04	Lecture 19 : Spatial Crowdsourcing [ slides ]	GeoCrowd; Enabling Query Answering with Spatial Crowdsourcing Maximizing the number of worker's self-selected tasks in spatial crowdsourcing Task matching and scheduling for multiple workers in spatial crowdsourcing Price-aware Real-time Ride-sharing at Scale; An Auction-based Approach
11/06	Lecture 20 : Geo-Social [ slides ]	GEOSO - A Geo-Social Model; From Real-World Co-occurrences to Social Connections EBM; An Entropy-based Model to Infer Social Strength from Spatiotemporal Data A General Framework for Geo-Social Query Processing Real-Time Multi-Criteria Social Graph Partitioning; A Game Theoretic Approach
11/11	Lecture 21 : Location Privacy [ slides ]	A Neural Approach to Spatio-Temporal Data Release with User-Level Differential Privacy A Neural Database for Diferentially Private Spatial Range Queries
11/13	Lecture 22 : Geo Privacy [ slides ]	Price-aware Real-time Ride-sharing at Scale; An Auction-based Approach walk2friends; Inferring Social Links from Mobility Profiles Protecting against Inference Attacks on Co-Location Data Privacy-Preserving Online Task Assignment in Spatial Crowdsourcing with Untrusted Server
11/18	Lecture 23 : Spatial Fairness [ slides ]	Fair Spatial Indexing; A paradigm for Group Spatial Fairness Models and Mechanisms for Spatial Data Fairness Spatial Fairness; The Case for its Importance, Limitations of Existing Work, and Guidelines for Future Research
11/20	Lecture 24 : Trajectory Mining and Moving Behavior Analysis [ slides ]	VAMBC; A Variational Approach for Mobility Behavior Clustering CSGAN; Modality-Aware Trajectory Generation via Clustering-based Sequence GAN Generating Realistic and Representative Trajectories with Mobility Behavior Clustering
11/25	Lecture 25 (Maria): Spatial Encoding/Representation Learning [ slides ]	MULTI-SCALE REPRESENTATION LEARNING FOR SPATIAL FEATURE DISTRIBUTIONS USING GRID CELLS Deep Representation Learning for Trajectory Similarity Computation Towards General-Purpose Representation Learning of Polygonal Geometries
11/27	No Class, Thanksgiving Break
12/02	Lecture 26 : LLMs for Geographic Data and Geo-Foundation Models [ slides ]	SPABERT; A Pretrained Language Model from Geographic Data for Geo-Entity Representation Embracing LLMs for Point-of-Interest Recommendations Geo-Foundation Models; Reality, Gaps and Opportunities (Vision Paper)
12/04	Midterm Exam 2

Reading Materials

There are no required text books but the following book is recommended as an optional reading material:

Foundations of Multidimensional and Metric Data Structures by Hanan Samet. (A 20% discount coupon for the book is available here.)

Other reading material is based on recently published technical papers available via the ACM/IEEE/Springer digital libraries. All USC students have automatic access to these digital archives.

A full list of the related published technical papers can be found here.

Additional Policies

Exam dates are announced on the first week of classes in order to allow students sufficient time to schedule other activities around those dates. Students need to make sure they can take exams on the specified dates and times. There will be no makeup exams.

Academic Integrity Policy

All homeworks must be solved and written independently, or you will be penalized for cheating. The USC Student Conduct Code prohibits plagiarism. All USC students are responsible for reading and following the Student Conduct Code.

In this course we encourage students to study together. This includes discussing general strategies to be used on individual assignments. However, all work submitted for the class is to be done individually.

Some examples of what is not allowed by the conduct code: copying all or part of someone else’s work (by hand or by looking at others’ files, either secretly or if shown), and submitting it as your own; giving another student in the class a copy of your assignment solution; consulting with another student during an exam. If you have questions about what is allowed, please discuss it with the instructor.

Academic Conduct

Students who violate University standards of academic integrity are subject to disciplinary sanctions, including failure in the course and suspension from the University. Since dishonesty in any form harms the individual, other students, and the University, policies on academic integrity will be strictly enforced. We expect you to familiarize yourself with the Academic Integrity guidelines found in the current SCampus.

Violations of the Student Conduct Code will be filed with the Office of Student Conduct, and appropriate sanctions will be given.

USC seeks to maintain an optimal learning environment. General principles of academic honesty include the concept of respect for the intellectual property of others, the expectation that individual work will be submitted unless otherwise allowed by an instructor, and the obligations both to protect one’s own academic work from misuse by others as well as to avoid using another’s work as one’s own. All students are expected to understand and abide by these principles. Students will be referred to the Office of Student Judicial Affairs and Community Standards for further review, should there be any suspicion of academic dishonesty. The Review process can be found at: https://sjacs.usc.edu/students/report.

Discrimination, sexual assault, and harassment are not tolerated by the University. You are encouraged to report any incidents to the Office of Equity and Diversity or to the Department of Public Safety. This is important for the safety of the whole USC community. Another member of the university community – such as a friend, classmate, advisor, or faculty member – can help initiate the report, or can initiate the report on behalf of another person. The Center for Women and Men provides 24/7 confidential support, and the sexual assault resource center webpage describes reporting options and other resources.

Viterbi School of Engineering Honor Code

Engineering enables and empowers our ambitions and is integral to our identities. In the Viterbi community, accountability is reflected in all our endeavors.

Engineering + Integrity.
Engineering + Responsibility.
Engineering + Community.
Think good. Do better. Be great.

These are the pillars we stand upon as we address the challenges of society and enrich lives.

Support Systems

A number of USC’s schools provide support for students who need help with scholarly writing. Check with your advisor or program staff to find out more. Students whose primary language is not English should check with the American Language Institute, which sponsors courses and workshops specifically for international graduate students. The Office of Disability Services and Programs provides certification for students with disabilities and helps arrange the relevant accommodations. If an officially declared emergency makes travel to campus infeasible, USC Emergency Information will provide safety and other updates, including ways in which instruction will be continued by means of blackboard, teleconferencing, and other technology.