{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T19:00:24Z","timestamp":1771614024438,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T00:00:00Z","timestamp":1475625600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Marie Sklodowska-Curie grant","award":["690941"],"award-info":[{"award-number":["690941"]}]},{"name":"Conicyt scholarship for PhD","award":["21120974"],"award-info":[{"award-number":["21120974"]}]},{"name":"Conicyt scholarship for PhD","award":["63130228"],"award-info":[{"award-number":["63130228"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s10115-016-1000-6","type":"journal-article","created":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T19:32:27Z","timestamp":1475695947000},"page":"1043-1066","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Parallel construction of wavelet trees on multicore architectures"],"prefix":"10.1007","volume":"51","author":[{"given":"Jos\u00e9","family":"Fuentes-Sep\u00falveda","sequence":"first","affiliation":[]},{"given":"Erick","family":"Elejalde","sequence":"additional","affiliation":[]},{"given":"Leo","family":"Ferres","sequence":"additional","affiliation":[]},{"given":"Diego","family":"Seco","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,5]]},"reference":[{"issue":"5","key":"1000_CR1","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.ipm.2011.01.008","volume":"48","author":"D Arroyuelo","year":"2012","unstructured":"Arroyuelo D, Costa VG, Gonz\u00e1lez S, Mar\u00edn M, Oyarz\u00fan M (2012) Distributed search based on self-indexed compressed text. Inf Process Manag 48(5):819\u2013827. doi:\n                        10.1016\/j.ipm.2011.01.008","journal-title":"Inf Process Manag"},{"key":"1000_CR2","unstructured":"Bingmann T (2015) malloc_count\u2014tools for runtime memory usage analysis and profiling. \n                        http:\/\/panthema.net\/2013\/malloc_count\/\n                        \n                     (2013). Last accessed: 17 Jan 2015"},{"issue":"5","key":"1000_CR3","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"RD Blumofe","year":"1999","unstructured":"Blumofe RD, Leiserson CE (1999) Scheduling multithreaded computations by work stealing. J ACM 46(5):720\u2013748. doi:\n                        10.1145\/324133.324234","journal-title":"J ACM"},{"issue":"5","key":"1000_CR4","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/j.is.2013.01.005","volume":"38","author":"NR Brisaboa","year":"2013","unstructured":"Brisaboa NR, Luaces MR, Navarro G, Seco D (2013) Space-efficient representations of rectangle datasets supporting orthogonal range querying. Inf Syst 38(5):635\u2013655. doi:\n                        10.1016\/j.is.2013.01.005","journal-title":"Inf Syst"},{"key":"1000_CR5","unstructured":"Burrows M, Wheeler DJ (1994) A block-sorting lossless data compression algorithm. Tech. rep., Digital Equipment Corporation"},{"key":"1000_CR6","unstructured":"Claude F (2011) A compressed data structure library. \n                        https:\/\/github.com\/fclaude\/libcds\n                        \n                    . Last accessed: 13 August 2015"},{"key":"1000_CR7","doi-asserted-by":"publisher","unstructured":"Claude F, Navarro G (2009) Practical rank\/select queries over arbitrary sequences. In: SPIRE. Springer, Berlin, pp 176\u2013187. doi:\n                        10.1007\/978-3-540-89097-3_18","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"1000_CR8","doi-asserted-by":"publisher","unstructured":"Claude F, Navarro G (2012) The wavelet matrix. In: SPIRE, vol 7608. Springer, Berlin, pp 167\u2013179. doi:\n                        10.1007\/978-3-642-34109-0_18","DOI":"10.1007\/978-3-642-34109-0_18"},{"key":"1000_CR9","doi-asserted-by":"publisher","unstructured":"Claude F, Nicholson PK, Seco D (2011) Space efficient wavelet tree construction. In: SPIRE, vol 7024. Springer, Berlin, pp 185\u2013196","DOI":"10.1007\/978-3-642-24583-1_19"},{"key":"1000_CR10","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn., chap. Multithreaded algorithms. The MIT Press, Cambridge, pp 772\u2013812"},{"key":"1000_CR11","doi-asserted-by":"publisher","unstructured":"Faro S, K\u00fclekci MO (2012) Fast multiple string matching using streaming SIMD extensions technology. In: SPIRE. Springer, Berlin, pp 217\u2013228. doi:\n                        10.1007\/978-3-642-34109-0_23","DOI":"10.1007\/978-3-642-34109-0_23"},{"key":"1000_CR12","doi-asserted-by":"publisher","unstructured":"Ferragina P, Manzini G (2000) Opportunistic data structures with applications. In: Proceedings of the 41st annual symposium on foundations of computer science, FOCS \u201900. IEEE Computer Society, Washington, DC, USA, p 390. \n                        http:\/\/dl.acm.org\/citation.cfm?id=795666.796543","DOI":"10.1109\/SFCS.2000.892127"},{"key":"1000_CR13","doi-asserted-by":"publisher","unstructured":"Ferragina P, Manzini G, M\u00e4kinen V, Navarro G (2004) String processing and information retrieval: 11th international conference, SPIRE 2004, Padova, Italy, 5\u20138 October 2004. Proceedings, chap. An Alphabet-Friendly FM-Index. Springer, Berlin, pp 150\u2013160. doi:\n                        10.1007\/978-3-540-30213-1_23","DOI":"10.1007\/978-3-540-30213-1_23"},{"issue":"2","key":"1000_CR14","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P Ferragina","year":"2007","unstructured":"Ferragina P, Manzini G, M\u00e4kinen V, Navarro G (2007) Compressed representations of sequences and full-text indexes. ACM Trans Algorithms 3(2):20. doi:\n                        10.1145\/1240233.1240243","journal-title":"ACM Trans Algorithms"},{"key":"1000_CR15","doi-asserted-by":"publisher","unstructured":"Fuentes-Sep\u00falveda J, Elejalde E, Ferres L, Seco D (2014) Efficient wavelet tree construction and querying for multicore architectures. In: Gudmundsson J, Katajainen J (eds) Experimental algorithms, Lecture Notes in Computer Science, vol 8504. Springer, Berlin, pp 150\u2013161. doi:\n                        10.1007\/978-3-319-07959-2_13","DOI":"10.1007\/978-3-319-07959-2_13"},{"key":"1000_CR16","unstructured":"Gog S (2015) Succinct data structure library 2.0. \n                        https:\/\/github.com\/simongog\/sdsl-lite\n                        \n                     (2012). Last accessed: 17 Jan 2015"},{"key":"1000_CR17","unstructured":"Gonz\u00e1lez R, Grabowski S, M\u00e4kinen V, Navarro G (2005) Practical implementation of rank and select queries. In: WEA. CTI Press, Greece, pp 27\u201338. Poster"},{"key":"1000_CR18","unstructured":"Grossi R, Gupta A, Vitter JS (2003) High-order entropy-compressed text indexes. In: SODA. Soc. Ind. Appl. Math., Philadelphia, pp 841\u2013850"},{"issue":"2","key":"1000_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/jpdc.2000.1678","volume":"61","author":"DR Helman","year":"2001","unstructured":"Helman DR, J\u00e1J\u00e1 J (2001) Prefix computations on symmetric multiprocessors. J Parallel Distrib Comput 61(2):265\u2013278. doi:\n                        10.1006\/jpdc.2000.1678","journal-title":"J Parallel Distrib Comput"},{"key":"1000_CR20","unstructured":"Illumina, Inc. (2016) An introduction to next-generation sequencing technology. \n                        http:\/\/www.illumina.com\/content\/dam\/illumina-marketing\/documents\/products\/illumina_sequencing_introduction.pdf"},{"key":"1000_CR21","doi-asserted-by":"publisher","unstructured":"Ladra S, Pedreira O, Duato J, Brisaboa NR (2012) Exploiting SIMD instructions in current processors to improve classical string algorithms. In: ADBIS. Springer, Berlin, pp 254\u2013267. doi:\n                        10.1007\/978-3-642-33074-2_19","DOI":"10.1007\/978-3-642-33074-2_19"},{"issue":"2","key":"1000_CR22","doi-asserted-by":"publisher","first-page":"585","DOI":"10.2298\/CSIS110606004M","volume":"9","author":"C Makris","year":"2012","unstructured":"Makris C (2012) Wavelet trees: a survey. Comput Sci Inf Syst 9(2):585\u2013625","journal-title":"Comput Sci Inf Syst"},{"issue":"1","key":"1000_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/272991.272995","volume":"8","author":"M Matsumoto","year":"1998","unstructured":"Matsumoto M, Nishimura T (1998) Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans Model Comput Simul 8(1):3\u201330. doi:\n                        10.1145\/272991.272995","journal-title":"ACM Trans Model Comput Simul"},{"key":"1000_CR24","doi-asserted-by":"publisher","unstructured":"Navarro G (2012) Wavelet trees for all. In: CPM. Springer, Berlin, pp 2\u201326. doi:\n                        10.1007\/978-3-642-31265-6_2","DOI":"10.1007\/978-3-642-31265-6_2"},{"key":"1000_CR25","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2012.11.031","volume":"482","author":"G Navarro","year":"2013","unstructured":"Navarro G, Nekrich Y, Russo LMS (2013) Space-efficient data-analysis queries on grids. Theor Comput Sci 482:60\u201372. doi:\n                        10.1016\/j.tcs.2012.11.031","journal-title":"Theor Comput Sci"},{"key":"1000_CR26","unstructured":"Pantaleoni J, Subtil N (2016) Nvbio library. \n                        http:\/\/nvlabs.github.io\/nvbio\/index.html\n                        \n                    . Accessed 12 April 2016"},{"issue":"4","key":"1000_CR27","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman R, Raman V, Satti SR (2007) Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans Algorithms 3(4):43. doi:\n                        10.1145\/1290672.1290680","journal-title":"ACM Trans Algorithms"},{"key":"1000_CR28","doi-asserted-by":"publisher","unstructured":"Schnattinger T, Ohlebusch E, Gog S (2012) Bidirectional search in a string with wavelet trees and bidirectional matching statistics. Inf Comput 213:13\u201322. doi:\n                        10.1016\/j.ic.2011.03.007\n                        \n                    . \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540112000235\n                        \n                    . Special Issue: Combinatorial Pattern Matching (CPM 2010)","DOI":"10.1016\/j.ic.2011.03.007"},{"key":"1000_CR29","doi-asserted-by":"publisher","unstructured":"Shun J (2015) Parallel wavelet tree construction. In: Proceedings of the IEEE data compression conference, Utah, USA, pp 63\u201372. doi:\n                        10.1109\/DCC.2015.7","DOI":"10.1109\/DCC.2015.7"},{"key":"1000_CR30","unstructured":"Singer J (2012) A wavelet tree based fm-index for biological sequences in SeqAn. Master\u2019s thesis, Freie Universit\u00e4t Berlin. \n                        http:\/\/www.mi.fu-berlin.de\/wiki\/pub\/ABI\/FMIndexThesis\/FMIndex.pdf"},{"key":"1000_CR31","doi-asserted-by":"publisher","unstructured":"Tischler G (2011) On wavelet tree construction. In: CPM. Springer, Berlin, pp 208\u2013218","DOI":"10.1007\/978-3-642-21458-5_19"},{"key":"1000_CR32","doi-asserted-by":"publisher","unstructured":"Touati SAA, Worms J, Briais S (2013) The Speedup-Test: a statistical methodology for program speedup analysis and computation. Concurr Comput Pract Exp 25(10):1410\u20131426. doi:\n                        10.1002\/cpe.2939\n                        \n                    . \n                        https:\/\/hal.inria.fr\/hal-00764454\n                        \n                    . Article first published online: 15 Oct 2012","DOI":"10.1002\/cpe.2939"},{"key":"1000_CR33","doi-asserted-by":"publisher","unstructured":"V\u00e4lim\u00e4ki N, M\u00e4kinen V (2007) Space-efficient algorithms for document retrieval. In: CPM, LNCS, vol. 4580. Springer, Berlin, pp 205\u2013215. doi:\n                        10.1007\/978-3-540-73437-6_22","DOI":"10.1007\/978-3-540-73437-6_22"},{"key":"1000_CR34","unstructured":"Wetterstrand KA (2016) DNA sequencing costs: data from the NHGRI genome sequencing program (GSP). \n                        http:\/\/www.genome.gov\/sequencingcosts\n                        \n                    . Accessed 12 April 2016"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-016-1000-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-016-1000-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-016-1000-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T16:33:12Z","timestamp":1494001992000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-016-1000-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,5]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["1000"],"URL":"https:\/\/doi.org\/10.1007\/s10115-016-1000-6","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,5]]}}}