Data Structures for Multidimensional Range Minimum Queries
Project: Research
Researcher(s)
Description
Given an array, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray. The 1D version of the RMQ problem is a fundamental problem in string pattern matching, and the multidimensional version has an important application in database systems, i.e., it can be used to answer range MIN/MAX queries in OLAP (online analytical processing) data cubes.This proposal aims to do an extensive study of the RMQ problem in multidimensional arrays, and design efficient data structures to meet various requirements. The requirements considered are related to (but not limited to) external memory data structures, time-space trade-offs, dynamic updates, and probabilistic inputs.Detail(s)
Project number | 9041688 |
---|---|
Grant type | GRF |
Status | Finished |
Effective start/end date | 1/01/12 → 25/05/16 |