{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:26:04Z","timestamp":1770751564819,"version":"3.50.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,5,3]],"date-time":"2020-05-03T00:00:00Z","timestamp":1588464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["677651"],"award-info":[{"award-number":["677651"]}]},{"name":"A.G. Leventis Foundation educational"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>\n            The suffix array is one of the most prevalent data structures for string indexing; it stores the lexicographically sorted list of suffixes of a given string. Its practical advantage compared to the suffix tree is space efficiency. In\n            <jats:italic>Property Indexing<\/jats:italic>\n            , we are given a string\n            <jats:italic>x<\/jats:italic>\n            of length\n            <jats:italic>n<\/jats:italic>\n            and a property \u03a0, i.e., a set of \u03a0-\n            <jats:italic>valid<\/jats:italic>\n            intervals over\n            <jats:italic>x<\/jats:italic>\n            so that a pattern\n            <jats:italic>p<\/jats:italic>\n            occurs in\n            <jats:italic>x<\/jats:italic>\n            if and only if\n            <jats:italic>x<\/jats:italic>\n            has an occurrence of\n            <jats:italic>p<\/jats:italic>\n            that lies entirely within an interval of \u03a0. A suffix-tree-like index over the valid prefixes of suffixes of\n            <jats:italic>x<\/jats:italic>\n            can be built in time and space\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). We show here how to directly build a suffix-array-like index, the\n            <jats:italic>Property Suffix Array<\/jats:italic>\n            (PSA), in time and space\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). We mainly draw our motivation from weighted (probabilistic) sequences: sequences of probability distributions over a given alphabet. Given a probability threshold 1\/\n            <jats:italic>z<\/jats:italic>\n            , we say that a string\n            <jats:italic>p<\/jats:italic>\n            of length\n            <jats:italic>m<\/jats:italic>\n            matches a weighted sequence\n            <jats:italic>x<\/jats:italic>\n            of length\n            <jats:italic>n<\/jats:italic>\n            at starting position\n            <jats:italic>i<\/jats:italic>\n            if the product of probabilities of the letters of\n            <jats:italic>p<\/jats:italic>\n            at positions\n            <jats:italic>i<\/jats:italic>\n            , \u2026,\n            <jats:italic>i<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            \u2212 1 in\n            <jats:italic>x<\/jats:italic>\n            is at least 1\/\n            <jats:italic>z<\/jats:italic>\n            . Our algorithm for building the PSA can be directly applied to build an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nz<\/jats:italic>\n            )-sized suffix-array-like index over\n            <jats:italic>x<\/jats:italic>\n            in time and space\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nz<\/jats:italic>\n            ). Finally, we present extensive experimental results showing that our new indexing data structure is well suited for real-world applications.\n          <\/jats:p>","DOI":"10.1145\/3385898","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T18:55:08Z","timestamp":1588618508000},"page":"1-16","source":"Crossref","is-referenced-by-count":7,"title":["Property Suffix Array with Applications in Indexing Weighted Sequences"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6024-1557","authenticated-orcid":false,"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[{"name":"Department of Informatics, King\u2019s College London, UK and Institute of Informatics, University of Warsaw, Stefana Banacha, Warsaw, Poland"}]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[{"name":"Department of Informatics, King\u2019s College London, Bush House, London, UK"}]},{"given":"Chang","family":"Liu","sequence":"additional","affiliation":[{"name":"Cancer Bioinformatics, School of Cancer and Pharmaceutical Science, King\u2019s College London, UK"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[{"name":"CWI, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2020,5,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Abecasis (1000 Genomes Project Consortium)","author":"Auton Adam","year":"2015"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.190"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM\u201919)","volume":"128","author":"Alamro Hayam"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA\u201917)","author":"Alzamel Mai"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.104462"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201916)","author":"Barton Carl","year":"2016"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Annual International Conference on Combinatorial Optimization and Applications (COCOA\u201916)","author":"Barton Carl"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118430062"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 16th International Symposium on Experimental Algorithms (SEA\u201917)","volume":"75","author":"Baumstark Niklas","year":"2017"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1120060.1712350"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Extended Database Technology Conference (EDBT\u201916)","author":"Biswas Sudip","year":"2016"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Theoretical Informatics (LATIN\u201918)","author":"Charalampopoulos Panagiotis"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.01.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_2_1_17_1","volume-title":"Leiserson","author":"Cormen Thomas H.","year":"2001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.05.009"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2016.09.002"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.09.001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.09.004"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.06.009"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974768.8"},{"key":"e_1_2_1_26_1","series-title":"Lecture Notes in Computer Science","volume-title":"Puglisi","author":"K\u00e4rkk\u00e4inen Juha","year":"2009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.80.18.5660"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48194-X_17"},{"key":"e_1_2_1_30_1","volume-title":"A linear time algorithm for seeds computation. CoRR arXiv:1107.2422v2","author":"Kociumaka Tomasz","year":"2011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9881-2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.11.035"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.02.033"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2009.42"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242471.1242472"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the Data Compression Conference (DCC\u201917)","author":"Radoszewski Jakub","year":"2017"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:50Z","timestamp":1750199570000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,3]]},"references-count":38,"alternative-id":["10.1145\/3385898"],"URL":"https:\/\/doi.org\/10.1145\/3385898","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,3]]}}}