Researcher at Inria
The objective of this course is to present the principles of the knowledge discovery and data mining pipeline, covering acquisition, storage, and extraction. From storing data to searching for similarities, the course will include a mix of lectures and practical sessions.
An overview of the knowledge discovery pipeline, from data acquisition to storage and extraction, and of the course organization. We then discuss data acquisition from a Web perspective: what information retrieval for web data is, and how search engines crawl, index, and rank data.
How data is physically stored and accessed: the memory hierarchy, disks and SSDs, files, pages and buffers. We see why access patterns matter for performance, and how these constraints shape the design of storage structures and database management systems.
The relational model and SQL, and the limits of relational systems at scale. We then introduce the NoSQL family (key-value, column, document and graph stores) and the trade-offs between consistency, availability and partition tolerance.
Semi-structured and connected data: document databases built on JSON-like documents, and graph databases for highly connected data, with their data models and query languages. The second part of the session is the first practice session (Lab 1).
Introduction to data extraction and Similarity search. We start with the basic search mechanisms in databases and distributed systems. We then take a deep dive into ordered indexes and B-trees, and hash indexes, such as extensible hashing and consistent hashing for distributed systems.
Similarity search as a core extraction task: given a query, find the most similar objects in a collection. We define distance measures (Euclidean, elastic distances such as DTW), dimensionality reduction (PAA, APCA, SAX), and the lower-bounding principle that enables exact search without scanning everything. The second part of the session is the second practice session (Lab 2).
Indexing data in many dimensions: space-partitioning and data-partitioning trees, bounding regions and best-first nearest-neighbor search, and why these structures degrade as dimensionality grows. We then cover time-series indexing techniques that combine space partitioning with lower bounds for exact search.
When exact answers are too expensive, approximate methods trade a little accuracy for large speed-ups. The second part of the lecture is a wrap-up of the course and an opening towards other extraction tasks built on top of similarity search, such as motif and anomaly discovery.
This exam lasts 2.5 h. The only documents allowed are 6 handwritten A4 sheets (both sides). Communicating devices are strictly forbidden. When writing code, imprecision in language syntax will be tolerated. The exam is graded out of 20 points. The questions will cover Lectures 1 (Sep. 18) to 8 Part 1 (Nov. 20). There is only one bonus question on Lecture 8 Part 2 (Nov. 06).
| Session | Type | |
|---|---|---|
| Dec. 01 | Written exam (2.5 h) |
This course has two practice sessions covering both database systems (Lab 1) and similarity-based algorithms (Lab 2). Each practice session is divided into Part 1, tackled in class, and Part 2, to do as homework. The notebook, with code, results, and explanation, should be filled out (for both Part 1 and Part 2) and sent to me by email in both PDF and IPYNB formats (at paul [dot] boniol [at] inria [dot] fr) before the corresponding deadline (at 5 pm CEST (Central European Summer Time)). Each practice session is graded out of 20 points.
| Session | Title | Topic | Notebook | Data | Deadline |
|---|---|---|---|---|---|
| Oct. 16 | Lab 1 · Database of documents | Nov. 05 | |||
| Oct. 30 | Lab 2 · Similarity search | Nov. 19 |
This course is highly inspired by previous courses of other professors and researchers listed below: