On Efficient and Effective Learned Index Structures

PhD Thesis Proposal Defence


Title: "On Efficient and Effective Learned Index Structures"

by

Mr. Qiyu LIU


Abstract:

Over the past decade, machine learning techniques, has achieved a breakthrough 
and opened a new paradigm for people to re-examine the traditional data 
management challenges such as data indexing and query optimization. In the 
seminal paper of Kraska et al., the ``learned index'' was first introduced to 
refer to the new paradigm of index design by using a combination of machine 
learning models (to give quick answers like search key lookup or membership 
guess) and traditional data structures (to handle the corner cases that ML 
models cannot correctly process).

As a promising research direction, optimizations and extensions to the original 
learned indexes have been studied recently. In this proposal, we introduce two 
of our recent works on improving learned index structures for efficient 
membership query over data streams and approximate spatial range query. 
Specifically, we first devise a new Bloom filter variant called Stable Learned 
Bloom filter which addresses the performance decay issue of Bloom filters on 
intensive insertion workloads by combining classifier with updatable backup 
filters. Second, we study the application of learned index as spatial data 
synopsis, which is widely adopted to speed-up query processing over large 
spatial databases. We propose a learned data synopsis technique named Learned 
Multi-dimensional Histogram (LHist). Compared with the traditional data 
synopsis techniques, LHist is fully data-driven, easy-to-implement, and has the 
potential to achieve better storage-accuracy trade-off.

Extensive experimental studies on large-scale real-world datasets and synthetic 
benchmarks reveal that our learned index structures can outperform the 
state-of-the-arts in terms of storage cost and query processing efficiency.


Date:			Thursday, 9 December 2021

Time:                  	2:00pm - 4:00pm

Venue: 			Room 1410
 			Lifts 25/26

Committee Members:	Prof. Lei Chen (Supervisor)
  			Prof. Qiong Luo (Chairperson)
 			Prof. Ke Yi
 			Prof. Xiaofang Zhou


**** ALL are Welcome ****