@preamble{ "\newcommand{\noopsort}[1]{} "
	# "\newcommand{\printfirst}[2]{#1} "
	# "\newcommand{\singleletter}[1]{#1} "
	# "\newcommand{\switchargs}[2]{#2#1} " }

% First work on rank and select in bit vector
@phdthesis{jacobson1988succinct,
author = {Jacobson, Guy Joseph},
title = {Succinct Static Data Structures},
year = {1988},
publisher = {Carnegie Mellon University},
address = {USA},
} https://dl.acm.org/doi/book/10.5555/915547

% Navarro's book
@book{navarro2016compact,
  title={Compact data structures: A practical approach},
  author={Navarro, Gonzalo},
  year={2016},
  publisher={Cambridge University Press}
}

% Overview of tree results
@incollection{raman2013succinct,
  title={Succinct representations of ordinal trees},
  author={Raman, Rajeev and Rao, S Srinivasa},
  booktitle={Space-efficient data structures, streams, and algorithms},
  pages={319--332},
  year={2013},
  publisher={Springer}
}

% succinct fenwick tree
@inproceedings{bille2017succinct,
  title={Succinct partial sums and Fenwick trees},
  author={Bille, Philip and Christiansen, Anders Roy and Prezza, Nicola and Skjoldjensen, Frederik Rye},
  booktitle={International Symposium on String Processing and Information Retrieval},
  pages={91--96},
  year={2017},
  organization={Springer}
}

% Trie
@article{grossi2015fast,
  title={Fast compressed tries through path decompositions},
  author={Grossi, Roberto and Ottaviano, Giuseppe},
  journal={Journal of Experimental Algorithmics (JEA)},
  volume={19},
  pages={1--1},
  year={2015},
  publisher={ACM New York, NY, USA}
}

% Succinct example, graphs
@article{farzan2013succinct,
  title={Succinct encoding of arbitrary graphs},
  author={Farzan, Arash and Munro, J Ian},
  journal={Theoretical Computer Science},
  volume={513},
  pages={38--52},
  year={2013},
  publisher={Elsevier}
}

% Grids
@article{chazelle1988functional,
  title={A functional approach to data structures and its use in multidimensional searching},
  author={Chazelle, Bernard},
  journal={SIAM Journal on Computing},
  volume={17},
  number={3},
  pages={427--462},
  year={1988},
  publisher={SIAM}
}

% Sparse array
@inproceedings{grossi2013design,
  title={Design of practical succinct data structures for large data collections},
  author={Grossi, Roberto and Ottaviano, Giuseppe},
  booktitle={International Symposium on Experimental Algorithms},
  pages={5--17},
  year={2013},
  organization={Springer}
} % https://link.springer.com/chapter/10.1007/978-3-642-38527-8_3

% Huffman encoding
@article{huffman1952method,
  title={A method for the construction of minimum-redundancy codes},
  author={Huffman, David A},
  journal={Proceedings of the IRE},
  volume={40},
  number={9},
  pages={1098--1101},
  year={1952},
  publisher={IEEE}
}

% BWT
@inproceedings{burrows1994block,
  title={A block-sorting lossless data compression algorithm},
  author={Burrows, Michael and Wheeler, David},
  booktitle={Digital SRC Research Report},
  year={1994},
  organization={Citeseer}
}

% FM-index
@inproceedings{ferragina2000opportunistic,
  title={Opportunistic data structures with applications},
  author={Ferragina, Paolo and Manzini, Giovanni},
  booktitle={Proceedings 41st annual symposium on foundations of computer science},
  pages={390--398},
  year={2000},
  organization={IEEE}
}

% FM-index in nH_k(T) + o(n)
@inproceedings{karkkainen2011fixed,
  title={Fixed block compression boosting in {FM}-indexes},
  author={K{\"a}rkk{\"a}inen, Juha and Puglisi, Simon J},
  booktitle={International Symposium on String Processing and Information Retrieval},
  pages={174--184},
  year={2011},
  organization={Springer}
}

% Read alignment
@article{langmead2009ultrafast,
  title={Ultrafast and memory-efficient alignment of short {DNA} sequences to the human genome},
  author={Langmead, Ben and Trapnell, Cole and Pop, Mihai and Salzberg, Steven L},
  journal={Genome biology},
  volume={10},
  number={3},
  pages={1--10},
  year={2009},
  publisher={BioMed Central}
}
@article{li2010fast,
  title={Fast and accurate long-read alignment with {B}urrows-{W}heeler transform},
  author={Li, Heng and Durbin, Richard},
  journal={Bioinformatics},
  volume={26},
  number={5},
  pages={589--595},
  year={2010},
  publisher={Oxford Academic}
}

% FM-index compression ratios
@article{ferragina2001experimental,
  title={An experimental study of a compressed index},
  author={Ferragina, Paolo and Manzini, Giovanni},
  journal={Information Sciences},
  volume={135},
  number={1-2},
  pages={13--28},
  year={2001},
  publisher={Elsevier}
}

% Use of BWT: bzip2
@article{seward1996bzip2,
  title={bzip2 and libbzip2},
  author={Seward, Julian},
  journal={avaliable at http://www.bzip.org},
  year={1996}
}

% Use of BWT
@article{manzini2001analysis,
  title={An analysis of the {B}urrows-{W}heeler transform},
  author={Manzini, Giovanni},
  journal={Journal of the ACM (JACM)},
  volume={48},
  number={3},
  pages={407--430},
  year={2001},
  publisher={ACM New York, NY, USA}
}

% wavelet tree
% Huffman tree and its space with H_0 impl of bit vector
% mentioned by makinen2005succinct
@article{grossi2003high,
  title={High-order entropy-compressed text indexes},
  author={Grossi, Roberto and Gupta, Ankur and Vitter, Jeffrey Scott},
  year={2003},
  publisher={Society for Industrial and Applied Mathematics Philadelphia}
} % https://kuscholarworks.ku.edu/handle/1808/7192

% Precompute rank for superblocks
@inproceedings{gonzalez2005practical,
  title={Practical implementation of rank and select queries},
  author={Gonz{\'a}lez, Rodrigo and Grabowski, Szymon and M{\"a}kinen, Veli and Navarro, Gonzalo},
  booktitle={Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA)},
  pages={27--38},
  year={2005},
  organization={CTI Press and Ellinika Grammata Greece}
}

% Constant time Select
@phdthesis{clark1997compact,
author = {Clark, David Richard},
title = {Compact {PAT} Trees},
year = {1998},
publisher = {University of Waterloo},
address = {CAN}
}

% RRR
@article{pagh2001low,
  title={Low redundancy in static dictionaries with constant query time},
  author={Pagh, Rasmus},
  journal={SIAM Journal on Computing},
  volume={31},
  number={2},
  pages={353--363},
  year={2001},
  publisher={SIAM}
}
@article{raman2007succinct,
  title={Succinct indexable dictionaries with applications to encoding $k$-ary trees, prefix sums and multisets},
  author={Raman, Rajeev and Raman, Venkatesh and Satti, Srinivasa Rao},
  journal={ACM Transactions on Algorithms (TALG)},
  volume={3},
  number={4},
  pages={43--es},
  year={2007},
  publisher={ACM New York, NY, USA}
} % https://dl.acm.org/doi/abs/10.1145/1290672.1290680?casa_token=593z8wA-YGYAAAAA:wv_kdp8YJTmvYbIU4DJMLCxiYGaLVemMQvX9jXWgSHcC_JbY-FAOl7hJ1IABIIh0VZumwDYQiF9ivA

% first real RRR
@inproceedings{claude2008practical,
  title={Practical rank/select queries over arbitrary sequences},
  author={Claude, Francisco and Navarro, Gonzalo},
  booktitle={International Symposium on String Processing and Information Retrieval},
  pages={176--187},
  year={2008},
  organization={Springer}
}

% Improvement with $O(b)$ decoding
@inproceedings{navarro2012fast,
  title={Fast, small, simple rank/select on bitmaps},
  author={Navarro, Gonzalo and Providel, Eliana},
  booktitle={International Symposium on Experimental Algorithms},
  pages={295--306},
  year={2012},
  organization={Springer}
}

% Constant time rank
@inproceedings{okanohara2007practical,
  title={Practical entropy-compressed rank/select dictionary},
  author={Okanohara, Daisuke and Sadakane, Kunihiko},
  booktitle={2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX)},
  pages={60--70},
  year={2007},
  organization={SIAM}
}

% SDSL
@inproceedings{gbmp2014sea,
  title     = {From Theory to Practice: {P}lug and Play with Succinct Data Structures},
  author    = {Gog, Simon and Beller, Timo and Moffat, Alistair and Petri, Matthias},
  booktitle = {13th International Symposium on Experimental Algorithms, (SEA 2014)},
  year      = {2014},
  pages     = {326-337},
  ee        = {http://dx.doi.org/10.1007/978-3-319-07959-2_28}
}

% SDSL benchmarking
@article{gog2014optimized,
  title={Optimized succinct data structures for massive data},
  author={Gog, Simon and Petri, Matthias},
  journal={Software: Practice and Experience},
  volume={44},
  number={11},
  pages={1287--1314},
  year={2014},
  publisher={Wiley Online Library}
}

% Pizza&Chili
@article{ferragina2005pizza,
  title={Pizza\&Chili Corpus—Compressed indexes and their testbeds},
  author={Ferragina, Paolo and Navarro, Gonzalo},
  journal={September},
  year={2005}
}

@article{ferragina2009compressed,
  title={Compressed text indexes: {F}rom theory to practice},
  author={Ferragina, Paolo and Gonz{\'a}lez, Rodrigo and Navarro, Gonzalo and Venturini, Rossano},
  journal={Journal of Experimental Algorithmics (JEA)},
  volume={13},
  pages={1--12},
  year={2009},
  publisher={ACM New York, NY, USA}
}

% Huffman shaped WT
@inproceedings{makinen2005succinct,
  title={Succinct suffix arrays based on run-length encoding},
  author={M{\"a}kinen, Veli and Navarro, Gonzalo},
  booktitle={Annual Symposium on Combinatorial Pattern Matching},
  pages={45--56},
  year={2005},
  organization={Springer}
}

% Huffman tree with average depth limited by $H_0+2$ and height $\BigO(log \sigma)$
% mentioned by makinen2005succinct
@inproceedings{grabowski2004first,
  title={First {H}uffman, then {B}urrows-{W}heeler: {A} simple alphabet-independent {FM}-index},
  author={Grabowski, Szymon and M{\"a}kinen, Veli and Navarro, Gonzalo},
  booktitle={International Symposium on String Processing and Information Retrieval},
  pages={210--211},
  year={2004},
  organization={Springer}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% May be used....

% best result in dynamic data structures
@incollection{munro2015compressed,
  title={Compressed data structures for dynamic sequences},
  author={Munro, J Ian and Nekrich, Yakov},
  booktitle={Algorithms-ESA 2015},
  pages={891--902},
  year={2015},
  publisher={Springer}
} % https://link.springer.com/chapter/10.1007/978-3-662-48350-3_74

% best result in static data structures
@article{belazzougui2015optimal,
  title={Optimal lower and upper bounds for representing sequences},
  author={Belazzougui, Djamal and Navarro, Gonzalo},
  journal={ACM Transactions on Algorithms (TALG)},
  volume={11},
  number={4},
  pages={1--21},
  year={2015},
  publisher={ACM New York, NY, USA}
} % https://dl.acm.org/doi/abs/10.1145/2629339?casa_token=6Wu_fZIU3e0AAAAA:QXlQMN8IpYn8RW9ve08j2OC7NLZp6eGNa24JGz3iupFuwHvvOqTJQOvdxWKcWZf_pMv0U-6sRy1ZQA

% lower bound for dynamic data structures
@inproceedings{fredman1989cell,
  title={The cell probe complexity of dynamic data structures},
  author={Fredman, Michael and Saks, Michael},
  booktitle={Proceedings of the twenty-first annual ACM symposium on Theory of computing},
  pages={345--354},
  year={1989}
} % https://dl.acm.org/doi/abs/10.1145/73007.73040?casa_token=NwRXAgySWSMAAAAA:DVGNGioy6tscgjrvUIqqiw0wTNVo0P6iD3a3oq4-X4mLq9p1PIlb5ID81S8BH-KcKxFp6XSkRiGF3A

% lower bound for dynamic data structures: optimal bound is \omega(lg n / lg w) from https://drive.google.com/file/d/14AZ3t0rZ58oiS_-KF05ycwjP5wvJ0-05/view
@article{beame2002optimal,
  title={Optimal bounds for the predecessor problem and related problems},
  author={Beame, Paul and Fich, Faith E},
  journal={Journal of Computer and System Sciences},
  volume={65},
  number={1},
  pages={38--72},
  year={2002},
  publisher={Elsevier}
} % https://www.sciencedirect.com/science/article/pii/S0022000002918222

% Implementations:

% Static:

% DYNAMIC
@article{prezza2017framework,
  title={A framework of dynamic data structures for string processing},
  author={Prezza, Nicola},
  journal={arXiv preprint arXiv:1701.07238},
  year={2017}
} % https://arxiv.org/abs/1701.07238


% Rank-select over bit-map
@article{pibiri2020rank,
  title={Rank/Select Queries over Mutable Bitmaps},
  author={Pibiri, Giulio Ermanno and Kanda, Shunsuke},
  journal={arXiv preprint arXiv:2009.12809},
  year={2020}
} % https://arxiv.org/abs/2009.12809

% Bit-vector using fenwick tree
@article{marchini2020compact,
  title={Compact {F}enwick trees for dynamic ranking and selection},
  author={Marchini, Stefano and Vigna, Sebastiano},
  journal={Software: Practice and Experience},
  volume={50},
  number={7},
  pages={1184--1202},
  year={2020},
  publisher={Wiley Online Library}
} % https://onlinelibrary.wiley.com/doi/full/10.1002/spe.2791?casa_token=UBfSNHXH8mEAAAAA%3A_XXoaDJlLJN3qzYhBR6suUP2T8wlXkW4-12fBmGC8jbNE8tf7TGBVCbRtRElSrEtY5yfOmaN3aFCmcsI

% sdsl
@inproceedings{gog2014theory,
  title={From theory to practice: {P}lug and play with succinct data structures},
  author={Gog, Simon and Beller, Timo and Moffat, Alistair and Petri, Matthias},
  booktitle={International Symposium on Experimental Algorithms},
  pages={326--337},
  year={2014},
  organization={Springer}
} % sdsl - https://link.springer.com/chapter/10.1007/978-3-319-07959-2_28

% libcsd
@inproceedings{brisaboa2011compressed,
  title={Compressed string dictionaries},
  author={Brisaboa, Nieves R and C{\'a}novas, Rodrigo and Claude, Francisco and Mart{\'\i}nez-Prieto, Miguel A and Navarro, Gonzalo},
  booktitle={International Symposium on Experimental Algorithms},
  pages={136--147},
  year={2011},
  organization={Springer}
} % https://github.com/migumar2/libCSD

@inproceedings{policriti2015average,
  title={Average linear time and compressed space construction of the Burrows-Wheeler transform},
  author={Policriti, Alberto and Gigante, Nicola and Prezza, Nicola},
  booktitle={International Conference on Language and Automata Theory and Applications},
  pages={587--598},
  year={2015},
  organization={Springer}
} % https://link.springer.com/chapter/10.1007/978-3-319-15579-1_46


@article{makinen2008dynamic,
  title={Dynamic entropy-compressed sequences and full-text indexes},
  author={M{\"a}kinen, Veli and Navarro, Gonzalo},
  journal={ACM Transactions on Algorithms (TALG)},
  volume={4},
  number={3},
  pages={1--38},
  year={2008},
  publisher={ACM New York, NY, USA}
}

% Other:

% Lempel Ziv compression algorithm
@article{ziv1977universal,
  title={A universal algorithm for sequential data compression},
  author={Ziv, Jacob and Lempel, Abraham},
  journal={IEEE Transactions on information theory},
  volume={23},
  number={3},
  pages={337--343},
  year={1977},
  publisher={IEEE}
} % https://ieeexplore.ieee.org/abstract/document/1055714

% Fenwick tree
@article{fenwick1994new,
  title={A new data structure for cumulative frequency tables},
  author={Fenwick, Peter M},
  journal={Software: Practice and experience},
  volume={24},
  number={3},
  pages={327--336},
  year={1994},
  publisher={Wiley Online Library}
} % https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380240306