PhD Course - Similarity Search Seminar Spring 2018

Course Title
Similarity Search Seminar Spring 18

Organizer(s)
Rasmus Pagh, Tobias Christiani

Lecturer(s)
Participants will take turns preparing and presenting research papers. A list of suggested papers is
provided.

Date(s) of the course
9/2 - 27/4

Time
Friday 10:00-11:00.

Room
DIKU room 1-0-04

Course description
The course is organized as a seminar where participants read and present recent theoretical results
related to similarity search. Each week a participant will select a paper and prepare a 1-hour
presentation (sometimes longer). The rest of the participants are expected to prepare for the
presentation by reading the paper and thinking about questions and open problems.
The goal of the course is for participants to obtain a better understanding of recent developments in
the theory of similarity search, to practice presenting complex theoretical work using only 1 hour,
and to formulate open problems in the area of similarity search.

Programme (tentative)

Date	Presenter	Paper
9/2	Tobias	The distortion of locality-sensitive hashing
16/2	Rasmus	Fast Locality-Sensitive Hashing for Approximate Near Neighbor Search
23/2	-	Break
2/3	Ninh	Hashing-Based-Estimators for Kernel Density in High Dimensions
9/3	Sam	Graph-based time-space trade-offs for approximate near neighbors
16/3	Jakob	LSH Forest: Practical Algorithms Made Theoretical
23/3	Anders	Distributed PCP Theorems for Hardness of Approximation in P
30/3	-	Good Friday
6/4	-	ARCO workshop
13/4	Martin
20/4	Nina
25/4	Johan	Practical Data-Dependent Metric Compression with Provable Guarantees

Prerequisites
Undergraduate proficiency in linear algebra, calculus, probability theory, number theory, and discrete math.

Exam
Students must participate actively and present at least two papers in order to pass the course.
Students are also expected to suggest open problems when presenting a paper. Rasmus Pagh will
determine whether the quality of the presentation is sufficient to pass the course.

Credits
2.5 ECTS

Amount of hours the student is expected to use on the course
Lectures: 10 Hours.
Preparation: 55 Hours
Total: 65 Hours

Reading material/Suggested papers

Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner: Practical Data-Dependent Metric Compression with Provable Guarantees. NIPS 2017: 2614-2623
Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki:
LSH Forest: Practical Algorithms Made Theoretical. SODA 2017: 67-78
Thijs Laarhoven: Graph-based time-space trade-offs for approximate near neighbors. CoRR abs/1712.03158 (2017)
Daniel Dadush, Cristóbal Guzmán, Neil Olver: Fast, Deterministic and Sparse Dimensionality Reduction. SODA 2018: 1330-1344
Ryan Williams: On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry. SODA 2018.
Amir Abboud, Aviad Rubinstein, Ryan Williams: Distributed PCP Theorems for Hardness of Approximation in P. STOC 2017.
Aviad Rubinstein: Hardness of Approximate Nearest Neighbor Search. STOC 2018.
Stefan Bamberger, Felix Krahmer: Optimal Fast Johnson-Lindenstrauss Embeddings for Large Data Sets. CoRR abs/1712.01774 (2017)
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount: Near-Optimal ε-Kernel Construction and Related Problems. SoCG 2017.
Timothy M. Chan: Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry. SoCG 2017.
Moses Charikar, Paris Siminelakis: Hashing-Based-Estimators for Kernel Density in High Dimensions. FOCS 2017.
Tobias Christiani: Fast Locality-Sensitive Hashing for Approximate Near Neighbor Search. CoRR abs/1708.07586 (2017).
Thomas D. Ahle: Optimal Las Vegas Locality Sensitive Data Structures. FOCS 2017.
Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, Erisa Terolli:
The Distortion of Locality Sensitive Hashing. ITCS 2017: 54:1-54:18
Paul Beame, Raphaël Clifford, and Widad Machmouchi. Element distinctness, frequency moments, and sliding windows. FOCS 2013