Synergistic solutions on multisets

Abstract

Karp et al. (1988) described Deferred Data Structures for Multisets as “lazy” data structureswhich partially sort data to support online rank and select queries, with the minimum amount ofwork in the worst case over instances of sizenand number of queriesqfixed. Barbay et al. (2016)refined this approach to take advantage of the gaps between the positions hit by the queries (i.e.,the structure in the queries). We develop new techniques in order to further refine this approachand take advantage all at once of the structure (i.e., the multiplicities of the elements), somenotions of local order (i.e., the number and sizes of runs) and global order (i.e., the number andpositions of existing pivots) in the input; and of the structure and order in the sequence of queries.Our main result is a synergistic deferred data structure which outperforms all solutions in thecomparison model that take advantage of only a subset of these features. As intermediate results,we describe two new synergistic sorting algorithms, which take advantage of some notions ofstructure and order (local and global) in the input, improving upon previous results which takeadvantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) inthe input; and one new multiselection algorithm which takes advantage of not only the order andstructure in the input, but also of the structure in the queries.