- Website is up... 06/30/2011
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....
InstructorProf. Cyrus Shahabi
Office hours: Mon. Wed. 4pm-5pm @ PHE 306A
Time & Location
Mon&Wed 5pm-6:20pm @ OHE120
TAOffice 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]|
|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]|
|14||28||11/23/2011||Thanksgiving Holiday, no class|
|15||29||11/28/2011||Project Presentation by USC teams (extend to 2 hours)|
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.
(group of 2)
Rating, commenting, and taking pictures of food and restaurants on/around campus using their Droid phones. All the data are geotagged. Next, the user can upload data to GeoDB database. Students need to design the schema for their data stored in the database. Design and implement a webservice to query the database and generate an output XML file (the format of the XML is pre-defined). The webservice can take parameters (start and end time, space such as a bounding box, etc) to generate desired datasets. GymInfo(group of 2)
Users can use their Droid phones to input data about gym and track field, e.g., the crowdedness (from 1 to 5), the available treadmills, # of available racketball rooms, etc. The students should define the indicators for each sport facility. They can define indicator for the overall condition of the facility and they can define objects like treadmill and racketball room and rate the availableness of each type of objects. e.g., there are 2 racketball rooms available at 5pm. The data are geotagged automatically using the locations acquired by the built-in GPS. Next, users upload the data to the GeoDB database. Design and implement a webservice to query the database and generate an output XML file (the format of the XML is pre-defined). The webservice can take parameters (start and end time, etc) to generate desired datasets. iCollaborate (group of 2)
Consider a class of students who are geo-located at different places. They need to gather together once in a while to have some group discussion. Each student runs your application to share their location while deciding a place to meet (to minimize the total travel time/distance, etc.). The application can geo-spatially checkin the student if he/she arrives the meeting location, and checkout the student when he/she leaves. The checkin/checkout information (times tamped) is uploaded to the server for the record. The checkin and checkout information are stored in the database (Oracle) on a server. Consider a supervisor can login the system and check the status of each meeting (who were there, who were absent, etc).DroidProfiler (group of 2) GeoTimer(group of 2)
In this project, you are required to implement a mobile application which can record where you spend your time in your everyday life. The project, a.k.a. GeoTimer, is a Map based application, meaning you should show everything on a map basis. The GUI design is open to any imagination. However, you may take the following description as a starting example. You should show a map of your surrounding area when you first start the application and the map can zoom in to your current location (either obtained by GPS or by the network location). If there are already some timer defined before, show them as well. The user can tap the screen and define a timer for that location. For example, as a user, I can tap on the Leavey library and create a timer for recording how many hours I spent in the library. If a timer is a placemarker, the application only starts to roll the timer when the userís current location is on the placemarker and the timer should stop when the user leaves that location. The process should be automatically triggered by the location update event, not the user. You can allow some error range in order to make the application function well. PalHunter(group of 2)
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 donít need to consider access control or management issue. GeoAlert(group of 2)
You are required to implement a mobile application that can provide automatic information alert with GeoSpatial context awareness. For example, as a mobile user walking along a certain path, the application retrieves all the events that are happening *near* the userís current location and alert the user on the phone. Events are stored on a server, which will provide API to retrieve. Event Data stored on the server are all Geo-Tagged and time stamped.
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.
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.
|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.|
- Android installation guide
- Project slides
- Responsibility Form
- Project contract template
- Oracle DB tutorial by Ugur Demiryurek
- Midterm report template
- project contract sample
- Best final project report 2010
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/.