Adaptive Multidimensional Indexing

PhD Thesis Proposal Defence


Title: "Adaptive Multidimensional Indexing"

by

Mr. Moin Hussain MOTI


Abstract:

Although several multidimensional indexes achieve fast query processing, they 
are ineffective for highly dynamic data sets because of costly updates. On the 
other hand, simple structures that enable efficient updates are slow for 
queries. Our first proposed index, Waffle, combines concepts of the space and 
data partitioning frameworks, and constitutes a complete indexing solution. In 
addition to query processing algorithms, it includes: (i) a novel bulk loading 
method that guarantees optimal disk page utilization on static data, (ii) 
algorithms for dynamic updates that guarantee zero overlapping of nodes, and 
(iii) a maintenance mechanism that adjusts the trade-off between query and 
update speed, based on the workload and query distribution. Our second index 
FMBI addresses the issue of expensive bulk loading of disk-based 
multidimensional points through multiple applications of external sorting. The 
proposed techniques apply linear scan, and are therefore significantly faster. 
FMBI possesses several desirable properties, including almost full and square 
nodes with zero overlap, and has excellent query performance. We also propose 
an adaptive version AMBI, which utilizes the query workload to build a partial 
index only for parts of the data space that contain query results. Finally, we 
extend FMBI and AMBI to parallel bulk loading and query processing in 
distributed systems.


Date:                   Wednesday, 22 May 2024

Time:                   1:30pm - 3:30pm

Venue:                  Room 4475
                        Lifts 25/26

Committee Members:      Prof. Dimitris Papadias (Supervisor)
                        Prof. Siu-Wing Cheng (Chairperson)
                        Prof. Raymond Wong
                        Prof. Ke Yi