@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},
}