License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.31
URN: urn:nbn:de:0030-drops-73441
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7344/
Barbay, Jérémy ;
Ochoa, Carlos ;
Satti, Srinivasa Rao
Synergistic Solutions on MultiSets
Abstract
Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. 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 approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions 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 the comparison 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 of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.
BibTeX - Entry
@InProceedings{barbay_et_al:LIPIcs:2017:7344,
author = {J{\'e}r{\'e}my Barbay and Carlos Ochoa and Srinivasa Rao Satti},
title = {{Synergistic Solutions on MultiSets}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {31:1--31:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-039-2},
ISSN = {1868-8969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7344},
URN = {urn:nbn:de:0030-drops-73441},
doi = {10.4230/LIPIcs.CPM.2017.31},
annote = {Keywords: deferred data structure, multivariate analysis, quick sort, select}
}
|
Keywords: |
|
deferred data structure, multivariate analysis, quick sort, select |
|
Collection: |
|
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
30.06.2017 |
