reference.bib

@misc{
fts4,
title = "SQLite FTS3 and FTS4 Extensions ",
note = "\url{http://sqlite.org/fts3.html}"
}

@misc{
csalib,
title = "Read and Researchmap",
note = "\url{http://researchmap.jp/sada/csalib/}"
}

@misc{
echizen,
title = "EchizenBlog-Zwei",
note = "\url{http://d.hatena.ne.jp/echizen_tm/20130928/1380363461}"
}

@misc{
sadakane,
title = "Read \& Researchmap",
note = "\url{http://researchmap.jp/sada/csalib/}"
}

@misc{
ssd,
title = "{SSD}向け全文検索エンジン",
note = "\url{http://www.slideshare.net/pfi/200948-3ssd}"
}

@misc{
ucsc,
title = "{UCSC} {G}enome {B}ioinformatics",
note = "\url{http://genome.ucsc.edu/}"
}

@Misc{massivethreads,
  key =		 {MassiveThreads},
  author =	 {Jun Nakashima},
  title =	 {{MassiveThreads: A Lightweight Thread Library for High Productivity Languages}},
  year =	 {2012}
}

@book{
ftiExtBook,
author = "Juha K{\"a}rkk{\"a}inen and S.Srinivasa Rao",
title = "Algorithms for Memory Hierarchies",
publisher = "Springer Berlin Heidelberg",
year = "2003"
}

@article{
kim_sa,
author = "D.K. Kim and J.S. Sim and H. Park and K. Park",
title = "Linear-time construction of suffix arrays",
journal = "CPM'03 Proceedings of the 14th annual conference on Combinatorial pattern matching",
pages = "186--199",
year = "2003"
}


@article{
dc3,
author = "Juha K{\"a}rkk{\"a}inen and Peter Sanders and Stefan Burkhardt",
title = "LinearWork Suffix Array Construction",
journal = "Journal of the ACM",
volume = "53",
pages = "918--936",
year = "2006"
}

@article{
dc3_original,
author = "Stefan Burkhardt and Juha K{\"a}rkk{\"a}inen",
title = "Fast Lightweight Suffix Array Construction and Checking",
journal = "CPM'03 Proceedings of the 14th annual conference on Combinatorial pattern matching",
pages = "55--69",
year = "2003"
}

@article{
pdc3,
author = "Fabian Kulla and Peter Sanders",
title = "Scalable parallel suffix array construction",
journal = "Parallel Computing",
volume = "33",
pages = "605--612",
year = "2007"
}

@article{
ka,
author = "Pang Ko and Srinivas Aluru",
title = "Space Efficient Linear Time Construction of Suffix Arrays",
journal = "In Proceedings 14th CPM, LNCS 2676",
pages = "200--210",
year = "2003"
}

@article{
sa_is,
author = "Ge Nong and Sen Zhang and Wai Hong Chan",
title = "Linear Suffix Array Construction by Almost Pure Induced-Sorting",
journal = "Data Compression Conference",
pages = "193--202",
year = "2009"
}

@article{
gp,
author = "Nicholas Lester and Alistair Mofatt and Justin Zobel",
title = "Fast on-line index construction by geometric partitioning",
journal = "Proceedings of the 14th ACM international conference on Information and knowledge management - CIKM '05",
pages = "776--783",
year = "2005"
}

@article{
incremental,
author = "吉原 潤 and 加藤 和彦",
title = "{WWW}検索エンジンのためのインクリメンタルな全文検索インデックス更新方式",
journal = "情報処理学会論文誌",
volume = "40",
pages = "112--125",
year = "1999"
}

@article{
dincremental,
author = "吉原 潤 and 高橋 慎 and 奈良崎 清彦 and 加藤 和彦",
title = "インクリメンタルな更新を伴う全文検索インデックスの分散並列処理方式",
journal = "情報処理学会研究報告. データベース・システム研究会報告",
pages = "41--48",
year = "2000"
}

@article{
succinct,
author = "岡野原 大輔",
title = "圧縮したまま検索 ─ Succinct Data Structure ─",
journal = "情報処理学会誌",
volume = "53",
number = "5",
pages = "504--512",
year = "2012"
}

@article{
cfi_survey,
author = "Gonzalo Navarro and Veli M{\"a}kinen",
title = "Compressed Full-Text Indexes",
journal = "ACM Computing Surveys",
volume = "39",
number = "1",
year = "2007"
}

@article{
suffix_array,
author = "Udi Manber and Gene Myers",
title = "Suffix arrays: A new method for on-line string searches",
journal = "SODA '90",
pages = "319--327",
year = "1990"
}

@article{
fmi,
author = "P. Ferragina and  G. Manzini ",
title = "Opportunistic data structures with applications",
journal = "FOCS '00",
pages = "390--398",
year = "2000"
}

@article{
csa,
author = "Roberto Grossi and Jeffrey Scott Vitter",
title = "Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching",
journal = "STOC '00 Proceedings of the thirty-second annual ACM symposium on Theory of computing",
pages = "397--406",
year = "2000"
}

@article{
wavelet_matrix,
author = "Francisco Claude and Gonzalo Navarro",
title = "The Wavelet Matrix",
journal = "Proc. SPIRE'12",
pages = "167--179",
year = "2012"
}

@article{
lwBwt,
author = "Paolo Ferragina Travis Gagie and Giovanni Manzini",
title = "Lightweight Data Indexing and Compression in External Memory",
journal = "Algorithmica",
volume = "63",
number = "3",
pages = "707--730",
year = "2012"
}

@article{
sampleSortBWT,
author = "Juha K{\"a}rkk{\"a}inen",
title = "Fast BWT in small space by blockwise suffix sorting",
journal = "Theoretical Computer Science",
volume = "387",
number = "3",
pages = "249--257",
year = "2007"
}

@article{
isBwt,
author = "Daisuke Okanohara and Kunihiko Sadakane",
title = "A Linear-Time Burrows-Wheeler Transform Using Induced Sorting",
journal = "SPIRE '09",
pages = "90--101",
year = "2009"
}

@article{
mrBwt,
author = "Rohith K. Menon and  Goutham P. Bhat and  Michael C. Schatz",
title = "Rapid parallel genome indexing with MapReduce",
journal = "MapReduce '11 Proceedings of the second international workshop on MapReduce and its applications ",
pages = "51--58",
year = "2011"
}

@article{
dcnu,
author = "Charles J. Colbourn and Alan C.H. Ling",
title = "Quorums from difference covers",
journal = "Information Processing Letters",
volume="75",
pages = "9--12",
year = "2000"
}

@TECHREPORT{
bwt,
author = {M. Burrows and D. J. Wheeler and M. Burrows and D. J. Wheeler},
title = {A block sorting lossless data compression algorithm},
year = {1994}
}

@article{
wavelet_tree,
author = "Roberto Grossi and Ankur Gupta",
title = "High-order entropy-compressed text indexes",
journal = "SODA '03 Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms",
pages = "841--850 ",
year = "2003"
}

@book{
kousoku,
author = "岡野原 大輔",
title = "高速文字列解析の世界",
publisher = "岩波書店",
year = "2012"
}

@article{
myth,
author = "中島潤 and 田浦健次朗", 
title = "高効率な I/O と軽量性を両立させるマルチスレッド処理系",
journal = "情報処理学会論文誌 プログラミング (PRO)",
volume = 4,
pages = "13--26",
year = "2011"
}

@article{
mkqsort,
author = "J. L. Bentley and R. Sedgewick" ,
title = "Fast algorithms for sorting and searching strings" ,
journal = "In Proceedings of the 8th ACM–SIAM Symposium on Discrete Algorithms" ,
pages = "360--369",
year = 1997
}

@misc{
pizzachili,
title = "Pizza{\&}{C}hili {C}orpus",
note = "\url{http://pizzachili.dcc.uchile.cl/index.html}"
}

@article{
steCSA,
author = "Wing-Kai Hon and Tak-Wah Lam and Kunihiko Sadakane and Wing-Kin Sung and Siu-Ming Yiu",
title = "A space and time efficient algorithm for constructing compressed suffix arrays",
journal = "Algorithmica",
pages = "23--36",
year = "2007"
}

@article{
seBWTgenome,
author = "Ross A. Lippert and Clark M. Mobarry and Brian P. Walenz",
title = "A Space-Efficient Construction of the Burrows–Wheeler Transform for Genomic Data",
journal = "Computational Biology",
year = "2005"
}

@article{
four_russian,
author="Arlazarov, V and Dinic, E and Konrod, M and Faradzev, I",
title="On economic construction of the transitive closure of a directed graph",
year="1975",
journal="Sov.Math. Dokl",
pages="1209--1210"
}

@article{
pssort,
author="Timo Bingmann and Peter Sanders",
title="Parallel String Sample Sort",
year="2013",
journal="arXiv preprint arXiv:1305.1157"
}

@inproceedings{
cilk,
 author = {Blumofe, Robert D. and Joerg, Christopher F. and Kuszmaul, Bradley C. and Leiserson, Charles E. and Randall, Keith H. and Zhou, Yuli},
 title = {{Cilk: An Efficient Multithreaded Runtime System}},
 booktitle = {Proc. of PPoPP '95},
 year = {1995},
 isbn = {0-89791-700-6},
 location = {Santa Barbara, California, USA},
 pages = {207--216},
 numpages = {10},
 doi = {10.1145/209936.209958},
 acmid = {209958},
}

@article{
work_stealing,
 author = {Blumofe, Robert D. and Leiserson, Charles E.},
 title = {{Scheduling Multithreaded Computations by Work Stealing}},
 journal = {J. ACM},
 issue_date = {Sept. 1999},
 volume = {46},
 number = {5},
 month = sep,
 year = {1999},
 issn = {0004-5411},
 pages = {720--748},
 numpages = {29},
 doi = {10.1145/324133.324234},
 acmid = {324234},
 keywords = {critical-path length, multiprocessor, multithreading, randomized algorithm, thread scheduling, work stealing},
}

@article{
twoSA,
author = "Ge Nong and Sen Zhang and Wai Hong Chan",
title = "Two Efficient Algorithms for Linear Suffix Array Construction",
journal = "IEEE Transactions on Computers",
volume = {60},
number = {10},
year = "2011"
}

@article{
bwa,
author = "Heng Li and Richard Durbin",
title = "Fast and accurate short read alignment with {B}urrows-{W}heeler transform",
journal = "Bioinformatics",
year = "2009",
pages = "1754--1760"
}

@book{
international,
author = "C.S. Langham",
title = "国際学会Englishスピーキング・エクササイズ 講演・発表・応答",
publisher = "医歯薬出版",
year = "2010"
}

@article{
suc_bit,
author = "David R. Clark and J. Ian Munro",
title = "Efficient suffix trees on secondary storage",
journal = "Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms",
year = "1999",
pages = "383--391"
}

@article{DBLP:journals/corr/abs-1304-6023,
  author    = {Gonzalo Navarro},
  title     = {Spaces, Trees and Colors: The Algorithmic Landscape of Document
               Retrieval on Sequences},
  journal   = {CoRR},
  volume    = {abs/1304.6023},
  year      = {2013},
  ee        = {http://arxiv.org/abs/1304.6023},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Muthukrishnan:2002:EAD:545381.545469,
 author = {Muthukrishnan, S.},
 title = {Efficient Algorithms for Document Retrieval Problems},
 booktitle = {Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '02},
 year = {2002},
 isbn = {0-89871-513-X},
 location = {San Francisco, California},
 pages = {657--666},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=545381.545469},
 acmid = {545469},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@inproceedings{Navarro:2012:TKD:2095116.2095200,
 author = {Navarro, Gonzalo and Nekrich, Yakov},
 title = {Top-k Document Retrieval in Optimal Time and Linear Space},
 booktitle = {Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '12},
 year = {2012},
 location = {Kyoto, Japan},
 pages = {1066--1077},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=2095116.2095200},
 acmid = {2095200},
 publisher = {SIAM},
} 

@inproceedings{Culpepper:2012:EIT:2348283.2348317,
 author = {Culpepper, J. Shane and Petri, Matthias and Scholer, Falk},
 title = {Efficient In-memory Top-k Document Retrieval},
 booktitle = {Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval},
 series = {SIGIR '12},
 year = {2012},
 isbn = {978-1-4503-1472-5},
 location = {Portland, Oregon, USA},
 pages = {225--234},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/2348283.2348317},
 doi = {10.1145/2348283.2348317},
 acmid = {2348317},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {data storage representations, text compression, text indexing},
} 

@inproceedings{Makinen:2000:CSA:647819.736207,
 author = {M\"{a}kinen, Veli},
 title = {Compact Suffix Array},
 booktitle = {Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching},
 series = {COM '00},
 year = {2000},
 isbn = {3-540-67633-3},
 pages = {305--319},
 numpages = {15},
 url = {http://dl.acm.org/citation.cfm?id=647819.736207},
 acmid = {736207},
 publisher = {Springer-Verlag},
 address = {London, UK, UK},
} 

@article{Makinen:2003:CSA:2370956.2370966,
 author = {M\"{a}kinen, Veli},
 title = {Compact Suffix Array \&Mdash; A Space-Efficient Full-Text Index},
 journal = {Fundam. Inf.},
 issue_date = {January 2003},
 volume = {56},
 number = {1-2},
 month = jan,
 year = {2003},
 issn = {0169-2968},
 pages = {191--210},
 numpages = {20},
 url = {http://dl.acm.org/citation.cfm?id=2370956.2370966},
 acmid = {2370966},
 publisher = {IOS Press},
 address = {Amsterdam, The Netherlands, The Netherlands},
 keywords = {Suffix array, full-text index, index compression, string matching},
} 

@article{Dean:2008:MSD:1327452.1327492,
 author = {Dean, Jeffrey and Ghemawat, Sanjay},
 title = {MapReduce: Simplified Data Processing on Large Clusters},
 journal = {Commun. ACM},
 issue_date = {January 2008},
 volume = {51},
 number = {1},
 month = jan,
 year = {2008},
 issn = {0001-0782},
 pages = {107--113},
 numpages = {7},
 url = {http://doi.acm.org/10.1145/1327452.1327492},
 doi = {10.1145/1327452.1327492},
 acmid = {1327492},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{Raman:2002:SID:545381.545411,
 author = {Raman, Rajeev and Raman, Venkatesh and Rao, S. Srinivasa},
 title = {Succinct Indexable Dictionaries with Applications to Encoding K-ary Trees and Multisets},
 booktitle = {Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '02},
 year = {2002},
 isbn = {0-89871-513-X},
 location = {San Francisco, California},
 pages = {233--242},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=545381.545411},
 acmid = {545411},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@INPROCEEDINGS{Makinen04run-lengthfm-index,
    author = {Veli M\"{a}kinen and Gonzalo Navarro},
    title = {Run-Length FM-index},
    booktitle = {In Proc. DIMACS Workshop: “The Burrows-Wheeler Transform: Ten Years Later},
    year = {2004},
    pages = {17--19}
}

@incollection{
alphabet_friendly,
year={2004},
isbn={978-3-540-23210-0},
booktitle={String Processing and Information Retrieval},
volume={3246},
series={Lecture Notes in Computer Science},
editor={Apostolico, Alberto and Melucci, Massimo},
doi={10.1007/978-3-540-30213-1_23},
title={An Alphabet-Friendly FM-Index},
url={http://dx.doi.org/10.1007/978-3-540-30213-1_23},
publisher={Springer Berlin Heidelberg},
author={Ferragina, Paolo and Manzini, Giovanni and M\"{a}kinen, Veli and Navarro, Gonzalo},
pages={150-160}
}