[USC logo]

CSCI 599 (Fall 2007)
Information Management

Course Summary Reading List Schedules Presentations
Projects Project Reports Related Web Sites Academic Integrity Policy


Prof. Cyrus Shahabi

University of Southern California
Computer Science Department
SAL 300
Los Angeles, CA 90089-0781
Office (PHE-410): (213) 740-8162
Lab (RTH-323): (213) 821-1462
Office Hours:  MW 11-12, PHE -410

  For projects and talks
email Jeff Khoshgozaran

Course Summary


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 the last couple of years that the power of digital geospatial information has been brought to mass population through online map services such as Yahoo-map and most recently 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. This market is projected to have annual revenues of $30 billion by 2005, consisting of $20 billion in the remote sensing market and $10 billion in the GIS market.

 The focus of this seminar course is on studying an important class of geospatial queries, called Nearest Neighbor queries.  Under this running research theme, the students become familiar with a variety of real-world geospatial applications (e.g., location-based services, online maps) and datasets (e.g., road-network data, aerial imagery, 3D models).

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 Google Earth and Microsoft Virtual Earth as well as our own GeoDec (http://infolab.usc.edu/projects/geodec/) platform.  


International and Multidisciplinary Collaboration:

 For some of the course projects (about 3), there are plans in place to collaborate with the students and faculty of an architecture course at National University of Singapore (NUS).  For each of these common projects, one team from one course gets connected with a team from the other course, generating a team of 6-8 students working on one collaborative project.  The team form USC would provide the technology expertise while the team from NUS provides the application-domain expertise.  We will focus on architecture and urban planning applications for the city of Singapore.  In particular, the NUS team would generate and provide geospatial datasets from the city of Singapore (e.g., satellite images, 3D building models, photographs, textures) and identify a set of interesting spatiotemporal queries from the domain of architecture and/or urban planning to utilize the developed software system and datasets for a real-world application. The USC team would store and index the provided datasets in appropriate formats in the InfoLab databases and then using one of the available software platforms: Google Earth, Microsoft Virtual Earth, or InfoLab’s proprietary GeoDec, builds a software application to access, visualize, navigate and query the formatted datasets in an integrated fashion for the focused application domain.


Class Format and Evaluation Method:

 In general, a class will consist of 2 paper presentations, each lasting 45-60 minutes followed by discussions, and a 30-minute implementation project update. Each paper will be presented by one student. The student is expected to go beyond the paper to seek online resources and examples that illustrate the principles and algorithms introduced in the paper. Every student is expected to complete the assigned reading, be prepared to discuss the articles in class, and to write a short critical summary of the presentations. The implementation of selected algorithms will be done in assigned teams of no more than four. Evaluation is based on: the team project (50%), the individual paper presentation(s) (30%) and the written paper summaries (20%).

Time and Location:
Wednesdays 3:30-6pm, GFS 223
CSCI-585 and Instructor Permission




Project Lead Team Members Project Description
Location Privacy and PIR Jeff Khoshgozaran Hootan & Medha
Geodec Songhua Xing Lu An, Ruchika, Rushit, Mridul
Moving Object Databases Ugur Demiryurek Ramin, Erdem, Rahul
Trajectory Coverage Project Leyla Kazemi Ankit, Larry
Hurricane Watch System Kai Song Ji Ma, Ramya, Aswani




Papers presented




Course introduction, Paper assignment, Project groups

Leyla Kazemi




Songhua Xing



Presentation of project proposals



b-1, b-2

Jeff Khoshgozaran (b1),Medha Shewale (b2)



b-3, b-4

Ji MA (b3), Leon Tang (b4)



c-1, c-4

Ramin Moazeni (c1), Erdem Ergin (c4)



c-3, c-2

Kai Song (c3), Ugur Demiryurek (c2)



c-5, d-1

Ramya Venkateswaran (c5), Ruchika Rawat (d1)



d-2, d-3

Rushit Patel (d2), Larry Hignight (d3)



d-4, d-5

Venkata Aswani Nerella (d4), Parisa Ghaemi (d5)



e-1, e-2

Houtan Shirani-Mehr (e1), Mridul Somani (e2)



f-1, f-2

Ankit Rana (f1), Rahul Jaitly (f2)



No Class


11/28/07 Project presentation


Project presentation

Reference Book:

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

Reading List

 a) Conventional Nearest Neighbor (NN) queries

1) ROUSSOPOULOS, N., KELLY, S., AND VINCENT, F. 1995. Nearest neighbor queries. In Proceedings of the ACM Conference on the Management of Data (SIGMOD; San Jose, CA, May 22–25). 71–79.


b) Reverse NN

1) Flip Korn, S. Muthukrishnan: Influence Sets Based on Reverse Nearest Neighbor Queries. SIGMOD Conference 2000: 201-212


2) Ioana Stanoi, Divyakant Agrawal, Amr El Abbadi: Reverse Nearest Neighbor Queries for Dynamic Databases. ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery 2000: 44-53


3) Yufei Tao, Dimitris Papadias, Xiang Lian: Reverse kNN Search in Arbitrary Dimensionality. VLDB 2004: 744-755


4) Dimitris Papadias, Yufei Tao, Kyriakos Mouratidis, Chun Kit Hui: Aggregate nearest neighbor queries in spatial databases. ACM Trans. Database Syst. 30(2): 529-576 (2005)


c) Time-aware NN

1) Baihua Zheng, Dik Lun Lee: Semantic Caching in Location-Dependent Query Processing. SSTD 2001: 97-116


2) Zhexuan Song, Nick Roussopoulos: K-Nearest Neighbor Search for Moving Query Point. SSTD 2001: 79-96


3) Yufei Tao, Dimitris Papadias: Time-parameterized queries in spatio-temporal databases. SIGMOD Conference 2002: 334-345


4) Jun Zhang, Manli Zhu, Dimitris Papadias, Yufei Tao, Dik Lun Lee: Location-based Spatial Queries. SIGMOD Conference 2003: 443-454


5) Yufei Tao, Dimitris Papadias, Qiongmao Shen: Continuous Nearest Neighbor Search. VLDB 2002: 287-298


d) NN queries in Road Networks

1) Dimitris Papadias, Jun Zhang, Nikos Mamoulis, Yufei Tao: Query Processing in Spatial Network Databases. VLDB 2003: 802-813


2) Cyrus Shahabi, Mohammad R. Kolahdouzan, Mehdi Sharifzadeh: A road network embedding technique for k-nearest neighbor search in moving object databases. ACM-GIS 2002: 94-10


3) Mohammad R. Kolahdouzan, Cyrus Shahabi: Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases. VLDB 2004: 840-851


4) Haibo Hu, Dik Lun Lee, Jianliang Xu: Fast Nearest Neighbor Search on Road Networks. EDBT 2006: 186-203


5) Evangelos Kanoulas, Yang Du, Tian Xia, Donghui Zhang: Finding Fastest Paths on A Road Network with Speed Patterns. ICDE 2006: 10


e) Skyline queries

1) Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001


2) Dimitris Papadias, Yufei Tao, Greg Fu, Bernhard Seeger: An Optimal and Progressive Algorithm for Skyline Queries. SIGMOD Conference 2003: 467-478


f) New variations of NN

1) Mehdi Sharifzadeh, Cyrus Shahabi: The Spatial Skyline Queries. VLDB 2006: 751-762


2) Ke Deng, Xiaofang Zhou, Heng Tao Shen, Kai Xu, Xuemin Lin: Surface k-NN Query Processing. ICDE 2006: 78


Related Web Sites

Academic Integrity Policy

Academic Integrity

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.