CSCI 587 • Geospatial Data Analysis |

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: ZHS 352 (Zumberge Hall)

Instructor
Prof. Cyrus Shahabi
Email: shahabi@usc.edu
OH: Wed, 4-6pm, GCS 505F

Teaching Assistant
Chen Chu
Email: chenchu@usc.edu
OH: TBA

Grading

The grading breakdown for this class is as follows:

Midterm 1: 30%
Midterm 2: 30%
Homeworks: 30% (10% each)
Participation: 10%

Lectures

Full Paper and Reading List: Link

Date	Lecture	Readings	Logistics
01/11	Lecture 1 : Introduction to Course and Homeworks	Readings 1-6
01/13	Lecture 2 (TBA): Geospatial Data Applications
01/18	Martin Luther King’s Birthday Holiday, No Class
01/20	Lecture 3 (TBA): Fundamentals of Computational Geometry
01/25	Lecture 4 : Spatial Indexes	Spatial Data Structures by Hanan Samet	HW1 is released .
01/27	Lecture 5 : Spatial Indexes: R-Trees	R-Trees, A dynamic index for spatial searching R+-Trees, A dynamic index for multi-dimensional objects
02/01	Lecture 6 : Nearest Neighbor Queries	Nearest Neighbor Queries
02/03	Lecture 7 : Reverse k-Nearest Neighbor Queries	Reverse kNN Search in Arbitrary Dimensionality
02/08	Lecture 8 : Skyline Queries	An Optimal and Progressive Algorithm for Skyline Queries
02/10	Lecture 9 : Spatial Skyline Queries	The Spatial Skyline Queries Processing Spatial Skyline Queries in Both Vector Spaces and Spatial Network Databases
02/15	President's Day Holiday, No Class
02/17	Lecture 10 : VoR Trees	VoR-Tree; R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries
02/22	Lecture 11 : Neural Architectures for Geospatial Intelligence	(Optional) Understanding Deep Learning	HW1 Due. HW2 is released .
02/24	Lecture 12 : Spatial Queries: Continuous Nearest Neighbor I	Time-Parameterized Queries in Spatio-Temporal Databases
03/01	Lecture 13 : Spatial Queries: Continuous Nearest Neighbor II	Continuous Nearest Neighbor Search
03/03	Lecture 14 : Spatial Queries on non-Euclidean Space: Road Networks I	Query Processing in Spatial Network Databases
03/08	Lecture 15 : Spatial Queries on non-Euclidean Space: Road Networks II	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases Indexing Network Voronoi Diagrams
03/10	Midterm Exam 1
03/22	Lecture 16 : Spatial Queries on non-Euclidean Space: Road Networks III	Scalable Network Distance Browsing in Spatial Databases
03/24	Lecture 17 : Spatial Queries on non-Euclidean Space: Time-dependent Road Network	Online Computation of Fastest Path in Time-Dependent Spatial Networks Efficient K-Nearest Neighbor Search in Time-Dependent Spatial Networks
03/29	Lecture 18 : Trajectory-based Routing / Reachability Analysis	Time-Dependent Reachability Analysis; A Data-Driven Approach TrajRoute; Rethinking Routing with a Simple Trajectory-Based Approach
03/31	Lecture 19 : Spatial Crowdsourcing	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	HW2 Due. HW3 is released .
04/05	Lecture 20 : Spatio-Temporal Forecasting Tasks	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
04/07	Lecture 21 : Geo-Social	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
04/12	Lecture 22 : Location Privacy	Providing K-Anonymity in Location Based Services Geo-indistinguishability, A Principled Approach to Location Privacy A Neural Approach to Spatio-Temporal Data Release with User-Level Differential Privacy A Neural Database for Diferentially Private Spatial Range Queries
04/14	Lecture 23 : Geo Privacy	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
04/19	Lecture 24 : Trajectory Mining and Moving Behavior Analysis	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
04/21	Lecture 25 : Location Encoding	Multi-Scale Representation Learning for Spatial Feature Distributions Using Grid Cells Poly2Vec; Polymorphic Fourier-Based Encoding of Geospatial Objects for GeoAI Applications Geo2Vec; Shape- and Distance-Aware Neural Representation of Geospatial Entities
04/26	Lecture 26 : Next Location Prediction	TrajGPT; Controlled Synthetic Trajectory Generation Using a Multitask Transformer-Based Spatiotemporal Model ICAD; A Self-Supervised Autoregressive Approach for Multi-Context Anomaly Detection in Human Mobility Data POIFormer; A Transformer-Based Framework for Accurate and Scalable Point-of-Interest Attribution Toward Foundation Models for Mobility Enriched Geospatially Embedded Objects
04/28	Midterm Exam 2
05/10	Final Exam Day		HW3 Due.

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.

Interactive Study Tool

An open-source web app for CSCI 587, developed by Ketan Joshi, that lets you visualize and step through the spatial indexing algorithms and queries covered in this course — including Grid File, Z-Ordering, Hilbert Curves, Quadtrees, R-trees (point/range/kNN/RkNN), Skyline and Spatial Skyline queries, VoR-Tree, CNN, TPQ, and non-Euclidean (network) queries.

🔗 csci587-class-study-app.vercel.app

The tool is an early MVP — feedback and contributions are welcome. Reach out to Ketan at kajoshi@usc.edu.

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.