Journal and Conference Articles

This section jointly lists Dr. Vitter's journal and conference papers. In several cases, the journal paper is an expanded and more detailed version of a conference paper, so for succinctness, their listings are combined into a single entry. Conference papers in computer science are important in their own right; they are generally peer-reviewed, often with very low acceptance ratios.

1.

J. S. Vitter. ``A Shared Memory Scheme for Coalesced Hashing,'' Information Processing Letters, 13(2), November 13, 1981, 77-79.

2.

J. S. Vitter. ``Deletion Algorithms for Hashing that Preserve Randomness,'' Journal of Algorithms, 3(3), September 1982, 261-275. An extended abstract appears in Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '81), Nashville, TN, October 1981, 127-132.

3.

J. S. Vitter. ``Implementations for Coalesced Hashing,'' Communications of the ACM, 25(12), December 1982, 911-926.

4.

J. S. Vitter. ``Analysis of the Search Performance of Coalesced Hashing,'' Journal of the ACM, 30(2), April 1983, 231-258. An extended abstract appears in ``Tuning the Coalesced Hashing Method to Obtain Optimum Performance,'' Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS '80), Syracuse, NY, October 1980, 238-247.

5.

J. S. Vitter and W.-C. Chen. ``Analysis of Early-Insertion Standard Coalesced Hashing,'' SIAM Journal on Computing, 12(4), November 1983, 667-676.

6.

J. S. Vitter. ``Faster Methods for Random Sampling,'' Communications of the ACM, 27(7), July 1984, 703-718. An extended abstract appears in ``Optimum Random Sampling,'' Proceedings of the 17th Annual Conference on Information Sciences and Systems, Baltimore, MD, March 1983, 158-164. Also in ``Optimum Algorithms for Two Random Sampling Problems,'' Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '83), Tucson, AZ, November 1983, 65-75.

7.

J. S. Vitter. ``US&R: A New Framework for Redoing,'' IEEE Software, 1(4), October 1984, 39-52. An extended abstract appears in Proceedings of the ACM Software Engineering Symposium on Practical Software Development Environments, Pittsburgh, PA, April 1984, 168-176.

8.

J. S. Vitter and R. A. Simons. ``Parallel Algorithms for Unification and Other Complete Problems for $\cal P$,'' Proceedings of the 1984 ACM Annual Conference: The Fifth Generation Challenge (ACM '84), San Francisco, CA, October 1984, 75-84.

9.

W.-C. Chen and J. S. Vitter. ``Analysis of New Variants of Coalesced Hashing,'' ACM Transactions on Database Systems, 9(4), December 1984, 616-645. An addendum appears in ACM Transactions on Database Systems, 10(1), March 1985, 127. An extended abstract appears in ``New Variants of Coalesced Hashing,'' Proceedings of the 21st Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, October 1983, 683-692.

10.

E. E. Lindstrom and J. S. Vitter. ``The Design and Analysis of BucketSort for Bubble Memory Secondary Storage,'' IEEE Transactions on Computers, C-34(3), March 1985, 218-233. An extended abstract appears in ``The Design and Analysis of BucketSort,'' 22nd Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, October 1984, 525-534.

11.

J. S. Vitter. ``Random Sampling with a Reservoir,'' ACM Transactions on Mathematical Software, 11(1), March 1985, 37-57. An extended abstract appears in ``Optimum Algorithms for Two Random Sampling Problems,'' Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '83), Tucson, AZ, November 1983, 65-75.

12.

J. S. Vitter and W.-C. Chen. ``Optimum Algorithms for a Model of Direct Chaining,'' SIAM Journal on Computing, 14(2), May 1985, 490-499.

13.

J. S. Vitter. ``An Efficient I/O Interface for Optical Disks,'' ACM Transactions on Database Systems, 10(2), June 1985, 129-162. An extended abstract appears in ``Computational Complexity of an Optical Disk Interface,'' Proceedings of the 11th Annual International Colloquium on Automata, Languages, and Programming (ICALP '84), Antwerp, Belgium, July 1984, published in Lecture Notes in Computer Science, 172, Springer-Verlag, Berlin, Germany, 490-502.

14.

C. J. Van Wyk and J. S. Vitter. ``The Complexity of Hashing with Lazy Deletion,'' Algorithmica 1(1), 1986, 17-29.

15.

R. Sedgewick and J. S. Vitter. ``Shortest Paths in Euclidean Graphs,'' Algorithmica, 1(1), 1986, 31-48. An extended abstract appears in Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science (FOCS '84), West Palm Beach, FL, October 1984, 417-424.

16.

J. S. Vitter and R. A. Simons. ``New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for $\cal P$,'' IEEE Transactions on Computers, C-35(5), May 1986, 403-418.

17.

W.-C. Chen and J. S. Vitter. ``Deletion Algorithms for Coalesced Hashing,'' The Computer Journal, 29(5), October 1986, 436-450.

18.

J. E. Savage and J. S. Vitter. ``Parallelism in Space-Time Tradeoffs,'' Proceedings of the International Workshop on Parallel Computing and VLSI, Amalfi, Italy, May 1984, published in VLSI: Algorithms and Architectures (edited by P. Bertolazzi and F. Luccio), Elsevier Science Press, 1985, 49-58.

19.

J. T. Stasko and J. S. Vitter. ``Pairing Heaps: Experiments and Analysis,'' Communications of the ACM, 30(3), March 1987, 234-249.

20.

J. S. Vitter. ``An Efficient Algorithm for Sequential Random Sampling,'' ACM Transactions on Mathematical Software, 13(1), March 1987, 58-67.

21.

J. S. Vitter. ``Design and Analysis of Dynamic Huffman Codes,'' Journal of the ACM, 34(4), October 1987, 825-845. An extended abstract appears in ``The Design and Analysis of Dynamic Huffman Coding,'' Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS '85), Portland, OR, October 1985, 293-302.

22.

C. A. Schevon and J. S. Vitter. ``A Parallel Algorithm for Recognizing Unordered Depth-First Search,'' Information Processing Letters, June 24, 1988, 105-110.

23.

A. Aggarwal and J. S. Vitter. ``The Input/Output Complexity of Sorting and Related Problems,'' Communications of the ACM, 31(9), September 1988, 1116-1127. An extended abstract appears in ``The I/O Complexity of Sorting and Related Problems,'' Proceedings of the 14th Annual International Colloquium on Automata, Languages, and Programming (ICALP '87), Karlsruhe, West Germany, July 1987, published in Lecture Notes in Computer Science, 267, Springer-Verlag, Berlin, Germany.

24.

J. S. Vitter. ``ALGORITHM 673 Dynamic Huffman Coding,'' ACM Transactions on Mathematical Software, 15(2), June 1989, 158-167. Also appears in Collected Algorithms of ACM.

25.

R. Tamassia and J. S. Vitter. ``Dynamic Graph Algorithms,'' Proceedings of the 3rd Australian Workshop on Combinatorial Algorithms, Bali, Indonesia, June 1990.

26.

F. P. Preparata, J. S. Vitter, and M. Yvinec. ``Computation of the Axial View of a Set of Isothetic Parallelepipeds,'' ACM Transactions on Graphics, 9(3), July 1990, 278-300.

27.

J. S. Vitter. ``Efficient Memory Access in Large-Scale Computation,'' invited paper in Proceedings of the 1991 Symposium on Theoretical Aspects of Computer Science (STACS '91), Hamburg, West Germany, February 1991, published in Lecture Notes in Computer Science, 480, Springer-Verlag, Berlin, Germany, 26-41.

28.

R. Tamassia, I. G. Tollis, and J. S. Vitter. ``Lower Bounds for Planar Orthogonal Drawings of Graphs,'' Information Processing Letters, 39, 1991, 35-40. An extended abstract appears in ``Lower Bounds and Parallel Algorithms for Planar Orthogonal Grid Drawings,'' Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing (SPDP '91), Dallas, TX, December 1991, 386-393.

29.

A. L. Buchsbaum, P. C. Kanellakis, and J. S. Vitter. ``A Data Structure for Arc Insertion and Regular Path Finding,'' invited paper in special issue on deductive databases in Annals of Mathematics and Artificial Intelligence, 3(2-4), March 1991. An extended abstract appears in Proceedings of the 1st Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '90), San Francisco, CA, January 1990, 22-31.

30.

R. Tamassia and J. S. Vitter. ``Parallel Transitive Closure and Point Location in Planar Structures,'' SIAM Journal on Computing, 20(4), August 1991, 708-725. An extended abstract appears in ``Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures,'' Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '89), Sante Fe, NM, June 1989, 399-408. Also appears as an invited paper in Proceedings of the International Workshop on Discrete Algorithms and Complexity, Fukuoka, Japan, November 1989, 169-178.

31.

C. M. Kenyon and J. S. Vitter. ``Maximum Queue Size and Hashing with Lazy Deletion,'' Algorithmica, 6(4), 1991, 597-619. An extended abstract appears in Proceedings of the 20th Annual Symposium on the Interface of Computing Science and Statistics, Reston, VA, April 1988, 743-748.

32.

M. H. Nodine, D. P. Lopresti and J. S. Vitter. ``I/O Overhead and Parallel VLSI Architectures for Lattice Computations,'' IEEE Transactions on Computers, 40(7), July 1991, 843-852. An extended abstract appears in Proceedings of the 1990 International Conference on Computing and Information (ICCI '90), Niagara Falls, Canada, May 1990, 472-476. Also published in Advances in Computing and Information, Lecture Notes in Computer Science, 468, Springer-Verlag, Berlin, Germany, 1990, 497-506.

33.

C. M. Kenyon-Mathieu and J. S. Vitter. ``The Maximum Size of Dynamic Data Structures,'' SIAM Journal on Computing, 20(5), October 1991, 807-823. An extended abstract appears in ``General Methods for the Analysis of the Maximum Size of Dynamic Data Structures,'' Proceedings of the 16th Annual International Colloquium on Automata, Languages, and Programming (ICALP '89), Stresa, Italy, July 1989, published in Lecture Notes in Computer Science, 372, Springer-Verlag, Berlin, Germany, 473-487.

34.

J.-H. Lin and J. S. Vitter. ``Complexity Results on Learning by Neural Nets,'' Machine Learning, 6, 1991, 211-230. An extended abstract appears in Proceedings of the 2nd Annual ACM Workshop on Computational Learning Theory (COLT '89), Santa Cruz, CA, July-August 1989, published by Morgan Kaufmann, San Mateo, CA, 118-133.

35.

J. S. Vitter and J.-H. Lin. ``Learning in Parallel,'' Information and Computation, 92(2), February 1992, 179-202. An extended abstract appears in Proceedings of the 1st Annual ACM Workshop on Computational Learning Theory (COLT '88), Cambridge, MA, August 1988, published by Morgan Kaufmann, San Mateo, CA, 106-124.

36.

P. G. Howard and J. S. Vitter. ``Practical Implementations of Arithmetic Coding,'' invited paper in Proceedings of the 3rd International Conference on Advances in Communication and Control Systems (COMCON '91), Victoria, Canada, October 1991.

37.

F. P. Preparata, J. S. Vitter, and M. Yvinec. ``Output-Sensitive Generation of the Perspective View of Isothetic Parallepipeds,'' Algorithmica, 8, 1992, 257-283. An extended abstract appears in Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT '90), Bergen, Norway, July 1990, published in Lecture Notes in Computer Science, 447, Springer-Verlag, Berlin, Germany, 71-84.

38.

P. G. Howard and J. S. Vitter. ``Analysis of Arithmetic Coding for Data Compression,'' invited paper in special issue on data compression for image and text in Journal of Information Processing and Management, 28(6), 1992, 749-763. An extended abstract appears in an invited paper in Proceedings of the 1991 IEEE Data Compression Conference (DCC '91), Snowbird, UT, April 1991, 3-12.

39.

P. G. Howard and J. S. Vitter. ``New Methods for Lossless Image Compression Using Arithmetic Coding,'' invited paper in special issue on data compression for image and text in Journal of Information Processing and Management, 28(6), 1992, 765-779. An extended abstract appears in Proceedings of the 1991 IEEE Data Compression Conference (DCC '91), Snowbird, UT, April 1991, 257-266.

40.

J.-H. Lin and J. S. Vitter. ``Approximation Algorithms for Geometric Median Problems,'' Information Processing Letters, 44, 1992, 245-249.

41.

J.-H. Lin and J. S. Vitter. ``Nearly Optimal Vector Quantization via Linear Programming,'' Proceedings of the 1992 IEEE Data Compression Conference (DCC '92), Snowbird, UT, March 1992, 22-31.

42.

P. G. Howard and J. S. Vitter. ``Error Modeling for Hierarchical Lossless Image Compression,'' Proceedings of the 1992 IEEE Data Compression Conference (DCC '92), Snowbird, UT, March 1992, 269-278.

43.

J.-H. Lin and J. S. Vitter. ``$\epsilon$-Approximations with Minimum Packing Constraint Violation,'' Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC '92), Victoria, Canada, May 1992, 771-782.

44.

J. S. Vitter and M. H. Nodine. ``Large-Scale Sorting in Uniform Memory Hierarchies,'' special issue on parallel I/O systems in Journal of Parallel and Distributed Computing, 17, January 1993, 107-114. An extended abstract appears in ``Large-Scale Sorting in Parallel Memories,'' Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '91), Hilton Head, SC, July 1991, 29-39.

45.

M. H. Nodine and J. S. Vitter. ``Paradigms for Optimal Sorting with Multiple Disks,'' Proceedings of the 26th Hawaii International Conference on Systems Sciences (HICSS '93), Maui, HI, January 1993, 50-59.

46.

F. P. Preparata and J. S. Vitter. ``A Simplified Technique for Hidden-Line Elimination in Terrains,'' International Journal of Computational Geometry & Applications, 3(2), 1993, 167-181. An extended abstract appears in Proceedings of the 1992 Symposium on Theoretical Aspects of Computer Science (STACS '92), Paris, France, February 1992, published in Lecture Notes in Computer Science, 577, Springer-Verlag, Berlin, Germany, 135-146.

47.

P. G. Howard and J. S. Vitter. ``Fast and Efficient Lossless Image Compression,'' Proceedings of the 1993 IEEE Data Compression Conference (DCC '93), Snowbird, UT, April 1993, 351-360.

48.

M. H. Nodine and J. S. Vitter. ``Load Balancing Paradigms for Optimal Use of Parallel Disks and Parallel Memory Hierarchies,'' invited paper in Proceedings of the 2nd Annual Dartmouth Institute for Advanced Graduate Studies (DAGS '93), Hanover, NH, June 1993.

49.

R. F. Cohen, S. Subramanian, R. Tamassia, and J. S. Vitter. ``Dynamic Algorithms for Optimization Problems on Bounded Tree-Width Graphs,'' Proceedings of the 3rd Conference on Integer Programming and Combinatorial Optimization (IPCO '93), Erice, Italy, April-May 1993, 99-112.

50.

K. M. Curewitz, P. Krishnan, and J. S. Vitter. ``Practical Prefetching via Data Compression,'' Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93), Washington, DC, May 1993, 257-266.

51.

M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. ``External-Memory Computational Geometry,'' Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS '93), Palo Alto, CA, November 1993, 714-723.

52.

Y. Matias, J. S. Vitter, and N. Young. ``Approximate Data Structures with Applications,'' Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '94), Alexandria, VA, January 1994, 361-370.

53.

P. G. Howard and J. S. Vitter. ``Fast Progressive Lossless Image Compression,'' Proceedings of the Image and Video Compression Conference, IS&T/SPIE 1994 Symposium on Electronic Imaging Science & Technology, 2186, San Jose, CA, February 1994, 98-109.

54.

D. T. Hoang, P. M. Long, and J. S. Vitter. ``Explicit Bit Minimization for Motion-Compensated Video Coding,'' Proceedings of the 1994 IEEE Data Compression Conference (DCC '94), Snowbird, UT, March 1994, 175-184.

55.

P. G. Howard and J. S. Vitter. ``Arithmetic Coding for Data Compression,'' Proceedings of the IEEE, 82(6), June 1994, 857-865.

56.

J. S. Vitter and E. A. M. Shriver. ``Algorithms for Parallel Memory, I: Two-Level Memories,'' double special issue on large-scale memories in Algorithmica, 12(2-3), 1994, 110-147. An extended abstract appears in ``Optimal Disk I/O with Parallel Block Transfer,'' Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Baltimore, MD, May 1990, 159-169.

57.

J. S. Vitter and E. A. M. Shriver. ``Algorithms for Parallel Memory, II: Hierarchical Multilevel Memories,'' double special issue on large-scale memories in Algorithmica, 12(2-3), 1994, 148-169. An extended abstract appears in ``Optimal Disk I/O with Parallel Block Transfer,'' Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Baltimore, MD, May 1990, 159-169.

58.

P. G. Howard and J. S. Vitter. ``Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding,'' Journal of Information Processing and Management, 30(6), 1994, 777-790. An extended abstract appears in Proceedings of the 1993 IEEE Data Compression Conference (DCC '93), Snowbird, UT, April 1993.

59.

P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia ``Complexity Models for Incremental Computation,'' special issue of Theoretical Computer Science, 130, 1994, 203-236. An extended abstract appears in S. Subramanian, J. S. Vitter, and R. Tamassia, ``A Complexity Theoretic Approach to Incremental Computation,'' Proceedings of the 1993 Symposium on Theoretical Aspects of Computer Science (STACS '93), Würzburg, Germany, February 1993, published in Lecture Notes in Computer Science, 665, Springer-Verlag, Berlin, Germany, 640-649.

60.

J.-H. Lin and J. S. Vitter. ``A Theory for Memory-Based Learning,'' special issue of Machine Learning, 17(2/3), November/December 1994, 143-167. An extended abstract appears in Proceedings of the 5th Annual ACM Conference on Computational Learning Theory (COLT '92), Pittsburgh, PA, July 1992, 103-115.

61.

Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter, ``External-Memory Graph Algorithms,'' Proceedings of the 6th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '95), San Francisco, CA, January 1995, 139-149.

62.

S. Subramanian, R. Tamassia, and J. S. Vitter. ``An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs,'' Algorithmica, 14, 1995, 322-339. An extended abstract appears in ``A Divide and Conquer Approach to Shortest Paths in Planar Layered Digraphs,'' Proceedings of the 4th IEEE Symposium on Parallel and Distributed Processing (SPDP '92), Dallas, TX, December 1992, 176-183.

63.

M. H. Nodine and J. S. Vitter. ``Greed Sort: An Optimal Sorting Algorithm on Parallel Disks,'' Journal of the ACM, 42(4), July 1995, 919-933. An extended abstract appears in ``Large-Scale Sorting in Parallel Memories,'' Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '91), Hilton Head, SC, July 1991, 29-39.

64.

E. F. Grove, M.-Y. Kao, P. Krishnan, and J. S. Vitter. ``Online Perfect Matching and Mobile Computing,'' Proceedings of the 4th Biannual Workshop on Algorithms and Data Structures (WADS '95), Kingston, Ontario, Canada, August 1995, 194-205.

65.

A. Awerbuch, A. Azar, E. F. Grove, P. Krishnan, M.-Y. Kao, and J. S. Vitter. ``Load Balancing in the L_p Norm,'' Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS '95), Milwaukee, WI, October 1995, 383-391.

66.

R. Tamassia and J. S. Vitter. ``Optimal Cooperative Search in Fractional Cascaded Data Structures,'' invited paper in special issue on parallel computing in Algorithmica, 15(2), February 1996, 154-171. An extended abstract appears in Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '90), Crete, Greece, July 1990, 307-316.

67.

P. G. Howard and J. S. Vitter. ``Parallel Lossless Image Compression Using Huffman and Arithmetic Coding,'' Information Processing Letters, 59, 1996, 65-73. An extended abstract appears in Proceedings of the 1992 IEEE Data Compression Conference (DCC '92), Snowbird, UT, March 1992, 299-308.

68.

D. T. Hoang, P. M. Long, and J. S. Vitter. ``Efficient Cost Measures for Motion Compensation at Low Bit Rates,'' Proceedings of the 1996 IEEE Data Compression Conference (DCC '96), Snowbird, UT, April 1996.

69.

P. Krishnan, J. S. Vitter, and B. Iyer. ``Estimating Alphanumeric Selectivity in the Presence of Wildcards,'' Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD '96), Montreal, Canada, May 1996, 282-293.

70.

D. E. Vengroff and J. S. Vitter. ``Efficient 3-D Range Searching in External Memory,'' Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), Philadelphia, PA, May 1996, 192-201.

71.

M. H. Nodine, M. T. Goodrich, and J. S. Vitter. ``Blocking for External Graph Searching,'' Algorithmica, 16(2), August 1996, 181-214. An extended abstract appears in Proceedings of the 12th Annual ACM Symposium on Principles of Database Systems (PODS '93), Washington, DC, May 1993, 222-232.

72.

K. Romanik and J. S. Vitter. ``Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments,'' Information and Computation, 128(2), August 1, 1996, 87-108. An extended abstract appears in ``Using Computational Learning Theory to Analyze the Testing Complexity of Program Segments,'' Proceedings of the 17th Annual IEEE International Computer Software and Applications Conference (COMPSAC '93), Phoenix, AZ, 1993, 367-373.

73.

J. S. Vitter and P. Krishnan. ``Optimal Prefetching via Data Compression,'' Journal of the ACM, 43(5) September 1996, 771-793. An extended abstract appears in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '91), San Juan, Puerto Rico, October 1991, 121-130.

74.

P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff, and J. S. Vitter. ``Indexing for Data Models with Constraints and Classes,'' Journal of Computer and System Sciences, 52(3), 1996, 589-612. An extended abstract appears in Proceedings of the 12th Annual ACM Symposium on Principles of Database Systems (PODS '93), Washington, DC, May 1993, 233-243.

75.

D. E. Vengroff and J. S. Vitter. ``I/O-Efficient Scientific Computation using TPIE,'' Proceedings of the Goddard Conference on Mass Storage Systems and Technologies, College Park, MD, September 1996, published in NASA Conference Publication 3340, Volume II, 553-570. A shorter preliminary version appears in ``Supporting I/O-Efficient Scientific Computing in TPIE,'' Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing (SPDP '95), San Antonio, TX, October 1995, 74-77.

76.

G. Gibson, J. S. Vitter, and J. Wilkes, editors. ``Strategic Directions in Storage I/O for Large-Scale Computing,'' ACM Computing Surveys, 28(4), December 1996, 779-793.

77.

J. S. Vitter. ``Communication Issues in Large-Scale Geometric Computation,'' ACM Computing Surveys, 28(4es), Article 20, December 1996.

78.

D. E. Vengroff and J. S. Vitter. ``I/O-Efficient Algorithms and Environments,'' ACM Computing Surveys, 28(4es), Article 212, December 1996.

79.

M. Wang, J. S. Vitter, and B. Iyer. ``Selectivity Estimation in the Presence of Alphanumeric Correlations,'' Proceedings of the 13th Annual IEEE International Conference on Data Engineering (ICDE '97), Birmingham, England, April 1997, 169-180.

80.

P. K. Agarwal, T. M. Murali, and J. S. Vitter. ``Practical Techniques for Constructing Binary Space Partitions for Orthogonal Rectangles,'' Proceedings of the 13th Annual ACM Symposium on Computational Geometry (SCG '97), Nice, France, June 1997, 382-384.

81.

R. D. Barve, E. F. Grove, and J. S. Vitter. ``Simple Randomized Mergesorting on Parallel Disks,'' special issue on parallel I/O in Parallel Computing, 23(4), 1997, 601-631. An extended abstract appears in Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '96), Padua, Italy, June 1996, 109-118. An updated extended abstract appears in [23].

82.

K. J. Basye, T. L. Dean, and J. S. Vitter. ``Coping with Uncertainty in Map Learning,'' Machine Learning, 29(1), 1997, 65-88. An extended abstract appears in Proceedings of the 11th Joint Conference on Artificial Intelligence (IJCAI '89), Detroit, MI, August 1989, 663-668.

83.

L. Arge, P. Ferragina, R. Grossi, and J. S. Vitter. ``On Sorting Strings in External Memory,'' Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC '97), El Paso, TX, May 1997, 540-548. Also appears as ``Sequence Sorting in Secondary Storage," invited paper in Proceedings of the 1997 International IEEE Conference on Compression and Complexity of Sequences (SEQUENCES '97), Positano, Italy, June 1997, 329-346.

84.

D. T. Hoang and J. S. Vitter. ``Multiplexing VBR Video Sequences onto a CBR Channel with Lexicographic Optimization,'' Proceedings of the 1997 IEEE International Conference on Image Processing (ICIP '97), Santa Barbara, CA, October 1997.

85.

D. T. Hoang, E. Linzer, and J. S. Vitter. ``Lexicographic Bit Allocation for MPEG Video,'' special issue on high-fidelity media processing in Journal of Visual Communication and Image Representation, 8(4), December 1997, 384-404. An extended abstract appears in D. T. Hoang, J. S. Vitter, and E. Linzer, Proceedings of the 1997 IEEE International Conference on Image Processing (ICIP '97), Santa Barbara, CA, October 1997. An earlier version appears in ``A Lexicographic Framework for MPEG Rate Control,'' Proceedings of the 1997 IEEE Data Compression Conference (DCC '97), Snowbird, UT, March 1997, 101-110.

86.

P. K. Agarwal, L. Arge, T. M. Murali, K. R. Varadarajan, and J. S. Vitter. ``I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking,'' Proceedings of the 9th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '98), San Francisco, CA, January 1998, 117-126.

87.

L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. ``Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems,'' Proceedings of the 9th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '98), San Francisco, CA, January 1998, 685-694.

88.

Y. Matias, J. S. Vitter, and M. Wang. ``Wavelet-Based Histograms for Selectivity Estimation,'' Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data (SIGMOD '98), Seattle, WA, June 1998, 448-459.

89.

D. T. Hoang, P. M. Long, and J. S. Vitter. ``Rate-Distortion Optimizations for Motion Estimation in Low-Bitrate Video Coding,'' IEEE Transactions on Circuits and Systems for Video Technology, 8(4), August 1998, 488-500. An extended abstract appears in Proceedings of the Digital Video Compression Conference, IS&T/SPIE 1996 Symposium on Electronic Imaging Science & Technology, 2668, San Jose, CA, January-February 1996.

90.

L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. ``Scalable Sweep-Based Spatial Join,'' Proceedings of the 24th International Conference on Very Large Databases (VLDB '98), New York, NY, August 1998, 570-581.

91.

T. M. Murali, P. K. Agarwal, and J. S. Vitter. ``Constructing Binary Space Partitions for Orthogonal Rectangles in Practice,'' Proceedings of the 6th Annual European Symposium on Algorithms (ESA '98), Venice, August 1998, published in Lecture Notes in Computer Science, 1461, Springer-Verlag, Berlin, Germany, 211-222.

92.

J. S. Vitter, M. Wang, and B. Iyer. ``Data Cube Approximation and Histograms via Wavelets,'' Proceedings of the 7th International Conference on Information and Knowledge Management (CIKM '98), Washington, DC, November 1998, 96-104.

93.

P. Krishnan and J. S. Vitter. ``Optimal Prediction for Prefetching in the Worst Case,'' SIAM Journal on Computing, 27(6), December 1998, 1617-1636. An extended abstract appears in Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '94), Alexandria, VA, January 1994, 392-401.

94.

P. Krishnan, P. M. Long, and J. S. Vitter. ``Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments,'' Algorithmica, 23(1), January 1999, 31-56. An extended abstract appears in ``Learning to Make Rent-to-Buy Decisions in Probabilistic Environments with Systems Applications,'' Proceedings of the 12th International Conference on Machine Learning (ML '95), Tahoe City, CA, July 1995, 322-330.

95.

P. K. Agarwal, L. Arge, G. Brodal, and J. S. Vitter. ``I/O-Efficient Dynamic Point Location in Monotone Subdivisions,'' Proceedings of the 10th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '99), Baltimore, MD, January 1999, 11-20.

96.

R. D. Barve, E. A. M. Shriver, P. B. Gibbons, B. K. Hillyer, Y. Matias, and J. S. Vitter. ``Modeling and Optimizing I/O Throughput of Multiple Disks on a Bus,'' Proceedings of the Joint International ACM Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '99), Atlanta, GA, May 1999, 83-92. An abstract appears in Proceedings of the Joint ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '98/PERFORMANCE '98), Madison, WI, June 1998, 264-265.

97.

R. D. Barve, E. A. M. Shriver, P. B. Gibbons, B. K. Hillyer, Y. Matias, and J. S. Vitter. ``Round-like Behavior in Multiple Disks on a Bus,'' Proceedings of the ACM-IEEE Workshop on I/O in Parallel And Distributed Systems (IOPADS '99), Atlanta, GA, May 1999, 1-9.

98.

L. Arge, V. Samoladas, and J. S. Vitter. ``Two-Dimensional Indexability and Optimal Range Search Indexing,'' Proceedings of the 18th Annual ACM Symposium on Principles of Database Systems (PODS '99), Philadelphia, PA, May-June 1999, 346-357.

99.

J. S. Vitter and M. Wang. ``Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets,'' Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data (SIGMOD '99), Philadelphia, PA, June 1999, 193-204. Recipient of the 2009 SIGMOD Test of Time award for the most impactful paper from SIGMOD '99.

100.

A. Condon, H. Edelsbrunner, E. A. Emerson, L. Fortnow, S. Haber, R. Karp, D. Leivant, R. Lipton, N. Lynch, I. Parberry, C. Papadimitriou, M. Rabin, A. Rosenberg, J. S. Royer, J. E. Savage, A. L. Selman, C. Smith, E. Tardos, and J. S. Vitter. ``Challenges for Theory of Computing,'' Report of an NSF-Sponsored Workshop on Research in Theoretical Computer Science, SIGACT NEWS, 30(2), June 1999, 62-76.

101.

J. S. Vitter. ``Online Data Structures in External Memory,'' invited paper in Proceedings of the 6th Biannual Workshop on Algorithms and Data Structures (WADS '99), Vancouver, Canada, August 1999, published in Lecture Notes in Computer Science, 1668, Springer-Verlag, Berlin, Germany. Also appears as an invited paper in Proceedings of the 26th Annual International Colloquium on Automata, Languages, and Programming (ICALP '99), Prague, Czech Republic, July 1999, published in Lecture Notes in Computer Science, 1644, Springer-Verlag, Berlin, Germany, 119-133.

102.

D. T. Hoang, P. M. Long, and J. S. Vitter. ``Dictionary Selection using Partial Matching,'' Information Sciences, 119(1-2), 1999, 57-72. An extended abstract appears in ``Multiple-dictionary Compression Using Partial Matching,'' Proceedings of the 1995 IEEE Data Compression Conference (DCC '95), Snowbird, UT, March 1995, 272-281.

103.

E. F. Grove, T. M. Murali, and J. S. Vitter. ``The Object Complexity Model for Hidden-Surface Elimination,'' International Journal of Computational Geometry & Applications, 9, 1999, 207-217. An extended abstract appears in Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG '95), Quebec, Canada, August 1995, 273-278.

104.

P. M. Long, A. I. Natsev, and J. S. Vitter. ``Text Compression Via Alphabet Re-Representation,'' Neural Networks, 12 (4-5), 1999, 755-765. An extended abstract appears in Proceedings of the 1997 IEEE Data Compression Conference (DCC '97), Snowbird, UT, March 1997.

105.

P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter. ``Binary Space Partitions for Fat Rectangles,'' SIAM Journal on Computing, 29(5), 2000, 1422-1448. An extended abstract appears in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS '96), Burlington, VT, October 1996, 482-493. Also appears in Abstracts of the 1st CGC Workshop on Computational Geometry, Center for Geometric Computing, Johns Hopkins University, Baltimore, MD, October 1996.

106.

P. K. Agarwal, L. Guibas, T. M. Murali, and J. S. Vitter. ``Cylindrical Static and Kinetic Binary Space Partitions,'' Computational Geometry, 16(2), 2000, 103-127. An extended abstract appears in Proceedings of the 13th Annual ACM Symposium on Computational Geometry (SCG '97), Nice, France, June 1997, 39-48.

107.

R. Tamassia, I. G. Tollis, and J. S. Vitter. ``A Parallel Algorithm for Planar Orthogonal Grid Drawings,'' Parallel Processing Letters, 10(1), March 2000, 141-150. An extended abstract appears in ``Lower Bounds and Parallel Algorithms for Planar Orthogonal Grid Drawings,'' Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing (SPDP '91), Dallas, TX, December 1991, 386-393.

108.

L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, J. Vahrenhold, and J. S. Vitter. ``A Unified Approach for Indexed and Non-Indexed Spatial Joins,'' Proceedings of the 7th International Conference on Extending Database Technology (EDBT '00), Konstanz, Germany, March 2000, published in Lecture Notes in Computer Science, Springer-Verlag, 1777, Berlin, Germany, 413-429.

109.

R. D. Barve, E. F. Grove, and J. S. Vitter. ``Application-Controlled Paging for a Shared Cache,'' SIAM Journal on Computing, 29(4), 2000, 1290-1303. An extended abstract appears in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS '95), Milwaukee, WI, October 1995, 204-213.

110.

R. D. Barve, M. Kallahalla, P. Varman, and J. S. Vitter. ``Competitive Analysis of Buffer Management Algorithms for Parallel I/O Systems,'' Journal of Algorithms, 36(2), August 2000, 152-181. An extended abstract appears in Proceedings of the ACM-IEEE Workshop on I/O in Parallel And Distributed Systems (IOPADS '97), San Jose, CA, November 1997, 47-56.

111.

Y. Matias, J. S. Vitter, and M. Wang. ``Dynamic Maintenance of Wavelet-Based Histograms,'' Proceedings of the 26th International Conference on Very Large Databases (VLDB '00), Cairo, Egypt, September 2000, 101-110.

112.

P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter. ``Efficient Searching with Linear Constraints,'' Journal of Computer and System Sciences, 61(2), October 2000, 194-216. An extended abstract appears in Proceedings of the 17th Annual ACM Symposium on Principles of Database Systems (PODS '98), Seattle, WA, June 1998, 169-178.

113.

A. Natsev, J. R. Smith, Y. C. Chang, C. S. Li, and J. S. Vitter. ``Constrained Querying of Multimedia Databases,'' Proceedings of the Storage and Retrieval for Media Databases Conference, IS&T/SPIE 2001 Symposium on Electronic Imaging Science & Technology, 4315, San Jose, CA, January 2001.

114.

A. Natsev, A. Chadha, B. Soetarman, J. S. Vitter. ``CAMEL: Concept Annotated iMagE Libraries,'' Proceedings of the Storage and Retrieval for Media Databases Conference, IS&T/SPIE 2001 Symposium on Electronic Imaging Science & Technology, 4315, San Jose, CA, January 2001.

115.

L. Arge, J. S. Chase, L. Toma, J. S. Vitter, R. Wickremesinghe, P. Halpin, and D. Urban. ``Digital Terrain Analysis for Massive Grids,'' Proceedings of the 16th Annual Symposium of the U.S. Chapter of International Association of Landscape Ecology (US-IALE), Pattern, Process, Scale, & Hierarchy: Interactions in Human-Dominated and Natural Landscapes, Tempe, AZ, April 2001.

116.

L. Arge, L. Toma, and J. S. Vitter. ``I/O-Efficient Algorithms for Problems on Grid-Based Terrains'', ACM Journal of Experimental Algorithmics, 6(1), 2001. An extended abstract appears in Proceedings of the 2nd Workshop on Algorithm Engineering and Experimentation (ALENEX '00), San Francisco, CA, January 2000, and in ``External-Memory Algorithms for Drainage Network Computation,'' Abstracts of the 4th CGC Workshop on Computational Geometry, Center for Geometric Computing, Johns Hopkins University, Baltimore, MD, October 1999.

117.

J. S. Vitter. ``External Memory Algorithms and Data Structures: Dealing with Massive Data,'' ACM Computing Surveys, 33(2), June 2001, 209-271. Shorter versions appear in ``External Memory Algorithms,'' invited paper in Proceedings of the 6th Annual European Symposium on Algorithms (ESA '98), Venice, August 1998, published in Lecture Notes in Computer Science, 1461, Springer-Verlag, Berlin, Germany, 1-25, and in an invited tutorial in Proceedings of the 17th Annual ACM Symposium on Principles of Database Systems (PODS '98), Seattle, WA, June 1998, 119-128.

118.

P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. ``A Framework for Index Bulk Loading and Dynamization,'' Proceedings of the 28th Annual International Colloquium on Automata, Languages, and Programming (ICALP '01), Crete, Greece, July 2001, published in Lecture Notes in Computer Science, 2076, Springer-Verlag, Berlin, Germany, 115-127.

119.

L. Lim, M. Wang, S. Padmanabhan, J. S. Vitter, and R. Agarwal. ``Characterizing Web Document Change,'' Proceedings of the 2nd International Conference on Web-Age Information Management, Xi'an, China, July 2001, published in Lecture Notes in Computer Science, 2118, Springer-Verlag, Berlin, Germany, 133-144.

120.

M. Wang, J. S. Vitter, L. Lim, and S. Padmanabhan. ``Wavelet-Based Cost Estimation for Spatial Queries,'' Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD '01), Redondo Beach, CA, July 2001, 175-196.

121.

D. A. Hutchinson, P. Sanders, and J. S. Vitter. ``The Power of Duality for Prefetching and Sorting with Parallel Disks,'' Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '01), Crete, Greece, July 2001, 334-335.

122.

A. Natsev, G. Fuh, W. Chen, C.-H. Chiu, and J. S. Vitter. ``Aggregate Predicates and Ranked Search in DBMS,'' Proceedings of the 13th Australian Database Conference (ADC '02), Melbourne, Australia, January-February 2002.

123.

R. Grossi and J. S. Vitter. ``Compressed Indexes for Fast Search in Sequences,'' invited paper in Proceedings of the 6th Joint Conference on Information Sciences (JCIS '02), Durham, NC, March 2002.

124.

R. D. Barve and J. S. Vitter. ``A Simple and Efficient Parallel Disk Mergesort,'' invited paper in special issue on parallel algorithms and architectures in Theory of Computing Systems, 35(2), March/April 2002, 189-215. An extended abstract appears in Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '99), St. Malo, France, June 1999, 232-241.

125.

L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter. ``Efficient Bulk Operations on Dynamic R-trees,'' special issue on experimental algorithmics in Algorithmica, 33(1), May 2002, 104-128. An extended abstract appears in Proceedings of the 1st Workshop on Algorithm Engineering and Experimentation (ALENEX '99), Baltimore, MD, January 1999, 328-348.

126.

R. Wickremesinghe, J. S. Chase, and J. S. Vitter. ``Distributed Computing with Load-Managed Active Storage,'' Proceedings of the 11th Annual IEEE International Symposium on High Performance Distributed Computing (HPDC '02), Edinburgh, Scotland, July 2002, 13-23.

127.

L. Lim, M. Wang, S. Padmanabhan, J. S. Vitter, and R. Parr. ``XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation,'' Proceedings of the 28th International Conference on Very Large Databases (VLDB '02), Hong Kong, China, August 2002, 442-453.

128.

L. Arge, O. Procopiuc, and J. S. Vitter. ``Implementing I/O-Efficient Data Structures Using TPIE,'' Proceedings of the 10th Annual European Symposium on Algorithms (ESA '02), Rome, Italy, September 2002, published in Lecture Notes in Computer Science, Springer-Verlag, 2461, Berlin, Germany, 88-100.

129.

R. Wickremesinghe, L. Arge, J. S. Chase, and J. S. Vitter. ``Efficient Sorting using Registers and Caches,'' invited paper in special issue of ACM Journal of Experimental Algorithmics, 7(9), 2002. An earlier and shorter version appears in L. Arge, R. Barve, J. S. Chase, J. S. Vitter, and R. Wickremesinghe. ``Efficient Sorting using Registers and Caches,'' Proceedings of the 4rd Workshop on Algorithm Engineering (WAE '00), Saarbrücken, Germany, September 2000, published in Lecture Notes in Computer Science, 1982 Springer-Verlag, Berlin, Germany, 51-62.

130.

L. Arge and J. S. Vitter. ``Optimal External Memory Interval Management,'' SIAM Journal on Computing, 32(6), 2003, 1488-1508. An extended abstract appears in ``Optimal Dynamic Interval Management in External Memory,'' Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS '96), Burlington, VT, October 1996, 560-569. Also appears in Abstracts of the 1st CGC Workshop on Computational Geometry, Center for Geometric Computing, Johns Hopkins University, Baltimore, MD, October 1996.

131.

O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter. ``Bkd-tree: A Dynamic Scalable kd-tree,'' Proceedings of the 8th International Symposium on Spatial and Temporal Databases (SSTD '03), Santorini island, Greece, July 2003, 46-65.

132.

Y. Matias, J. S. Vitter and W.-C. Ni. ``Dynamic Generation of Discrete Random Variates,'' Theory of Computing Systems, 36(4), 2003, 329-358. An extended abstract appears in Proceedings of the 4th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '93), Austin, TX, January 1993, 361-370.

133.

L. Arge, J. S. Chase, L. Toma, J. S. Vitter, R. Wickremesinghe, P. Halpin, and D. Urban, ``Efficient Flow Computation on Massive Grid Terrain Datasets,'' Geoinformatica, 7(4), December 2003, 283-313. An extended abstract appears in ``Flow Computation on Massive Grids,'' Proceedings of the 9th ACM International Symposium on Advances in Geographic Information Systems (ACM-GIS '01) Atlanta, GA, November 2001, 82-87.

134.

L. Foschini, R. Grossi, A. Gupta, and J. S. Vitter. ``Fast Compression with a Static Model in High-Order Entropy,'' Proceedings of the 2004 IEEE Data Compression Conference (DCC '04), Snowbird, UT, March 2004, 62-71.

135.

R. Shah, P. J. Varman, and J. S. Vitter. ``Online Algorithms for Prefetching and Caching in Parallel Disks,'' Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '04), Barcelona, Spain, June 2004, 255-264.

136.

T. M. Ghanem, R. Shah, M. F. Mokbel, W. G. Aref, and J. S. Vitter. ``Bulk Operations for Space-Partitioning Trees,'' Proceedings of the 20th Annual IEEE International Conference on Data Engineering (ICDE '04), Boston, March-April 2004, 29-41.

137.

I. Ilyas, R. Shah, W. G. Aref, J. S. Vitter, and A. Elmagarmid. ``Rank-aware Query Optimization,'' Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD '04), Paris, France, June 2004, 203-214.

138.

S. Muthukrishnan, R. Shah, and J. S. Vitter. ``Mining Deviants in Time Series Data Streams,'' Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM '04), Santorini Island, Greece, June 2004, 41-50.

139.

M. Wang, B. Iyer, and J. S. Vitter. ``Scalable Mining for Classification Rules in Relational Databases,'' Herman Rubin Festschrift, Lecture Notes Monograph Series, 45, Institute of Mathematical Statistics, Hayward, CA, Fall 2004. An extended abstract appears in Proceedings of the International Database Engineering & Application Symposium (IDEAS '98), Cardiff, Wales, July 1998, 58-67. A shorter version appears in Proceedings of the ACM SIGMOD Data Mining and Knowledge Discovery Workshop (DMKD '98), Seattle, WA, June 1998.

140.

M. Ouzzani, W. G. Aref, E. Bertino, A. C. Catlin, C. W. Clifton, W.-K. Hon, A. K. Elmagarmid, A. Ghafoor, S. E. Hambrusch, S. Prabhakar, J. S. Vitter, X. Zhang. ``The Indiana Center for Database Systems at Purdue University,'' SIGMOD Record, 34(2), June 2005, 53-58.

141.

S. Anastasiadis, P. J. Varman, J. S. Vitter, and K. Yi. ``Optimal Lexicographic Shaping of Aggregate Streaming Data,'' IEEE Transactions on Computers, 54(4), April 2005, 398-408. An extended abstract appears in S. Anastasiadis, P. J. Varman, and J. S. Vitter. ``Lexicographically Optimal Smoothing for Broadband Traffic Multiplexing,'' Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC '02), July 2002, Monterey, CA, 68-77.

142.

D. A. Hutchinson, P. Sanders, and J. S. Vitter. ``Duality Between Prefetching and Queued Writing with Parallel Disks,'' SIAM Journal on Computing, 34(6), 1443-1463, June 2005. An extended abstract appears in Proceedings of the 9th Annual European Symposium on Algorithms (ESA '01), Århus, Denmark, August 2001, published in Lecture Notes in Computer Science, 2161, Springer-Verlag, Berlin, Germany, 62-73.

143.

R. Grossi and J. S. Vitter. ``Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching,'' SIAM Journal on Computing, 35(2), 2005, 378-407. An extended abstract appears in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC '00), Portland, OR, May 2000, 397-406.

144.

R. Shah, P. J. Varman, J. S. Vitter. ``On Competitive Online Read-Many Parallel Disks Scheduling,'' Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '05), Las Vegas, NV, July 2005, 217.

145.

Y. Matias, E. Segal, and J. S. Vitter. ``Efficient Bundle Sorting,'' SIAM Journal on Computing, 36(2), 2006, 394-410. An extended abstract appears in Proceedings of the 11th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '00), San Francisco, CA, January 2000, 839-848.

146.

A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. ``Compressed Dictionaries: Space Measures, Data Sets, and Experiments,'' Proceedings of the 5th International Workshop on Experimental Algorithmics (WEA '06), Menorca, Spain, May 2006, 158-169.

147.

J. S. Vitter and D. A. Hutchinson. ``Distribution Sort with Randomized Cycling,'' Journal of the ACM, 53(7), July 2006, 656-680. An extended abstract appears in Proceedings of the 12th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '01), Washington, DC, January 2001, 77-86.

148.

L. Foschini, R. Grossi, A. Gupta, and J. S. Vitter. ``Indexing Equals Compression: Experiments on Suffix Arrays and Trees,'' ACM Transactions on Algorithms, 2(4), 2006, 611-639. An extended abstract appears in R. Grossi, A. Gupta, and J. S. Vitter, ``When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications,'' Proceedings of the 15th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '04), New Orleans, LA, January 2004, 636-645..

149.

R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. ``Efficient Join Processing over Uncertain-Valued Attributes,'' Proceedings of the 2006 ACM Conference on Information and Knowledge Management (CIKM '06), Arlington, VA, November 2006, 738-747.

150.

I. Ilyas, W. G. Aref, A. K. Elmagarmid, H. G. Elmongui, R. Shah, and J. S. Vitter. ``Adaptive Rank-aware Query Optimization in Relational Databases'', ACM Transactions on Database Systems, 31(4), December 2006, 1257-1304.

151.

L. Arge, D. E. Vengroff, and J. S. Vitter. ``External-Memory Algorithms for Processing Line Segments in Geographic Information Systems,'' Algorithmica, 47(1), January 2007, 1-25. An extended abstract appears in Proceedings of the 3rd Annual European Symposium on Algorithms (ESA '95), Corfu, Greece, September 1995, published in Lecture Notes in Computer Science, 979, Springer-Verlag, Berlin, Germany, 295-310.

152.

L. Lim, M. Wang, S. Padmanabhan, J. S. Vitter, and R. Agarwal. ``Efficient Update of Indexes for Dynamically Changing Web Documents,'' World Wide Web, 10(1), March 2007, 37-69. An extended abstract appears in ``Dynamic Maintenance of Web Indexes Using Landmarks,'' Proceedings of the 12th International World Wide Web Conference (WWW '03), Budapest, May 2003, 102-111.

153.

A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. ``Compressed Data Structures: Dictionaries and the Data-Aware Measures,'' Theoretical Computer Science, 387(3), November 2007, 313-331. An extended abstract appears in Proceedings of the 2006 IEEE Data Compression Conference (DCC '06), Snowbird, UT, March 2006, 213-222.

154.

M. H. Nodine and J. S. Vitter. ``Optimal Deterministic Sorting on Parallel Disks,'' submitted to journal. An extended abstract appears in ``Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors,'' Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '93), Velen, Germany, June-July 1993, 120-129.

155.

M. H. Nodine and J. S. Vitter. ``Optimal Deterministic Sorting on Parallel Processors and Parallel Memory Hierarchies,'' submitted to journal. An extended abstract appears in ``Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors,'' Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '93), Velen, Germany, June-July 1993, 120-129.

156.

R. D. Barve, J. S. Vitter, and K. Yi. ``A Theoretical Framework for Memory-Adaptive Algorithms,'' being submitted to journal. An extended abstract appears in R. D. Barve and J. S. Vitter, Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS '99), New York, NY, October 1999, 273-284.

157.

A. Natsev, J. R. Smith, Y.-C. Chang, C.-S. Li, and J. S. Vitter. ``Supporting Incremental Join Queries on Ranked Inputs,'' Proceedings of the 27th International Conference on Very Large Databases (VLDB '01), Rome, Italy, September 2001, 281-290.

158.

R. Grossi, A. Gupta, and J. S. Vitter. ``High-Order Entropy-Compressed Text Indexes,'' submitted to journal. An extended abstract appears in Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '03), Baltimore, MD, January 2003, 841-850.

159.

L. Lim, M. Wang, and J. S. Vitter. ``SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads,'' in preparation. An extended abstract appears in Proceedings of the 29th International Conference on Very Large Databases (VLDB '03), Berlin, Germany, September 2003, 369-380.

160.

R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. ``Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data,'' in preparation. An extended abstract appears in Proceedings of the 30th International Conference on Very Large Databases (VLDB '04), Toronto, CA, August 2004, 876-887.

161.

L. Lim, M. Wang, and J. S. Vitter. ``CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation,'' in preparation. An extended abstract appears in Proceedings of the 31st International Conference on Very Large Databases (VLDB '05), Trondheim, Norway, August-September 2005, 1187-1198.

162.

A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. ``A Framework for Dynamizing Succinct Data Structures,'' in preparation. An extended abstract appears in Proceedings of the 34th Annual International Colloquium on Automata, Languages, and Programming (ICALP '07), Wrocaw, Poland, July 2007, published in Lecture Notes in Computer Science, 4596 Springer-Verlag, Berlin, Germany, 521-532.

163.

W.-K. Hon, T.-W. Lam, R. Shah, S.-L. Tam, and J. S. Vitter. ``Cache-Oblivious Index for Approximate String Matching,'' in preparation. An extended abstract appears in Proceedings of the 16th Annual Conference on Combinatorial Pattern Matching (CPM '07), London, Ontario, Canada, July 2007, published in Lecture Notes in Computer Science, 4580 Springer-Verlag, Berlin, Germany, 40-51.

164.

R. Grossi, A. Gupta, and J. S. Vitter. ``Nearly Tight Bounds on the Encoding Length of the Burrows-Wheeler Transform,'' in preparation. An extended abstract appears in Proceedings of the 5th Workshop on Analytical Algorithmics and Combinatorics (ANALCO '08), San Francisco, CA, January 2008.

165.

M. Y. Eltabakh, W.-K. Hon, R. Shah, W. Aref, and J. S. Vitter. ``The SBC-tree: An Index for Run-Length Compressed Sequences,'' in preparation. An extended abstract appears in Proceedings of the 11th International Conference on Extending Database Technology (EDBT '08), Nantes, France, March 2008, 523-534.

166.

Y.-F. Chien, W.-K. Hon, R. Shah, and J. S. Vitter. ``Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing,'' in preparation. An extended abstract appears in Proceedings of the 2008 IEEE Data Compression Conference (DCC '08), Snowbird, UT, March 2008.

167.

W.-K. Hon, T.-W. Lam, R. Shah, S.-L. Tam, and J. S. Vitter. ``Compressed Index for Dictionary Matching,'' in preparation. An extended abstract appears in Proceedings of the 2008 IEEE Data Compression Conference (DCC '08), Snowbird, UT, March 2008.

168.

P. Ferragina, R. Grossi, A. Gupta, R. Shah, and J. S. Vitter. ``On Searching Compressed String Collections Cache-Obliviously,'' in preparation. An extended abstract appears in Proceedings of the 27th Annual ACM Symposium on Principles of Database Systems (PODS '08), Vancouver, Canada, June 2008.

169.

W.-K. Hon, R. Shah, P. J. Varman, and J. S. Vitter. ``Tight Competitive Ratios for Parallel Disk Prefetching,'' Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '08), Munich, Germany, June 2008.

170.

W.-K. Hon, R. Shah, S. V. Thankachan, and J. S. Vitter. ``On Entropy-Compressed Text Indexing in External Memory,'' in preparation. An extended abstract appears in Proceedings of the 16th International Conference on String Processing and Information Retrieval (SPIRE '09), Saariselkä, Finland, August 2009, published in Lecture Notes in Computer Science, 5721 Springer-Verlag, Berlin, Germany, 75-89.

171.

W.-K. Hon, R. Shah, and J. S. Vitter. ``Space-Efficient Framework for Top-k String Retrieval Problems,'' in preparation. An extended abstract appears in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09), Atlanta, GA, October 2009.

172.

W.-K. Hon, T.-W. Lam, R. Shah, S.-L. Tam, and J. S. Vitter. ``Succinct Index for Dynamic Dictionary Matching,'' in preparation. An extended abstract appears in Proceedings of the 20th annual International Symposium on Algorithms and Computation (ISAAC '09), Honolulu, Hawaii, December 2009.

173.

S.-Y. Chiu, W.-K. Hon, R. Shah, and J. S. Vitter. ``I/O-efficient Compressed Text Indexes: From Theory to Practice,'' being submitted.

174.

A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. ``Dynamic Rank/Select Dictionaries with Applications to XML Indexing,'' being submitted.

175.

D. Gardy and J. S. Vitter. ``A Comparison of the Finite and Infinite Models for Trie Structures,'' in preparation.