A Survey on Partial Persistent Indexes

PhD Qualifying Examination


Title: "A Survey on Partial Persistent Indexes"

by

Mr. Kai WANG


Abstract:

Traditional database indexes (e.g., B+-trees, R-trees) are ephemeral since 
they manage only the current data. However, many systems, e.g., banking 
systems or e-commerce platforms, are required to maintain historical data 
over years according to regulations. To handle this, index structures have to 
be persistent. A structure is partial persistent if all versions (old and 
new) can be accessed, but only the current version can be modified. In 
practice, partial persistent structures are widely used in time series 
databases (e.g., InfluxDB) and databases with versioning extensions (e.g., 
MongoDB and PostgreSQL).

The survey first examines classic in-memory data structures for managing 
intervals, and their external variants. It then introduces recent in-memory 
interval management structures, which assume the availability of sufficiently 
large memory. However, most partial persistent indexes are designed to be 
disk-resident due to the potentially large size of the time-evolving data. 
Among the disk-based partial persistent structures, the multi-version index 
and its variants are highlighted as state-of-the-art approaches. The survey 
further discusses how adaptive structural designs potentially address the 
redundancy problem. Experimental evaluations on redundancy issues provide 
insightful findings. Finally, the survey summarizes the existing methods and 
suggests promising future research directions.


Date:                   Wednesday, 18 December 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 5564
                        Lifts 27/28

Committee Members:      Prof. Dimitris Papadias (Supervisor)
                        Prof. Raymond Wong (Chairperson)
                        Prof. Qiong Luo
                        Prof. Ke Yi