Assignment 2

Students will be divided into 9 groups, each of which will do a 12-minute presentation on a paper. All the presentations will take place in the last lecture (on 29 May). Each group should include 4-5 students.

The papers for presentation should be selected from the list of 10 papers below.

The paper assignment will be done in a first-come-first-served manner. A group hoping to secure a paper should email the instructor (i) the title of the paper, and (ii) the names of all group members. Once a paper is assigned, the instructor will announce the presenters on this page, after which no changes can be made. You are encouraged to send in a preference list of papers, and you will be given the first paper that is still available.

Spatial Databases

Hilbert Space Filling Curve

Ibrahim Kamel, Christos Faloutsos.
Hilbert R-tree: An Improved R-tree Using Fractals.
VLDB 1994: 500-509.

Presenters: Claire houvenagel, Nickol sickelmore, Manal Alghamdi, Balqees Mohammed.

Main Points to Present:
1. Hilbert curve.
2. Structure of the Hilvert R-tree, and its algorithm for range queries.
Spatial Join

Jignesh M. Patel, David J. DeWitt.
Partition Based Spatial-Merge Join.
SIGMOD Conference 1996: 259-270.

Presenters: Zun Tian Tan, Jason Pham, Yanuar Wicaksana, Yue Han Loke.

Main Points to Present:
1. The algorithm in Sec 3 (except Sec 3.2).
Reverse Nearest Neighbor Search

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

Presenters: Li Meng, Yang Shidi, Li Jiepeng, Liu Yi, Heming Yuan.

Main Points to Present:
1. What is monochromatic and bichromatic reverse nearest neighbor?
2. The static algorithms (Sec 3.1 and 4.1).
Aggregate Nearest Neighbor Search

Feifei Li, Bin Yao, Piyush Kumar.
Group Enclosing Queries.
IEEE Trans. Knowl. Data Eng. 23(10): 1526-1540 (2011).

Presenters: Ken Yoong Lim, Dongnan Nie, Yangyang Xu, Yukai Qiao, James Daniel Cullen

Main Points to Present:
1. What is a group enclosing query, and what is its approximate version?
2. The square-root-2 approximate algorithm in Sec 5.1.
Indexing Moving Objects

Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez
Indexing the Positions of Continuously Moving Objects.
SIGMOD Conference 2000: 331-342.

Presenters: Klaudia Laila Swiecka, Saad Jaouni, Alexander Zhou, Thomas Zhou.

Main Points to Present:
1. How are range queries defined on moving objects? (Sec 2)
2. Structure of the TPR-tree (Sec 3.1) and its query algorithm (Sec 3.2).

High Dimensional Data

VA File

Roger Weber, Hans-Jorg Schek, Stephen Blott.
A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces.
VLDB 1998: 194-205.

Presenters: Yifan Wang, Han Gao, Shangjie Du, Fang Wan, Nesith Weerasinghe.

Main Points to Present:
1. What is the motivation of the VA file?
2. How to build a VA file and how to use it to answer NN queries. (Sec 4)
The Pyramid Technique

Stefan Berchtold, Christian Bohm, Hans-Peter Kriegel.
The Pyramid-Technique: Towards Breaking the Curse of Dimensionality.
SIGMOD Conference 1998: 142-153.

Presenters: Samuel Teed, Ashleigh Armstrong, Anastasios Karydas, Lewis Smith.

Main Points to Present:
1. How to build a Pyramid index? (Sec 4)
2. How to use it to answer a range query? (Sec 5)
K-Dominant Skylines

Chee Yong Chan, H. V. Jagadish, Kian-Lee Tan, Anthony K. H. Tung, Zhenjie Zhang.
Finding k-dominant skylines in high dimensional space.
SIGMOD Conference 2006: 503-514.

Presenters: [None]

Main Points to Present:
1. What is k-dominant skyline and why do we need it?
2. The one-scan algorithm in Sec 4.1.

Data Mining

Density-Based Clustering

Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu.
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.
KDD 1996: 226-231.

Presenters: Chuan Leong Foo, Roshan Bagla, Leopoid Fournier, Saisrikar Paruchuri, Jiayu Gao.

Main Points to Present:
1. How are clusters defined under DBSCAN?
2. How to compute these clusters?
Distance-Based Outliers

Edwin M. Knorr, Raymond T. Ng.
Algorithms for Mining Distance-Based Outliers in Large Datasets..
VLDB 1998: 392-403.

Presenters: [None]

Main Points to Present:
1. How are distance-based outliers defined?
2. The cell-based algorithm in Sec 4.

Grading Scheme

Each presentation will be graded by two referees: the instructor and the tutor. The items of assessment include:

Contents: 60%.
- We will evaluate (i) whether you have covered all the main points of the paper you selected (the main points can be found in the paper list above), and (ii) how well those points are explained.
Slides: 30%.
- We will evaluate (i) whether your slides are professionally written, (ii) whether they are concise (verbose slides are discouraged), and (iii) how well they assist your presentation in explaining the contents of the paper.
Time management: 10%.
- We will evaluate whether the time you spend on each sub-topic of your presentation is reasonable. In general, the amount of time a sub-topic receives should be closely relevant to its difficulty.

FAQs

This section may grow as more questions are asked and answered.

Q: Who should speak in the presentation?
A: It does not matter. The group members may take turns to speak, or one member takes care of the whole talk. Both are ok.
Q: Will all the members receive the same score?
A: Yes. Every member has her/his strengths: some are good at deciphering math, others good at presenting, etc. Your score is the result of team work.
Q: Can I approach the instructor to discuss the paper?
A: Yes. You are very welcome to do so.
Q: What if I have trouble forming a group of size 4-5?
A: Email the instructor, and he will help.

Presentation Order

Same as shown in the list of topics.