Faster range minimum queries. (28th June 2018)

• Record Type: Journal Article
• Authors: Kowalski, Tomasz M.; Grabowski, Szymon
• Is Part Of: Software, practice & experience. Volume 48:Number 11(2018)
• Page Start: 2043
• Page End: 2060
• Publication Date: 2018-06-28
• Subjects: bulk queries -- range minimum query -- string algorithms; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2597
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Range minimum query is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, practical performance and construction time also matter. Additionally, there are offline scenarios in which the number of queries, ie, q, is rather small and given beforehand, which encourages to use a simpler approach. In this work, we present a simple data structure, with very fast construction, which allows to handle queries in constant time on average. This algorithm, however, requires access to the input data during queries (which is not the case of sophisticated range minimum query solutions). We subsequently refine our technique, combining it with one of the existing succinct solutions with O (1) worst‐case time queries and no access to the input array. The resulting hybrid is still a memory frugal data structure, spending usually up to about 3 n bits and providing competitive query times, especially for wide ranges. We also show how to make our baseline data structure more compact. Experimental results demonstrate that the proposed block‐based sparse table (BbST) variants are competitive to existing solutions, also in the offline scenario.