This seminar studies the structures that make data searchable — from classical relational indices, through high-dimensional vector indices, to the hybrid query engines behind modern AI-era data processing. Across these three settings we trace recurring design tensions: exact vs. approximate, static vs. learned/adaptive, and in-memory vs. disk/distributed.
Part I covers classical and relational indexing: B-trees, hashing, spatial indices, Bloom and Cuckoo filters, sketches, and learned indexes. Part II covers vector indexing: locality-sensitive hashing, product and optimized quantization, inverted-file variants, and graph-based indices. Part III covers hybrid and complicated query processing: filtered vector search, semantic query processing with LLM-based operators, and sparse-dense hybrid retrieval. Invited speakers from both academic and industry backgrounds will share their experience building and deploying indices in practice.
While there are no formal prerequisites, a background in undergraduate-level databases, algorithms, and probability is recommended. Coursework includes attending lectures, presenting and reviewing papers, and completing a research project that offers hands-on experience with indices in practical systems. Upon completion, students will understand the algorithmic foundations and systems trade-offs of indexing across relational, vector, and hybrid data processing.
Students will master the algorithmic foundations and systems trade-offs of relational, vector, and hybrid indices, and learn to critically read, present, and discuss state-of-the-art research. The course project offers hands-on opportunities to build, tune, or benchmark an index on real datasets and report reproducible recall–latency–memory results.
| Item | Details |
|---|---|
| Course | CS 848-001(8929) |
| Term | Fall 2026 |
| Instructor | Xiao Hu (xiaohu@uwaterloo.ca) |
| Lectures | Tue/Thu, 10:00–11:20 AM, DC 2568 |
| Office Hour | By Appointment |
| Submissions | LEARN (reviews, course presentation slides, project report, project presentation slides) |
Mark breakdown: Participation 10% + Reviews 10% + Presentation 30% + Project 50%.
Attendance at lectures is required. Missing more than one lecture without a valid reason renders you ineligible to pass the course.
The schedule is tentative and subject to change. Online delivery may be used in special situations. Supplementary reading materials will be posted on the course page.
| Week | Date | Topic | Presenter | Slides |
|---|---|---|---|---|
| 1 | Sep 10, 2026 | Course Overview | Xiao Hu | lecture-01 |
| 2 | Sep 15, 2026 | B-trees | Xiao Hu | lecture-02 |
| 2 | Sep 17, 2026 | Hashing | Xiao Hu | lecture-03 |
| 3 | Sep 22, 2026 | Spatial Indices: KD-tree, Quadtree, R-tree | Online; Stavros Sintos (UIC) | lecture-04 |
| 3 | Sep 24, 2026 | Sketches: Count-Min, AMS, HyperLogLog | Xiao Hu | lecture-06 |
| 4 | Sep 29, 2026 | Bloom & Cuckoo Filters Space/Time Trade-offs in Hash Coding with Allowable Errors Cuckoo Filter: Practically Better Than Bloom |
Student 1 | lecture-05 |
| 4 | Oct 1, 2026 | Learned Indexes The Case for Learned Index Structures (optional reading: ALEX) |
Student 2 | lecture-07 |
| 5 | Oct 6, 2026 | Index for Multi-way Join Query Processing: Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees |
Online; Qichen Wang (NTU) and Bingnan Chen (HKUST; Alibaba) | lecture-08 |
Related links:
Faiss: A Library for Efficient Similarity Search and Clustering of Dense Vectors
| Week | Date | Topic | Presenter | Slides |
|---|---|---|---|---|
| 5 | Oct 8, 2026 | Inverted index: text retrieval & vector retrieval Inverted Files for Text Search Engines Video Google: A Text Retrieval Approach to Object Matching in Videos |
Student 3 | lecture-09 |
| 6 | Oct 13 & 15, 2026 | Reading Week – No Class | ||
| 7 | Oct 20, 2026 | Locality-Sensitive Hashing (1) Similarity Search in High Dimensions via Hashing (optional reading: Approximate nearest neighbors) |
Student 4 | lecture-10 |
| 7 | Oct 22, 2026 | Locality-Sensitive Hashing (2) Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search (optional reading: Locality-Sensitive Hashing Scheme Based on p-Stable Distributions) |
Student 5 | lecture-11 |
| 8 | Oct 27, 2026 | Quantization (1) Product Quantization for NN Search (optional reading: Reconfigurable Inverted Index) |
Student 6 | lecture-12 |
| 8 | Oct 29, 2026 | Quantization (2) RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for ANN Search |
Student 7 | lecture-13 |
| 9 | Nov 3, 2026 | Graph-Based ANN (1) Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World Graphs |
Online; Yuxi Liu (Duke; Meta) | lecture-14 |
| 9 | Nov 5, 2026 | Graph-Based ANN (2) DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node |
Student 8 | lecture-15 |
| 10 | Nov 10, 2026 | Key-Value Store & LSM tree | Online; Zichen Zhu (Google) | lecture-16 |
Each student presents one paper. Sign up for a paper and a time slot, and submit your slides and accompanying notes by 11:59 PM EST two days before your presentation (Sunday for a Tuesday slot; Tuesday for a Thursday slot).
Each presentation runs one hour, followed by 20 minutes of open discussion. When describing an index or algorithm:
Reviews are submitted through LEARN. Each week features at most two related papers; read them in advance and submit your reviews. Reviews are due by 11:59 PM every Monday.
The project is required and submitted through LEARN. Each project has one or at most two students. Choose a research problem related to the course material and pursue either theoretical or empirical aspects. Suggested tracks:
| Milestone | Due |
|---|---|
| Proposal | 11:59 PM EST, Sunday, Oct 18 |
| Project Presentation | Thursday, Dec 3 and Tuesday, Dec 8 in class |
| Final Report | 11:59 PM EST, Friday, Dec 11 |
Plagiarism is a very serious academic offence and is penalized accordingly. When you plagiarize you damage the learning experience for yourself and others. To avoid plagiarism accusations, do not copy other people's work, and cite all references that you use. If you work with others, only discuss general aspects of the course material, not specific solutions. Write up the solutions yourself, not in groups.
Generative and agentic AI tools (e.g., ChatGPT, Claude, Copilot, Cursor, and autonomous coding or research agents) are permitted only as assistive aids, not as substitutes for your own understanding and work.
If you or anyone you know experiences academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.
On-campus
Off-campus
It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students' learning needs be addressed both in and out of class. Suggestions for improving the course are encouraged and appreciated. In particular: