{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:49:08Z","timestamp":1743072548553,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030866914"},{"type":"electronic","value":"9783030866921"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-86692-1_12","type":"book-chapter","created":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:24:41Z","timestamp":1632777881000},"page":"143-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9106-6192","authenticated-orcid":false,"given":"Tomohiro","family":"I","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert W.","family":"Irving","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorna","family":"Love","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,27]]},"reference":[{"key":"12_CR1","first-page":"263","volume":"146","author":"GM Adelson-Velsky","year":"1962","unstructured":"Adelson-Velsky, G.M., Landis, E.M.: An algorithm for organization of information. Dokl. Akad. Nauk SSSR 146, 263\u2013266 (1962)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bille, P., Fischer, J., G\u00f8rtz, I.L., Kopelowitz, T., Sach, B., Vildh\u00f8j, H.W.: Sparse text indexing in small space. ACM Trans. Algorithms 12(3), 39:1\u201339:19 (2016)","DOI":"10.1145\/2836166"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Birenzwige, O., Golan, S., Porat, E.: Locally consistent parsing for text indexing in small space. In: Proceedings of SODA, pp. 607\u2013626 (2020)","DOI":"10.1137\/1.9781611975994.37"},{"key":"12_CR4","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm. Technical report 124, Digital Equipment Corporation, Palo Alto, California (1994)"},{"issue":"2","key":"12_CR5","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/s00453-013-9792-1","volume":"71","author":"Y Chien","year":"2015","unstructured":"Chien, Y., Hon, W., Shah, R., Thankachan, S.V., Vitter, J.S.: Geometric BWT: compressed text indexing via sparse suffixes and range searching. Algorithmica 71(2), 258\u2013278 (2015)","journal-title":"Algorithmica"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-540-73437-6_33","volume-title":"Combinatorial Pattern Matching","author":"P Ferragina","year":"2007","unstructured":"Ferragina, P., Fischer, J.: Suffix arrays on words. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 328\u2013339. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73437-6_33"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, J., I, T., K\u00f6ppl, D.: Deterministic sparse suffix sorting in the restore model. ACM Trans. Algorithms 16(4), 50:1\u201350:53 (2020)","DOI":"10.1145\/3398681"},{"key":"12_CR8","unstructured":"I, T., K\u00e4rkk\u00e4inen, J., Kempa, D.: Faster sparse suffix sorting. In: Proceedings of STACS. LIPIcs, vol. 25, pp. 386\u2013396 (2014)"},{"key":"12_CR9","unstructured":"I, T., K\u00f6ppl, D.: Load-balancing succinct B trees. arXiv CoRR abs\/2104.08751 (2021)"},{"key":"12_CR10","unstructured":"Irving, R.W., Love, L.: Suffix binary search trees and suffix arrays. University of Glasgow, Technical report (2001)"},{"issue":"5\u20136","key":"12_CR11","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/S1570-8667(03)00034-0","volume":"1","author":"RW Irving","year":"2003","unstructured":"Irving, R.W., Love, L.: The suffix binary search tree and suffix AVL tree. J. Discret. Algorithms 1(5\u20136), 387\u2013408 (2003)","journal-title":"J. Discret. Algorithms"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/978-3-319-46049-9_20","volume-title":"String Processing and Information Retrieval","author":"J K\u00e4rkk\u00e4inen","year":"2016","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: LCP array construction using O(sort(n)) (or Less) I\/Os. In: Inenaga, S., Sadakane, K., Sakai, T. (eds.) SPIRE 2016. LNCS, vol. 9954, pp. 204\u2013217. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-46049-9_20"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/3-540-61332-3_155","volume-title":"Computing and Combinatorics","author":"J K\u00e4rkk\u00e4inen","year":"1996","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Sparse suffix trees. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol. 1090, pp. 219\u2013230. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61332-3_155"},{"issue":"13","key":"12_CR14","doi-asserted-by":"publisher","first-page":"1609","DOI":"10.1093\/bioinformatics\/btp275","volume":"25","author":"Z Khan","year":"2009","unstructured":"Khan, Z., Bloom, J.S., Kruglyak, L., Singh, M.: A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays. Bioinform. 25(13), 1609\u20131616 (2009)","journal-title":"Bioinform."},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., Kucherov, G., Starikovskaya, T.A.: Pattern matching on sparse suffix trees. In: Proceedings of CCP, pp. 92\u201397 (2011)","DOI":"10.1109\/CCP.2011.45"},{"key":"12_CR16","unstructured":"K\u00f6ppl, D.: Exploring regular structures in strings. Ph.D. thesis, TU Dortmund (2018)"},{"key":"12_CR17","unstructured":"Kosolobov, D., Sivukhin, N.: Construction of sparse suffix trees and LCE indexes in optimal time and space. arXiv CoRR abs\/2105.03782 (2021)"},{"key":"12_CR18","unstructured":"Love, L.: The suffix binary search tree. Ph.D. thesis, University of Glasgow, UK (2001)"},{"issue":"5","key":"12_CR19","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Prezza, N.: In-place sparse suffix sorting. In: Proceedings of SODA, pp. 1496\u20131508 (2018)","DOI":"10.1137\/1.9781611975031.98"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-21458-5_22","volume-title":"Combinatorial Pattern Matching","author":"T Uemura","year":"2011","unstructured":"Uemura, T., Arimura, H.: Sparse and truncated suffix trees on variable-length codes. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 246\u2013260. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_22"},{"issue":"6","key":"12_CR22","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1093\/bioinformatics\/btt042","volume":"29","author":"M Vyverman","year":"2013","unstructured":"Vyverman, M., Baets, B.D., Fack, V., Dawyndt, P.: essaMEM: finding maximal exact matches using enhanced sparse suffix arrays. Bioinform. 29(6), 802\u2013804 (2013)","journal-title":"Bioinform."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86692-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:27:12Z","timestamp":1632778032000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86692-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030866914","9783030866921"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86692-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"27 September 2021","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":"Lille","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cristal.univ-lille.fr\/spire2021\/","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":"30","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":"14","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":"4","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.87","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":"2.32","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)"}},{"value":"2 invited papers are also included. The symposium was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}