Course Description
Reference Book
Reading List
Academic Integrity Policy


Course Description

Geospatial information, in the form of traditional maps, has been used for several centuries for decision making tasks.  The oldest map is known to be from 2500 B.C. of a city near Babylon. In the past forty years, the field of Geospatial Information Systems (GIS), with ESRI leading the industry, has been increasing the role of geospatial information in decision making tasks by allowing their digital manipulation. However, it was not until early 2000’s that the power of digital geospatial information has been brought to mass population through online map services such as Yahoo-map and later Google-Earth and Microsoft Virtual Earth. Nowadays, you cannot see a news story without a screen-shot of Google Earth. According to US Department of Labor, the market for geospatial technologies in 2002 was estimated at $5 billion.

The focus of this course is on studying techniques to efficiently store, manipulate, index and query geospatial information in support of real-world geographical and decision-making applications.  In this course, the students become familiar with a variety of geospatial applications (e.g., location-based services, online maps) and datasets (e.g., road-network data, aerial imagery, 3D models). Topics include: Object-Relational and Spatial Databases (e.g., Oracle 11g), Spatial Index Structures (e.g., Quadtrees, K-d Trees, One-dimensional Orderings, PK-Trees, R-Trees and Voronoi-based indexes), Spatial Queries (kNN, Reverse-NN, Skyline, Spatial Skyline), Non-Euclidean Spaces (e.g., road-networks, land surfaces), Spatial Data Outsourcing, Spatial Data Privacy, and Geospatial Applications.  Meanwhile, as part of the course projects, the students will learn to use the state-of-the-art geospatial software tools, applications and libraries such as those provided by Oracle, Google and Microsoft.  

The course assumes that student are familiar with conceptual data modeling tools such as Entity-Relationship (ER) data model, logical data models such as the relational and object-relational data model, SQL3 as a commercial query language, normal forms and logical data design, physical design of a database using persistent data structures such as B+-tree and Hash indexes, transactions, concurrency control and crash recovery techniques.

The VEF U.S. Faculty Scholar program has sponsored this course to be offered simultaneously and remotely to Hanoi University of Science and Technology (HUST) at Vietnam in Fall 2011. The VEF U.S. Faculty Scholar program is a highly competitive program as each year only four faculty members are awarded a grant across the entire field of engineering and nation-wide. In 2011-12 academic year, even thought the priority was given to applicants, whose field of study focuses on climate change (environmental sciences) or on nuclear energy (as these fields are of great interest to Vietnam and to U.S. bilateral interests), this course in the area of Information Technology, received one of the four grants. For more information on the program, please click....




Prof. Cyrus Shahabi

Office hours: Mon. Wed. 4pm-5pm @ PHE 306A

Time & Location

Mon&Wed 5pm-6:20pm @ OHE120


Office hours (office PHE316): Wed 11:30am-1:30pm

Lectures@USC (see lecture schedule at HUST)

1 1 8/22/2011 no class due to instructor's trip to coordinate with the course in Vietnam  
1 2 8/24/2011 course project introduction  
2 3 8/29/2011 Intro to Geospatial DB, team up, and phone handout 1-6
2 4 8/31/2011 Spatial indexes 7, 32
3 5 9/5/2011 Labor Day, no class  
3 6 9/7/2011 Spatial indexes: R-Trees 8, 9, 33
4 7 9/12/2011 Nearest neighbor queires 11[NNQueries,SIGMOD95]
4 8 9/14/2011 Reverse kNN and skyline queries 14[RkNN,VLDB04]
5 9 9/19/2011 Reverse kNN and skyline queries 15[OptSkyline,SIGMOD03]
5 10 9/21/2011 Spatial Queries: Continuous NN 21[TP-Spatial-Temporal-DB,SIGMOD02]
6 11 9/26/2011 Spatial Queries: Continuous NN 12[CNN,VLDB02]
6 12 9/28/2011 Spatial Queries: Continuous NN 13[CPCNN,SIGMOD05]
7 13 10/3/2011 Spatial skyline and VoR-tree 16[SpatialSkyline,VLDB06], 34[SSQ, TODS09]
7 14 10/5/2011 Spatial skyline and VoR-tree 10[Vor-Tree,VLDB10]
8 15 10/10/2011 exam review  
8 16 10/12/2011 Exam 1  
9 17 10/17/2011 Spatial Queries on non-euclidean space: road network 18[Query-In-Spatial-Network,VLDB03]
9 18 10/19/2011 Spatial Queries on non-euclidean space: road networks 19[VoronoikNN-Spatial-Netowrk,VLDB04]
10 19 10/24/2011 Spatial Queries on non-euclidean space: road networks 20[Distance-browsing,SIGMOD08]
10 20 10/26/2011 Spatial Queries on non-euclidean space: road networks 22[CkNN-RoadNetworks,VLDB06] 
11 21 10/31/2011 Time dependent spatial Queries on road networks   35[TkNN, DEXA10]
11 22 11/2/2011 Spatial Queries on non-euclidean space: land surface  24[kNN-Land-Surface,VLDB08]
12 23 11/7/2011 Spatial Queries on non-euclidean space: land surface  25[CkNN-Land-Surface,VLDB09], 31[SP-Land-Surface,ACMGIS10]
12 24 11/9/2011 Location Privacy 26[NewCasper,VLDB06]
13 25 11/14/2011 Location Privacy 27[Blind-Evaluation,SSTD07],
13 26 11/16/2011 Query Integrity 35[VN-Auth,ACMGIS10]
14 27 11/21/2011 Exam review  
14 28 11/23/2011 Thanksgiving Holiday, no class  
15 29 11/28/2011 Project Presentation by USC teams (extend to 2 hours)  
15 30 11/30/2011 Exam 2  




Class projects are designed for students to learn how to use the state-of-the-art GeoSpatial software/tools/APIs in developing real-world geographical applications. Most of the projects require programming on Google Android Phone together with Oracle, Google Map, or other tools of the same kind. Sample applications are defined in the areas of location-based services, geographical information management, social networking, real-time traffic, online map services, urban mobile sensing, smart city/campus, etc. Six or seven projects will be defined and two students should form a team and pick one project. Students can form their own team to accomplish one project chosen on your own from the project list. You may also define your own project and team. But you need to convince the professor or the TA that your project is related to the course and the workload is reasonable.

ATTENTION: Here are only the sample projects. Please refer to project-slides for up-to-date information on projects.


  • Midterm 1: 30%
  • Midterm 2: 30%
  • Class project: 30%
  • Class participation: 10%
  • Late penalty: Please observe the deadline for submission dues. If late, you will have 25% of the total points possible penalty per day. Therefore, no late submission will be accepted after 4 days past deadline.

    Reference Book

    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.

    Reading List

    Paper ID Papers
    1 Jim Gray. "Evolution of Data Management." Computer v29 n10 (October 1996):38-46.
    2 Michael Stonebraker. "Object-Relational DBMS-The Next Wave." Informix white paper.
    3 Thomas Connolly, Carolyn Begg, and Anne Strachan. "Ch 17: Object Databases." Database Systems.
    4 Ralf Hartmut Guting. "An Introduction to Spatial Database Systems." VLDB Journal 3(4): 357-399, 1994.
    5 Oracle Documentations. "Application Developer's Guide - Object-Relational Features".
    6 Chapter-1 of: Hanan Samet, “Foundations of Multidimensional and Metric Data Structures”, Morgan Kaufmann
    7 Hanan Samet. "Spatial Data Structures." Appears in Modern Database Systems: The Object Model, Interoperability, and Beyond, W.Kim, ed., Addison Wesley/ACM Press, Reading, MA, 1995, 361-385.
    8 Antomn Guttman. "R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING." Proceedings of ACM SIGMOD, pp.47-57, 1984.
    9 Timos Sellis, Nick Roussopoulos and Chrishtos Faloutsos. "THE R+-TREE: A DYNAMIC INDEX FOR MULTI-DIMENSIONAL OBJECTS." Proceedings of the 13th VLDB Conference, Brighton 1987.
    10 M. Sharifzadeh and C. Shahabi, " VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries", VLDB 2010
    11 N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In SIGMOD, pages 71-79, 1995.
    12 Tao, Y.; Papadias, D. & Shen, Q. Continuous Nearest Neighbor Search. VLDB, 2002, 287-298.
    13 Mouratidis, K.; Hadjieleftheriou, M. & Papadias, D. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring . SIGMOD Conference, 2005, 634-645.
    14 Tao, Y.; Papadias, D. & Lian, X. Reverse kNN Search in Arbitrary Dimensionality . VLDB, 2004, 744-755.
    15 Papadias, D.; Tao, Y.; Fu, G. & Seeger, B. An Optimal and Progressive Algorithm for Skyline Queries . SIGMOD Conference, 2003, 467-478.
    16 Mehdi Sharifzadeh and Cyrus Shahabi, The Spatial Skyline Queries, VLDB 2006, Seoul, Korea, September 2006.
    17 Zhang, D.; Du, Y.; Xia, T. & Tao, Y. Progressive Computation of the Min-Dist Optimal-Location Query . VLDB, 2006, 643-654.
    18 Dimitris Papadias, Jun Zhang, Nikos Mamoulis, Yufei Tao: Query Processing in Spatial Network Databases. VLDB 2003:802-813
    19 Kolahdouzan, M. R. & Shahabi, C. Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases . VLDB, 2004, 840-851            .
    20 Hanan Samet, Jagan Sankaranarayanan, Houman Alborzi: Scalable network distance browsing in spatial databases. SIGMOD Conference 2008: 43-54
    21 Tao, Y. & Papadias, D. Time-parameterized queries in spatio-temporal databases . SIGMOD Conference, 2002, 334-345.
    22 Mouratidis, K.; Yiu, M. L.; Papadias, D. & Mamoulis, N. Continuous Nearest Neighbor Monitoring in Road Networks . VLDB, 2006, 43-54.
    23 Ke Deng, Xiaofang Zhou, Heng Tao Shen, Kai Xu, Xuemin Lin: Surface k-NN Query Processing. ICDE 2006:78
    24 Shahabi, C.; Tang, L.-A. & Xing, S. Indexing land surface for efficient kNN query. PVLDB, 2008, 1, 1020-1031.
    25 Songhua Xing, Cyrus Shahabi, Bei Pan, Continuous Monitoring of Nearest Neighbors on Land Surface, VLDB 2009.
    26 Mohamed F. Mokbel, Chi-Yin Chow, Walid G. Aref: The New Casper: Query Processing for Location Services without Compromising Privacy.. VLDB 2006: 763-774.
    27 Ali Khoshgozaran, Cyrus Shahabi: Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy. SSTD 2007:239-257.
    28 Ghinita, G.; Kalnis, P.; Khoshgozaran, A.; Shahabi, C. & Tan, K.-L. Private queries in location based services: anonymizers are not necessary. SIGMOD Conference, 2008, 121-132.
    29 Li, F.; Hadjieleftheriou, M.; Kollios, G. & Reyzin, L. Dynamic authenticated index structures for outsourced databases . SIGMOD Conference, 2006, 121-132.
    30 Yang, Y.; Papadopoulos, S.; Papadias, D. & Kollios, G. Spatial Outsourcing for Location-based Services. ICDE, 2008, 1082-1091.
    31 Songhua Xing and Cyrus Shahabi, Scalable Shortest Paths Browsing on Land Surface, ACM GIS, San Jose, CA, November 2010.
    32 Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71 (1984).
    33 Norbert Beckmann and Hans-Peter Kriegel and Ralf Schneider and Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference (1990).
    34 Mehdi Sharifzadeh, Cyrus Shahabi, Leyla Kazemi: Processing spatial skyline queries in both vector spaces and spatial network databases. ACM Trans. Database Syst. 34(3): (2009)
    35 Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi, Efficient K-Nearest Neighbor Search in Time-Dependent Spatial Networks, 21st International Conference on Database and Expert Systems Applications (DEXA10), Bilbao, Spain, August 2010.
    36 Ling Hu, Wei-Shinn Ku, Spiridon Bakiras, and Cyrus Shahabi,Verifying Spatial Queries using Voronoi Neighbors, ACM SIGSPATIAL, San Jose, California , November 2010.