{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T23:40:01Z","timestamp":1749944401660,"version":"3.41.0"},"reference-count":17,"publisher":"EDP Sciences","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1994]]},"DOI":"10.1051\/ita\/1994280100251","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T15:00:06Z","timestamp":1486047606000},"page":"25-49","source":"Crossref","is-referenced-by-count":8,"title":["Using persistent data structures for adding range restrictions to searching problems"],"prefix":"10.1051","volume":"28","author":[{"given":"Hans-Peter","family":"Lenhof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"1. BENTLEY J. L., Decomposable Searching Problems, Inform. Proc. Lett., 1979, 8, 244-251.5340720404.68067","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"2. BENTLEY J. L., Multidimensional Divide and Conquer, Comm. ACM., 1980, 23, 214-229.5671500434.68049","DOI":"10.1145\/358841.358850"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. CHAZELLE B. and GUIBAS L. J., Fractional Cascading I: a Data Structuring Technique, Algorithmica, 1986, 1, 133-162.8584020639.68056","DOI":"10.1007\/BF01840440"},{"key":"R4","unstructured":"4. DIETZ P. F. and RAMAN R., Persistence, Amortization and Randomization, Tech. Report 353, University of Rochester, 1991.0800.683461095822"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"5. DIETZFELBINGER M., KARLIN A., MEHLHORN K., MEYERauf der HEIDE F., ROHNERT H., TARJAN R. E., Dynamic Perfect Hashing, Proc. 29-th Annual IEEE Symp. on Foundations of Computer Science, 1988, 524-531.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"6. DRISCOLL J. R., SARNAK N., SLEATOR D. D. and TARJAN R. E., Making Data Structures Persistent, J. Comput. System Sci., 1989, 38, 86-124.9900510667.68026","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"R7","unstructured":"7. EDELSBRUNNER H., A Note on Dynamic Range Searching, Bull. of the EATCS, 1981, 15, 34-40."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"8. GABOW H. N., BENTLEY J. L. and TARJAN R. E., Scaling and Related Techniques for Geometry Problems, Proc. 16-th Annual ACM Symp. on Theory of Computing, 1984, 135-143.","DOI":"10.1145\/800057.808675"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"9. KLEIN R., NURMI O., OTTMANN T. and WOOD D., A Dynamic Fixed Windowing Problem, Algorithmica, 1989, 4, 535-550.10193920684.68035","DOI":"10.1007\/BF01553907"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"10. MEHLHORN K. and N\u00c4HER S., Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space, Inform. Proc. Lett., 1990, 35, 183-189.10661210702.68042","DOI":"10.1016\/0020-0190(90)90022-P"},{"key":"R11","unstructured":"11. OVERMARS M. H., The Design of Dynamic Data Structures, Lecture Notes in Computer Science, 1983, Vol. 156, Springer-Verlag, Berlin.7108320545.68009"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"12. OVERMARS M. H., Efficient Data Structures for Range Searching on a Grid, J. of Algorithms, 1988, 9, 254-275.9361090637.68067","DOI":"10.1016\/0196-6774(88)90041-7"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"13. SARNAK N. and TARJAN R. E., Planar Point Location Using Persistent Search Trees, Comm. A.C.M., 1986, 29, 669-679.0732.68102848411","DOI":"10.1145\/6138.6151"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"14. SCHOLTEN H. W. and OVERMARS M. H., General Methods for Adding Range Restrictions to Decomposable Searching Problems, J. Symbolic Computation, 1989, 7, 1-10.9842670668.68073","DOI":"10.1016\/S0747-7171(89)80002-1"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"15. van EMDE BOAS P., Preserving Order in a Forest in Less than Logarithmic Time and Linear Space, Inform. Proc. Lett., 1977, 6, 80-82.0364.68053","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"16. van EMDE BOAS P., KAAS R. and ZIJLSTRA E., Design and Implementation of an Efficient Priority Queue, Math. Systems Theory, 1977, 10, 99-127.4317770363.60104","DOI":"10.1007\/BF01683268"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"17. WILLARD D. E. and LUEKER G. S., Adding Range Restriction Capability to Dynamic Data Structures, J. A.C.M., 1985, 32, 597-617.7962040629.68097","DOI":"10.1145\/3828.3839"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1994280100251\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T23:16:50Z","timestamp":1749943010000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1994280100251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"references-count":17,"journal-issue":{"issue":"1"},"alternative-id":["ita1994280100251"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1994280100251","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"type":"print","value":"0988-3754"},{"type":"electronic","value":"1290-385X"}],"subject":[],"published":{"date-parts":[[1994]]}}}