Data Structures for Multidimensional Range Minimum Queries

Project: Research

View graph of relations

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 number9041688
Grant typeGRF
StatusFinished
Effective start/end date1/01/1225/05/16