Learned Structures: Data-Aware Primitives for State Management

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Learned Structures: Data-Aware Primitives for State Management"

By

Mr. Siyuan HAN


Abstract:

In-memory data structures must use memory efficiently while supporting fast 
access. We investigate how learned representations can improve this balance 
in two settings: exact lookup over sorted keys and lossless compression of 
existing product-quantization (PQ) codes for vector retrieval.

We develop PGM++ to accelerate exact lookup in the Piecewise Geometric Model 
(PGM) index, which predicts key positions. Under statistical assumptions on 
key gaps, our analysis relates data regularity to segment coverage and 
hierarchy height. Our profiling identifies internal bounded search as a major 
lookup cost even in shallow hierarchies. PGM++ reduces this cost through 
hybrid and vectorized search, layer bypassing, and calibrated tuning while 
preserving exact lookup. Static lookup benchmarks show 1.2x-2.2x speedups 
over PGM at comparable measured index sizes. Dynamic PGM++ adds batched 
prefetching and merge optimizations.

For vector retrieval, PQ compresses vectors, but the resulting code tables 
can still occupy substantial memory. We develop SegPQ, which packs PQ codes 
into integers and compresses their sorted sequence using piecewise linear 
models and exact residuals. Decoding reconstructs the original codes for 
distance computation, introducing no additional quantization error. Compared 
with the original PQ-code table, SegPQ reduces memory by 76.1% on Deep1B with 
32-bit codes, while increasing the batch time for 1000 top-50 queries with 
decoded-code reuse by 6.2%.

Through these studies, we improve lookup speed and code-storage efficiency 
while preserving exact search results and the original PQ codes.


Date:                   Friday, 23 October 2026

Time:                   3:00pm - 5:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Prof. Shingyu LEUNG (MATH)

Committee Members:      Prof. Lei CHEN (Supervisor)
                        Prof. Bo LI
                        Prof. Qiong LUO
                        Prof. Can YANG (MATH)
                        Prof. Jianliang XU (HKBU)