{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T02:26:29Z","timestamp":1769394389175,"version":"3.49.0"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030326852","type":"print"},{"value":"9783030326869","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-32686-9_21","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T22:02:27Z","timestamp":1570226547000},"page":"285-303","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":64,"title":["COBS: A Compact Bit-Sliced Signature Index"],"prefix":"10.1007","author":[{"given":"Timo","family":"Bingmann","sequence":"first","affiliation":[]},{"given":"Phelim","family":"Bradley","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Gauger","sequence":"additional","affiliation":[]},{"given":"Zamin","family":"Iqbal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"key":"21_CR1","unstructured":"Almodaresi, F., Pandey, P., Patro, R.: Rainbowfish: a succinct colored de Bruijn graph representation. In: 17th International Workshop on Algorithms in Bioinformatics (WABI). LIPIcs, vol. 88, pp. 18:1\u201318:15. Schloss Dagstuhl, August 2017. preprint bioRxiv:138016"},{"issue":"13","key":"21_CR2","doi-asserted-by":"publisher","first-page":"i169","DOI":"10.1093\/bioinformatics\/bty292","volume":"34","author":"F Almodaresi","year":"2018","unstructured":"Almodaresi, F., Sarkar, H., Srivastava, A., Patro, R.: A space and time-efficient index for the compacted colored de Bruijn graph. Bioinformatics 34(13), i169\u2013i177 (2018)","journal-title":"Bioinformatics"},{"key":"21_CR3","unstructured":"Bingmann, T.: NVMe \u201cdisk\u201d bandwidth and latency for batched block requests, March 2019. Online Article, http:\/\/panthema.net\/2019\/0322-nvme-batched-block-access-speed"},{"issue":"7","key":"21_CR4","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1038\/s41587-018-0010-1","volume":"37","author":"P Bradley","year":"2019","unstructured":"Bradley, P., den Bakker, H.C., Rocha, E.P.C., McVean, G., Iqbal, Z.: Ultrafast search of all deposited bacterial and viral genomic data. Nat. Biotechnol. 37, 152\u2013159 (2019)","journal-title":"Nat. Biotechnol."},{"issue":"1\u20137","key":"21_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","volume":"30","author":"S Brin","year":"1998","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Networks ISDN Syst. 30(1\u20137), 107\u2013117 (1998)","journal-title":"Comput. Networks ISDN Syst."},{"issue":"4","key":"21_CR7","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1080\/15427951.2004.10129096","volume":"1","author":"AZ Broder","year":"2003","unstructured":"Broder, A.Z., Mitzenmacher, M.: Network applications of Bloom filters: a survey. Internet Math. 1(4), 485\u2013509 (2003)","journal-title":"Internet Math."},{"key":"21_CR8","unstructured":"Chikhi, R., Holub, J., Medvedev, P.: Data structures to represent sets of $$k$$ -long DNA sequences. Computing Research Repository (CoRR), arXiv:1903.12312:1\u201316 , March 2019"},{"key":"21_CR9","unstructured":"Collet, Y.: xxHash: extremely fast non-cryptographic hash algorithm, 2014. Git repository. https:\/\/github.com\/Cyan4973\/xxHash . Accessed July 2019"},{"issue":"D1","key":"21_CR10","doi-asserted-by":"publisher","first-page":"D15","DOI":"10.1093\/nar\/gky1124","volume":"47","author":"CE Cook","year":"2019","unstructured":"Cook, C.E., Lopez, R., Stroe, O., Cochrane, G., Brooksbank, C., Birney, E., Apweiler, R.: The European Bioinformatics Institute in 2018: tools, infrastructure and training. Nucleic Acids Res. 47(D1), D15\u2013D22 (2019)","journal-title":"Nucleic Acids Res."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.is.2015.01.002","volume":"54","author":"A Crainiceanu","year":"2015","unstructured":"Crainiceanu, A., Lemire, D.: Bloofi: multidimensional bloom filters. Inf. Syst. 54, 311\u2013324 (2015)","journal-title":"Inf. Syst."},{"issue":"4","key":"21_CR12","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/2275.357411","volume":"2","author":"C Faloutsos","year":"1984","unstructured":"Faloutsos, C., Christodoulakis, S.: Signature files: an access method for documents and its analytical performance evaluation. ACM Trans. Inf. Syst. (TOIS) 2(4), 267\u2013288 (1984)","journal-title":"ACM Trans. Inf. Syst. (TOIS)"},{"key":"21_CR13","unstructured":"Gauger, F.: Engineering a compact bit-sliced signature index for approximate search on genomic data. Master Thesis. Karlsruhe Institute of Technology, Germany, February 2018"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_28"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Goodwin, B., et al.: BitFunnel: revisiting signatures for search. In: 40th ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 605\u2013614. ACM, August 2017","DOI":"10.1145\/3077136.3080789"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Harris, R.S., Medvedev, P.: Improved representation of sequence Bloom trees. bioRxiv, pp. 501452, December 2018","DOI":"10.1101\/501452"},{"issue":"1","key":"21_CR17","doi-asserted-by":"publisher","first-page":"D84","DOI":"10.1093\/nar\/gky1078","volume":"D47","author":"PW Harrison","year":"2019","unstructured":"Harrison, P.W., et al.: The european nucleotide archive in 2018. Nucleic Acids Res. D47(1), D84\u2013D88 (2019)","journal-title":"Nucleic Acids Res."},{"issue":"2","key":"21_CR18","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1145\/506309.506312","volume":"20","author":"S Heinz","year":"2002","unstructured":"Heinz, S., Zobel, J., Williams, H.E.: Burst tries: a fast, efficient data structure for string keys. ACM Trans. Inf. Syst. (TOIS) 20(2), 192\u2013223 (2002)","journal-title":"ACM Trans. Inf. Syst. (TOIS)"},{"issue":"1","key":"21_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-016-0066-8","volume":"11","author":"G Holley","year":"2016","unstructured":"Holley, G., Wittler, R., Stoye, J.: Bloom filter trie: an alignment-free and reference-free data structure for pan-genome storage. Algorithms Mol. Biol. 11(1), 3 (2016)","journal-title":"Algorithms Mol. Biol."},{"issue":"2","key":"21_CR20","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z Iqbal","year":"2012","unstructured":"Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., McVean, G.: De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat. Genet. 44(2), 226 (2012)","journal-title":"Nat. Genet."},{"issue":"2","key":"21_CR21","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1093\/bioinformatics\/bts673","volume":"29","author":"Z Iqbal","year":"2012","unstructured":"Iqbal, Z., Turner, I., McVean, G.: High-throughput microbial population genomics using the cortex variation assembler. Bioinformatics 29(2), 275\u2013276 (2012)","journal-title":"Bioinformatics"},{"key":"21_CR22","unstructured":"Krugel, J.: Approximate Pattern Matching with Index Structures. Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen, Germany, February 2016"},{"issue":"6","key":"21_CR23","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","volume":"27","author":"G Mar\u00e7ais","year":"2011","unstructured":"Mar\u00e7ais, G., Kingsford, C.: A fast, lock-free approach for efficient parallel counting of occurrences of $$k$$ -mers. Bioinformatics 27(6), 764\u2013770 (2011)","journal-title":"Bioinformatics"},{"key":"21_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"issue":"9","key":"21_CR25","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1093\/bioinformatics\/btw832","volume":"33","author":"H Mohamadi","year":"2017","unstructured":"Mohamadi, H., Khan, H., Birol, I.: ntCard: a streaming algorithm for cardinality estimation in genomics data. Bioinformatics 33(9), 1324\u20131330 (2017)","journal-title":"Bioinformatics"},{"issue":"20","key":"21_CR26","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","volume":"33","author":"MD Muggli","year":"2017","unstructured":"Muggli, M.D., et al.: Succinct colored de Bruijn graphs. Bioinformatics 33(20), 3181\u20133187 (2017). preprint bioRxiv:040071","journal-title":"Bioinformatics"},{"issue":"4","key":"21_CR27","first-page":"19","volume":"24","author":"G Navarro","year":"2001","unstructured":"Navarro, G., Baeza-Yates, R.A., Sutinen, E., Tarhio, J.: Indexing methods for approximate string matching. IEEE Bull. Tech. Committee Data Eng. 24(4), 19\u201327 (2001)","journal-title":"IEEE Bull. Tech. Committee Data Eng."},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Pandey, P., Almodaresi, F., Bender, M.A., Ferdman, M., Johnson, R., Patro, R.: Mantis: a fast, small, and exact large-scale sequence-search index. Cell Systems, June 2018. preprint bioRxiv:217372","DOI":"10.1101\/217372"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Pandey, P., Bender, M.A., Johnson, R., Patro, R.: A general-purpose counting filter: making every bit count. In: ACM International Conference on Management of Data, pp. 775\u2013787. ACM (2017)","DOI":"10.1145\/3035918.3035963"},{"issue":"4","key":"21_CR30","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1093\/bioinformatics\/btx636","volume":"34","author":"P Pandey","year":"2018","unstructured":"Pandey, P., Bender, M.A., Johnson, R., Patro, R.: Squeakr: an exact and approximate k-mer counting system. Bioinformatics 34(4), 568\u2013575 (2018). preprint bioRxiv:122077","journal-title":"Bioinformatics"},{"key":"21_CR31","unstructured":"Raman, R., Raman, V., Srinivasa Rao, S.: Succinct indexable dictionaries with applications to encoding $$k$$ -ary trees and multisets. In: 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233\u2013242. SIAM, January 2002"},{"issue":"3","key":"21_CR32","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1038\/nbt.3442","volume":"34","author":"B Solomon","year":"2016","unstructured":"Solomon, B., Kingsford, C.: Fast search of thousands of short-read sequencing experiments. Nat. Biotechnol. 34(3), 300\u2013312 (2016)","journal-title":"Nat. Biotechnol."},{"issue":"7","key":"21_CR33","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1089\/cmb.2017.0265","volume":"25","author":"B Solomon","year":"2018","unstructured":"Solomon, B., Kingsford, C.: Improved search of large transcriptomic sequencing databases using split sequence Bloom trees. J. Comput. Biol. 25(7), 755\u2013765 (2018)","journal-title":"J. Comput. Biol."},{"issue":"5","key":"21_CR34","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1089\/cmb.2017.0258","volume":"25","author":"C Sun","year":"2018","unstructured":"Sun, C., Harris, R.S., Chikhi, R., Medvedev, P.: AllSome sequence Bloom trees. J. Computat. Biol. 25(5), 467\u2013479 (2018)","journal-title":"J. Computat. Biol."},{"issue":"15","key":"21_CR35","doi-asserted-by":"publisher","first-page":"2556","DOI":"10.1093\/bioinformatics\/bty157","volume":"34","author":"I Turner","year":"2018","unstructured":"Turner, I., Garimella, K.V., Iqbal, Z., McVean, G.: Integrating long-range connectivity information into de Bruijn graphs. Bioinformatics 34(15), 2556\u20132565 (2018)","journal-title":"Bioinformatics"},{"issue":"1","key":"21_CR36","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E Ukkonen","year":"1992","unstructured":"Ukkonen, E.: Approximate string-matching with $$q$$ -grams and maximal matches. Theoret. Comput. Sci. 92(1), 191\u2013211 (1992)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR37","unstructured":"Wong, H.K.T., Liu, H.-F., Olken, F., Rotem, D., Wong, L.: Bit transposed files. In 11th International Conference on Very Large Data Bases (VLDB), pp. 448\u2013457. VLDB Endowment, August 1985"},{"issue":"3","key":"21_CR38","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1109\/TNET.2018.2820067","volume":"26","author":"Y Ye","year":"2018","unstructured":"Ye, Y., Belazzougui, D., Qian, C., Zhang, Q.: Memory-efficient and ultra-fast network lookup and forwarding using othello hashing. IEEE\/ACM Trans. Networking 26(3), 1151\u20131164 (2018)","journal-title":"IEEE\/ACM Trans. Networking"},{"issue":"1","key":"21_CR39","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1186\/s13059-018-1535-9","volume":"19","author":"Y Ye","year":"2018","unstructured":"Ye, Y., et al.: SeqOthello: querying RNA-seq experiments at scale. Genome Biol. 19(1), 167 (2018). preprint bioRxiv:258772","journal-title":"Genome Biol."},{"issue":"2","key":"21_CR40","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/1132956.1132959","volume":"38","author":"J Zobel","year":"2006","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surveys (CSUR) 38(2), 6 (2006)","journal-title":"ACM Comput. Surveys (CSUR)"},{"issue":"4","key":"21_CR41","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/296854.277632","volume":"23","author":"J Zobel","year":"1998","unstructured":"Zobel, J., Moffat, A., Ramamohanarao, K.: Inverted files versus signature files for text indexing. ACM Trans. Database Syst. (TODS) 23(4), 453\u2013490 (1998)","journal-title":"ACM Trans. Database Syst. (TODS)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-32686-9_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T09:07:07Z","timestamp":1695287227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-32686-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030326852","9783030326869"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32686-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"3 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Segovia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/spire19.lbd.org.es\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}