{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:32:17Z","timestamp":1762867937153,"version":"3.37.3"},"reference-count":78,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T00:00:00Z","timestamp":1569888000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T00:00:00Z","timestamp":1570579200000},"content-version":"vor","delay-in-days":8,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17H01693","JPMJCR1402"],"award-info":[{"award-number":["17H01693","JPMJCR1402"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17K20023JST"],"award-info":[{"award-number":["17K20023JST"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Rev Socionetwork Strat"],"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:p>A data structure is called succinct if its asymptotical space requirement matches the original data size. The development of succinct data structures is an important factor to deal with the explosively increasing big data. Moreover, wider variations of big data have been produced in various fields recently and there is a substantial need for the development of more application-specific succinct data structures. In this study, we review the recently proposed application-oriented succinct data structures motivated by big data applications in three different fields: privacy-preserving computation in cryptography, genome assembly in bioinformatics, and work space reduction for compressed communications.<\/jats:p>","DOI":"10.1007\/s12626-019-00045-1","type":"journal-article","created":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T17:05:28Z","timestamp":1570640728000},"page":"227-236","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Application-Oriented Succinct Data Structures for Big Data"],"prefix":"10.1007","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1514-5766","authenticated-orcid":false,"given":"Tetsuo","family":"Shibuya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,9]]},"reference":[{"issue":"6","key":"45_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: An aid to bibliographic search. Communications of the ACM, 18(6), 333\u2013340.","journal-title":"Communications of the ACM"},{"key":"45_CR2","unstructured":"Asharov, G., Komargodski, I., Lin, W. K., Nayak, K., & Shi, E. (2018). Optorama: Optimal \noblivious ram. In Cryptology ePrint Archive, Report 2018\/892. \n                    https:\/\/eprint.iacr.org\/2018\/892\n                    \n                  ."},{"key":"45_CR3","doi-asserted-by":"crossref","unstructured":"Baker, B.S. (1995). On finding duplication and near-duplication in large software systems. In Reverse engineering, proceedings of 2nd working conference on (pp. 86\u201395). IEEE.","DOI":"10.1109\/WCRE.1995.514697"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., M\u00e4kinen, V., & Previtali, M. (2016). Fully dynamic de Bruijn graphs. In International symposium on string processing and information retrieval (pp. 145\u2013152). Springer.","DOI":"10.1007\/978-3-319-46049-9_14"},{"key":"45_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., M\u00e4kinen, V., Previtali, M., & Puglisi, S.J. (2016). Bidirectional variable-order de Bruijn graphs. In Latin American Symposium on Theoretical Informatics (pp. 164\u2013178). Springer.","DOI":"10.1007\/978-3-662-49529-2_13"},{"issue":"4","key":"45_CR6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E. D., Munro, J. I., Raman, R., Raman, V., & Rao, S. S. (2005). Representing trees of higher degree. Algorithmica, 43(4), 275\u2013292.","journal-title":"Algorithmica"},{"issue":"12","key":"45_CR7","doi-asserted-by":"publisher","first-page":"1492","DOI":"10.1093\/bioinformatics\/btt178","volume":"29","author":"I Birol","year":"2013","unstructured":"Birol, I., Raymond, A., Jackman, S. D., Pleasance, S., Coope, R., Taylor, G. A., et al. (2013). Assembling the 20 gb white spruce (picea glauca) genome from whole-genome shotgun sequencing data. Bioinformatics, 29(12), 1492\u20131497.","journal-title":"Bioinformatics"},{"issue":"7","key":"45_CR8","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B. H. (1970). Space\/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422\u2013426.","journal-title":"Communications of the ACM"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Boucher, C., Bowe, A., Gagie, T., Puglisi, S.J., & Sadakane, K. (2015). Variable-order de Bruijn graphs. In 2015 data compression conference (pp. 383\u2013392). IEEE.","DOI":"10.1109\/DCC.2015.70"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Bowe, A., Onodera, T., Sadakane, K., & Shibuya, T. (2012). Succinct de Bruijn graphs. In International workshop on algorithms in bioinformatics (pp. 225\u2013235). Springer.","DOI":"10.1007\/978-3-642-33122-0_18"},{"key":"45_CR11","unstructured":"Boyle, E., & Naor, M. (2016). Is there an oblivious ram lower bound? In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, ITCS \u201916 (pp. 357\u2013368)."},{"issue":"49","key":"45_CR12","first-page":"758","volume":"49","author":"NG de Bruijn","year":"1946","unstructured":"de Bruijn, N. G. (1946). A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 49(49), 758\u2013764.","journal-title":"Koninklijke Nederlandse Akademie v. Wetenschappen"},{"key":"45_CR13","unstructured":"Burrows, M., & Wheeler, D. J. (1994). A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, Palo Alto."},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"Cash, D., Grubbs, P., Perry, J., & Ristenpart, T. (2015). Leakage-abuse attacks against searchable encryption. In Proceedings of SIGSAC Conference on Computer and Communications Security (CCS) (pp. 668\u2013669).","DOI":"10.1145\/2810103.2813700"},{"key":"45_CR15","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.14778\/2994509.2994528","volume":"9","author":"Z Chang","year":"2016","unstructured":"Chang, Z., Xie, D., & Li, F. (2016). Oblivious ram: A dissection and experimental evaluation. Proceedings of the VLDB Endowment, 9, 1113\u20131124.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"45_CR16","doi-asserted-by":"crossref","unstructured":"Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., & Medvedev, P. (2014). On the representation of de Bruijn graphs. In International conference on research in computational molecular biology (pp. 35\u201355). Springer.","DOI":"10.1007\/978-3-319-05269-4_4"},{"issue":"1","key":"45_CR17","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/1748-7188-8-22","volume":"8","author":"R Chikhi","year":"2013","unstructured":"Chikhi, R., & Rizk, G. (2013). Space-efficient and exact de Bruijn graph representation based on a bloom filter. Algorithms for Molecular Biology, 8(1), 22.","journal-title":"Algorithms for Molecular Biology"},{"issue":"4","key":"45_CR18","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1093\/bioinformatics\/btq697","volume":"27","author":"TC Conway","year":"2011","unstructured":"Conway, T. C., & Bromage, A. J. (2011). Succinct data structures for assembling large genomes. Bioinformatics, 27(4), 479\u2013486.","journal-title":"Bioinformatics"},{"issue":"2","key":"45_CR19","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1089\/gen.37.02.14","volume":"37","author":"B Davis-Dusenbery","year":"2017","unstructured":"Davis-Dusenbery, B. (2017). Precision medicine research in the million-genome era: Gaining the most from research with multi-omic data in the million-genome era. Genetic Engineering & Biotechnology News, 37(2), 26\u201327.","journal-title":"Genetic Engineering & Biotechnology News"},{"key":"45_CR20","doi-asserted-by":"crossref","unstructured":"Devadas, S., van Dijk, M., Fletcher, C.W., Ren, L., Shi, E., & Wichs, D. (2016). Onion oram: A constant bandwidth blowup oblivious ram. In Proceedings of the 13th international conference on theory of cryptography conference (pp. 145\u2013174). Springer.","DOI":"10.1007\/978-3-662-49099-0_6"},{"issue":"12","key":"45_CR21","doi-asserted-by":"publisher","first-page":"e1003345","DOI":"10.1371\/journal.pcbi.1003345","volume":"9","author":"S El-Metwally","year":"2013","unstructured":"El-Metwally, S., Hamza, T., Zakaria, M., & Helmy, M. (2013). Next-generation sequence assembly: Four stages of data processing and computational challenges. PLoS Computational biology, 9(12), e1003345.","journal-title":"PLoS Computational biology"},{"key":"45_CR22","doi-asserted-by":"crossref","unstructured":"Farach, M. (1997). Optimal suffix tree construction with large alphabets. In Foundations of computer science. Proceedings, 38th annual symposium on (pp. 137\u2013143). IEEE.","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"1","key":"45_CR23","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1613676.1613680","volume":"57","author":"P Ferragina","year":"2009","unstructured":"Ferragina, P., Luccio, F., Manzini, G., & Muthukrishnan, S. (2009). Compressing and indexing labeled trees, with applications. Journal of the ACM (JACM), 57(1), 4.","journal-title":"Journal of the ACM (JACM)"},{"key":"45_CR24","doi-asserted-by":"crossref","unstructured":"Ferragina, P., & Manzini, G. (2000). Opportunistic data structures with applications. In Foundations of computer science. Proceedings, 41st annual symposium on (pp. 390\u2013398). IEEE.","DOI":"10.1109\/SFCS.2000.892127"},{"key":"45_CR25","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2017.06.016","volume":"698","author":"T Gagie","year":"2017","unstructured":"Gagie, T., Manzini, G., & Sir\u00e9n, J. (2017). Wheeler graphs: A framework for bwt-based data structures. Theoretical Computer Science, 698, 67\u201378.","journal-title":"Theoretical Computer Science"},{"key":"45_CR26","unstructured":"Ganguly, A., Hon, W.K., Sadakane, K., Shah, R., Thankachan, S.V., & Yang, Y. (2016). Space-efficient dictionaries for parameterized and order-preserving pattern matching. In LIPIcs-Leibniz International Proceedings in Informatics (vol.\u00a054). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"issue":"2","key":"45_CR27","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1109\/MCSE.2017.32","volume":"19","author":"PA Gargini","year":"2017","unstructured":"Gargini, P. A. (2017). How to successfully overcome inflection points, or long live Moore\u2019s law. Computing in Science & Engineering, 19(2), 51\u201362.","journal-title":"Computing in Science & Engineering"},{"key":"45_CR28","doi-asserted-by":"crossref","unstructured":"Goldreich, O. (1987). Towards a theory of software protection and simulation by oblivious rams. In Proceedings of symposium on theory of computing (STOC) (pp. 182\u2013194).","DOI":"10.1145\/28395.28416"},{"issue":"3","key":"45_CR29","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/233551.233553","volume":"43","author":"O Goldreich","year":"1996","unstructured":"Goldreich, O., & Ostrovsky, R. (1996). Software protection and simulation on oblivious rams. Journal of the ACM (JACM), 43(3), 431\u2013473.","journal-title":"Journal of the ACM (JACM)"},{"key":"45_CR30","doi-asserted-by":"crossref","unstructured":"Howe, A.C., Jansson, J.K., Malfatti, S.A., Tringe, S.G., Tiedje, J.M., & Brown, C.T. (2014). Tackling soil diversity with the assembly of large, complex metagenomes. In Proceedings of the National Academy of Sciences (p. 201402564).","DOI":"10.1073\/pnas.1402564111"},{"key":"45_CR31","unstructured":"Islam, M., Kuzu, M., & Kantarcioglu, M. (2012). Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In Proceedings of network and distributed system security symposium (NDSS)."},{"key":"45_CR32","doi-asserted-by":"publisher","first-page":"gr-214346","DOI":"10.1101\/gr.214346.116","volume":"27","author":"SD Jackman","year":"2017","unstructured":"Jackman, S. D., Vandervalk, B. P., Mohamadi, H., Chu, J., Yeo, S., Hammond, S. A., et al. (2017). Abyss 2.0: Resource-efficient \nassembly of large genomes using a bloom filter. Genome Research, 27, gr-214346.","journal-title":"Genome Research"},{"key":"45_CR33","doi-asserted-by":"crossref","unstructured":"Jacobson, G. (1989). Space-efficient static trees and graphs. In Foundations of Computer Science, 30th Annual Symposium on (pp. 549\u2013554). IEEE.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"45_CR34","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., & Sanders, P. (2003). Simple linear work suffix array construction. In International colloquium on automata, languages, and programming (pp. 943\u2013955). Springer.","DOI":"10.1007\/3-540-45061-0_73"},{"issue":"2","key":"45_CR35","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D. E., Morris, J. H, Jr., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323\u2013350.","journal-title":"SIAM Journal on Computing"},{"key":"45_CR36","doi-asserted-by":"crossref","unstructured":"Ko, P., & Aluru, S. (2003). Space efficient linear time construction of suffix arrays. In Annual Symposium on Combinatorial Pattern Matching  (pp. 200\u2013210). Springer.","DOI":"10.1007\/3-540-44888-8_15"},{"key":"45_CR37","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R. (1989). Efficient tree pattern matching. In Foundations of Computer Science, 30th Annual Symposium on (pp. 178\u2013183). IEEE.","DOI":"10.1109\/SFCS.1989.63475"},{"key":"45_CR38","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Lu, S., & Ostrovsky, R. (2012). On the (in)security of hash-based oblivious ram and a new balancing scheme. In Proceedings of the 23rd Annual ACM-SIAM symposium on Discrete Algorithms (SODA) (pp. 143\u2013156). Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973099.13"},{"key":"45_CR39","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2017.04.001","volume":"43","author":"J Labeit","year":"2017","unstructured":"Labeit, J., Shun, J., & Blelloch, G. E. (2017). Parallel lightweight wavelet tree, suffix array and fm-index construction. Journal of Discrete Algorithms, 43, 2\u201317.","journal-title":"Journal of Discrete Algorithms"},{"issue":"3","key":"45_CR40","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009). Ultrafast and memory-efficient alignment of short dna sequences to the human genome. Genome Biology, 10(3), R25.","journal-title":"Genome Biology"},{"key":"45_CR41","first-page":"523","volume":"10992","author":"K Larsen","year":"2018","unstructured":"Larsen, K., & Nielsen, J. (2018). Yes, there is an oblivious ram lower bound!. Advances in Cryptology CRYPTO, 10992, 523\u2013542.","journal-title":"Advances in Cryptology CRYPTO"},{"key":"45_CR42","unstructured":"Lehman, E., & Shelat, A. (2002). Approximation algorithms for grammar-based compression. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms  (pp. 205\u2013212). Society for Industrial and Applied Mathematics."},{"issue":"10","key":"45_CR43","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1093\/bioinformatics\/btv033","volume":"31","author":"D Li","year":"2015","unstructured":"Li, D., Liu, C. M., Luo, R., Sadakane, K., & Lam, T. W. (2015). Megahit: An ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph. Bioinformatics, 31(10), 1674\u20131676.","journal-title":"Bioinformatics"},{"key":"45_CR44","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.ymeth.2016.02.020","volume":"102","author":"D Li","year":"2016","unstructured":"Li, D., Luo, R., Liu, C. M., Leung, C. M., Ting, H. F., Sadakane, K., et al. (2016). Megahit v1. 0: A fast and scalable metagenome assembler driven by advanced methodologies and community practices. Methods, 102, 3\u201311.","journal-title":"Methods"},{"issue":"14","key":"45_CR45","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., & Durbin, R. (2009). Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics, 25(14), 1754\u20131760.","journal-title":"Bioinformatics"},{"issue":"5","key":"45_CR46","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., & Myers, G. (1993). Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5), 935\u2013948.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"45_CR47","doi-asserted-by":"publisher","first-page":"63","DOI":"10.3390\/info7040063","volume":"7","author":"K Marumo","year":"2016","unstructured":"Marumo, K., Yamagiwa, S., Morita, R., & Sakamoto, H. (2016). Lazy management for frequency table on hardware-based stream lossless data compression. Information, 7(4), 63.","journal-title":"Information"},{"issue":"2","key":"45_CR48","doi-asserted-by":"publisher","first-page":"214","DOI":"10.3390\/a5020214","volume":"5","author":"S Maruyama","year":"2012","unstructured":"Maruyama, S., Sakamoto, H., & Takeda, M. (2012). An online algorithm for lightweight grammar-based compression. Algorithms, 5(2), 214\u2013235.","journal-title":"Algorithms"},{"key":"45_CR49","doi-asserted-by":"crossref","unstructured":"Maruyama, S., & Tabei, Y. (2014). Fully online grammar compression in constant space. In Data Compression Conference (DCC) (pp. 173\u2013182). IEEE.","DOI":"10.1109\/DCC.2014.69"},{"key":"45_CR50","doi-asserted-by":"crossref","unstructured":"Masaki, T., & Kida, T. (2016). Online grammar transformation based on re-pair algorithm. In 2016 Data Compression Conference (DCC) (pp. 349\u2013358). IEEE.","DOI":"10.1109\/DCC.2016.69"},{"issue":"2","key":"45_CR51","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E. M. (1976). A space-economical suffix tree construction algorithm. Journal of the ACM (JACM), 23(2), 262\u2013272.","journal-title":"Journal of the ACM (JACM)"},{"key":"45_CR52","unstructured":"Moffat, N.L.A., & Larsson, J. (2000). Offline dictionary-based compression. In Data Compression Conference (pp. 296\u2013305)."},{"issue":"8","key":"45_CR53","first-page":"114","volume":"38","author":"G Moore","year":"1965","unstructured":"Moore, G. (1965). Cramming more components \nonto integrated circuits. Electronics, 38(8), 114\u2013117.","journal-title":"Electronics"},{"issue":"20","key":"45_CR54","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","volume":"33","author":"MD Muggli","year":"2017","unstructured":"Muggli, M. D., Bowe, A., Noyes, N. R., Morley, P. S., Belk, K. E., Raymond, R., et al. (2017). Succinct colored de Bruijn graphs. Bioinformatics, 33(20), 3181\u20133187.","journal-title":"Bioinformatics"},{"key":"45_CR55","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., & Chan, W.H. (2009). Linear suffix array construction by almost pure induced-sorting. In Data Compression Conference, 2009. DCC\u201909 (pp. 193\u2013202). IEEE.","DOI":"10.1109\/DCC.2009.42"},{"issue":"4","key":"45_CR56","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1093\/bib\/bbx098","volume":"20","author":"Nathan D Olson","year":"2017","unstructured":"Olson, N. D., Treangen, T. J., Hill, C. M., Cepeda-Espinoza, V., Ghurye, J., Koren, S., & Pop, M. (2017). Metagenomic assembly through the lens of validation: Recent advances in assessing and improving the quality of genomes assembled from metagenomes. Briefings in Bioinformatics. \n                    https:\/\/doi.org\/10.1093\/bib\/bbx098","journal-title":"Briefings in Bioinformatics"},{"key":"45_CR57","unstructured":"Onodera, T., & Shibuya, T. (2018). Succinct Oblivious RAM. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Leibniz International Proceedings in Informatics (LIPIcs), 96, 52.1\u201352.16."},{"key":"45_CR58","doi-asserted-by":"crossref","unstructured":"Patel, S., Persiano, G., Raykova, M., & Yeo, K. (2018). Panorama: Oblivious ram with logarithmic overhead. In Proceedings of 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 871\u2013882).","DOI":"10.1109\/FOCS.2018.00087"},{"issue":"33","key":"45_CR59","doi-asserted-by":"publisher","first-page":"13272","DOI":"10.1073\/pnas.1121464109","volume":"109","author":"J Pell","year":"2012","unstructured":"Pell, J., Hintze, A., Canino-Koning, R., Howe, A., Tiedje, J. M., & Brown, C. T. (2012). Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. Proceedings of the National Academy of Sciences, 109(33), 13272\u201313277.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"17","key":"45_CR60","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). An eulerian path approach to dna fragment assembly. Proceedings of the National Academy of Sciences, 98(17), 9748\u20139753.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"45_CR61","doi-asserted-by":"crossref","unstructured":"Policriti, A., & Prezza, N. (2014). Hashing and indexing: Succinct datastructures and smoothed analysis. In International Symposium on Algorithms and Computation  (pp. 157\u2013168). Springer.","DOI":"10.1007\/978-3-319-13075-0_13"},{"key":"45_CR62","doi-asserted-by":"crossref","unstructured":"Sadakane, K., & Navarro, G. (2010). Fully-functional succinct trees. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms (pp. 134\u2013149). Society for Industrial and Applied Mathematics","DOI":"10.1137\/1.9781611973075.13"},{"key":"45_CR63","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84882-903-9","volume-title":"Handbook of data compression","author":"D Salomon","year":"2010","unstructured":"Salomon, D., & Motta, G. (2010). Handbook of data compression. New York: Springer."},{"key":"45_CR64","first-page":"197","volume-title":"Oblivious ram with $$o((\\log n)^3)$$","author":"E Shi","year":"2011","unstructured":"Shi, E., Chan, T. H. H., Stefanov, E., & Li, M. (2011). Oblivious ram with $$o((\\log n)^3)$$ worst-case cost (pp. 197\u2013214). Berlin: Springer."},{"issue":"5","key":"45_CR65","first-page":"1061","volume":"86","author":"T Shibuya","year":"2003","unstructured":"Shibuya, T. (2003). Constructing the suffix tree of a tree with a large alphabet. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 86(5), 1061\u20131066.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"issue":"1","key":"45_CR66","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1067-9","volume":"39","author":"T Shibuya","year":"2004","unstructured":"Shibuya, T. (2004). Generalization of a suffix tree for rna structural pattern matching. Algorithmica, 39(1), 1\u201319.","journal-title":"Algorithmica"},{"key":"45_CR67","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1146\/annurev-genom-090314-050032","volume":"16","author":"JT Simpson","year":"2015","unstructured":"Simpson, J. T., & Pop, M. (2015). The theory and practice of genome sequence assembly. Annual review of genomics and human genetics, 16, 153\u2013172.","journal-title":"Annual review of genomics and human genetics"},{"issue":"6","key":"45_CR68","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"JT Simpson","year":"2009","unstructured":"Simpson, J. T., Wong, K., Jackman, S. D., Schein, J. E., Jones, S. J., & Birol, I. (2009). Abyss: A parallel assembler for short read sequence data. Genome Research, 19(6), 1117\u20131123.","journal-title":"Genome Research"},{"key":"45_CR69","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n, J. (2017). Indexing variation graphs. In 2017 Proceedings of the ninteenth workshop on algorithm engineering and experiments (ALENEX) (pp. 13\u201327). SIAM.","DOI":"10.1137\/1.9781611974768.2"},{"key":"45_CR70","unstructured":"Stefanov, E., Shi, E., & Song, D. (2012). Towards practical oblivious ram. In Proceedings of the 19th Annual Network and Distributed System Security Symposium."},{"key":"45_CR71","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Van\u00a0Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., & Devadas, S. (2013). Path oram: an extremely simple oblivious ram protocol. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security (pp. 299\u2013310). ACM.","DOI":"10.1145\/2508859.2516660"},{"key":"45_CR72","unstructured":"Takabatake, Y., Sakamoto, H., et\u00a0al. (2017). A space-optimal grammar compression. In LIPIcs-Leibniz International Proceedings in Informatics (vol.\u00a087). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"issue":"3","key":"45_CR73","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E. (1995). On-line construction of suffix trees. Algorithmica, 14(3), 249\u2013260.","journal-title":"Algorithmica"},{"key":"45_CR74","doi-asserted-by":"crossref","unstructured":"Wang, X., Chan, H., & Shi, E. (2015). Circuit oram: On tightness of the goldreich-ostrovsky lower bound. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (pp. 850\u2013861). ACM.","DOI":"10.1145\/2810103.2813634"},{"key":"45_CR75","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973). Linear pattern matching algorithms. In Switching and Automata Theory, 1973. SWAT\u201908. IEEE Conference Record of 14th Annual Symposium on (pp. 1\u201311). IEEE.","DOI":"10.1109\/SWAT.1973.13"},{"key":"45_CR76","unstructured":"Yamagiwa, S., Marumo, K., & Sakamoto, H. (2015). Stream-based lossless data compression hardware using adaptive frequency table management. In Workshop on Big Data Benchmarks, Performance Optimization, and Emerging Hardware (pp. 133\u2013146). Springer."},{"key":"45_CR77","doi-asserted-by":"crossref","unstructured":"Ye, C., Ma, Z.S., Cannon, C.H., Pop, M., & Douglas, W.Y. (2012). Exploiting sparseness in de novo genome assembly. In BMC bioinformatics (vol.\u00a013, p.\u00a0S1). BioMed Central.","DOI":"10.1186\/1471-2105-13-S6-S1"},{"issue":"5","key":"45_CR78","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., & Lempel, A. (1978). Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5), 530\u2013536.","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["The Review of Socionetwork Strategies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00045-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12626-019-00045-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12626-019-00045-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T23:35:54Z","timestamp":1602113754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12626-019-00045-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10]]},"references-count":78,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["45"],"URL":"https:\/\/doi.org\/10.1007\/s12626-019-00045-1","relation":{},"ISSN":["2523-3173","1867-3236"],"issn-type":[{"type":"print","value":"2523-3173"},{"type":"electronic","value":"1867-3236"}],"subject":[],"published":{"date-parts":[[2019,10]]},"assertion":[{"value":"21 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}