{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:44:15Z","timestamp":1787341455103,"version":"build-2736575974"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data structure that handles unbounded-length keys whose comparison cost is not a constant. Examples of these keys are strings, multidimensional points, multiple-precision numbers, multikey data (e.g., records), XML paths, URL addresses, etc. The technique is more general than what has been done in previous work as no particular exploitation of the underlying structure is required. The only requirement is that the insertion of a key must identify its predecessor or its successor. Using the proposed technique, online suffix tree construction can be done in worst case time $O(\\log n)$ per input symbol (as opposed to amortized $O(\\log n)$ time per symbol, achieved by previously known algorithms). To our knowledge, our algorithm is the first that achieves $O(\\log n)$ worst case time per input symbol. Searching for a pattern of length $m$ in the resulting suffix tree takes $O(\\min(m \\log |\\Sigma|, m + \\log n) + tocc)$ time, where $tocc$ is the number of occurrences of the pattern. The paper also describes more applications and shows how to obtain alternative methods for dealing with suffix sorting, dynamic lowest common ancestors, and order maintenance. The technical features of the proposed technique for a given data structure $\\mathscr{D}$ are the following ones. The new data structure $\\mathscr{D}'$ is obtained from $\\mathscr{D}$ by augmenting the latter with an oracle for strings, extending the functionalities of the Dietz--Sleator list for order maintenance [P. F. Dietz and D. D. Sleator, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 365--372; A. Tsakalidis, Acta Inform., 21 (1984), pp. 101--112]. The space complexity of $\\mathscr{D}'$ is $\\mathscr{S}(n) + O(n)$ memory cells for storing $n$ keys, where $\\mathscr{S}(n)$ denotes the space complexity of $\\mathscr{D}$. Then, each operation involving $O(1)$ keys taken from $\\mathscr{D}'$ requires $O(\\mathscr{T}(n))$ time, where $\\mathscr{T}(n)$ denotes the time complexity of the corresponding operation originally supported in $\\mathscr{D}$. Each operation involving a key $y$ not stored in $\\mathscr{D}'$ takes $O(\\mathscr{T}(n) + |y|)$ time, where $|y|$ denotes the length of $y$. For the special case where the oracle handles suffixes of a string, the achieved insertion time is $O(\\mathscr{T}(n))$.<\/jats:p>","DOI":"10.1137\/110836377","type":"journal-article","created":{"date-parts":[[2014,7,31]],"date-time":"2014-07-31T11:34:08Z","timestamp":1406806448000},"page":"1396-1416","source":"Crossref","is-referenced-by-count":9,"title":["Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing"],"prefix":"10.1137","volume":"43","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gianni","family":"Franceschini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noa","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,7,31]]},"reference":[{"key":"atypb1","first-page":"819","author":"Alstrup S.","year":"2000","journal-title":"Philadelphia"},{"key":"atypb2","first-page":"365","author":"Alstrup S.","year":"2000","journal-title":"Berlin"},{"key":"atypb3","first-page":"67","author":"Amir A.","year":"2005","journal-title":"Berlin"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240242"},{"key":"atypb5","first-page":"1086","author":"Amir A.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240481X"},{"key":"atypb7","first-page":"88","author":"Bender M.A.","year":"2000","journal-title":"Berlin"},{"key":"atypb8","first-page":"152","author":"Bender M.A.","year":"2002","journal-title":"Berlin"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"atypb10","first-page":"360","author":"Bentley J.L.","year":"1997","journal-title":"Philadelphia"},{"key":"atypb11","first-page":"156","author":"Breslauer D.","year":"2011","journal-title":"Berlin"},{"key":"atypb12","unstructured":"M. Burrows and D. Wheeler,\n                      A Block Sorting Lossless Data Compression Algorithm\n                      , Technical report 124, Digital Systems Research Center, Palo Alto, CA, 1994."},{"key":"atypb13","first-page":"235","author":"Cole R.","year":"1999","journal-title":"Philadelphia"},{"key":"atypb14","first-page":"358","author":"Cole R.","year":"2006","journal-title":"Berlin"},{"key":"atypb15","first-page":"851","author":"Cole R.","year":"2003","journal-title":"PA"},{"key":"atypb16","first-page":"81","author":"Crescenzi P.","year":"2003","journal-title":"Berlin"},{"key":"atypb17","first-page":"365","author":"Dietz P.F.","year":"1987","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. Farach,\n                      Optimal suffix tree construction with large alphabets\n                      , in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, 1997, IEEE Computer Society Press, Los Alamitos, CA, 1997, pp. 137-143.","DOI":"10.1109\/SFCS.1997.646102"},{"key":"atypb19","first-page":"130","author":"Farach M.","year":"1996","journal-title":"Berlin"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286119"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"atypb22","first-page":"606","author":"Franceschini G.","year":"2004","journal-title":"Berlin"},{"key":"atypb23","first-page":"376","author":"Gonzalez T.F.","year":"1992","journal-title":"New York"},{"key":"atypb24","first-page":"372","author":"Grossi R.","year":"1999","journal-title":"Berlin"},{"key":"atypb25","unstructured":"M. Gu, M. Farach, and R. Beigel,\n                      An efficient algorithm for dynamic text indexing\n                      , in Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, pp. 697-704."},{"key":"atypb26","first-page":"375","author":"Gueting R.H.","year":"1980","journal-title":"Germany"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00034-0"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/363958.363987"},{"key":"atypb32","first-page":"16","author":"Kent C.","year":"2007","journal-title":"Berlin"},{"key":"atypb33","first-page":"283","author":"Kopelowitz T.","year":"2012","journal-title":"IEEE Computer Society"},{"key":"atypb34","first-page":"565","author":"Kopelowitz T.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299635"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/0208014"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn,\n                      Data Structures and Algorithms1:Sorting and Searching.\n                      , Springer, Berlin, 1984.","DOI":"10.1007\/978-3-642-69672-5_2"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"atypb42","unstructured":"M.H. Overmars,\n                      The Design of Dynamic Data Structures\n                      , Lecture Notes in Comput. Sci. 156, Springer, Berlin, 1983."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1160"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"S.C. Sahinalp and U. Vishkin,\n                      Efficient approximate and dynamic matching of patterns using a labeling paradigm (extended abstract)\n                      , in Proceedings of the 37th Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1996, pp. 320-328.","DOI":"10.1109\/SFCS.1996.548491"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940876"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"atypb48","first-page":"493","author":"Slisenko A.O.","year":"1978","journal-title":"Tokyo"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan,\n                      Data Structures and Network Algorithms\n                      , CBMS-NSF Regional Conf. Ser. in Appl. Math. 44, SIAM, Philadelphia, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289142"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0025"},{"key":"atypb53","doi-asserted-by":"crossref","unstructured":"P. Weiner,\n                      Linear pattern matching algorithm\n                      , in Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, IEEE Computer Society, Northridge, CA, 1973, pp. 1-11.","DOI":"10.1109\/SWAT.1973.13"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90034-D"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110836377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:21:16Z","timestamp":1787340076000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110836377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/110836377"],"URL":"https:\/\/doi.org\/10.1137\/110836377","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}