Jeffrey Scott Vitter

Yossi Matias ¡ Efficient Bundle Sorting (2008)

We present a unified algorithmic framework to obtain nearly optimal space bounds for text compression and compressed text indexing, apart from lower-order terms. For a text T of n symbols drawn from...

Eran Segal, Jeffrey Scott Vitter

Puzzle J in Abstract (2008)

Min Wang, Jeffrey Scott Vitter

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P, we need to estimate the...

A Framework for Dynamizing Succinct Data Structures ⋆ (2008)

Ankur Gupta, Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter

Abstract. We present a framework to dynamize succinct data structures, to encourage their use over non-succinct versions in a wide variety of important application areas. Our framework can dynamize...

Entropy-Compressed Indexes for Multidimensional Pattern Matching (2008)

Compressed Index for Dictionary Matching ∗ (2008)

In this talk, we will discuss the challenges involved in developing a multidimensional generalizations of compressed text indexing structures. These structures depend on some notion of...

Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter, Tak-wah Lam, Siu-lung Tam

The past few years have witnessed several exciting results on compressed representation of a string T that supports efficient pattern matching, and the space complexity has been reduced to |T |Hk(T)...

U.S.A. Abstract (2008)

Mark H. Nodine, Intrinsity Inc, Jeffrey Scott Vitter

We present a practical deterministic load balancing strategy for distribution sort that is applicable to parallel disks and parallel memory hierarchies with both single and parallel processors. The...

Optimal Lexicographic Shaping of Aggregate Streaming Data (2008)

Stergios V. Anastasiadis, Peter Varman, Senior Member, Jeffrey Scott Vitter, Ke Yi

Abstract—We investigate the problem of smoothing multiplexed network traffic when either a streaming server transmits data to multiple clients or a storage server accesses data from multiple...

U.S.A. Abstract (2008)

Mark H. Nodine, Intrinsity Inc, Jeffrey Scott Vitter

We present a load balancing technique that leads to an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks. Our measure of performance is the number of...

Efficient Update of Indexes for Dynamically Changing Web Documents (2008)

Min Wang, Jeffrey Scott Vitter, Lipyeow Lim, Sriram Padmanabhan, Ramesh Agarwal

Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is...

AND (2008)

Jeffrey Scott Vitter, P. Krishnan

Abstract. Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new...

(page i) Average-Case Analysis of Algorithms and Data Structures (2008)

Constructing Binary Space Partitions for Orthogonal Rectangles in Practice (2007)

L’analyse en moyenne des algorithmes et des structures de données

T. M. Murali, Pankaj K. Agarwal, Jeffrey Scott Vitter

. In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in R 3 . Our algorithm has the novel feature that it tunes its...

Apostol (paul Natsev, Atul Chadha, Basuki Soetarman, Jeffrey Scott Vitter

We present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. Our data structure settles an open problem in databases...

c (2007)

a y

and Theoretical Computer Science External Memory Algorithms and Data Structures (2007)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

Abstract. Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal...

x (2007)

We show how to preprocess a set S of points in R d to get an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint a...

Acknowledgments (2007)

Have Been Very, T. M. Murali, T. M. Murali, Jeffrey Scott Vitter, Pankaj K. Agarwal, John F. Hughes

this paper, we consider the following problem:

Lexicographic Bit Allocation For Mpeg Video Coding (2007)

Dzung Hoang Jeffrey, Jeffrey Scott Vitter, Elliot L. Linzer

We consider the problem of allocating bits among pictures in an MPEG video coder to equalize the visual quality of the coded pictures, while meeting buffer and channel constraints imposed by the MPEG...

External-Memory Graph Algorithms (2007)

Appeared In, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...

We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...

Efficient 3-D Range Searching in External Memory (2007)

Lars Arge, Darren Erik Vengroff, Jeffrey Scott Vitter

We present a new approach to designing data structures for the important problem of externalmemory range searching in two and three dimensions. We construct data structures for answering range...

z (2007)

In the design of algorithms for large-scale applications it is essential to consider the problem of minimizing I/O communication. Geographical information systems (GIS) are good examples of such...

y Motorola Semiconductor Products Sector (2007)

Mark H. Nodine, W. Parmer Lane, Bldg C, Jeffrey Scott Vitter

We present a load balancing technique that leads to an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks. Our measure of performance is the number of...

1 (2007)

Pankaj K. Agarwal, Leonidas J. Guibas, T. M. Murali, Jeffrey Scott Vitter

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a...

z (2007)

We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show...

3 (2007)

Yossi Matias, Jeffrey Scott Vitter, Wen-chun Ni

This paper is a combination of two independent works [17] and [24] and collaborative work. A summarized version appears in [19]. 2

(page 1) Learning in Parallel* (2007)

Jeffrey Scott Vitter, Jyh-han Lin

Abstract. In this paper, we extend Valiant's sequential model of concept learning from examples [Valiant 1984] and introduce models for the efficient learning of concept classes from examples in...

(page 1) Design and Analysis of Dynamic Huffman Codes Dessein et Analyse des Codes (2007)

Huffman Dynamiques, Jeffrey Scott Vitter

Abstract. We introduce and analyze a new one-pass algorithm for constructing dynamic Huffman codes and also analyze the one-pass algorithm due to Faller, Gallager, and Knuth. In each algorithm, both...

y Motorola Semiconductor Products Sector (2007)

Mark H. Nodine, W. Parmer Lane, Bldg C, Jeffrey Scott Vitter

We present a practical deterministic load balancing strategy for distribution sort that is applicable to parallel disks and parallel memory hierarchies with both single and parallel processors. The...

and (2007)

Franco P. Preparata, Jeffrey Scott Vitter

In this paper we give a practical and efficient output-sensitive algorithm for constructing the display of a polyhedral terrain. It runs in O((d + n) log 2 n) time and uses O(nff(n)) space, where d...

and (2007)

Roberto Tamassia, Ioannis G. Tollis, Jeffrey Scott Vitter, Communicated Michel Cosnard

In this paper we consider the problem of constructing planar orthogonal grid drawings (or more simply, layouts) of graphs, with the goal of minimizing the number of bends along the edges. We present...

International Journal of Computational Geometry & Applications c fl World Scientific Publishing Company THE OBJECT COMPLEXITY MODEL FOR HIDDEN-SURFACE REMOVAL (2007)

Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We define a new model of complexity, called object complexity, for measuring the performance of hidden-surface removal algorithms. This model is more appropriate for predicting the performance of...

x (2007)

Rakesh Barve, Mahesh Kallahalla, Peter J. Varman, Jeffrey Scott Vitter

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread...

Former S'equentiellement un (2007)

Proposed Running Head: Lexicographic Bit Allocation for MPEG Video (2007)

Abstract. We examine several methods for drawing a sequential random sample of n records from a file containing N records. Method D, which was introduced in [10], is recommended for general use. The...

Elliot L. Linzer, Jeffrey Scott Vitter, Dzung T. Hoang, Dzung T. Hoang

We consider the problem of allocating bits among pictures in an MPEG video coder to equalize the visual quality of the coded pictures, while meeting buffer and channel constraints imposed by the MPEG...

Rakesh Barve, Elizabeth Shriver, Phillip B. Gibbons, Bruce K. Hillyer, Yossi Matias, Jeffrey Scott Vitter

Abstract For a wide variety of computational tasks, disk I/O continues to be a serious obstacle to high performance. The focus of the present paper is on systems that use multiple disks per SCSI bus....

2 (2007)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

This work concerns the search for text compressors that compress better than existing dictionary coders, but run faster than statistical coders. We describe a new method for text compression using...

z (2007)

P. Krishnan, Philip M. Long, Jeffrey Scott Vitter

In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...

Optimal Prefetching via Data Compression I (2007)

In this paper, we introduce an efficient method for the dynamic maintenance of wavelet-based histograms (and other transform-based histograms). Previous work has shown that wavelet-based histograms...

Jeffrey Scott, Vitter P. Krishnan, Jeffrey Scott Vitter, P. Krishnan

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms...

Approximation Algorithms for Geometric Median Problems * (2007)

Michael T. Goodrich, National Chung Cheng, Darren Erik Vengroff, Jeffrey Scott Vitter

In this paper we present approximation algorithms for median problems in metric spaces and fixed-dimensional Euclidean space. Our algorithms use a new method for transforming an optimal solution of...

devcs. brown. edu (2007)

j svcs. duke. edu In this paper, we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory, and we use these...

ABSTRACT Flow Computation on Massive Grids ∗ (2007)

Laura Toma, Rajiv Wickremesinghe, Lars Arge, Jeffrey S. Chase, Jeffrey Scott Vitter, Patrick N. Halpin, ...

As detailed terrain data becomes available, GIS applications target larger geographic areas at finer resolutions. Processing the massive data presents significant challenges to GIS systems and...

Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter

z In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the first part of the paper, we apply the theory of indexability to...

A Framework for Index Bulk Loading and (2007)

Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

Abstract. In this paper we investigate automated methods for externalizing internal memory data structures. We consider a class of balanced trees that we call weight-balanced partitioning trees (or...

Optimal Prefetching via Data Compression (2007)

Jeffrey Scott, Vitter P. Krishnan, Jeffrey Scott Vitter, P. Krishnan

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms...

International Journal of Computational Geometry & Applications c fl World Scientific Publishing Company THE OBJECT COMPLEXITY MODEL FOR HIDDEN-SURFACE REMOVAL (2007)

Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We define a new model of complexity, called object complexity, for measuring the performance of hidden-surface removal algorithms. This model is more appropriate for predicting the performance of...

1 (2007)

A Framework for Index Bulk Loading (2007)

L'analyse en moyenne des algorithmes et des structures de donn'ees

Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

Abstract. In this paper we investigate automated methods for externalizing internal memory data structures. We consider a class of balanced trees that we call weight-balanced partitioning trees (or...

Applied Research/Communications Lab. (2007)

Jyh-han Lin, Jeffrey Scott Vitter, Jeffrey Scott Vitter

A memory-based learning system is an extended memorymanagement system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and retrieving...

SUCCINCT DATA STRUCTURES Date: (2007)

Ankur Gupta, Jeffrey Scott Vitter, Pankaj Agarwal, Roberto Grossi, Xiaobai Sun, Ankur Gupta, ...

Dynamic rank/select dictionaries with applications to XML indexing (2006)

Jeffrey S. Vitter, Ankur Gupta, Ankur Gupta, Wing-kai Hon, Wing-kai Hon, Rahul Shah, ...

\lie consider a central problem in text indexing: Given a text T over an alphabet C, construct a conlpressed data structure answering the queries char(i), rank,(i); and select,(i) for a synlbol s E...

Compressed Text Indexing and Range Searching (2006)

Yu-feng Chien, Waing-kai Hon, Raul Shah, Jeffrey Scott Vitter, Yu-feng Chien, Wing-kai Hon, ...

We introduce two transformations Text2Points and Points2Text that, respectively, convert text to points in space and vice-versa. With these transformations, data structural problems in pattern...

Ordered Pattern Matcliing: Towards Full-Text Retrieval (2006)

Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter, Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter

A typical query in Information Retrieval consists of multiple keywords, and the target is to retrieve matching documents. Various selection heuristics and

Adaptive rank-aware query optimization in relational databases (2006)

Ihab F. Ilyas, Walid G. Aref, Ahmed K. Elmagarmid, Hicham G. Elmongui, Rahul Shah, Jeffrey Scott Vitter

Rank-aware query processing has emerged as a key requirement in modern applications. In these applications, efficient and adaptive evaluation of top-k queries is an integral part of the application...

Dynamic rank/select dictionaries with applications to XML indexing (2006)

Ankur Gupta, Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter

We consider a central problem in text indexing: Given a text T over an alphabet Σ, construct a compressed data structure answering the queries char(i), rank s(i), and select s(i) for a symbol s ∈...

Compressed data structures: dictionaries and data-aware measures (2006)

Ankur Gupta, Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter

Abstract. We propose measures for compressed data structures, in which space usage is measured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data, where...

Compressed dictionaries: Space measures, data sets, and experiments (2006)

Ankur Gupta, Wing-kai Hon, Rahul Shah, Jeffrey Scott Vitter

Abstract. In this paper, we present an experimental study of the spacetime tradeoffs for the dictionary problem, where we design a data structure to represent set data, which consist of a subset S of...

CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation (2005)

Roberto Grossi, Jeffrey Scott Vitter

Query optimization in IBM's System RX, the first truly relational-XML hybrid data management system, requires accurate selectivity estimation of path-value pairs, i.e., the number of nodes in...

Abstract (2005)

The proliferation of online text, such as on the World Wide Web and in databases, motivates the need for space-efficient text indexing methods that support fast string searching. We model this...

Fast compression with a static model in high-order entropy (2004)

Luca Foschini, Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter

We report on a simple encoding format called wzip for decompressing blocksorting transforms, such as the Burrows-Wheeler Transform (BWT). Our compressor uses the simple notions of gamma encoding and...

When indexing equals compression: Experiments with compressing suffix arrays and applications (2004)

Efficient indexing methods for probabilistic threshold queries over uncertain data (2004)

We report on a new and improved version of high-order entropy-compressed suffix arrays, which has theoretical performance guarantees similar to those in our earlier work [16], yet represents an...

Reynold Cheng, Yuni Xia, Sunil Prabhakar, Rahul Shah, Jeffrey Scott Vitter

It is infeasible for a sensor database to contain the exact value of each sensor at all points in time. This uncertainty is inherent in these systems due to measurement and sampling errors, and...

Efficient indexing methods for probabilistic threshold queries over uncertain data (2004)

Reynold Cheng, Yuni Xia, Sunil Prabhakar, Rahul Shah, Jeffrey Scott Vitter

It is infeasible for a sensor database to contain the exact value of each sensor at all points in time. This uncertainty is inherent in these systems due to measurement and sampling errors, and...

Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data (2004)

Reynold Cheng, Yuni Xia, Sunil Prabhakar, Rahul Shah, Jeffrey Scott Vitter

It is infeasible for a sensor database to contain the exact value of each sensor at all points in time. This uncertainty is inherent in these systems due to measurement and sampling errors, and...

Dynamic Maintenance of Web Indexes Using Landmarks (2003)

Lim, Lipyeow, Wang, Min, Padmanabhan, Sriram, Vitter, Jeffrey Scott, Agarwal, Ramesh

Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is...

High-order entropy-compressed text indexes (2003)

Bkd-tree: A dynamic scalable kd-tree (2003)

We present a novel implementation of compressed suffix arrays exhibiting new tradeoffs between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet Σ, where...

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter

Abstract. In this paper we propose a new data structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkd-tree is an I/O-efficient dynamic data structure based on...

Bkd-tree: A dynamic scalable kd-tree (2003)

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter

Abstract. In this paper we propose a new index structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkdtree is an I/O-efficient dynamic data structure based on...

Bkd-tree: A dynamic scalable kd-tree (2003)

Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, Jeffrey Scott Vitter

Abstract. In this paper we propose a new data structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkd-tree is an I/O-efficient dynamic data structure based on...

Dynamic maintenance of web indexes using landmarks (2003)

Lipyeow Lim, Min Wang, Sriram Padmanabhan, Jeffrey Scott Vitter, Ramesh Agarwal

Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is...

SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads (2003)

SASH: A Self-Adaptive Histogram Set For Dynamically Changing Workloads (2003)

Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries.

SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads (2003)

Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries. These selectivities are typically used for costbased query optimization. While the problem of building an...

Optimal external memory interval management (2003)

Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries.

Dynamic maintenance of web indexes using landmarks (2003)

In this paper we present the external interval tree, an optimal external memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The external interval tree...

Lipyeow Lim, Jeffrey Scott Vitter, Min Wang, Ramesh Agarwal

SASH: A Self-Adaptive Histogram Set For Dynamically Changing Workloads (2003)

Implementing I/O-efficient data structures using TPIE (2002)

Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries. These selectivities are typically used for costbased query optimization. While the problem of building an...

Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

Abstract. In recent years, many theoretically I/O-efficient algorithms and data structures have been developed. The TPIE project at Duke University was started to investigate the practical importance...

Implementing I/O-efficient data structures using TPIE (2002)

Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

large,tavi,jsv¤ Abstract. In recent years, many theoretically I/O-efficient algorithms and data structures have been developed. The TPIE project at Duke University was started to investigate the...

Implementing I/O-efficient data structures using TPIE (2002)

Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter

large,tavi,jsv¤ Abstract. In recent years, many theoretically I/O-efficient algorithms and data structures have been developed. The TPIE project at Duke University was started to investigate the...

Efficient sorting using registers and caches (2002)

Rajiv Wickremesinghe, Lars Arge, Jeff Chase, Jeffrey Scott Vitter

Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets,...

The power of duality for prefetching and sorting with parallel disks (2001)

David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter

External memory (EM) algorithms are designed to be efficient when the problem data do not fit into the high-speed random access memory (RAM) of a computer and must instead

Duality between prefetching and queued writing with parallel disks (2001)

David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter

Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat...

Supporting incremental join queries on ranked inputs (2001)

Apostol Natsev, Yuan-chi Chang, John R. Smith, Chung-sheng Li, Jeffrey Scott Vitter

This paper investigates the problem of incremental joins of multiple ranked data sets when the join condition is a list of arbitrary user-defined predicates on the input tuples. This problem arises...

Distribution sort with randomized cycling (2001)

Jeffrey Scott Vitter, David A. Hutchinson

Paxallel independent disks can enhance the performance of external memory (EM) algorithms, but the programming task is often difficult. In this paper we develop randomized vaxiants of distribution...

Wavelet-based cost estimation for spatial queries (2001)

Min Wang, Jeffrey Scott Vitter, Lipyeow Lim, Sriram Padmanabhan

Abstract. Query cost estimation is an important and well-studied problem in relational database systems. In this paper we study the cost estimation problem in the context of spatial database systems....

Characterizing Web document change (2001)

Lipyeow Lim, Min Wang, Sriram Padmanabhan, Jeffrey Scott Vitter, Ramesh Agarwal

The World Wide Web is growing and changing at an astonishing rate. For the information in the web to be useful, web information systems such as search engines have to keep up with the growth and...

Supporting incremental join queries on ranked inputs (2001)

Apostol Natsev, Yuan-chi Chang, John R. Smith, Chung-sheng Li, Jeffrey Scott Vitter

This paper investigates the problem of incremental joins of multiple ranked data sets when the join condition is a list of arbitrary user-defined predicates on the input tuples. This problem arises...

External Memory Algorithms and Data Structures: Dealing with Massive Data (2001)

Supporting incremental join queries on ranked inputs (2001)

. Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication for I/O between fast internal memory and...

Apostol Natsev, Yuan-chi Chang, John R. Smith, Chung-sheng Li, Jeffrey Scott Vitter

This paper investigates the problem of incremental joins of multiple ranked data sets when the join condition is a list of arbitrary user-defined predicates on the input tuples. This problem arises...

I/O-efficient algorithms for problems on grid-based terrains (2000)

Efficient sorting using registers and caches (2000)

The potential and use of Geographic Information Systems (GIS) is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to...

Rajiv Wickremesinghe, Lars Arge, Jeff Chase, Jeffrey Scott Vitter

Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets,...

I/O-efficient algorithms for problems on grid-based terrains (2000)

A unified approach for indexed and non-indexed spatial joins (2000)

The potential and use of Geographic Information Systems (GIS) is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to...

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter

Abstract. Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process,or solve the problem by sorting, partitioning, or on-the-fly...

Compressed suffix arrays and suffix trees with applications to text indexing and string matching (2000)

Roberto Grossi, Jeffrey Scott Vitter

The proliferation of online text, such as on the World Wide Web and in databases, motivates the need for space-efficient index methods that support fast search. Consider a text T of n binary symbols...

I/O-efficient algorithms for problems on grid-based terrains (2000)

I/O-efficient algorithms for problems on grid-based terrains (2000)

The potential and use of Geographic Information Systems (GIS) is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to...

Dynamic Maintenance of Wavelet-Based Histograms (2000)

The potential and use of Geographic Information Systems (GIS) is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to...

I/O-Efficient Algorithms for Problems on Grid-based Terrains (Extended Abstract) (2000)

In this paper, we introduce an efficient method for the dynamic maintenance of wavelet-based histograms (and other transform-based histograms). Previous work has shown that wavelet-based histograms...

A Unified Approach For Indexed and Non-Indexed Spatial Joins (2000)

The potential and use of Geographic Information Systems (GIS) is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to...

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Jeffrey Scott Vitter, Jan Vahrenhold, Torsten Suel

A large number of spatial join algorithms have been proposed over the last few years. Most of the algorithms can be broadly categorized into two approaches. The first approach assumes the existence...

A Unified Approach For Indexed and (2000)

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter

Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process, or solve the problem by sorting, partitioning, or on-the-fly index...

A unified approach for indexed and non-indexed spatial joins (2000)

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter

Abstract. Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process,or solve the problem by sorting, partitioning, or on-the-fly...

I/O-efficient algorithms for problems on grid-based terrains (Extended Abstract) (2000)

Efficient bundle sorting (2000)

The potential and use of Geographic Information Systems (GIS) is rapidly increasing due to the increasing availability of massive amounts of geospatial data from projects like NASA's Mission to...

Yossi Matias, Eran Segal, Jeffrey Scott Vitter

Many data sets to be sorted consist of a limited number of distinct keys. Sorting such data sets can be thought of as bundling together identical keys and having the bundles placed in order; we...

A simple and efficient parallel disk mergesort (1999)

Rakesh D. Barve, Jeffrey Scott Vitter

External sorting---the process of sorting a massive data set that is too large to fit into the computer's internal memory and must be stored externally on disks---is a fundamental primitive in...

Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets (1999)

Jeffrey Scott Vitter, Min Wang

Computing multidimensional aggregates in high dimensions is a performance bottleneck for many OLAP applications. Obtaining the exact answer to an aggregation query can be prohibitively expensive in...

Efficient Hidden-Surface Removal in Theory and in Practice (1999)

T. M. Murali, T. M. Murali, Jeffrey Scott Vitter, Pankaj K. Agarwal, John F. Hughes

A central component of rendering is hiddent-surface removal. Given a set of objects, compute the scrne visible from the viewpoint as projected onto the image plane, we would like to compute the first...

A Theoretical Framework for Memory-Adaptive Algorithms (1999)

Rakesh D. Barve, Jeffrey Scott Vitter

External Memory algorithms play a key role in database management systems and large scale processing systems. External memory algorithms are typically tuned for efficient performance given a fixed,...

Online data structures in external memory (1999)

External Memory Algorithms and Data Structures (1999)

The data sets for many of today's computer applications are too large to fit within the computer's internal memory and must instead be stored on external storage devices such as disks. A...

Dictionary selection using partial matching (1999)

. Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory...

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

This work concerns the search for text compressors that compress better than existing dictionary coders, but run faster than statistical coders. We describe a new method for text compression using...

Efficient Bulk Operations on Dynamic R-trees (1999)

Lars Arge, Klaus H. Hinrichs, Jan Vahrenholt, Jeffrey Scott Vitter

In recent years, there has been an upsurge of interest in spatial databases. A major issue is how to e ciently manipulate massive amounts of spatial data stored on disk in multidimensional spatial...

and (1999)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paulo G. Franciosa, Jeffrey Scott Vitter

194

I/O-optimal computation of segment intersections (1999)

Crauser, Andreas, Ferragina, Paolo, Mehlhorn, Kurt, Meyer, Ulrich, Ramos, Edgar A., Abello, James M., ...

I/O-efficient algorithms for contour-line extraction and planar graph blocking (1998)

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter

For a polyhedral terrain \Sigma, the contour at z-coordinate h, denoted Ch, is defined to be the intersection of the plane z = h with \Sigma. In this paper, we study the contour-line extraction...

Efficient cost measures for motion estimation at low bit rates (1998)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

Abstract--- We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and videoconferencing applications, where...

External memory algorithms with dynamically changing memory allocations: Long version (1998)

Jeffrey S. Vitter, Rakesh Barve, Rakesh Barve, Jeffrey Scott Vitter

We consider the problem of devising external memory algorithms whose memory allocations can change dynamically and unpredictably at run-time. The investigation of "memory-adaptive "...

Efficient cost measures for motion estimation at low bit rates (1998)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

Abstract--- We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and videoconferencing applications, where...

Scalable Sweeping-Based Spatial Join (1998)

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter

In this paper, we consider the filter step of the spatial join problem, for the case where neither of the inputs are indexed. We present a new algorithm, Scalable Sweeping-Based Spatial Join (SSSJ),...

Wavelet-Based Histograms for Selectivity Estimation (1998)

Data Cube Approximation and Histograms via Wavelets (Extended Abstract) (1998)

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P, we need to estimate the...

Jeffrey Scott Vitter, Min Wang, Bala Iyer

) Jeffrey Scott Vitter Center for Geometric Computing and Department of Computer Science Duke University Durham, NC 27708--0129 USA jsv@cs.duke.edu Min Wang y Center for Geometric Computing and...

Efficient Cost Measures for Motion Estimation at Low Bit Rates (1998)

Dzung Hoang Philip, Philip M. Long, Jeffrey Scott Vitter

We present and compare methods for choosing motion vectors for block-based motioncompensated video coding. The primary focus is on videophone and videoconferencing applications, where low bit rates...

Efficient Searching with Linear Constraints (Extended Abstract) (1998)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint a...

Scalable Sweeping-Based Spatial Join (1998)

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter

In this paper, we consider the filter step of the spatial join problem, for the case where neither of the inputs are indexed. We present a new algorithm, Scalable Sweeping-Based Spatial Join (SSSJ),...

Efficient Searching with Linear Constraints (1998)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...

Fast and Efficient Algorithms for Video Compression and Rate Control (1998)

Dzung Tien Hoang, Jeffrey Scott Vitter, J. S. Vitter

ceived a Bachelor of Science with Highest Honors in Mathematics from the University of Notre Dame in 1977, and a Doctor of Philosophy in Computer Science from Stanford University in 1980. He was on...

Wavelet-Based Histograms for Selectivity Estimation (1998)

Scalable Sweeping-Based Spatial Join (1998)

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P , we need to estimate...

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter

In this paper, we examine the spatial join problem. In particular, we focus on the case when neither of the inputs is indexed. We present a new algorithm, Scalable Sweep-based Spatial Join (SSSJ),...

Scalable Mining for Classification Rules in Relational Databases (1998)

Min Wang, Bala Iyer, Jeffrey Scott Vitter

Classification is a key function of many "business intelligence" toolkits and a fundamental building block in data mining. Immense data may be needed to train a classifier for good...

Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems (1998)

Extend Ed, Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter

) Lars Arge Octavian Procopiuc y Sridhar Ramaswamy z Torsten Suel x Jeffrey Scott Vitter -- Abstract We describe a powerful framework for designing efficient batch algorithms for certain large-scale...

I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract) (1998)

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter

) Pankaj K. Agarwal Lars Arge y T. M. Murali z Kasturi R. Varadarajan x Jeffrey Scott Vitter -- Center for Geometric Computing Department of Computer Science Duke University Durham, NC 27708--0129...

External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (1998)

Lars Arge, Darren Erik Vengroff, Jeffrey Scott Vitter

In the design of algorithms for large-scale applications it is essential to consider the problem of minimizing I/O communication. Geographical information systems (GIS) are good examples of such...

I/O-efficient algorithms for contour-line extraction and planar graph blocking (Extended Abstract) (1998)

Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter

For a polyhedral terrain, the contour at z-coordinate h, denoted Ch, is de ned to be the intersection of the plane z = h with. In this paper, we study the contour-line extraction problem, where we...

Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems (1998)

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter

We describe a powerful framework for designing efficient batch algorithms for certain large-scale dynamic problems that must be solved using external memory. The class of problems we consider, which...

Cylindrical static and kinetic binary space partitions (1997)

Pankaj K. Agarwal, Leonidas J. Guibas, T. M. Murali, Jeffrey Scott Vitter

We describe the first known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane, whose interiors remain disjoint throughout the...

Practical Techniques for Constructing Binary Space Partitions for Orthogonal Rectangles (1997)

Pankaj K. Agarwal, T. M. Murali, Jeffrey Scott Vitter

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R 3 . We compare known algorithms with our...

A lexicographic framework for mpeg rate control (1997)

Dzung T. Hoang, Elliot L. Linzer, Jeffrey Scott Vitter

We consider the problem of allocating bits among pictures in an MPEG video coder to equalize the visual quality of the coded pictures, while meeting buffer and channel constraints imposed by the MPEG...

Multiplexing Vbr Video Sequences Onto A Cbr Channel With Lexicographic Optimization (1997)

Dzung Hoang Digital, Dzung T. Hoang, Jeffrey Scott Vitter

We apply a novel lexicographic framework for bit allocation to the multiplexing of multiple VBR video streams onto a single CBR channel. In the lexicographic framework, the maximum distortion is...

Competitive Parallel Disk Prefetching and Buffer Management (1997)

Rakesh Barve, Mahesh Kallahalla, Peter J. Varman, Jeffrey Scott Vitter

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread...

Dynamic Generation of Discrete Random Variates (1997)

Yossi Matias, Jeffrey Scott Vitter, Yossi Matias, Je#rey Scott Vitter, Je#rey Scott Vitter, Wen-chun Ni

We present and analyze e#cient new algorithms for generating a random variate distributed according to a dynamically changing set of weights. The base version of each algorithm generates the discrete...

Binary Space Partitions for Fat Rectangles (1997)

Pankaj K. Agarwal, Pankaj K. Agarwal, Edward F. Grove, Edward F. Grove, T. M. Murali, T. M. Murali, ...

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, non-intersecting, two-dimensional rectangles in R 3 such that the aspect ratio of each...

Efficient Searching with Linear Constraints (1997)

Pankaj Agarwal Lars, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...

Efficient Searching with Linear Constraints (1997)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R^d into an external memory....

Efficient Searching with Linear Constraints (1997)

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo G. Franciosa, Jeffrey Scott Vitter

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0...

On Sorting Strings in External Memory (1997)

Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter

) Lars Arge Paolo Ferragina y Roberto Grossi z Jeffrey Scott Vitter x Abstract. In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory,...

Practical techniques for constructing binary space partitions for orthogonal rectangles (1997)

Pankaj K. Agarwal, T. M. Murali, Jeffrey Scott Vitter

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R³. We compare known algorithms with our...

Competitive Parallel Disk Prefetching and Buffer Management (1997)

Rakesh Barve, Mahesh Kallahalla, Peter J. Varman, Jeffrey Scott Vitter

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread...

Selectivity Estimation in the Presence of Alphanumeric Correlations (1997)

Min Wang, Jeffrey Scott Vitter, Bala Iyer

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P , we need to estimate...

Application-Controlled Paging for a Shared Cache (1997)

Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter

We propose a provably efficient application-controlled global strategy for organizing a cache of size k shared among P application processes. Each application has access to information about its own...

and (1997)

Roberto Tamassia, Ioannis G. Tollis, Communicated Michel Cosnard, Jeffrey Scott Vitter

In this paper we consider the problem of constructing planar orthogonal grid drawings (or more simply, layouts) of graphs, with the goal of minimizing the number of bends along the edges. We present...

Competitive parallel disk prefetching and buffer management (1997)

Rakesh Barve, Mahesh Kallahalla, Peter J. Varman, Jeffrey Scott Vitter

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I�O systems, using a read-once model of block references. This has widespread...

Competitive parallel disk prefetching and buffer management (1997)

Rakesh Barve, Mahesh Kallahalla, Peter J. Varman, Jeffrey Scott Vitter

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread...

On sorting strings in external memory (extended abstract (1997)

Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter

Abstract. In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory, which is a fundamental component of many large-scale text applications....

Simple randomized mergesort on parallel disks (1997)

Rakesh Barve, Rakesh D. Barve, Edward F. Grove, Edward F. Grove, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We consider the problem of sorting a file of N records on the D-disk model of parallel I/O in which there are two sources of parallelism. Records are transferred to and from disk concurrently in...

Estimating alphanumeric selectivity in the presence of wildcards (1996)

P. Krishnan, Jeffrey Scott Vitter, Bala Iyer

Success of commercial query optimizers and database management systems (object-oriented or relational) depend on accurate cost estimation of various query reorderings [BGI]. Estimating predicate...

Optimal Dynamic Interval Management in External Memory (1996)

We present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. Our data structure settles an open problem in databases...

Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, non-intersecting, two-dimensional rectangles in R 3 such that the aspect ratio of each...

Rate-distortion optimizations for motion estimation in low-bit-rate video coding (1996)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

2

Simple Randomized Mergesort on Parallel Disks (1996)

Rakesh Barve Dept, Rakesh Barve, Rakesh Barve, Edward F. Grove, Edward F. Grove, Jeffrey Scott Vitter, ...

We consider the problem of sorting a file of N records on the D-disk model of parallel I/O [VS94] in which there are two sources of parallelism. Records are transferred to and from disk concurrently...

Simple Randomized Mergesort on Parallel Disks (1996)

Rakesh Barve, Rakesh D. Barve, Jeffrey Scott Vitter, Edward F. Grove, Edward F. Grove, Je#rey Scott Vitter, ...

We consider the problem of sorting a file of N records on the D-disk model of parallel I/O in which there are two sources of parallelism. Records are transferred to and from disk concurrently in...

Report of the Working Group on Storage I/O for Large-Scale Computing (1996)

Garth A. Gibson, Jeffrey Scott Vitter, John Wilkes, David Kotz (dartmouth, Kai Li (princeton

We discuss the strategic directions and challenges in the management and use of storage systems -- those components of computer systems responsible for the storage and retrieval of data. The...

Optimal Dynamic Interval Management in External Memory (1996)

Blocking for External Graph Searching (1996)

We present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. Our data structure settles an open problem in databases...

Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter

In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of...

Efficient Cost Measures for Motion Compensation at Low Bit Rates (Extended Abstract) (1996)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

We make a case that, even with severe efficiency constraints, taking the number of bits to code each motion vector into account when estimating motion for video compression results in significantly...

Pankaj Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in IR 3 such that the aspect ratio of each...

Optimal Dynamic Interval Management in External Memory (1996)

n the plane, a stabbing query with q reduces to the special case of two-sided 2-dimensional range searching called diagonal corner queries with corner (q; q) on the x = y line. The metablock tree...

Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in IR 3 such that the aspect ratio of each...

Simple Randomized Mergesort on Parallel Disks (1996)

Rakesh Barve, Rakesh D. Barve, Edward F. Grove, Edward F. Grove, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We consider the problem of sorting a file of N records on the D-disk model of parallel I/O in which there are two sources of parallelism. Records are transferred to and from disk concurrently in...

Pankaj Agarwal, Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

This paper is to be presented at FOCS '96; a copy of the paper is available at

Simple Randomized Mergesort on Parallel Disks (1996)

Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter

We consider the problem of sorting a file of N records on the D-disk model of parallel I/O in which there are two sources of parallelism. Records are transferred to and from disk concurrently in...

Efficient 3-D range searching in external memory (1996)

I/O-efficient scientific computation using TPIE (1995)

We present a new approach to designing data structures for the important problem of external-memory range searching in two and three dimensions. We construct data structures for answering range...

Load balancing in the L_p norm (1995)

In recent years, I/O-efficient algorithms for a wide variety of problems have appeared in the literature. Thus far, however, systems specifically designed to assist programmers in implementing such...

Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion....

Application-Controlled Paging for a Shared Cache (1995)

Rakesh Barve Edward, Rakesh D. Barve, Edward F. Grove, Edward F. Grove, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We propose a provably efficient application-controlled global strategy for organizing a cache of size k shared among P application processes. Each application has access to information about its own...

An Efficient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs (1995)

Sairam Subramanian, Sairam Subramanian, Roberto Tamassia, Roberto Tamassia, Jeffrey Scott Vitter, Jeffrey Scott Vitter

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the...

Application-Controlled Paging for a Shared Cache (1995)

Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...

We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...

Extended Rakesh, Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter

We consider a cache shared by several concurrently running application processes and propose a provably efficient application-controlled global strategy for the shared cache. Using future information...

Load balancing in the L_p norm (1995)

Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion....

Online Perfect Matching and Mobile Computing (1995)

Edward Grove, Ming-yang Kao, P. Krishnan, Jeffrey Scott Vitter

. We present a natural online perfect matching problem motivated by problems in mobile computing. A total of n customers connect and disconnect sequentially, and each customer has an associated set...

Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...

We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...

The Object Complexity Model for Hidden-Surface Elimination (1995)

Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...

We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...

Edward F. Grove, T. M. Murali, Jeffrey Scott Vitter

We define a new complexity measure, called object complexity, for hidden-surface elimination algorithms. This model is more appropriate than the standard scene complexity measure used in...

Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1995)

Krishnan Brown, Jeffrey S. Vitter, P. Krishnan, P. Krishnan, Philip M. Long, Philip M. Long, ...

In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...

Multiple-Dictionary Compression Using Partial Matching (1995)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

Motivated by the desire to find text compressors that compress better than existing dictionary methods, but run faster than PPM implementations, we describe methods for text compression using...

Application-Controlled Paging for a Shared Cache (1995)

Rakesh D. Barve, Edward F. Grove, Jeffrey Scott Vitter

We consider a cache shared by several concurrently running application processes and propose a provably efficient application-controlled global strategy for the shared cache. Using future information...

Rate-Distortion Optimizations for Motion Estimation in Low-Bitrate Video Coding (1995)

Dzung Hoang, Philip M. Long, Jeffrey Scott Vitter

We present and compare methods for choosing motion vectors for motion-compensated video coding. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are...

Efficient 3-D Range Searching in External Memory (1995)

Load Balancing in the (1995)

We present a new approach to designing data structures for the important problem of externalmemory range searching in two and three dimensions. We construct data structures for answering range...

Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-yang Kao, P. Krishnan, Jeffrey Scott Vitter

In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion....

I/O-Efficient Scientific Computation Using TPIE (1995)

In recent years, I/O-efficient algorithms for a wide variety of problems have appeared in the literature. Thus far, however, systems specifically designed to assist programmers in implementing such...

I/O-Efficient Scientific Computation Using TPIE (1995)

Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...

We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...

External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (1995)

In recent years, I/O-efficient algorithms for a wide variety of problems have appeared in the literature. Thus far, however, systems specifically designed to assist programmers in implementing such...

Lars Arge, Darren Erik Vengroff, Jeffrey Scott Vitter

Abstract. In the design of algorithms for large-scale applications it is essential to consider the problem of minimizing I/O communication. Geographical information systems (GIS) are good examples of...

Optimal prediction for prefetching in the worst case (1994)

P. Krishnan, Jeffrey Scott Vitter

Response time delays caused by I/O are a major problem in many systems and database applications. Prefetching and cache-replacement methods are attracting renewed attention because of their success...

Approximate data structures with applications (1994)

Yossi Matias, Jeffrey Scott Vitter, Neal E. Young

In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output. Approximate data structures trade error of approximation for faster...

Algorithms for parallel memory II: Hierarchical multilevel memories (1994)

Jeffrey Scott Vitter, Jeffrey Scott Vitter

In this paper we introduce parallel versions of two hierarchical memory models and give optimal algorithms in these models for sorting, FFT, and matrix multiplication. In our parallel models, there...

Arithmetic Coding for Data Compression (1994)

Jeffrey Scott Vitter, Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter

.23> , en , and an accurate assessment of the probability distribution P of the events, Shannon [1] proved that the the smallest possible expected number of bits needed to encode an event is the...

Optimal Prediction for Prefetching in the Worst Case (1994)

Krishnan Dept Of, P. Krishnan, Jeffrey Scott Vitter

Response time delays caused by I/O is a major problem in many systems and database applications. Prefetching and cache-replacement methods are attracting renewed attention because of their success in...

Complexity Models for Incremental Computation (1994)

Peter Bro, Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia

We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...

Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding (1994)

Jeffrey S. Vitter, Paul Howard, Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We give a detailed algorithm for fast text compression. Our algorithm, related to the PPM method, simplifies the modeling phase by eliminating the escape mechanism and speeds up coding by using a...

Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments (1994)

Kathleen Romanik, Kathleen Romanik, Jeffrey Scott Vitter, Jeffrey Scott Vitter

: We examine the complexity of testing different program constructs. We do this by defining a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik-Chervonenkis...

Explicit Bit Minimization for Motion-Compensated Video Coding (Extended Abstract) (1994)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

We compare methods for choosing motion vectors for motion-compensated video compression. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are necessary,...

Explicit Bit Minimization for Motion-Compensated Video Coding (1994)

Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter

We compare methods for choosing motion vectors for motion-compensated video compression. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are necessary,...

Lower Bounds for Planar Orthogonal Drawings of Graphs (1994)

Roberto Tamassia, Ioannis G. Tollis, Jeffrey Scott Vitter

We study planar orthogonal drawings of graphs and provide lower bounds on the number of bends along the edges. We exhibit graphs on n vertices that require \Omega\Gamma n) bends in any layout, and...

Approximate Data Structures with Applications (Extended Abstract) (1994)

Yossi Matias, Jeffrey Scott Vitter, Neal E. Young

) Yossi Matias y Jeffrey Scott Vitter z Neal E. Young x Abstract In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output....

Fast Progressive Lossless Image Compression (1994)

Jeffrey S. Vitter, Paul Howard, Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We present a method for progressive lossless compression of still grayscale images that combines the speed of our earlier FELICS method with the progressivity of our earlier MLP method. We use...

Fast and Efficient Lossless Image Compression (1994)

Jeffrey S. Vitter, Paul G. Howard, Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We present a new method for lossless image compression that gives compression comparable to JPEG lossless mode with about five times the speed. Our method, called FELICS, is based on a novel use of...

Complexity Models for Incremental Computation (1994)

Peter B. Miltersen, Jeffresy S. Vitter, Peter Bro Miltersen, Sairam Subramanian, Sairam Subramanian, Jeffrey Scott Vitter, ...

We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...

Practical Prefetching via Data Compression (1994)

Jeffrey S. Vitter, Kenneth M. Curewitz, Kenneth M. Curewitz, P. Krishnan, P. Krishnan, ...

An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem...

Fast Progressive Lossless Image Compression (1994)

Algorithms for parallel memory I: Two-level memories (1994)

We present a method for progressive lossless compression of still grayscale images that combines the speed of our earlier FELICS method with the progressivity of our earlier MLP method. We use...

Fast and efficient lossless image compression (1993)

Optimal Deterministic Sorting on Parallel Memory Hierarchies (1993)

We present a new method for lossless image compression that gives compression comparable to JPEG lossless mode with about five times the speed. Our method, called FELICS, is based on a novel use of...

Jeffrey Scott Vitter, Mark H. Nodinc, Mark H. Nodinc, Jeffrey Scott Vittcr

We present a general deterministic sorting strategy that is applicable to a wide variety of parallel memory hierarchies with parallel processors. The simplest incarnation of the strategy is an...

External-memory computational geometry, Proc. 34th Annu (1993)

Michael T. Goodrich, Darren Erik Vengro, Jeffrey Scott Vitter

In this paper we give new techniques for designing efficiet algorithms for computatioal geometry problems that are too lawe to be solved i iteral memory. We use these techiques to develop optimal ad...

Jeffrey Scott Vitter, P. Krishnan

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms...

Dynamic Generation of Discrete Random Variates (1993)

Jeffrey Scott Vitter, Jeffrey Scott Vitter, Wen-chun Ni, Wen-chun Ni

We present and analyze an efficient new algorithm for generating a random variate distributed according to a dynamically changing set of weights. The algorithm can generate the random variate and...

Kenneth M. Curewitz, P. Krishnan, Jeffrey Scott Vitter

An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem...

Indexing for Data Models with Constraints and Classes (1993)

Jeffrey Scott Vitter, Paris Kanellakis Sridhar, Paris Kanellakis, Sridhar Ramaswamy, Sridhar Ramaswamy, Darren Vengroff, ...

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational...

Extended Kenneth, Kenneth M. Curewitz, P. Krishnan, Jeffrey Scott Vitter

An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem...

A Complexity Theoretic Approach to Incremental Computation (1993)

Jeffrey S. Vitter, Sairam Jeffrey Scott, S. Sairam, Jeffrey Scott Vitter, Roberto Tamassia, Roberto Tamassia

We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...

Optimal Prediction for Prefetching in the Worst Case (1993)

P. Krishnan, P. Krishnan, Jeffrey Scott Vitter, Jeffrey Scott Vitter

Response time delays caused by I/O is a major problem in many systems and database applications. Prefetching and cache-replacement methods are attracting renewed attention because of their success in...

Dynamic Generation of Discrete Random Variates (1993)

Yossi Matias, Jeffrey Scott Vitter, Wen-chun Ni

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of weights. The base version of each algorithm generates the...

Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding (1993)

Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We give a detailed algorithm for fast text compression. Our algorithm, related to the PPM method, simplifies the modeling phase by eliminating the escape mechanism and speeds up coding by using a...

Kenneth M. Curewitz, P. Krishnan, Jeffrey Scott Vitter

An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem...

An E cient Parallel Algorithm for Shortest Paths in Planar Layered Digraphs (1993)

Sairam Subramanian, Roberto Tamassia, Jeffrey Scott Vitter, Sairam Subramanian, Roberto Tamassia

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the...

Large-scale sorting in uniform memory hierarchies (1993)

Jeffrey Scott Vitter, Mark H. Nodine

We present several efficient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its parallelization P-UMH. We give optimal and nearly-optimal...

Optimal Deterministic Sorting on Parallel Disks (1993)

Mark H. Nodine, Intrinsity Inc, Jeffrey Scott Vitter

We present a load balancing technique that leads to an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks. Our measure of performance is the number of...

A Theory for Memory-Based Learning (1992)

Jeffrey Scott Vitter, Lisa Hellerstein

Abstract. A memory-based learning system is an extended memory management system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and...

Analysis of arithmetic coding for data compression (1992)

Nearly optimal vector quantization via linear programming (1992)

Arithmetic coding provides an effective mechanism for removing redundancy in the encoding of data. We show how arithmetic coding works and describe an efficient implementation that uses table lookup...

Jyh-han Lin, Jeffrey Scott Vitter

We present new vector quantization algorithms based on the theory devel-oped in [LiV]. The new approach is to formulate a vector quantization problem as a 0-1 integer linear program. We first solve...

Error Modeling for Hierarchical Lossless Image Compression (1992)

Jcff'cy Scott Vittcr, Paul G. Howard, Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We present a new method for error modeling applicable to the MLP algorithm for hierarchical lossless image compression. This method, based on a concept called the variability index, provides accurate...

Error Modeling for Hierarchical Lossless Image Compression (1992)

Jcff'cy Scott Vittcr, Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter

We present a new method for error modeling applicable to the MLP algorithm for hierarchical lossless image compression. This method, based on a concept called the variability index, provides accurate...

Algorithms for Parallel Memory II: Hierarchical Multilevel Memories (1992)

Jeffrey Scott Vitter, Jeffrey Scott Vitter

In this paper we introduce parallel versions of two hierarchical memory models and give optimal algorithms in these models for sorting, FFT, and matrix multiplication. In our parallel models, there...

Approximation Algorithms for Geometric Median Problems (1992)

Jyh-Han Lin, Jyh-han Lin, Jeffrey Scott Vitter, Jeffrey Scott Vitter

In this paper we present approximation algorithms for median problems in metric spaces and fixed-dimensional Euclidean space. Our algorithms use a new method for transforming an optimal solution of...

A Theory for Memory-Based Learning (1992)

Jyh-Han Lin, Jyh-han Lin, Jeffrey Scott Vitter, Jeffrey Scott Vitter

A memory-based learning system is an extended memorymanagement system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and retrieving...

Large-Scale Sorting in Uniform Memory Hierarchies (1992)

Jeffrey Scott Vitter, Jeffrey Scott Vitter, Mark H. Nodine, Mark H. Nodine

. We present several efficient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its parallelization P-UMH. We give optimal and nearly-optimal...

Practical Implementations of Arithmetic Coding (1992)

Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

We provide a tutorial on arithmetic coding, showing how it provides nearly optimal data compression and how it can be matched with almost any probabilistic model. We indicate the main disadvantage of...

Analysis of Arithmetic Coding for Data Compression (1992)

Paul G. Howard, Paul G. Howard, Jeffrey Scott Vitter, Jeffrey Scott Vitter

Arithmetic coding, in conjunction with a suitable probabilistic model, can provide nearly optimal data compression. In this article we analyze the effect that the model and the particular...

A Divide-and-Conquer Approach to Shortest Paths in Planar Layered Digraphs (1992)

Jeffrey Scott, S. Sairam, S. Sairam, Roberto Tamassia, Roberto Tamassia, Jeffrey Scott Vitter

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the...

A Theory for Memory-Based Learning (1992)

Jeffrey Scott Vitter, Lisa Hellerstein

Abstract. A memory-based learning system is an extended memory management system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and...

Parallel lossless image compression using Huffman and arithmetic coding (1992)

Analysis of arithmetic coding for data compression (1992)

We show that high-resolution images can be encoded and decoded efficiently in parallel. We present an algorithm based on the hierarchical MLP method, used either with Huffman coding or with a new...

Complexity Results on Learning by Neural Nets (1991)

Arithmetic coding provides an e ective mechanism for removing redundancy in the encoding of data. We show how arithmetic coding works and describe an e cient implementation that uses table lookup as...

Jyh-han Lin, Jeffrey Scott Vitter

We consider the computational complexity of learning by neural nets. We are interested in how hard it is to design appropriate neural net architectures and to train neural nets for general and...

Optimal Prefetching via Data Compression (1991)

Jeffrey Scott Vitter, Jeffrey Scott Vitter, P. Krishnan, P. Krishnan

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms...

Optimal Cooperative Search in Fractional Cascaded Data Structures (1990)

Roberto Tamassia, Jeffrey Scott Vitter

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total size n. The search consists of locating a key in the catalogs along a path. In this...

Algorithm 673: Dynamic Huffman Coding (1989)

Coping With Uncertainty in Map Learning (1989)

We present a Pascal implementation of the one-pass algorithm for constructing dynamic Huffman codes that is described and analyzed in a companion paper [3]. The program runs in real time; that is,...

Dynamic Huffman Coding (1989)

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a...

Coping With Uncertainty in Map Learning (1989)

. We present a Pascal implementation of the one-pass algorithm for constructing dynamic Huffman codes that is described and analyzed in a companion paper [Vitter, 1987]. The program runs in real time

Kenneth Basye, Kenneth Basye, Thomas Dean, Thomas Dean, Jeffrey Scott Vitter, Jeffrey Scott Vitter

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a...

Coping With Uncertainty in Map Learning (1989)

Coping with uncertainty in map learning (1989)

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a...

Design and analysis of dynamic Huffman codes (1987)

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a...

Random sampling with a reservoir (1985)

Abstract. A new one-pass algorithm for constructing dynamic Huffman codes is introduced and analyzed. We also analyze the one-pass algorithm due to Failer, Gallager, and Knuth. In each algorithm,...