{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:26Z","timestamp":1759638926183,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"\n Let\n T<\/jats:italic>\n be a string with\n n<\/jats:italic>\n characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for\n T<\/jats:italic>\n in optimal space (i.e.,\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) bits), while supporting very efficient pattern matching [Ferragina and Manzini 2000; Grossi and Vitter 2000]. Yet the compressed nature of such indexes also makes them difficult to update dynamically.\n <\/jats:p>\n \n This article extends the work on optimal-space indexing to a dynamic collection of texts. Our first result is a compressed solution to the\n library management<\/jats:italic>\n problem, where we show an index of\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) bits for a text collection\n L<\/jats:italic>\n of total length\n n<\/jats:italic>\n , which can be updated in\n O<\/jats:italic>\n (|\n T<\/jats:italic>\n | log\n n<\/jats:italic>\n ) time when a text\n T<\/jats:italic>\n is inserted or deleted from\n L<\/jats:italic>\n ; also, the index supports searching the occurrences of any pattern\n P<\/jats:italic>\n in all texts in\n L<\/jats:italic>\n in\n O<\/jats:italic>\n (|\n P<\/jats:italic>\n | log\n n<\/jats:italic>\n +\n occ<\/jats:italic>\n log\n 2<\/jats:sup>\n n<\/jats:italic>\n ) time, where\n occ<\/jats:italic>\n is the number of occurrences.\n <\/jats:p>\n \n Our second result is a compressed solution to the\n dictionary matching<\/jats:italic>\n problem, where we show an index of\n O<\/jats:italic>\n (\n d<\/jats:italic>\n ) bits for a pattern collection\n D<\/jats:italic>\n of total length\n d<\/jats:italic>\n , which can be updated in\n O<\/jats:italic>\n (|\n P<\/jats:italic>\n | log\n 2<\/jats:sup>\n d<\/jats:italic>\n ) time when a pattern\n P<\/jats:italic>\n is inserted or deleted from\n D<\/jats:italic>\n ; also, the index supports searching the occurrences of all patterns of\n D<\/jats:italic>\n in any text\n T<\/jats:italic>\n in\n O<\/jats:italic>\n ((|\n T<\/jats:italic>\n | +\n occ<\/jats:italic>\n )log\n 2<\/jats:sup>\n d<\/jats:italic>\n ) time. When compared with the\n O<\/jats:italic>\n (\n d<\/jats:italic>\n log\n d<\/jats:italic>\n )-bit suffix-tree-based solution of Amir et al. [1995], the compact solution increases the query time by roughly a factor of log\n d<\/jats:italic>\n only.\n <\/jats:p>\n \n The solution to the dictionary matching problem is based on a new compressed representation of a suffix tree. Precisely, we give an\n O<\/jats:italic>\n (\n n<\/jats:italic>\n )-bit representation of a suffix tree for a dynamic collection of texts whose total length is\n n<\/jats:italic>\n , which supports insertion and deletion of a text\n T<\/jats:italic>\n in\n O<\/jats:italic>\n (|\n T<\/jats:italic>\n | log\n 2<\/jats:sup>\n n<\/jats:italic>\n ) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. In the study of the aforementioned result, we also derive the first\n O<\/jats:italic>\n (\n n<\/jats:italic>\n )-bit representation for maintaining\n n<\/jats:italic>\n pairs of balanced parentheses in\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n \/log log\n n<\/jats:italic>\n ) time per operation, matching the time complexity of the previous\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n )-bit solution.\n <\/jats:p>","DOI":"10.1145\/1240233.1240244","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":62,"title":["Compressed indexes for dynamic text collections"],"prefix":"10.1145","volume":"3","author":[{"given":"Ho-Leung","family":"Chan","sequence":"first","affiliation":[{"name":"University of Hong Kong"}]},{"given":"Wing-Kai","family":"Hon","sequence":"additional","affiliation":[{"name":"National Tsing Hua University"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[{"name":"University of Hong Kong"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[{"name":"Kyushu University"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185445"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80047-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1090"},{"volume-title":"Proceedings of the Symposium on Combinatorial Pattern Matching. 262--275","author":"Amir A.","key":"e_1_2_1_5_1","unstructured":"Amir , A. , Farach , M. , and Matias , Y . 1992. Efficient randomized dictionary matching algorithms (extended abstract) . In Proceedings of the Symposium on Combinatorial Pattern Matching. 262--275 . Amir, A., Farach, M., and Matias, Y. 1992. Efficient randomized dictionary matching algorithms (extended abstract). In Proceedings of the Symposium on Combinatorial Pattern Matching. 262--275."},{"key":"e_1_2_1_6_1","volume-title":"Tech. Rep. 124","author":"Burrows M.","year":"1994","unstructured":"Burrows , M. , and Wheeler , D. J . 1994 . A block-sorting lossless data compression algorithm. Tech. Rep. 124 , Digital Equipment Corporation, Paolo Alto , California . Burrows, M., and Wheeler, D. J. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation, Paolo Alto, California."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796543"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"volume-title":"Proceedings of the International Symposium on String Processing and Information Retrieval. 150--160","author":"Ferragina P.","key":"e_1_2_1_10_1","unstructured":"Ferragina , P. , Manzini , G. , M\u00e4kinen , V. , and Navarro , G . 2004. An alphabet-friendly FM-index . In Proceedings of the International Symposium on String Processing and Information Retrieval. 150--160 . Ferragina, P., Manzini, G., M\u00e4kinen, V., and Navarro, G. 2004. An alphabet-friendly FM-index. In Proceedings of the International Symposium on String Processing and Information Retrieval. 150--160."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73040"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms. 841--850","author":"Grossi R.","key":"e_1_2_1_12_1","unstructured":"Grossi , R. , Gupta , A. , and Vitter , J. S . 2003. High-order entropy-compressed text indexes . In Proceedings of the Symposium on Discrete Algorithms. 841--850 . Grossi, R., Gupta, A., and Vitter, J. S. 2003. High-order entropy-compressed text indexes. In Proceedings of the Symposium on Discrete Algorithms. 841--850."},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms. 636--645","author":"Grossi R.","key":"e_1_2_1_13_1","unstructured":"Grossi , R. , Gupta , A. , and Vitter , J. S . 2004. When indexing equals compression: Experiments with compressing suffix arrays and applications . In Proceedings of the Symposium on Discrete Algorithms. 636--645 . Grossi, R., Gupta, A., and Vitter, J. S. 2004. When indexing equals compression: Experiments with compressing suffix arrays and applications. In Proceedings of the Symposium on Discrete Algorithms. 636--645."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335351"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments. 31--38","author":"Hon W. K.","key":"e_1_2_1_16_1","unstructured":"Hon , W. K. , Lam , T. W. , Sung , W. K. , Tse , W. L. , Wong , C. K. , and Yiu , S. M . 2004. Practical aspects of compressed suffix arrays and FM-index in searching DNA sequences . In Proceedings of the Workshop on Algorithm Engineering and Experiments. 31--38 . Hon, W. K., Lam, T. W., Sung, W. K., Tse, W. L., Wong, C. K., and Yiu, S. M. 2004. Practical aspects of compressed suffix arrays and FM-index in searching DNA sequences. In Proceedings of the Workshop on Algorithm Engineering and Experiments. 31--38."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199911)29:13%3C1149::AID-SPE274%3E3.0.CO;2-O"},{"volume-title":"Proceedings of the International Conference on Computing and Combinatorics. 401--410","author":"Lam T. W.","key":"e_1_2_1_19_1","unstructured":"Lam , T. W. , Sadakane , K. , Sung , W. K. , and Yiu , S. M . 2002. A space and time efficient algorithm for constructing compressed suffix arrays . In Proceedings of the International Conference on Computing and Combinatorics. 401--410 . Lam, T. W., Sadakane, K., Sung, W. K., and Yiu, S. M. 2002. A space and time efficient algorithm for constructing compressed suffix arrays. In Proceedings of the International Conference on Computing and Combinatorics. 401--410."},{"volume-title":"Run-Length FM-index. In Proceedings of the DIMACS Workshop: The Burrows-Wheeler Transform: Ten Years Later. 17--19","author":"M\u00e4kinen V.","key":"e_1_2_1_20_1","unstructured":"M\u00e4kinen , V. , and Navarro , G . 2004 . Run-Length FM-index. In Proceedings of the DIMACS Workshop: The Burrows-Wheeler Transform: Ten Years Later. 17--19 . M\u00e4kinen, V., and Navarro, G. 2004. Run-Length FM-index. In Proceedings of the DIMACS Workshop: The Burrows-Wheeler Transform: Ten Years Later. 17--19."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"volume-title":"Proceedings of the Symposium on Combinatorial Pattern Matching. 261--285","author":"Mewes H. W.","key":"e_1_2_1_23_1","unstructured":"Mewes , H. W. , and Heumann , K . 1995. Genome analysis: Pattern search in biological macromolecules . In Proceedings of the Symposium on Combinatorial Pattern Matching. 261--285 . Mewes, H. W., and Heumann, K. 1995. Genome analysis: Pattern search in biological macromolecules. In Proceedings of the Symposium on Combinatorial Pattern Matching. 261--285."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"The design of dynamic data structures","author":"Overmars M. H.","unstructured":"Overmars , M. H. 1983. The design of dynamic data structures . Lecture Notes in Computer Science , vol. 156 . Overmars, M. H. 1983. The design of dynamic data structures. Lecture Notes in Computer Science, vol. 156."},{"volume-title":"Proceedings of the Workshop on Algorithms and Data Structures. 426--437","author":"Raman R.","key":"e_1_2_1_26_1","unstructured":"Raman , R. , Raman , V. , and Rao , S. S . 2001. Succinct dynamic data structures . In Proceedings of the Workshop on Algorithms and Data Structures. 426--437 . Raman, R., Raman, V., and Rao, S. S. 2001. Succinct dynamic data structures. In Proceedings of the Workshop on Algorithms and Data Structures. 426--437."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646343.689570"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms. 225--232","author":"Sadakane K.","year":"2002","unstructured":"Sadakane , K. 2002 . Succinct representations of lcp information and improvements in the compressed suffix arrays . In Proceedings of the Symposium on Discrete Algorithms. 225--232 . Sadakane, K. 2002. Succinct representations of lcp information and improvements in the compressed suffix arrays. In Proceedings of the Symposium on Discrete Algorithms. 225--232."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Sadakane K. 2007. Compressed suffix trees with full functionality. Theor. Comput. Syst. to appear. Sadakane K. 2007. Compressed suffix trees with full functionality. Theor. Comput. Syst. to appear.","DOI":"10.1007\/s00224-006-1198-x"},{"volume-title":"Proceedings of the Symposium on Foundations of Computer Science. 320--328","author":"Sahinalp S. C.","key":"e_1_2_1_30_1","unstructured":"Sahinalp , S. C. , and Vishkin , U . 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm . In Proceedings of the Symposium on Foundations of Computer Science. 320--328 . Sahinalp, S. C., and Vishkin, U. 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In Proceedings of the Symposium on Foundations of Computer Science. 320--328."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240244"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240244","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}