Data Structures for Range Sorted Consecutive Occurrence Queries

Data Structures for Range Sorted Consecutive Occurrence Queries | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Data Structures for Range Sorted Consecutive Occurrence Queries Waseem Akram, Takuya Mieno This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7493901/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 6 You are reading this latest preprint version Abstract The string indexing problem is a fundamental computational problem with numerous applications, including information retrieval and bioinformatics. It aims to efficiently solve the pattern matching problem: given a text T of length n for preprocessing and a pattern P of length m as a query, the goal is to report all occurrences of P as substrings of T. Navarro and Thankachan~[CPM 2015, Theor. Comput. Sci. 2016] introduced a variant of this problem called the gap-bounded consecutive occurrence query, which reports pairs of consecutive occurrences of P in T such that their gaps (i.e., the distances between them) lie within a query-specified range [g_1, g_2]. Recently, Bille et al.~[FSTTCS 2020, Theor. Comput. Sci. 2022] proposed the top-k close consecutive occurrence query, which reports the k closest consecutive occurrences of P in T, sorted in non-decreasing order of distance. Both problems are optimally solved in query time with O(n \log n)-space data structures. In this paper, we generalize these problems to the range query model, which focuses only on occurrences of P in a specified substring T[a.. b] of T. Our contributions are as follows: (1) We propose an O(n \log 2 n)-space data structure that answers the range top-k consecutive occurrence query in O(m + \log\log n + k) time and can be built in O(n\log3 n) time; and (2) We propose an O(n \log {2+\epsilon} n)-space data structure that answers the range gap-bounded consecutive occurrence query in O(m + \log\log n + \out) time and can be constructed in O(n\log5/2n) time, where \epsilon is a positive constant and \out denotes the number of outputs. As by-products, we present algorithms for geometric problems involving weighted horizontal segments in a 2D plane, which are of independent interest. Furthermore, we observe that consecutive occurrences are related to closed substrings of a string. string pattern matching consecutive occurrences range queries suffix trees segment trees segments intersections closed words Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviews received at journal 28 Feb, 2026 Reviewers agreed at journal 19 Jan, 2026 Reviewers invited by journal 19 Jan, 2026 Editor assigned by journal 04 Sep, 2025 Submission checks completed at journal 01 Sep, 2025 First submitted to journal 30 Aug, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7493901","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":576945243,"identity":"1f78b90d-c939-4303-94a3-88635d97c744","order_by":0,"name":"Waseem Akram","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAtElEQVRIiWNgGAWjYDACHhBRIcEDYTBIEKvljAQPD2laGNuANA+x7uLvOfvw0815FjL2PAcYP/xgsMgjqEXibLuxdO42oMN4G5glexgkiglbc56NAaKFn4FBGmhEYgMhHfLn2Zh/584Ba2H+TZQWg7NtbNK5DWCHsRFni+GZY2zWOceAWs4cbLPsMSBCi9yZNObbOTV19uw9yYdv/KioI6wFCTACFRuQoH4UjIJRMApGAW4AAAK+LltxO7ZqAAAAAElFTkSuQmCC","orcid":"","institution":"Indian Institute of Technology, Kanpur","correspondingAuthor":true,"prefix":"","firstName":"Waseem","middleName":"","lastName":"Akram","suffix":""},{"id":576945244,"identity":"c30eba7e-d76e-45ca-aa7b-5283eb4cf64b","order_by":1,"name":"Takuya Mieno","email":"","orcid":"","institution":"University of Electro-Communications","correspondingAuthor":false,"prefix":"","firstName":"Takuya","middleName":"","lastName":"Mieno","suffix":""}],"badges":[],"createdAt":"2025-08-30 08:23:22","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7493901/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7493901/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":100752576,"identity":"0d0ae0cc-bea9-404b-b1ed-906517c05b54","added_by":"auto","created_at":"2026-01-21 05:14:33","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":481816,"visible":true,"origin":"","legend":"","description":"","filename":"consocc.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7493901/v1_covered_2cf935f4-b0a5-464f-8b6d-a58df3f20b8b.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Data Structures for Range Sorted Consecutive Occurrence Queries","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"acta-informatica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"acin","sideBox":"Learn more about [Acta Informatica](http://link.springer.com/journal/236)","snPcode":"236","submissionUrl":"https://submission.nature.com/new-submission/236/3","title":"Acta Informatica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"string pattern matching, consecutive occurrences, range queries, suffix trees, segment trees, segments intersections, closed words","lastPublishedDoi":"10.21203/rs.3.rs-7493901/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7493901/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"The string indexing problem is a fundamental computational problem with numerous applications, including information retrieval and bioinformatics. It aims to efficiently solve the pattern matching problem: given a text T of length n for preprocessing and a pattern P of length m as a query, the goal is to report all occurrences of P as substrings of T. Navarro and Thankachan~[CPM 2015, Theor. Comput. Sci. 2016] introduced a variant of this problem called the gap-bounded consecutive occurrence query, which reports pairs of consecutive occurrences of P in T such that their gaps (i.e., the distances between them) lie within a query-specified range [g_1, g_2]. Recently, Bille et al.~[FSTTCS 2020, Theor. Comput. Sci. 2022] proposed the top-k close consecutive occurrence query, which reports the k closest consecutive occurrences of P in T, sorted in non-decreasing order of distance. Both problems are optimally solved in query time with O(n \\log n)-space data structures. In this paper, we generalize these problems to the range query model, which focuses only on occurrences of P in a specified substring T[a.. b] of T. Our contributions are as follows: (1) We propose an O(n \\log 2 n)-space data structure that answers the range top-k consecutive occurrence query in O(m + \\log\\log n + k) time and can be built in O(n\\log3 n) time; and (2) We propose an O(n \\log {2+\\epsilon} n)-space data structure that answers the range gap-bounded consecutive occurrence query in O(m + \\log\\log n + \\out) time and can be constructed in O(n\\log5/2n) time, where \\epsilon is a positive constant and \\out denotes the number of outputs. As by-products, we present algorithms for geometric problems involving weighted horizontal segments in a 2D plane, which are of independent interest. Furthermore, we observe that consecutive occurrences are related to closed substrings of a string.","manuscriptTitle":"Data Structures for Range Sorted Consecutive Occurrence Queries","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-01-21 05:14:09","doi":"10.21203/rs.3.rs-7493901/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorInvitedReview","content":"","date":"2026-03-01T00:56:26+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"320735611020401048900428662316718228688","date":"2026-01-19T15:07:24+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-01-19T12:43:56+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-09-04T19:58:21+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-09-01T09:29:48+00:00","index":"","fulltext":""},{"type":"submitted","content":"Acta Informatica","date":"2025-08-30T08:15:53+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"acta-informatica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"acin","sideBox":"Learn more about [Acta Informatica](http://link.springer.com/journal/236)","snPcode":"236","submissionUrl":"https://submission.nature.com/new-submission/236/3","title":"Acta Informatica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"8b657c10-4c86-4347-a5a5-f8d5399dfc72","owner":[],"postedDate":"January 21st, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-01-21T05:14:09+00:00","versionOfRecord":[],"versionCreatedAt":"2026-01-21 05:14:09","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7493901","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7493901","identity":"rs-7493901","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}