News

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.

Instructor

Prof. Cyrus Shahabi
Office: PHE 306
Office hours: Mon, Wed 3:30pm-4:30pm
Address: 3737 Watt Way, Los Angeles, CA 90089
Email: Instructor Email

TA

Yaguang Li
Office: RTH 323
Office hours: Tue, Thu 10:30am-11:30am
Address: 3710 S. McClintock Ave, Los Angeles, CA 90089
Email: TA Email

Location and Time

Class Location:  SOS B44
Class Time: Mon, Wed 4:30pm-6:20pm

Grading

Midterm 1
30%
Midterm 2
30%
Class Project
30%
Participation
10%
30% Midterm 1
30% Midterm 2
30% Class Project
10% Participation

Lectures

Projects

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.

Project Descriptions

  • PalHunter (group of 2 - 3)

    In the project, you are required to design and implement an application that can record your own moving trajectories and share it with your friends. There are two ways that you can use to exchange the data with another mobile phone, one is to talk to another mobile phone through the server; the other is to communication with another phone directly using P2P communication. You should be able to view your own trajectory on a map, as well as view another person's trajectory on the map (using different color or line to symbolize different users) from the phone. You should also receive alert information when your friend is close to you (define your own metrics of closeness). Along your moving trajectory, you can take images using the phone camera or record videos using the phone camcord and upload them to the server. All the data sent to the server should be Geo-Tagged. You are also required to implement a web service which listens to incoming data uploads and displays them on a Map. In this project, we leave privacy issue behind, meaning that you do not need to consider access control or management issue.

  • iCampusProfiler (group of 2-3)

    Consider your cell phones as moving sensors, implement an app to collect information on/around campus. The client will share geo-tagged and timestamped messages with the server. The server shows all messages on campus maps with location markers.

  • GeoFence (group of 2-3)

    GeoFences are critical areas defined by either a mobile user or by a security officer. GenFence information is stored in the database on Server. Mobile clients received GeoFence alerts once their location are relevant to some GeoFences.

  • TransDec

  • MediaQ

Previous Demos

iCampusFood

QExplorer

AroundMe

GeoCrowdSensing

CollabParking

PalHunter

GeoFence

Reading Material

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 Leyla Kazemi and Cyrus Shahabi GeoCrowd: Enabling Query Answering with Spatial Crowdsourcing, ACM SIGSPATIAL GIS 2012.
25 Leyla Kazemi, Cyrus Shahabi, and Lei Chen GeoTruCrowd: Trustworthy Query Answering with Spatial Crowdsourcing, ACM SIGSPATIAL GIS 2013.
26 Hien To, Gabriel Ghinita, and Cyrus Shahabi A Framework for Protecting Worker Location Privacy in Spatial Crowdsourcing, VLDB 2014.
27 Huy Pham, Ling Hu, and Cyrus Shahabi GEOSO - A Geo-Social Model: From Real-World Co-occurrences to Social Connections, DNIS 2011.
28 Huy Pham, Cyrus Shahabi, and Yan Liu EBM - An Entropy-Based Model to Infer Social Strength from Spatiotemporal Data, SIGMOD 2013: 265-276
29 Mohamed F. Mokbel, Chi-Yin Chow, Walid G. Aref: The New Casper: Query Processing for Location Services without Compromising Privacy. VLDB 2006: 763-774.
30 Ali Khoshgozaran, Cyrus Shahabi: Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy. SSTD 2007:239-257.
31 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.
32 Li, F.; Hadjieleftheriou, M.; Kollios, G. & Reyzin, L. Dynamic authenticated index structures for outsourced databases . SIGMOD Conference, 2006, 121-132.
33 Yang, Y.; Papadopoulos, S.; Papadias, D. & Kollios, G. Spatial Outsourcing for Location-based Services. ICDE, 2008, 1082-1091.
34 Songhua Xing and Cyrus Shahabi, Scalable Shortest Paths Browsing on Land Surface, ACM GIS, San Jose, CA, November 2010.
35 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).
36 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).
37 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)
38 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.
39 Ling Hu, Wei-Shinn Ku, Spiridon Bakiras, and Cyrus Shahabi,Verifying Spatial Queries using Voronoi Neighbors, ACM SIGSPATIAL, San Jose, California, November 2010.
40 Ugur Demiryurek, Farnoush Banaei-Kashani, Cyrus Shahabi , and Anand Ranganathan,Online Computation of Fastest Path in Time-Dependent Spatial Networks, 12th International Symposium on Spatial and Temporal Databases (SSTD11), Minneapolis, MN, USA, August 2011.
41 Ali Khoshgozaran and Cyrus Shahabi,Towards Private Navigation of Tree Structured Spatial Indexes, The Third International Conference on Emerging Databases (EDB 2011), Incheon, Korea, August 2011.
42 Ugur Demiryurek and Cyrus Shahabi, Indexing Network Voronoi Diagrams, The 17th International Conference on Database Systems for Advanced Applications , Busan, South Korea , April 2012.
43 Songhua Xing, Cyrus Shahabi and Bei Pan, Continuous Monitoring of Nearest Neighbors on Land Surface, VLDB 2009.
44 Jinbao Wang, Sai Wu, Hong Gao, Jianzhong Li and Beng Chin Ooi, Indexing multi-dimensional data in a cloud system, ACM SIGMOD 2010.
45 Afsin Akdogan, Ugur Demiryurek, Farnoush Banaei-Kashani , and Cyrus Shahabi, Voronoi-based Geospatial Query Processing with MapReduce, IEEE CloudCom 2010.
46 Afsin Akdogan, Cyrus Shahabi, and Ugur Demiryurek, ToSS-it: A Cloud-based Throwaway Spatial Index Structure for Dynamic Location Data, IEEE MDM 2014.
47 Dingxiong Deng, Cyrus Shahabi, and Ugur Demiryurek, Maximizing the Number of Worker's Self-Selected Tasks in Spatial Crowdsourcing, ACM SIGSPATIAL GIS 2013.
48 Dingxiong Deng, Cyrus Shahabi, and Linhong Zhu, Task Matching and Scheduling for Multiple Workers in Spatial Crowdsourcing, ACM SIGSPATIAL GIS 2015.
49 Nikos Armenatzoglou, Stavros Papadopoulos, Dimitris Papadias, A General Framework for Geo-Social Query Processing, PVLDB 2013: 913-924.
50 Nikos Armenatzoglou, Huy Pham, Vasilis Ntranos, Dimitris Papadias, Cyrus Shahabi, Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach, SIGMOD 2015: 1617-1628.
51 Cyrus Shahabi, Liyue Fan, Luciano Nocera, Li Xiong, Ming Li, Privacy-Preserving Inference of Social Relationships from Location Data: A Vision Paper, ACM SIGSPATIAL GIS 2015.
52 Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, Carola Wenk, On Map-Matching Vehicle Tracking Data, VLDB 2005.
53 Paul Newson, John Krumm, Hidden Markov Map Matching Through Noise and Sparseness, ACM SIGSPATIAL GIS 2009.
54 Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, Yan Huang, Map-Matching for Low-Sampling-Rate GPS Trajectories, ACM SIGSPATIAL GIS 2009.

Resources

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, which appears on pp. 73-78 of the 1999-2000 SCampus.

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.

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. Scampus, the Student Guidebook, contains the Student Conduct Code in Section 11.00, while the recommended sanctions are located in Appendix A: http://www.usc.edu/dept/publications/SCAMPUS/gov/. 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: http://www.usc.edu/student-affairs/SJACS/.

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.