Speaker: Zeyu Wang, PhD Candidate
Title: From Dimensionality Reduction to Query Hardness Measurement: A Deep Dive into Approximate Nearest Neighbor Search
Date: 2025-07-16
Time: 15:00- 16:00 (EEST)
Location: Orphanoudakis Seminar Room - FORTH, Main Building, 1st floor
Host: George Tzagkarakis, FORTH-ICS, SPL
Abstract:
Approximate Nearest Neighbor (ANN) search has become a foundational component in many data analysis and AI applications. In this presentation, I will first present a comprehensive overview of dimensionality-reduction techniques tailored for ANN, based on a recent survey and evaluation study. We will explore how these techniques—ranging from classic methods like PCA to advanced learned projections—help reduce the effort to calculate distance between vectors while maintaining high recall and speed in modern ANN indexes.
In the second part, I will introduce a novel ANNS query hardness measure for graph-based indexes: Steiner-Hardness. Steiner-Hardness is the first measure that pays attention to the connections and topology in the graph-based indexes.. By drawing connections to Steiner Tree problems in graph theory, this metric provides an interpretable and efficient way to estimate how much effort is needed to answer a given query. Interesting future works that extend these projects will be discussed finally, which are expected to give a deeper and clearer understanding of the data distribution in high-d space and the performance of current indexing techniques.
Short bio:
Zeyu Wang is a PhD candidate at Fudan University (China), and a visiting PhD student at Universite Paris Cite (co-advised by Prof Themis Palpanas).