Please note: This seminar will take place in DC 1304.
Qiao Miao, Senior Lecturer
School of Computer Science, University of Auckland
Graph-based query processing faces scalability challenges. This talk explores two facets of the problem. First, when a graph grows too large for efficient querying, can query processing algorithms exhibit strongly local properties, making the search independent of the graph’s overall size? Second, in approximate nearest neighbor search using indexes of Hierarchical Navigable Small World (HNSW) graphs, how can we compress the index while maintaining equivalent query performance, when queries include attribute-based filters?
To address the first question, we examine cases where dense subgraph search admits strongly local algorithms and where it does not. For the second, we present a novel compression method that transforms the n^2 HNSW graphs into a more compact structure called the 2D segment graph, enabling lossless compression while preserving query efficiency. Theory plays a central role in both solutions, shaping the performance and feasibility of scalable graph-based querying.
Bio: Dr. Qiao is a Senior Lecturer in Computer Science at the University of Auckland, New Zealand, a role equivalent to Associate Professor in tenure-track systems. Her research centers on big data management, with a focus on query optimization, indexing, joins, sampling, graph analysis, and graph-based nearest neighbor search. She has advanced indexing techniques for query processing in graph databases, including shortest distance and subgraph matching queries.
Her recent work on range-filtering nearest neighbor search, along with an ongoing submission on its dynamic variant, has potential applications in modern vector databases, particularly for unstructured queries.