Premium
Faster range minimum queries
Author(s) -
Kowalski Tomasz M.,
Grabowski Szymon
Publication year - 2018
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.2597
Subject(s) - computer science , data structure , range (aeronautics) , string (physics) , matching (statistics) , block (permutation group theory) , constant (computer programming) , range query (database) , competitive analysis , simple (philosophy) , table (database) , theoretical computer science , algorithm , data mining , upper and lower bounds , information retrieval , search engine , mathematics , web search query , sargable , mathematical analysis , philosophy , statistics , materials science , geometry , epistemology , composite material , mathematical physics , programming language
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.