Using persistent data structures for adding range restrictions to searching problems
Hans-Peter Lenhof; Michiel Smid
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1994)
- Volume: 28, Issue: 1, page 25-49
- ISSN: 0988-3754
Access Full Article
top
How to cite
topLenhof, Hans-Peter, and Smid, Michiel. "Using persistent data structures for adding range restrictions to searching problems." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.1 (1994): 25-49. <http://eudml.org/doc/92468>.
@article{Lenhof1994,
author = {Lenhof, Hans-Peter, Smid, Michiel},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {1},
pages = {25-49},
publisher = {EDP-Sciences},
title = {Using persistent data structures for adding range restrictions to searching problems},
url = {http://eudml.org/doc/92468},
volume = {28},
year = {1994},
}
TY - JOUR
AU - Lenhof, Hans-Peter
AU - Smid, Michiel
TI - Using persistent data structures for adding range restrictions to searching problems
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 1
SP - 25
EP - 49
LA - eng
UR - http://eudml.org/doc/92468
ER -
References
top- 1. J. L. BENTLEY, Decomposable Searching Problems, Inform. Proc. Lett., 1979, 8, 244-251. Zbl0404.68067MR534072
- 2. J. L. BENTLEY, Multidimensional Divide and Conquer, Comm. ACM., 1980, 23, 214-229. Zbl0434.68049MR567150
- 3. B. CHAZELLE and L. J. GUIBAS, Fractional Cascading I: a Data Structuring Technique, Algorithmica, 1986, 1, 133-162. Zbl0639.68056MR858402
- 4. P. F. DIETZ and R. RAMAN, Persistence, Amortization and Randomization, Tech. Report 353, University of Rochester, 1991. Zbl0800.68346MR1095822
- 5. M. DIETZFELBINGER, A. KARLIN, K. MEHLHORN, F. MEYERauf der HEIDE, H. ROHNERT, R. E. TARJAN, Dynamic Perfect Hashing, Proc. 29-th Annual IEEE Symp. on Foundations of Computer Science, 1988, 524-531.
- 6. J. R. DRISCOLL, N. SARNAK, D. D. SLEATOR and R. E. TARJAN, Making Data Structures Persistent, J. Comput. System Sci., 1989, 38, 86-124. Zbl0667.68026MR990051
- 7. H. EDELSBRUNNER, A Note on Dynamic Range Searching, Bull. of the EATCS, 1981, 15, 34-40.
- 8. H. N. GABOW, J. L. BENTLEY and R. E. TARJAN, Scaling and Related Techniques for Geometry Problems, Proc. 16-th Annual ACM Symp. on Theory of Computing, 1984, 135-143.
- 9. R. KLEIN, O. NURMI, T. OTTMANN and D. WOOD, A Dynamic Fixed Windowing Problem, Algorithmica, 1989, 4, 535-550. Zbl0684.68035MR1019392
- 10. K. MEHLHORN and S. NÄHER, Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space, Inform. Proc. Lett., 1990, 35, 183-189. Zbl0702.68042MR1066121
- 11. M. H. OVERMARS, The Design of Dynamic Data Structures, Lecture Notes in Computer Science, 1983, Vol. 156, Springer-Verlag, Berlin. Zbl0545.68009MR710832
- 12. M. H. OVERMARS, Efficient Data Structures for Range Searching on a Grid, J. of Algorithms, 1988, 9, 254-275. Zbl0637.68067MR936109
- 13. N. SARNAK and R. E. TARJAN, Planar Point Location Using Persistent Search Trees, Comm. A.C.M., 1986, 29, 669-679. Zbl0732.68102MR848411
- 14. H. W. SCHOLTEN and M. H. OVERMARS, General Methods for Adding Range Restrictions to Decomposable Searching Problems, J. Symbolic Computation, 1989, 7, 1-10. Zbl0668.68073MR984267
- 15. P. van EMDE BOAS, Preserving Order in a Forest in Less than Logarithmic Time and Linear Space, Inform. Proc. Lett., 1977, 6, 80-82. Zbl0364.68053
- 16. P. van EMDE BOAS, R. KAAS and E. ZIJLSTRA, Design and Implementation of an Efficient Priority Queue, Math. Systems Theory, 1977, 10, 99-127. Zbl0363.60104MR431777
- 17. D. E. WILLARD and G. S. LUEKER, Adding Range Restriction Capability to Dynamic Data Structures, J. A.C.M., 1985, 32, 597-617. Zbl0629.68097MR796204
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.