@string{stoc = "Proc. ACM Symp. on Theory of Computation"} @string{focs = "Proc. IEEE Symp. on Foundations of Comp. Sci."} @string{socg = "Proc. ACM Symp. on Computational Geometry"} @string{soda = "Proc. ACM-SIAM Symp. on Discrete Algorithms"} @string{wads = "Proc. Workshop on Algorithms and Data Structures"} @string{alenex = "Proc. Workshop on Algorithm Engineering and Experimentation"} @string{swat = "Proc. Scandinavian Workshop on Algorithms Theory"} @string{esa = "Proc. Annual European Symposium on Algorithms"} @string{isaac = "Proc. Int. Symp. on Algorithms and Computation"} @string{spaa = "Proc. ACM Symp. on Parallel Algorithms and Architectures"} @string{pods = "Proc. ACM Symp. Principles of Database Systems"} @string{graph = "Proc. Graph-Theoretic Concepts in Computer Science"} @string{stacs = "Symposium on Theoretical Aspects of Computer Science"} @string{cad = "Proc. IEEE International Conference on CAD"} @string{design = "Proc. ACM/IEEE Design Automation Conference"} @string{manage = "Proc. ACM SIGMOD Conf. on Management of Data"} @string{vldb = "Proc. International Conf. on Very Large Databases"} @string{mfcs = "Proc. International Symp. on Mathematical Foundations of Computer Science"} @string{icalp= "Proc. Annual International Colloquium on Automata, Languages, and Programming"} @string{sigmod = "Proc. SIGMOD Intl. Conf. on Management of Data"} @string{wae = "Proc. Workshop on Algorithm Engineering"} @string{edbt = "Proc. Conference on Extending Database Technology"} @string{icde = "Proc. IEEE International Conference on Data Engineering"} @string{icdt = "Proc. International Conference on Database Theory"} @string{cocoon = "Proc. Annual Combinatorics and Computing Conference"} @string{sstd = "Proc. International Symposium on Spatial and Temporal Databases"} @string{survey = "ACM Computing Surveys"} @string{jcss = "Journal of Computer and System Sciences"} @string{jacm = "Journal of the ACM"} @string{ipl = "Information Processing Letters"} @string{transcomp = "IEEE Transactions on Computers"} @string{cacm = "Communications of the ACM"} @string{siamjour = "SIAM Journal of Computing"} @string{tcs = "Theoretical Computer Science"} @string{jalg = "Journal of Algorithms"} @string{computer = "IEEE Computer"} @string{alg = "Algorithmica"} @string{transknow ="IEEE Transactions on Knowledge and Data Engineering"} @string{dcg="Discrete and Computational Geometry"} @string{iandc="Information and Computation"} @string{cgta="International Journal of Computational Geometry \& Applications"} @string{acmexp="ACM Journal on Journal on Experimental Algorithmics"} @string{acmtrans="ACM Transactions on Database Systems"} @article{aggarwal:optimal, author = {A. Aggarwal and G. Plaxton}, title = {Optimal Parallel Sorting in Multi-Level Storage}, year = 1994, journal = soda, pages = {659-668}, address = {Arlington, VA} } @book{aho:design, author = {A. V. Aho and J. E. Hopcroft and J. D. Ullman}, title = {The Design and Analysis of Computer Algorithms}, publisher = {Addison-Wesley, Reading, MA}, year = 1974 } @article{aggarwal:input, author = {A. Aggarwal and J.~S. Vitter}, title = {The {I}nput/{O}utput Complexity of Sorting and Related Problems}, year = 1988, journal = cacm, volume = 31, number = 9, pages = {1116--1127}, keywords = {cacm} } @inproceedings{andrews:further, author = {D. S. Andrews and J. Snoeyink and J. Boritz and T. Chan and G. Denham and J. Harrison and C. Zhu}, title = {Further Comparisons of Algorithms for Geometric Intersection Problems}, year = 1994, booktitle = {Proc. 6th Int'l. Symp. on Spatial Data Handling} } @book{arcinfo, author = {ARC/INFO}, publisher = {ARC/INFO}, title = {Understanding GIS---the ARC/INFO method}, note = {Rev. 6 for workstations}, year = {1993} } @article{bayer:organization, author = {R. Bayer and E. McCreight}, title = {Organization and Maintenance of Large Ordered Indexes}, year = {1972}, journal = {Acta Informatica}, volume = 1, pages = {173-189} } @article{bentley:algorithms, author = {J. L. Bentley and T. A. Ottmann}, title = {Algorithms for Reporting and Counting Geometric Intersections}, year = 1979, journal = transcomp, volume = {C-28}, number = 9, pages = {643-647} } @article{bentley:multidimensional, author = {J. L. Bentley}, title = {Multidimensional Divide and Conquer}, year = {1980}, journal = cacm, volume = 23, number = 6, pages = {214-229} } @unpublished{bentley:klees, author = {J. L. Bentley}, title = {Algorithms for Klee's Rectangle Problems}, note = {Dept. of Computer Science, Carnegie Mellon Univ., unpublished notes}, year = 1977 } @techreport{blankenagel:xp-tree, author = {G. Blankenagel and R. H. G\"{u}ting}, title = {{XP}-Trees---{E}xternal Priority Search Trees}, institution = {FernUniversit\"{a}t Hagen, Informatik-Bericht Nr. 92}, year = 1990 } @article{blankenagel:external, author = {G. Blankenagel and R.H. G\"{u}ting}, title = {External Segment Trees}, journal = {Algorithmica}, volume = 12, year = 1994, pages = {498-532} } @article{blum:average, author = {N. Blum and K. Mehlhorn}, title = {On the average number of rebalancing operations in weight-balanced trees}, journal = tcs, volume = 11, year = 1980, pages = {303-320} } @inproceedings{chan:simple, author = {T. M. Chan}, title = {A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections}, year = 1994, booktitle = {Proc. of 6th Canadian Conference on Computational Geometry} } @inproceedings{chiang:experiments, author = {Y.-J. Chiang}, title = {Experiments on the Practical {I/O} Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep}, year = 1995, booktitle = wads # {, LNCS 955}, pages = {346-357} } @article{chiang:dynamic, author = {Y.-J. Chiang and R. Tamassia}, title = {Dynamic Algorithms in Computational Geometry}, journal = {Proceedings of IEEE, Special Issue on Computational Geometry}, volume = 80, number = 9, year = 1992, pages = {362-381} } @inproceedings{chiang:external, author = {Y.-J. Chiang and M. T. Goodrich and E. F. Grove and R. Tamassia and D. E. Vengroff and J. S. Vitter}, title = {External-Memory Graph Algorithms}, year = 1995, booktitle = soda, pages = {139-149}, } @inproceedings{chazelle:triangulating, author = {B. Chazelle}, title = {Triangulating a Simple Polygon in Linear Time}, year = 1990, booktitle = focs } @article{chazelle:optimal, author = {B. Chazelle and H. Edelsbrunner}, title = {An Optimal Algorithm for Intersecting Line Segments in the Plane}, year = 1992, journal = jacm, volume = 39, pages = {1-54} } @article{chazelle:bichromatic, author = {B. Chazelle and H. Edelsbrunner and L. J. Guibas and M. Sharir}, title = {Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains}, year = 1994, journal = {Algorithmica}, volume = 11, pages = {116-132} } @article{chazelle:fractionalI, author = {B. Chazelle and L. J. Guibas}, title = {Fractional Cascading: {I}. {A} Data Structuring Technique}, year = 1986, journal = {Algorithmica}, volume = 1, pages = {133-162} } @article{chazelle:fractionalII, author = {B. Chazelle and L. J. Guibas}, title = {Fractional Cascading: {II}.{A}pplications}, year = 1986, journal = {Algorithmica}, volume = 1, pages = {163-191} } @inproceedings{cormen:old, author = {Thomas H. Cormen and Leonard F. Wisniewski}, title = {Asymptotically Tight Bounds for Performing {BMMC} Permutations on Parallel Disk Systems}, year = {1993}, booktitle = spaa, pages = {130--139} } @Article{cormen:fast, author = "Thomas H. Cormen", title = "Fast Permuting in Disk Arrays", journal = "Journal of Parallel and Distributed Computing", year = 1993, volume = 17, number = "1-2", pages = "41-57", } @phdthesis{cormen:thesis, author = {Thomas H. Cormen}, title = {Virtual Memory for Data Parallel Computing}, year = 1992, school = {Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology}, } @InProceedings{cormen:asymptotically2, author = {Thomas H. Cormen and Thomas Sundquist and Leonard F. Wisniewski}, title = {Asymptotically Tight Bounds for Performing {BMMC} Permutations on Parallel Disk Systems}, booktitle = spaa, year = {1993}, pages = {130-139}, comment = {Expanded and improved version of cormen:asymptotically} } %%% change this!! @article{cormer:ubiquitous, author = {D. Comer}, title = {The Ubiquitous {B}-tree}, year = {1979}, journal = survey, number = {2}, volume = {11}, pages = {121-137} } @inproceedings{cromp, author = {R. F. Cromp}, title = {An Intellegent Information Fusion System for Handling the Archiving and Querying of Terabyte-sized Spatial Databases}, year = 1993, booktitle = {S. R. Tate ed., Report on the Workshop on Data and Image Compression Needs and Uses in the Scientific Community, CESDIS Technical Report Series, TR--93--99}, pages = {75-84}, } @article{edelsbrunner:new, author = {H. Edelsbrunner}, title = {A New Approach to Rectangle Intersections, Part {I} \& {II}}, journal = {Int. J. Computer Mathematics}, volume = 13, year = 1983, pages = {209-229} } @article{edelsbrunner:new1, author = {H. Edelsbrunner}, title = {A New Approach to Rectangle Intersections, Part {I}}, journal = {Int. J. Computer Mathematics}, volume = 13, year = 1983, pages = {209-219} } @article{edelsbrunner:new2, author = {H. Edelsbrunner}, title = {A New Approach to Rectangle Intersections, Part {II}}, journal = {Int. J. Computer Mathematics}, volume = 13, year = 1983, pages = {221-229} } @article{edelsbrunner:batched, author = {H. Edelsbrunner and M. Overmars}, title = {Batched Dynamic Solutions to Decomposable Searching Problems}, year = {1985}, journal = jalg, volume = {6}, pages = {515-542}, } @inproceedings{fleischer:simple, author = {R. Fleischer}, title = {A Simple Balanced Search Tree with {$O$}$(1)$ Worst-Case Update Time}, booktitle = isaac # {, LNCS 762}, year = 1993 } @book{foley:computer, author = {J.D. Foley and A. van Dam and S.K. Feiner and J.F. Hughes}, title = {Computer Graphics: Principles and Practice}, publisher = {Addison-Wesley}, year = {1990} } @article{fournier:triangulating, author = {A. Fournier and D. Y. Montuno}, title = {Triangulating Simple Polygons and Equivalent Problems}, year = 1984, journal = {ACM Trans. on Graphics}, volume = 3, number = 2, pages = {153-174} } @Article{nodine:blocking, author = {M. H. Nodine and M. T. Goodrich and J. S. Vitter}, title = {Blocking for External Graph Searching}, journal = alg, year = 1996, volume = 16, number = 2, pages = {181-214} } @inproceedings{goodrich:external, author = {M. T. Goodrich and J.-J. Tsay and D. E. Vengroff and J. S. Vitter}, title = {External-Memory Computational Geometry}, year = 1993, booktitle = focs, pages = {714-723} } @inproceedings{gunther:cell, author = {O. G\"{u}nther}, title = {The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases}, booktitle = icde, year = {1989}, pages = {598-605} } @inproceedings{icking:priority, author = {Ch. Icking and R. Klein and Th. Ottmann}, title = {Priority Search Trees in Secondary Memory}, booktitle = graph # {, LNCS 314}, year = 1987, pages = {84-93} } @inproceedings{kanellakis:constraint, author = {P. C. Kanellakis and G.M. Kuper and P.Z. Revesz}, title = {Constraint Query Languages}, booktitle = pods, year = 1990, pages = {299-313} } @Article{kanellakis:indexing, author = {P. C. Kanellakis and S. Ramaswamy and D. E. Vengroff and J. S. Vitter}, title = {Indexing for Data Models with Constraints and Classes}, journal = jcss, year = {1996}, volume = {52}, number = {3}, pages = {589-612} } @book{knuth:sorting, author = {D. E. Knuth}, series = {The Art of Computer Programming}, title = {Sorting and Searching}, year = 1998, volume = 3, edition = {second}, publisher = {Addison-Wesley, Reading MA} } @article{lomet:hB-tree, author = {D.B. Lomet and B. Salzberg}, title = {The {hB}-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance}, journal = {ACM Transactions on Database Systems}, volume = 15, number = 4, pages = {625-658}, year = 1990 } @book{laurini:fundamentals, author = {R. Laurini and A. D. Thompson}, title = {Fundamentals of Spatial Information Systems}, year = 1992, publisher = {A.P.I.C. Series, Academic Press, New York, NY} } @inproceedings{mairson:reporting, author = {H. G. Mairson and J. Stolfi}, title = {Reporting and Counting Intersections Between Two Sets of Line Segments}, year = 1988, booktitle = {R. Earnshaw (ed.), Theoretical Foundation of Computer Graphics and CAD, NATO ASI Series, Vol. F40}, pages = {307-326} } @article{mccreight:priority, author = {E.M. McCreight}, title = {Priority Search Trees}, year = 1985, journal = siamjour, volume = 14, number = 2, pages = {257-276} } @book{mehlhorn:1, author = {K. Mehlhorn}, title = {Data Structures and Algorithms 1: Sorting and Searching}, year = 1984, publisher = {Springer-Verlag, EATCS Monographs on Theoretical Computer Science} } @book{mehlhorn:3, author = {K. Mehlhorn}, title = {Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry}, year = 1984, publisher = {Springer-Verlag, EATCS Monographs on Theoretical Computer Science} } @article{nievergelt:grid, author = {J. Nievergelt and H. Hinterberger and K.C. Sevcik}, title = {The Grid File: An Adaptable, Symmetric Multikey File Structure}, journal = {ACM Transactions on Database Systems}, volume = 9, number = 1, year = 1984, pages = {38-71} } @article{nievergelt:binary, author = {J. Nievergelt and E. M. Reingold}, title = {Binary search tree of bounded balance}, journal = siamjour, volume = 2, number = 1, pages = {33-43}, year = 1973 } @inproceedings{nodine:deterministic, author = {M. H. Nodine and J. S. Vitter}, title = {Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors}, year = 1993, booktitle = spaa, pages= {120-129}, mynote = {this is the balance sort paper - parallel distribution sort} } @inproceedings{nodine:paradigms, author = {M. H. Nodine and J. S. Vitter}, title = {Paradigms for Optimal Sorting with Multiple Disks}, year = 1993, booktitle = {Proc. of the 26th Hawaii Int. Conf. on Systems Sciences} } @inproceedings{orenstein:spatial, author = {J.A. Orenstein}, title = {Spatial Query Processing in an Object-Oriented Database System}, booktitle = manage, year = 1986, pages = {326-336} } @book{overmars:design, author = {Mark H. Overmars}, title = {The Design of Dynamic Data Structures}, publisher = {Springer-Verlag, LNCS 156}, year = 1983 } @inproceedings{palazzi:counting, author = {L. Palazzi and J. Snoeyink}, title = {Counting and Reporting Red/Blue Segment Intersections}, year = 1993, booktitle = wads # {, LNCS 709}, pages = {530-540} } @article{yale:computer, author = {Yale N. Patt}, title = {The {I/O} Subsystem---A Candidate for Improvement}, year = 1994, journal = {Guest Editor's Introduction in IEEE Computer}, volume = 27, number = 3, pages = {15-16} } @book{preparata:computational, author = {F. P. Preparata and M. I. Shamos}, title = {Computational Geometry: An Introduction}, publisher = {Springer-Verlag}, year = {1985} } @inproceedings{ramaswamy:oodb, author = {S. Ramaswamy and P.C. Kanellakis}, title = {{OODB} indexing by class division}, booktitle = {A.P.I.C. Series, Academic Press, New York}, year = {1995} } @inproceedings{ramaswamy:path, author = {S. Ramaswamy and S. Subramanian}, title = {Path Caching: A Technique for Optimal External Searching}, booktitle = pods, year = {1994}, pages = {25-35} } @Article{ruemmler:iddm94, author = "Chris Ruemmler and John Wilkes", title = "An Introduction to Disk Drive Modeling", journal = computer, year = 1994, volume = 27, number = 3, pages = "17--28" } @inproceedings{robinson:kdb-tree, author = {J.T. Robinson}, title = {The {K-D-B} Tree: A Search Structure for Large Multidimensional Dynamic Indexes}, booktitle = sigmod, year = 1981, pages = {10-18} } @book{samet:applications, author = {H. Samet}, title = {Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS}, publisher = {Addison Wesley, MA}, year = 1990 } @book{samet:design, author = {H. Samet}, title = {The Design and Analyses of Spatial Data Structures}, publisher = {Addison Wesley, MA}, year = 1990 } @inproceedings{sellis:R+-tree, author = {T. Sellis and N. Roussopoulos and C. Faloutsos}, title = {The {R}$^+$-tree: A Dynamic Index for Multi-Dimensional Objects}, booktitle = vldb, year = {1987}, pages = {507-518} } @inproceedings{subramanian:p-range, author = {S. Subramanian and S. Ramaswamy}, title = {The {P}-range Tree: A New Data Structure for Range Searching in Secondary Memory}, booktitle = soda, pages = {378-387}, year = 1995 } @inproceedings{vengroff:transparent, author = {D. E. Vengroff}, title = {A Transparent Parallel {I/O} Environment}, year = 1994, booktitle = {Proc. DAGS Symposium on Parallel Computation}, keyword = {tpie} } @inproceedings{vengroff:efficient, author = {D. E. Vengroff and J. S. Vitter}, title = {Efficient {3-D} Range Searching in External Memory}, booktitle = stoc, year = 1996, pages = {192-201} } @inproceedings{vengroff:scientific, author = {D. E. Vengroff and J. S. Vitter}, title = {Supporting {I/O}-efficient Scientific Computation in {TPIE}}, booktitle = {Proc. IEEE Symp. on Parallel and Distributed Computing}, year = 1995, pages = {74-77}, note = {Appears also as Duke University Dept. of Computer Science technical report CS-1995-18}, } @article{vitter:parmem1, author = {J. S. Vitter and E. A. M. Shriver}, title = {Algorithms for Parallel Memory, {I}: Two-level Memories}, year = {1994}, journal = {Algorithmica}, volume = {12}, number = {2--3}, keyword = {parallel I/O algorithms, parallel memory, pario bib}, pages = {110-147}, comment = {Summarized in vitter:optimal.} } @article{vitter:parmem2, author = {J. S. Vitter and E. A. M. Shriver}, title = {Algorithms for Parallel Memory, {II}: {H}ierarchical Multilevel Memories}, year = {1994}, journal = {Algorithmica}, volume = {12}, number = {2--3}, pages = {148-169} } @inproceedings{zhu:further, author = {B. Zhu}, title = {Further Computational Geometry in Secondary Memory}, year = 1994, pages = {514-522}, booktitle = isaac } @unpublished{vankreveld:geographic, author = {M. van~Kreveld}, title = {Geographic Information Systems}, note = {Utrecht University, INF/DOC--95--01}, year = 1995 } @inproceedings{haas:exploiting, author = {Laura M. Haas and William F. Cody}, title = {Exploiting Extensible DBMS in Integrated Geographic Information Systems}, booktitle = {Proc. of Advances in Spatial Databases, LNCS 525}, year = 1991 } @article{hellerstein:coding, author = {L. Hellerstein and G. Gibson and R. M. Karp and R. H. Katz and D. A. Patterson}, title = {Coding Techniques for Handling Failures in Large Disk Arrays}, year = 1994, journal = {Algorithmica}, volume = 12, number = {2--3}, } @article{patterson:case, author = {D. A. Patterson and G. Gibson and R. H. Katz}, title = {A Case for Redundant Arrays of Inexpensive Disks (RAID)}, year = 1988, journal = manage, pages = {109-116}, address = {Chicago, IL}, keywords = {RAID} } @article{nodine:greed, author = {M. H. Nodine and J. S. Vitter}, title = {Greed Sort: {A}n Optimal Sorting Algorithm for Multiple Disks}, year = 1995, journal = jacm, vloume = 42, pages = {919-933}, mynote = {it used to be called nodine:large - SPAA 1991} } @article{vaishnavi:rectilinear, author = {V. K. Vaishnavi and D. Wood}, title = {Rectilinear Line Segment Intersection, Layered Segment Trees, and Dynamization}, year = 1982, journal = jalg, volume = 3, pages = {160-176} } @article{willard:adding, author = {D.E. Willard and G.S. Lueker}, title = {Adding Range Restriction Capability to Dynamic Data Structures}, year = 1985, journal = {Journal of the ACM}, volume = 32, number = 3, pages = {597-617} } @inproceedings{ashar:efficient, author = {P. Ashar and M. Cheong}, title = {Efficient Breadth-First Manipulation of Binary Decision Diagrams.}, booktitle = cad, year = 1994 } @inproceedings{brace:efficient, author = {S. K. Brace and R. L. Rudell and R. E. Bryant}, title = {Efficient Implementation of a {BDD} Package}, booktitle = design, year = 1990 } @article{gifford:twa, author = {D. Gifford and A. Spector}, title = {The{ TWA} Reservation System}, journal = cacm, volume = 27, year = 1984, pages = {650-665} } @TechReport{Klarlund:bdd, author = {N. Klarlund and T. Rauhe}, title = {{BDD} algorithms and cache misses}, institution = {BRICS, University of Aarhus}, year = 1996, number = {RS-96-26} } @inproceedings{vitter:efficient, author = {J. S. Vitter}, title = {Efficient Memory Access in Large-Scale Computation (invited paper)}, booktitle = stacs # {, LNCS 480}, year = {1991}, pages = {26-41} } @inproceedings{floyd:permuting, author = {R. W. Floyd}, title = {Permuting information in idealized two-level storage}, booktitle = {Complexity of Computer Calculations}, note = {R. Miller and J. Thatcher, Eds. Plenum, New York}, year = {1972}, pages = {105-109} } @inproceedings{hong:io, author = {J. W. Hong and H. T. Kung}, title = {{I/O} complexity: {T}he red-blue pebble game}, booktitle = stoc, year = {1981}, pages = {326-333} } @inproceedings{arge:obdd, author = {L. Arge}, title = {The {I/O}-Complexity of Ordered Binary-Decision Diagram Manipulation}, booktitle = isaac # {, LNCS 1004}, year = 1995, pages = {82-91}, note = {A complete version appear as BRICS technical report RS-96-29, University of Aarhus}, } @article{huddleston:new, author = {S. Huddleston and K. Mehlhorn}, title = {A New Data Structure for Representing Sorted Lists}, journal = {Acta Informatica}, volume = 17, year = 1982, pages = {157-184} } @article{blum:time, author = {M. Blum and R. W. Floyd and V. Pratt and R. L. Rievest and R. E. Tarjan}, title = {Time bounds for selection}, journal = jcss, volume = 7, year = 1973, pages = {448-461} } @article{bentley:optimal, author = {J. L. Bentley and D. Wood}, title = {An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles}, journal = transcomp, volume = 29, year = 1980, pages = {571-577} } @Article{ullman:input, author = {J. D. Ullman and M. Yannakakis}, title = {The input/output complexity of transitive closure}, journal = {Annals of Mathematics and Artificial Intellegence}, year = {1991}, volume = {3}, pages = {331-360} } @InProceedings{feuerstein:memory, author = {E. Feuerstein and A. Marchetti-Spaccamela}, title = {Memory paging for connectivity and path problems in graphs}, booktitle = isaac # {, LNCS 762}, pages = {416-425}, year = {1993} } @Article{bryant:graph, author = {R. Bryant}, title = {Graph-Based Algorithms for Boolean Function Manipulation}, journal = transcomp, year = {1986}, volume = {C-35}, number = {8} } @Article{Bryant:symbolic, author = {R. Bryant}, title = {Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams}, journal = survey, year = 1992, volume = 24, number = 3 } @Article{anderson:simple, author = {R. J. Anderson and G. L. Miller}, title = {A simple randomized parallel algorithm for list-ranking}, journal = ipl, year = {1990}, volume = {33}, pages = {269-273} } @Misc{vengroff:private96, author = {D. E. Vengroff}, title = {Private communication}, year = {1996} } @Misc{vengroff:private95, author = {D. E. Vengroff}, title = {Private communication}, year = {1995} } @Article{cole:deterministic, author = {R. Cole and U. Vishkin}, title = {Deterministic coin tossing with applications to optimal list-ranking}, journal = {Information and Control}, year = {1986}, volume = {70}, number = {1}, pages = {32-53} } @PhdThesis{chiang:thesis, author = {Yi-Jen Chiang}, title = {Dynamic and {I/O}-Efficient Algorithms for Computational Geometry and Graph Problems: Theoretical and Experimental Results}, school = {Brown University}, year = {1995}, month = {August} } @Misc{kumar:private95, author = {V. Kumar}, title = {Private Communication}, year = {1995} } @InProceedings{gergov:frontiers, author = {J. Gergov and C. Meinel}, title = {Frontiers of Feasible and Probabilistic Feasible Boolean Manipulation with Branching Programs}, booktitle = stacs # {, LNCS 665}, year = {1993} } @InProceedings{ochi:vector, author = {H. Ochi and N. Ishiura and S. Yajima}, title = {Breadth-First Manipulation of SBDD of Boolean Functions for Vector Processing}, booktitle = design, year = {1991} } @InProceedings{ochi:very, author = {H. Ochi and K. Yasuoka and S. Yajima}, title = {Breadth-First manipulation of Very Large Binary-Decision Diagrams}, booktitle = cad, year = {1993} } @InProceedings{rudell:dynamic, author = {R. Rudell}, title = {Dynamic Variable Ordering for Ordered Binary Decision Diagrams}, booktitle = cad, year = {1993} } @Article{sieling:reduction, author = {D. Sieling and I. Wegener}, title = {Reduction of OBDDs in linear time}, journal = ipl, year = {1993}, volume = {48} } @InProceedings{malik:logic, author = {S. Malik and A. R. Wang and R. K. Brayton and A. Sangiovanni-Vincentelli}, title = {Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment}, booktitle = cad, year = 1988 } @Book{Leeuwen:handbookA, author = {J. van Leeuwen}, title = {Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity}, publisher = {Elsevier}, year = {1990} } @Article{ganger:disk, author = {G. R. Ganger and B. L. Worthington and R. Y. Hou and Y. N. Patt}, title = {Disk Arrays. {H}igh-Performance, High-Reliability Storage Subsystems}, journal = computer, year = 1994, volume = 27, number = 3, pages = {30-46} } @InProceedings{aggarwal:virtual, author = {A. Aggarwal and A. K. Chandra}, title = {Virtual Memory Algorithms}, booktitle = stoc, year = {1988}, pages = {173-185}, } @InProceedings{alpern:uniform_old, author = {B. Alpern and L. Carter and E. Feig}, title = {Uniform Memory Hierarchies}, booktitle = focs, year = {1990}, pages = {600-608}, } @article{alpern:uniform, author = {B. Alpern and L. Carter and E. Feig and T. Selker}, title = {The Uniform Memory Hierarchy Model of Computation}, year = 1994, journal = {Algorithmica}, volume = 12, number = {2-3} } @InProceedings{aggarwal:model, author = {A. Aggarwal and B. Alpern and A. K. Chandra and M. Snir}, title = {A Model for Hierarchical Memory}, booktitle = stoc, year = {1987}, pages = {305-314}, } @InProceedings{aggarwal:hierarchical, author = {A. Aggarwal and A. K. Chandra and M. Snir}, title = {Hierarchical Memory with Block Transfer}, booktitle = focs, year = {1987}, pages = {204-216}, } @Book{cockcroft:sun, author = {A. Cockcroft}, title = {Sun Performance and Tuning. {SPARC} \& {S}olaris}, publisher = {Sun Microsystems {I}nc.}, year = {1995}, } @InProceedings{callahan:topology, author = {P. Callahan and M. T. Goodrich and K. Ramaiyer}, title = {Topology {B}-trees and Their Applications}, booktitle = wads # {, LNCS 955}, year = {1995}, pages = {381-392} } @PhdThesis{smid:thesis, author = {M. Smid}, title = {Dynamic Data Structures on Multiple Storage Media}, school = {University of Amsterdam}, year = {1989}, } @Misc{knudsen:simulating, author = {M. Knudsen and K. Larsen}, title = {Simulating {I/O}-algorithms}, howpublished = {Master student project, University of Aarhus}, year = {1993}, month = {August} } @InProceedings{ben-or:lower, author = {M. Ben-Or}, title = {Lower bounds for algebraic computation trees}, booktitle = stoc, year = {1983}, pages = {80-86} } @MastersThesis{mk, author = {M. Knudsen and K. Larsen}, title = {{I/O}-complexity of comparison and permutation problems}, school = {University of Aarhus}, year = {1992}, month = {November} } @Article{misra:finding, author = {J. Misra and D. Gries}, title = {Finding Repeated Elements}, journal = {Science of Computer Programming}, year = {1982}, volume = {2}, pages = {143-152} } @InProceedings{munro:sorting, author = {J. I. Munro and V. Raman}, title = {Sorting Multisets and Vectors In-Place}, booktitle = wads # {, LNCS 519}, year = {1991}, pages = {473-479}, } @Article{spira:sorting, author = {J. I. Munro and P. M. Spira}, title = {Sorting and Searching in Multisets}, journal = siamjour, year = {1976}, volume = {5}, number = {1}, pages = {1-8} } @Article{watson:human, author = {J. D. Watson}, title = {The human genome projekt: {P}ast, present, and future}, journal = {Science}, year = {1990}, volume = {248}, pages = {44-49} } @Book{mulmuley:computational, author = {K. Mulmuley}, title = {Computational {G}eometry. {A}n introduction through randomized algorithms}, publisher = {Prentice-{H}all}, year = {1994} } @Article{vitter:large, author = {J. S. Vitter and M. H. Nodine}, title = {Large-Scale Sorting in Uniform Memory Hierarchies}, journal = {Journal of Parallel and Distributed Computing}, year = {1993}, volume = {17}, pages = {107-114} } @InProceedings{juurlink:parallel, author = {B. H. H. Juurlink and H. A. G. Wijshoff}, title = {The Parallel Hierarchical Memory Model}, booktitle = swat # {, LNCS 824}, pages = {240-251}, year = {1993} } @TechReport{savage:space, author = {J. E. Savage}, title = {Space-Time Tradeoffs in Memory Hierarchies}, institution = {Brown University}, year = {1993}, number = {CS-93-08} } @InProceedings{savage:extending, AUTHOR = {J. E. Savage}, TITLE = {Extending the {H}ong-{K}ung model to memory hierachies}, BOOKTITLE = {Proceedings of the 1st Annual International Conference on Computing and Combinatorics}, PAGES = {270--281}, YEAR = 1995, VOLUME = 959, SERIES = {LNCS}, } @InProceedings{franciosa:orders, author = {P. G. Franciosa and M. Talamo}, title = {Orders, $k$-sets and fast halfplane search on paged memory}, booktitle = {Proc. Workshop on Orders, Algorithms and Applications (ORDAL'94), LNCS 831}, year = {1994}, pages = {117-127} } @Article{overmars:maintaining, author = {M. Overmars and M. Smid and M. de Berg and M. van Kreveld}, title = {Maintaining Range Trees in Secundary Memory. {P}art {I: P}artitions}, journal = {Acta Informatica}, year = {1990}, volume = {27}, pages = {423-452} } @Article{smid:maintaining, author = {M. Smid and M. Overmars}, title = {Maintaining Range Trees in Secundary Memory. {P}art {II: L}ower Bounds}, journal = {Acta Informatica}, year = {1990}, volume = {27}, pages = {453-480} } @InCollection{arge:miltersen, author = {L. Arge and P. B. Miltersen}, title = {On showing lower bounds for external-memory computational geometry}, booktitle = {External memory algorithms and visualization}, publisher = {American Mathematical Society, DIMACS series}, year = {1999}, editor = {J. Abello and J. S. Vitter}, } @InProceedings{henrich:paging, author = {A. Henrich and H-W. Six and P. Widmayer}, title = {Paging binary trees with external balancing}, booktitle = graph # {, LNCS 411}, year = {1989}, pages = {260-276} } @InProceedings{leiserson:efficient, author = {C. E. Leiserson and S. Rao and S. Toledo}, title = {Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers}, booktitle = focs, year = {1993}, pages = {704-713} } @Article{jiang:traversing, author = {B. Jiang}, title = {Traversing graphs in a paging environment {BFS} or {DFS}?}, journal = ipl, year = {1991}, volume = {37}, pages = {143-147} } @Article{jiang:io, author = {B. Jiang}, title = {{I/O} and {CPU}-optimal recorgnition of strongly connected components}, journal = ipl, year = {1993}, volume = {45}, pages = {111-115} } @InProceedings{gil:packing, author = {J. Gil and A. Itai}, title = {Packing Trees}, booktitle = esa # {, LNCS 979}, year = 1995, pages = {113-127} } @inproceedings{barve:competitive, author = {R. Barve and E. F. Grove and J. S. Vitter}, title = {A Competitive Application-Controlled Paging Algorithm for a Shared Cache}, booktitle = {Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science}, month = {October}, year = 1995, pages = {204--213} } @inproceedings{matias:dynamic, author = {Y. Matias and J. S. Vitter and W.-C. Ni}, title = {Dynamic Generation of Discrete Random Variates}, year = 1993, booktitle = {Proc. Fourth Annual ACM-SIAM Symp. on Discrete Algorithms}, address = {Austin, TX} } @inproceedings{hoang:multiple, author = {D. T. Hoang and P. M. Long and J. S. Vitter}, title = {Multiple-dictionary Compression Using Partial Matching}, month = {March}, year = 1995, booktitle = {Proceedings of the 1995 IEEE Data Compression Conference}, pages = {272--281} } @inproceedings{long:text, author = {P. M. Long and A. I. Natsev and J. S. Vitter}, booktitle = {Proceedings of the 1996 IEEE Data Compression Conference}, title = {Text Compression via Alphabet Re-Representation}, year = {1996}, month = {March}, pages = {161--170} } @inproceedings{lin:epsilon, author = {J.-H. Lin and J. S. Vitter}, title = {$\Epsilon$-Approximations with Minimum Packing Constraint Violation}, year = 1992, month = may, booktitle = {Proceedings of the 24th Annual ACM Symposium on Theory of Computation}, keywords = {stoc} } @article{lin:theory, author = {J.-H. Lin and J. S. Vitter}, title = {A Theory for Memory-Based Learning}, year = 1994, journal = {Machine Learning}, keywords = {COLT} } @inproceedings{lin:nearly, author = {J.-H. Lin and J. S. Vitter}, title = {Nearly Optimal Vector Quantization Via Linear Programming}, year = 1992, month = mar, booktitle = {Proceedings of the IEEE Data Compression Conference}, address = {Snowbird, Utah}, keywords = {DCC} } @inproceedings{hoang:explicit, author = {D. T. Hoang and P. M. Long and J. S. Vitter}, title = {Explicit Bit Minimization for Motion-Compensated Video Coding}, booktitle = {Proceedings of the 1994 IEEE Data Compression Conference}, publisher="IEEE Computer Society Press", address="Snowbird, UT", month={March}, year=1994, pages="175--184" } @article{barve:simple, author = {R. D. Barve and E. F. Grove and J. S. Vitter}, title = {Simple Randomized Mergesort on Parallel Disks}, journal = {Parallel Computing}, year = 1997, volume = 23, number = 4, comment = {Special issue on parallel I/O. An earlier version appears in Proc. of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA~'96), Padua, Italy, June 1996, 109--118} } @InProceedings{clark:efficient, author = {D. R. Clark and J. I. Munro}, title = {Efficient Suffix Trees on Secondary Storage}, booktitle = soda, year = {1996}, pages = {383-391} } @InProceedings{ferragina:fully, author = {P. Ferragina and R. Grossi}, title = {A fully-Dynamic Data Structure for External Substring Search}, booktitle = stoc, year = {1995}, pages = {693-702}, } @InProceedings{ferragina:fast, author = {P. Ferragina and R. Grossi}, title = {Fast String Searching in Secondary Storage: {T}heoretical Developments and Experimental Results}, booktitle = soda, year = {1996}, pages = {373-382} } @Article{tarjan:amortized, author = {R. E. Tarjan}, title = {Amortized Computational Complexity}, journal = {SIAM J. Alg. Disc. Meth.}, year = {1985}, volume = {6}, number = {2}, pages = {306-318} } @PhdThesis{arge:thesis, author = {L. Arge}, title = {Efficient External-Memory Data Structures and Applications}, school = {University of Aarhus}, year = {1996}, month = {February/August} } @Article{graham:efficient, author = {R. L. Graham}, title = {An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set}, journal = ipl, year = 1972, volume = 1, pages = {132-133} } @Article{kirkpatrick:ultimate, author = {D. G. Kirkpatrick and R. Seidel}, title = {The Ultimate Planar Convex Hull Algorithm?}, journal = siamjour, year = 1986, volume = 15, pages = {287-299} } @Article{guibas:primitives, author = {L. J. Guibas and J. Stolfi}, title = {Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams}, journal = {ACM Trans. on Graphics}, year = 1985, volume = 4, pages = {74-123} } @Book{cormen:introduction, author = {T. H. Cormen and C. E. Leiserson and R. L. Rivest}, title = {Introduction to Algorithms}, publisher = {The MIT Press, Cambridge, Mass.}, year = 1990 } @Book{deberg:computational, title = {Computational Geometry -- Algorithms and Applications}, author = {M. de Berg and M. van Kreveld and M. Overmars and O. Schwarzkopf}, publisher = {Springer Verlag, Berlin}, year = {1997} } @Manual{arge:tpie0901a, title = {TPIE User Manual and Reference (edition 0.9.01a)}, author = {L. Arge and R. Barve and O. Procopiuc and L. Toma and D. E. Vengroff and R. Wickremesinghe}, organization = {Duke University}, year = 1999, note = "The manual and software distribution are available on the web at \texttt{http://www.cs.duke.edu/TPIE/}" } @InProceedings{kumar:improved, author = {V. Kumar and E. Schwabe}, title = {Improved Algorithms and Data Structures for Solving Graph Problems in External Memory}, booktitle = {Proc. IEEE Symp. on Parallel and Distributed Processing}, year = {1996}, pages = {169-177} } @InProceedings{arge:interval, author = {L. Arge and J. S. Vitter}, title = {Optimal Dynamic Interval Management in External Memory}, booktitle = focs, year = 1996, pages = {560-569} } @Article{baumgarten:dynamic, author = {H. Baumgarten and H. Jung and K. Mehlhorn}, title = {Dynamic Point Location in General Subdivisions}, journal = jalg, year = 1994, volume = 17, pages = {342-380} } @Article{atallah:cascading, author = {M. J. Atallah and R. Cole and M. T. Goodrich}, title = {Cascading divide-and-conquer: {A} technique for designing parallel algorithms}, journal = siamjour, year = 1989, volume = 18, number = 3, pages = {499-532} } @InProceedings{bentley:fast, author = {J. L. Bentley and R. Sedgewick}, title = {Fast Algorithms for Sorting and Searching Strings}, booktitle = soda, pages = {360-369}, year = {1996} } @InProceedings{hagerup:string, author = {T. Hagerup}, title = {Optimal Parallel String Algorithms: {M}erging, Sorting and Computing the Minimum}, booktitle = stoc, year = {1994}, pages = {382-391} } @Article{jaja:sorting, author = {J. F. J\'{a}{J}\'{a} and K. W. Ryu and U. Vishkin}, title = {Sorting strings and constructing digital search trees in parallel}, journal = tcs, volume = 154, number = 2, pages = {225-245}, year = 1996 } @Article{frenkel:human, author = {K. A. Frenkel}, title = {The human genome project and informatics}, journal = cacm, volume = 34, year = 1991, pages = {41-51} } @Article{prywes:organization, author = {N. S. Prywes and H. J. Gray}, title = {The organization of a Multilist-type associative memory}, journal = {IEEE Trans. on Communication and Electronics}, volume = 68, year = 1963, pages = {488-492} } @Article{bayer:prefix, author = {R. Bayer and K. Unterauer}, title = {Prefix {B}-trees}, journal = {ACM Trans. Database Syst.}, volume = 2, number = 1, year = 1977, pages = {11-26} } @Article{morrison:patricia, author = {D. R. Morrison}, title = {{PATRICIA}: {P}ractical algorithm to retrieve information coded in alphanumeric}, journal = jacm, volume = 15, year = 1968, pages = {514-534} } @Article{mamber:suffix, author = {U. Manber and G. Myers}, title = {Suffix arrays: {A} new method for on-line string searches}, journal = siamjour, volume = 25, number = 5, year = 1993, pages = {935-948} } @Unpublished{ferragina:external, author = {P. Ferragina and R. Grossi}, title = {An external-memory indexing data structure with applications}, year = {1996}, note = {Full version of STOC'95 paper ``A fully-Dynamic data structure for external substring search''} } @InProceedings{karp:rapid, author = {R. Karp and R. Miller and A. Rosenberg}, title = {Rapid identification of repeated patterns in strings, arrays and trees}, booktitle = stoc, year = 1972, pages = {125-136} } @InProceedings{adler:coding, author = {M. Adler}, title = {New coding techniques for improved bandwidth utilization}, booktitle = focs, year = 1996, pages = {173-182} } %%%% Roberto and Paolo (string) refs %%%% @book{book-gonnet, author = {R.~A. Baeza-Yates and G.~H. Gonnet}, title = {Handbook of Algorithms and Data Structures}, publisher = {Addison-Wesley}, year = 1991, } @article{emde, author = {P. Van~Emde~Boas}, title = {Preserving order in a forest in less than logarithmic time and linear space}, journal = ipl, year = 1977, volume = "6", pages = {80--82}, } @article{fredwil, author = {M.L. Fredman and D.E. Willard}, title = {Surpassing the information theoretic bound with fusion trees}, journal = jcss, volume = 47, pages = "424--436", year = 1993 } @inProceedings{AHNR, author = {A. Andersson and T. Hagerup and S. Nilsson and R. Raman}, title = {Sorting in linear time?}, booktitle = stoc, pages = "427--436", year = 1995, } @inProceedings{AN94, author = {A. Andersson and S. Nilsson}, title = {A new efficient radix sort}, booktitle = focs, pages = "714--721", year = 1994, } @inProceedings{T97, author = {M. Thorup}, title = {Randomized sorting in $O(n \log \log n)$ time and linear space using addition, shift, and bit-wise boolean operations}, booktitle = soda, year = 1997, pages = {352-359} } @inProceedings{HP92, author = {T. Hagerup and O. Petersson}, title = {Merging and sorting strings in parallel}, booktitle = mfcs, pages = "298--306", year = 1992 } @article{dienst, author = {E. A. Fox and R. M. Akscyn and R. K. Furuta and J. J. Leggett}, title = {Special issue: Digital Libraries: Introduction}, journal = {Communications of the ACM}, volume = 38, number = 4, month = {April}, year = 1995 } @Article{merret, author = "T. H. Merrett", title = "Why Sort-Merge Gives the Best Implementation of the Natural Join", journal = "ACM SIGMOD Record", volume = "13", number = "2", year = "1983" } @article{mccreight, author = {E. M. McCreight}, title = {A space-economical suffix tree construction algorithm}, journal = jacm, year = 1976, volume = 23, number = 2, pages = {262--272}, } @inproceedings{vengroff:i/o, author = {D. E. Vengroff and J. S. Vitter}, title = {{I/O}-Efficient Scientific Computation using {TPIE}}, year = 1996, booktitle = {Proceedings of the Goddard Conference on Mass Storage Systems and Technologies}, series = {NASA Conference Publication 3340, Volume II}, pages = {553--570} } %%%%%%% @Article{chen:raid-survey, author = {Peter M. Chen and Edward K. Lee and Garth A. Gibson and Randy H. Katz and David A. Patterson}, title = {{RAID:} High-performance, Reliable Secondary Storage}, journal = {ACM Computing Surveys}, year = {1994}, month = {June}, volume = {26}, number = {2}, pages = {145--185}, keyword = {RAID, disk array, parallel I/O, survey, pario bib}, comment = {An excellent overview of RAID concepts and technology. It starts from the beginning with a discussion of disk hardware, RAID basics, etc, and then goes on to discuss some of the more advanced features. They also describe a few RAID implementations. Basically, it is a perfect paper to read for folks new to RAID.} } @InProceedings{thorup:ram, author = {M. Thorup}, title = {On {RAM} priority queues}, booktitle = soda, year = 1996, pages = {59-67} } @article{gibson:strategic, title = {Strategic Directions in Storage {I/O} for Large-Scale Computing}, author = {G. A. Gibson and J. S. Vitter and J. Wilkes, Eds.}, journal = survey, volume = {28}, number = {4}, year = 1996 } @article{vitter:IO, title = {{I/O}-Efficient Algorithms and Environments for Large-Scale Computing}, author = {D. E. Vengroff and J. S. Vitter}, journal = {ACM Computing Surveys}, volume = {28}, number = {4es}, month = {December}, year = 1996, note = {article 212} } @article{vitter:communication, title = {Communication Issues in Large-Scale Geometric Computation}, author = {J. S. Vitter}, journal = {ACM Computing Surveys}, volume = {28}, number = {4es}, month = {December}, year = 1996, note = {article 20} } @inproceedings{arge:strings, author = {L. Arge and P. Ferragina and R. Grossi and J. Vitter}, title = {On Sorting Strings in External Memory}, booktitle = stoc, pages = {540-548}, year = {1997} } %%%% @incollection{widmayer:notes, author = {J. Nievergelt and P. Widmayer}, title = {Spatial data structures: {C}oncepts and design choices}, booktitle = {Algorithmic Foundations of GIS}, editor = {M. van Kreveld and J. Nievergelt and T. Roos and P. Widmayer}, publisher = {Springer-Verlag, LNCS 1340}, year = 1997, pages = {153-197} } @inproceedings{esastring:96, author = {P. Ferragina and F. Luccio}, title = {On the parallel dictionary matching problem: New results with applications}, booktitle = esa # {, LNCS 1136}, pages = {261-275}, year = 1996 } %%%% @inproceedings{kobler:nasa, author = {B. Kobler and J. Berbert}, title = {{NASA} Earth Observing Systems Data Information System ({EOSDIS})}, booktitle = {Digest of Papers: 11'th IEEE Symp. on Mass Storage Systems}, year = {1991} } @Article{lipton:separator, author = {R. J. Lipton and R. E. Tarjan}, title = {A separator theorem for planar graphs}, journal = {SIAM Journal of Applied Math.}, year = {1979}, volume = {36}, pages = {177-189}, } @incollection{kreveld:gisbook, author = {M. Van Kreveld}, title = {Digital Elevation Models: overview and selected {TIN} algorithms}, booktitle = {Algorithmic Foundations of GIS}, editor = {M. van Kreveld and J. Nievergelt and T. Roos and P. Widmayer}, publisher = {Springer-Verlag, LNCS 1340}, year = 1997 } @Article{sarnak:planar, author = {N. Sarnak and R. E. Tarjan}, title = {Planar point location using persistent search trees}, journal = cacm, year = {1986}, volume = {29}, pages = {669-679}, } @Article{frederickson:fast, author = {G. N. Frederickson}, title = {Fast algorithms for shortest paths in planar graphs, with applications}, journal = siamjour, year = {1987}, volume = {16}, pages = {1004-1022} } @inproceedings{pflm-tin-78, author = "T.K. Peucker and R.J. Fowler and J.J. Little and D.M. Mark", title = "The Triangulated Irregular Network", booktitle = "Proc. DTM Symp.\ Am.\ Soc. of Photogrammetry---Am. Congress on Survey and Mapping", year = 1978, pages = "24--31", update = "96.07 kreveld" } @inproceedings{chiang:isosurface, author = {Y.-J. Chiang and C. T. Silva}, title = {{I/O} Optimal Isosurface Extraction}, booktitle = {Proc. IEEE Visualization}, pages = {293-300}, year = {1997} } @InProceedings{chiang:interactive, author = {Y.-J. Chiang and C. T. Silva and W. J. Schroeder}, title = {Interactive Out-Of-Core Isosurface Extraction}, booktitle = {Proc. IEEE Visualization}, pages = {167--174}, year = {1998} } @InCollection{chiang:isosurfacebook, author = {Y.-J. Chiang and C. T. Silva}, title = {External memory techniques for isosurface extraction in scientific visualization}, booktitle = {External memory algorithms and visualization}, publisher = {American Mathematical Society, DIMACS series in Discrete Mathematics and Theoretical Computer Science}, year = {1999}, pages = {247-277}, editor = {J. Abello and J. S. Vitter}, } @InProceedings{borodin:competitive, author = {A. Borodin and S. Irani and P. Raghaven and B. Schieber}, title = {Competitive Paging with Locality of Reference}, booktitle = stoc, year = {1991}, pages = {249-259} } @article{romanik:using, author = {K. Romanik and J. S. Vitter}, title = {Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments}, journal = {Information and Computation}, volume = {128}, number = {2}, month = {August~1}, year = {1996}, pages = {87--108} } @inproceedings{kreveld:variations , author = "M. van Kreveld" , title = "Variations on sweep algorithms: Efficient computation of extended viewsheds and classifications" , booktitle = "Proc. 7th Int.\ Symp.\ on Spatial Data Handling" , year = 1996 , pages = "13A.15--13A.27" , update = "96.08 kreveld" } @inproceedings{deberg:simple , author = "M. de Berg and M. van Kreveld and R. van Oostrum and M. Overmars" , title = "Simple traversal of a subdivision without extra storage" , booktitle = "Proc. 3rd ACM Workshop on Advances in GIS" , year = 1995 , pages = "77--84" , update = "96.08 kreveld" } @Book{gisbook, author = {M. van Kreveld and J. Nievergelt and T. Roos and P. Widmayer (Eds.)}, title = {Algorithmic Foundations of GIS}, publisher = {Springer-Verlag}, year = {1997}, series = {LNCS 1340}, } @article{evans:selection , author = "I. S. Evans" , title = "The Selection of Class Intervals" , journal = "Trans. Inst. Br. Geogrs." , volume = 2 , year = 1977 , pages = "98--124" , update = "95.12 kreveld" } %%%% @InProceedings{patel:building, author = {J. Patel and J. Yu and N. Kabra and K. Tufte and J. Burger and N. Hall and K. Ramasamy and R. Lueder and C. Ellmann and J. Kupsch and S. Guo and J. Larson and D. DeWitt and J. Naughton}, title = {Building a Scalable Geo-Spatial {DBMS}: {T}echnology, Implementation, and Evaluation}, booktitle = sigmod, year = {1997}, } %%%% @InProceedings{aamvv-empgbtag97, author = {P. K. Agarwal and L. Arge and T. M. Murali and K. Varadarajan and J. S. Vitter}, title = {{I/O}-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking}, booktitle = soda, pages = {117-126}, year = {1998} } @Article{mccreight:problem81-8, author = {E. McCreight}, title = {$<$problem 81-8$>$}, journal = jalg, year = {1981}, volume = {2}, pages = {314}, } @InProceedings{patel:partition, author = {J. M. Patel and D. J. DeWitt}, title = {Partition Based Spatial-Merge Join}, booktitle = sigmod, pages = {259-270}, year = {1996}, } @InProceedings{brinkhoff:efficient, author = {T. Brinkhoff and H.-P. Kriegel and B. Seeger}, title = {Efficient Processing of Spatial Joins Using {R}-trees}, booktitle = sigmod, year = {1993}, } @Article{bentley:decomposable, author = {J. L. Bentley}, title = {Decomposable searching problems}, journal = ipl, year = {1979}, volume = {8}, number = {5}, pages = {244-251}, } @Article{overmars:worstcase, author = {M. H. Overmars and J. Van Leeuwen}, title = {Worst-case optimal insertion and deletion methods for decomposable searching problems}, journal = ipl, year = {1981}, volume = {12}, pages = {168-173}, } @Article{edelsbrunner:intersection, author = {H. Edelsbrunner and H. A. Maurer}, title = {On the intersection of orthogonal objects}, journal = ipl, year = {1981}, volume = {13}, pages = {177-181}, } @Article{six:counting, author = {H. W. Six and D. Wood}, title = {Counting and reporting intersections of $d$-ranges}, journal = transcomp, year = {1982}, volume = {31}, pages = {181-187}, } @Article{graefe:query, author = {G. Graefe}, title = {Query evaluation techniques for large databases}, journal = survey, year = {1993}, volume = {25}, number = {2}, pages = {73-170}, } %%% change this!! @Book{tanzel:temporal, author = {A. U. Tanzel and J. Clifford and S. Gadia and S. Jajodia and A. Segev and R. Snodgrass}, title = {Temporal Databases: {T}heory, Design and Implementation}, publisher = {The Benjamin/Cummings Publishing Company Inc.}, year = {1993}, } @Article{driscoll:making, author = {J. R. Driscoll and N. Sarnak and D. D. Sleator and R. Tarjan}, title = {Making Data Structures Persistent}, journal = jcss, year = {1989}, volume = {38}, pages = {86-124} } @InProceedings{lo:seeded, title = "Spatial Joins Using Seeded Trees", author = "M.-L. Lo and C. V. Ravishankar", booktitle = sigmod, year = "1994", pages = "209--220", } @InProceedings{lo:hash, title = "Spatial Hash-Joins", author = "M.-L. Lo and C. V. Ravishankar", booktitle = sigmod, year = "1996", pages = "247--258", } @InProceedings{gunter:spatial, author = "O. G{\"u}nther", title = "Efficient Computation of Spatial Joins", pages = "50--60", booktitle = icde, year = "1993", } @InProceedings{koudas:size, author = {N. Koudas and K. C. Sevcik}, title = {Size Separation Spatial Join}, booktitle = sigmod, year = {1997}, pages = {324-335}, } @InProceedings{kreveld:contour, author = {M. van Kreveld and R. van Oostrum and C. Bajaj and V. Pascucci and D. Schikore}, title = {Contour Trees and Small Seed Sets for Isosurface Traversal}, booktitle = {Proc. ACM Annual Symposium on Computational Geometry}, year = {1997}, pages = {212-219} } @InProceedings{arge:theory, author = {L. Arge and O. Procopiuc and S. Ramaswamy and T. Suel and J. S. Vitter}, title = {Theory and Practice of {I/O}-Efficient Algorithms for Multidimensional Batched Searching Problems}, booktitle = soda, pages = {685-694}, year = {1998} } @InCollection{ae-grsr-97, author = {P. K. Agarwal and J. Erickson}, title = {Geometric range searching and its relatives}, booktitle = {Discrete and Computational Geometry: {T}en Years Later}, year = {1997}, editor = {B. Chazelle and E. Goodman and R. Pollack}, publisher = {Mathematical Society Press}, } @Article{tamassia:strategic, author = {R. Tamassia, editor}, title = {Strategic directions in computational geometry}, journal = survey, year = {1996}, volume = {28}, number = {4}, }