main.bib

% Encoding: UTF-8
% DEEP-SHALLOW

@article{quicksort,
  title = {Quicksort},
  author = {Hoare, C. A. R.},
  journal = {The Computer Journal},
  volume = {5},
  number = {1},
  pages = {10-16},
  year = {1962},
}

@article{radixsort:inplace,
  author = {Nasir Al-Darwish},
  title ={Formulation and analysis of in-place MSD radix sort algorithms},
  journal = {Journal of Information Science},
  volume = {31},
  number = {6},
  pages = {467-481},
  year = {2005},
}

@inproceedings{multikey_quicksort,
  title={Fast algorithms for sorting and searching strings},
  author={Bentley, Jon L and Sedgewick, Robert},
  booktitle={Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
  pages={360--369},
  year={1997},
  organization={Society for Industrial and Applied Mathematics}
}

@article{ternary_quicksort,
  title={Engineering a sort function},
  author={Bentley, Jon L and McIlroy, M Douglas},
  journal={Software: Practice and Experience},
  volume={23},
  number={11},
  pages={1249--1265},
  year={1993},
  publisher={Wiley Online Library}
}

@article{ds:blind,
  title={The string B-tree: a new data structure for string search in external memory and its applications},
  author={Ferragina, Paolo and Grossi, Roberto},
  journal={Journal of the ACM (JACM)},
  volume={46},
  number={2},
  pages={236--280},
  year={1999},
  publisher={ACM}
}

@book{makinen,
  title={Genome-scale algorithm design},
  author={M{\"a}kinen, Veli and Belazzougui, Djamal and Cunial, Fabio and Tomescu, Alexandru I},
  year={2015},
  publisher={Cambridge University Press}
}

%DIV-SUF-SORT


@ARTICLE{Musser97,
    author = {David Musser},
    title = {Introspective Sorting and Selection Algorithms},
    journal = {Software Practice and Experience},
    year = {1997},
    volume = {27},
    pages = {983--993}
}

@TECHREPORT{Blelloch90,
    author = {Guy E. Blelloch},
    title = {Prefix Sums and Their Applications},
    institution = {Synthesis of Parallel Algorithms},
    year = {1990}
}


% SACAS
@InProceedings{saca:3,
  author =	{Uwe Baier},
  title =	{{Linear-time Suffix Sorting - A New Approach for Suffix Array Construction}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{23:1--23:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Roberto Grossi and Moshe Lewenstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6069},
  URN =		{urn:nbn:de:0030-drops-60698},
  doi =		{10.4230/LIPIcs.CPM.2016.23},
  annote =	{Keywords: Suffix array, sorting algorithm, linear time}
}

@online{saca:3:github,
	author = {Uwe Baier},
	title={GSACA Repository},
	url = {https://github.com/waYne1337/gsaca},
	urldate = {10.03.2018}
}

@INPROCEEDINGS{ saca:5,
 author = "Johannes Fischer and Florian Kurpicz",
 title = "Dismantling DivSufSort",
 booktitle = "Proceedings of the Prague Stringology Conference 2017",
 address = "Czech Technical University in Prague, Czech Republic",
 editor = "Jan Holub and Jan {\v{Z}}{\v{d}}{\'{a}}rek",
 isbn = "978-80-01-06193-0",
 year = 2017,
 pages = "62--76",
}

@Online{saca:5:repo,
author={Y. Mori},
title={DivSufSort},
url={https://github.com/y-256/libdivsufsort},
urldate={03.04.2018}
}

@inproceedings{saca:10,
	Author = {Nong, Ge and Zhang, Sen},
	Booktitle = {Workshop on Algorithms and Data Structures},
	Organization = {Springer},
	Pages = {613--624},
	Title = {Optimal lightweight construction of suffix arrays for constant alphabets},
	Year = {2007}}

@article{saca:12,
  title={Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets},
  author={Goto, Keisuke},
  journal={arXiv preprint arXiv:1703.01009},
  year={2017}
}
@inproceedings{Karp,
 author = {Karp, Richard M. and Miller, Raymond E. and Rosenberg, Arnold L.},
 title = {Rapid Identification of Repeated Patterns in Strings, Trees and Arrays},
 series = {STOC '72},
 year = {1972},
 location = {Denver, Colorado, USA},
 pages = {125--136},
 numpages = {12}
}

@online{saisSlides,
	Author = {Ge Nong, Sen Zhang, Wai Hong Chan},
	Title = {Linear Time Suffix Array Construction Using D-Critical Substrings},
	Url = {http://slideplayer.com/slide/12300993/},
	Urldate = {04.04.2018},
	Year = 2018,
	Bdsk-Url-1 = {http://slideplayer.com/slide/12300993/}}

% mSufSort

@article{saca:8,
 author = {Maniscalco, Michael A. and Puglisi, Simon J.},
 title = {An Efficient, Versatile Approach to Suffix Sorting},
 journal = {J. Exp. Algorithmics},
 issue_date = {2008},
 volume = {12},
 month = jun,
 year = {2008},
 issn = {1084-6654},
 pages = {1.2:1--1.2:23},
 articleno = {1.2},
 numpages = {23},
 doi = {10.1145/1227161.1278374},
 acmid = {1278374},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Burrows--Wheeler transform, Suffix sorting, suffix array, suffix tree},
}

@article{dc3:new,
 author = {K\"{a}rkk\"{a}inen, Juha and Sanders, Peter and Burkhardt, Stefan},
 title = {Linear Work Suffix Array Construction},
 journal = {J. ACM},
 issue_date = {November 2006},
 volume = {53},
 number = {6},
 month = nov,
 year = {2006},
 issn = {0004-5411},
 pages = {918--936},
 numpages = {19},
 doi = {10.1145/1217856.1217858},
 acmid = {1217858},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Difference cover, external memory algorithms, suffix array},
}

@inproceedings{saca:2,
  author    = {Sch{\"{u}}rmann, Klaus{-}Bernd and Stoye, Jens},
  title     = {{An Incomplex Algorithm for Fast Suffix Array Construction}},
  booktitle = {Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments
               and the Second Workshop on Analytic Algorithmics and Combinatorics,
               {ALENEX} /ANALCO 2005, Vancouver, BC, Canada, 22 January 2005},
  pages     = {78--85},
  year      = {2005},
  url       = {http://www.siam.org/meetings/alenex05/papers/07kschuermann.pdf},
  timestamp = {Tue, 30 Jan 2007 13:47:28 +0100},
  biburl    = {http://dblp.org/rec/bib/conf/alenex/SchurmannS05},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@Article{saca:11,
  author        = {Dementiev, Roman and K{\"a}rkk{\"a}inen, Juha and Mehnert, Jens and Sanders, Peter},
  title         = {Better external memory suffix array construction},
  journal       = {Journal of Experimental Algorithmics (JEA)},
  year          = {2008},
  volume        = {12},
  pages         = {3--4},
  __markedentry = {[marvin:6]},
  publisher     = {ACM},
}

@Article{Vitter1994,
  author        = {Vitter, Jeffrey Scott and Shriver, Elizabeth AM},
  title         = {Algorithms for parallel memory, I: Two-level memories},
  journal       = {Algorithmica},
  year          = {1994},
  volume        = {12},
  number        = {2-3},
  pages         = {110--147},
  __markedentry = {[marvin:6]},
  publisher     = {Springer},
}

@InProceedings{Arge1997,
  author        = {Arge, Lars and Ferragina, Paolo and Grossi, Roberto and Vitter, Jeffrey Scott},
  title         = {On sorting strings in external memory},
  booktitle     = {Proceedings of the 29th annual ACM symposium on Theory of computing},
  year          = {1997},
  organization  = {ACM},
  pages         = {540--548},
  __markedentry = {[marvin:6]},
}

@Article{Crauser2002,
  author        = {Crauser, Andreas and Ferragina, Paolo},
  title         = {A theoretical and experimental study on the construction of suffix arrays in external memory},
  journal       = {Algorithmica},
  year          = {2002},
  volume        = {32},
  number        = {1},
  pages         = {1--35},
  __markedentry = {[marvin:6]},
  publisher     = {Springer},
}

@Article{Aggarwal1988,
  author        = {Aggarwal, Alok and Vitter, Jeffrey and others},
  title         = {The input/output complexity of sorting and related problems},
  journal       = {Communications of the ACM},
  year          = {1988},
  volume        = {31},
  number        = {9},
  pages         = {1116--1127},
  __markedentry = {[marvin:6]},
  publisher     = {ACM},
}

@Article{Manber1993,
  author        = {Manber, Udi and Myers, Gene},
  title         = {Suffix Arrays: A New Method for On-Line String Searches},
  journal       = {SIAM Journal on Computing},
  year          = {1993},
  volume        = {22},
  number        = {5},
  pages         = {935--948},
  __markedentry = {[marvin:6]},
  publisher     = {SIAM},
}

@Book{Cormen2009,
  title         = {Introduction to algorithms},
  author        = {Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford},
  year          = {2009},
  publisher     = {MIT press}
}

@InProceedings{seward2000,
  author       = {Seward, Julian},
  title        = {On the performance of BWT sorting algorithms},
  booktitle    = {Proceedings DCC 2000. Data Compression Conference},
  year         = {2000},
  organization = {IEEE},
  month        = {March},
  pages        = {173--182},
  doi          = {10.1109/DCC.2000.838157},
  issn         = {1068-0314},
  keywords     = {sorting;data compression;text analysis;cache storage;performance;BWT sorting algorithms;lossless text compression;Burrows-Wheeler transform;rotation sorting;optimisation;Sadakane sorting algorithm;instruction counts;cache misses;Sorting},
}

@Article{saca:6,
  author     = {Nong, Ge and Zhang, Sen and Chan, Wai Hong},
  title      = {Two Efficient Algorithms for Linear Time Suffix Array Construction},
  journal    = {IEEE Transactions on Computers},
  year       = {2011},
  volume     = {60},
  number     = {10},
  pages      = {1471--1484},
  doi        = {http://doi.ieeecomputersociety.org/10.1109/TC.2010.188},
  bdsk-url-1 = {http://doi.ieeecomputersociety.org/10.1109/TC.2010.188},
  publisher  = {IEEE CS Home},
}

@Article{saca:1,
  author    = {N. Jesper Larsson and Kunihiko Sadakane},
  title     = {Faster suffix sorting},
  journal   = {Theoretical Computer Science},
  year      = {2007},
  volume    = {387},
  number    = {3},
  pages     = {258--272},
  doi       = {10.1016/j.tcs.2007.07.017},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/bib/journals/tcs/LarssonS07},
  publisher = {Elsevier},
}

@Article{saca:4,
  author    = {Manzini, Giovanni and Ferragina, Paolo},
  title     = {Engineering a lightweight suffix array construction algorithm},
  journal   = {Algorithmica},
  year      = {2004},
  volume    = {40},
  number    = {1},
  pages     = {33--50},
  publisher = {Springer},
}

@InProceedings{saca:9,
  author    = {Kärkkäinen, Juha and Sanders, Peter},
  title     = {Simple linear work suffix array construction},
  year      = {2003},
  volume    = {30},
  publisher = {Springer},
  pages     = {943--955},
  doi       = {10.1007/3-540-45061-0},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  biburl    = {https://dblp.org/rec/bib/conf/icalp/KarkkainenS03},
  journal   = {International Colloquium on Automata, Languages and Programming (ICALP)},
}

@online{r-project,
  title     = {The Comprehensive R Archive Network},
  url       = {https://cran.r-project.org/},
  urldate   = {29.08.2018},
  key = {rproject}
}

@online{rjson,
  author    = {Alex Couture-Beil},
  title     = {Package ‘rjson’},
  url       = {https://cran.r-project.org/web/packages/rjson/rjson.pdf},
  urldate   = {29.08.2018},
  key = {rjson}
}

@online{rcolorbrewer,
  author    = {Erich Neuwirth},
  title     = {Package ‘RColorBrewer’},
  url       = {https://cran.r-project.org/web/packages/RColorBrewer/index.html},
  urldate   = {29.08.2018},
  key = {rcolorbrewer}
}

@InProceedings{axtmann2017,
  author    = {Michael Axtmann and Sascha Witt and Daniel Ferizovic and Peter Sanders},
  title     = {{In-Place Parallel Super Scalar Samplesort (IPSSSSo)}},
  booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
  pages     = {9:1--9:14},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN      = {978-3-95977-049-1},
  ISSN      = {1868-8969},
  year      = {2017},
  volume    = {87},
  editor    = {Kirk Pruhs and Christian Sohler},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address   = {Dagstuhl, Germany},
  URL       = {http://drops.dagstuhl.de/opus/volltexte/2017/7854},
  URN       = {urn:nbn:de:0030-drops-78542},
  doi       = {10.4230/LIPIcs.ESA.2017.9},
  annote    = {Keywords: shared memory, parallel sorting, in-place algorithm, comparison-based sorting, branch prediction}
}

@online{ips4o:repo,
  author    = {Sascha Witt},
  title     = {GitHub: In-place Parallel Super Scalar Samplesort (IPS4o)},
  url       = {https://github.com/SaschaWitt/ips4o},
  urldate   = {25.02.2019}
}

@article{saca:7,
 author = {Nong, Ge},
 title = {Practical Linear-time {$\mathcal O(1)$}-workspace Suffix Sorting for Constant Alphabets},
 journal = {ACM Trans. Inf. Syst.},
 issue_date = {July 2013},
 volume = {31},
 number = {3},
 month = aug,
 year = {2013},
 issn = {1046-8188},
 pages = {15:1--15:15},
 articleno = {15},
 numpages = {15},
 doi = {10.1145/2493175.2493180},
 acmid = {2493180},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {O(1)-workspace, Suffix array, linear time, sorting algorithm},
}

@Article{psais,
author="Lao, Bin and Nong, Ge and Chan, Wai Hong and Pan, Yi",
title="Fast induced sorting suffixes on a multicore machine",
journal="The Journal of Supercomputing",
year="2018",
month="Jul",
day="01",
volume="74",
number="7",
pages="3468--3485",
issn="1573-0484",
doi="10.1007/s11227-018-2395-5",
url="https://doi.org/10.1007/s11227-018-2395-5"
}

@Article{asianAlphabets,
  author    = {Vines, Phil and Zobel, Justin},
  title     = {Compression techniques for Chinese text},
  journal   = {Software-Practice and Experience},
  year      = {1998},
  volume    = {28},
  number    = {12},
  pages     = {1299--1314},
  publisher = {Citeseer},
}

@Article{BWT,
  author    = {Burrows, Michael and Wheeler, David J},
  title     = {A block-sorting lossless data compression algorithm},
  year      = {1994},
  publisher = {Citeseer},
}

@online{testdaten:tagme,
	title={TAGME Datasets},
	urldate   = {01.01.2016},
	url={http://acube.di.unipi.it/tagme-dataset/},
	key = {tagme}
}

@Online{testdaten:wiki,
  title   = {Vital articles/Expanded},
  url     = {https://en.wikipedia.org/wiki/Wikipedia:Vital\_articles/Expanded},
  urldate = {01.01.2016},
  key = {vital}
}
@online{testdaten:commoncrawl,
	title={Common Crawl, {\texttt{commoncrawl.org}}},
	urldate   = {01.01.2016},
	url={http://commoncrawl.org/},
  key = {commoncrawl}
}
@online{testdaten:pizzachilli2007,
	title={{P}izza\&{C}hili Corpus - Compressed Indexes and their Testbeds},
	author={Paolo Farragina and Gonzalo Navarro},
	urldate   = {01.01.2016},
	url={http://pizzachili.dcc.uchile.cl/index.html},
  key = {pizzachilli}
}

@online{sqlplottools,
	author = {Timo Bingmann},
	title={{SqlPlotTools}},
	url = {https://github.com/bingmann/sqlplot-tools},
	urldate = {15.02.2019}
}

@online{lido3,
	author = {Technische Universität Dortmund},
	title={{LiDO3}},
	url = {https://www.itmc.tu-dortmund.de/cms/de/dienste/hochleistungsrechnen/lido3/index.html},
	urldate = {04.03.2019}
}

@online{pss_intel,
	author = {Arch D. Robison},
	title={{A Parallel Stable Sort Using C++11 for TBB, Cilk Plus, and OpenMP}},
	url = {https://software.intel.com/en-us/articles/a-parallel-stable-sort-using-c11-for-tbb-cilk-plus-and-openmp},
	urldate = {28.02.2019}
}

@techreport{grundlagen:utf8,
  title={UTF-8, a transformation format of ISO 10646},
  author={Yergeau, Francois},
  year={2003}
}

%GPU
@InProceedings{osipovGPU,
author="Osipov, Vitaly",
title="Parallel Suffix Array Construction for Shared Memory Architectures",
booktitle="String Processing and Information Retrieval",
year="2012",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="379--384",
}

@article{deoGPU,
 author = {Deo, Mrinal and Keely, Sean},
 title = {Parallel Suffix Array and Least Common Prefix for the GPU},
 journal = {SIGPLAN Not.},
 issue_date = {August 2013},
 volume = {48},
 number = {8},
 month = feb,
 year = {2013},
 issn = {0362-1340},
 pages = {197--206},
 numpages = {10},
 publisher = {ACM},
 address = {New York, NY, USA},

} 
@article{wangGPU,
 author = {Wang, Leyuan and Baxter, Sean and Owens, John D.},
 title = {Fast Parallel Skew and Prefix-doubling Suffix Array Construction on the GPU},
 journal = {Concurr. Comput. : Pract. Exper.},
 issue_date = {August 2016},
 volume = {28},
 number = {12},
 month = aug,
 year = {2016},
 issn = {1532-0626},
 pages = {3466--3484},
 numpages = {19},
} 
[download]

@Comment{jabref-meta: databaseType:biblatex;}

@ARTICLE{merge:kruskal,
    author={Kruskal, Clyde P.},
    journal={IEEE Transactions on Computers},
    title={Searching, Merging, and Sorting in Parallel Computation},
    year={1983},
    volume={C-32},
    number={10},
    pages={942--946},
    month={Oct},
}

@article{merge:valiant,
    author = {Valiant, L.},
    title = {Parallelism in Comparison Problems},
    journal = {SIAM Journal on Computing},
    volume = {4},
    number = {3},
    pages = {348-355},
    year = {1975},
}

@inproceedings{parallelstdsort,
  title={The GNU libstdc++ parallel mode: software engineering considerations},
  author={Singler, Johannes and Konsik, Benjamin},
  booktitle={Proceedings of the 1st international workshop on Multicore software engineering},
  pages={15--22},
  year={2008},
  organization={ACM}
}

@online{sacabench:github,
  author = {Johannes Bahne and Nico Bertram and Marvin Böcker and Jonas Bode and Hermann Foot and Florian Grieskamp and Marvin Löbel and Oliver Magiera and Rosa Pink and David Piper and Christopher Poeplau},
 	title={GitHub: sacabench},
	url = {https://github.com/sacabench/sacabench},
	urldate = {28.02.2019}
}

@online{tudostat,
  author = {The tudocomp authors},
  title = {tudocomp - The TU Dortmund Compression Framework},
  url = {http://tudocomp.org},
  urldate = {2.3.2019}
}

@article{1000genomeproject,
  title={A global reference for human genetic variation},
  author={1000 Genomes Project Consortium and others},
  journal={Nature},
  volume={526},
  number={7571},
  pages={68--74},
  year={2015},
  publisher={Nature Publishing Group}
}

@online{commoncrawl,
  title={Common Crawl},
  author={{The Common Crawl Team}},
  year={2019},
  url={http://commoncrawl.org}
}