Office of the Provost: Recent submissions
Now showing items 41-60 of 95
-
Arithmetic Coding for Data Compression
(IEEE, 1994)Arithmetic coding provides an e ective mechanism for remov- ing redundancy in the encoding of data. We show how arithmetic coding works and describe an e cient implementation that uses table lookup as a fast alternative ... -
A Unified Approach for Indexed and Non-Indexed Spatial Joins
(Springer Verlag, 2000)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 ... -
Online Data Structures in External Memory
(Springer Verlag, 1999)The data sets for many of today's computer applications are too large to t within the computer's internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be ... -
Constructing Binary Space Partitions for Orthogonal Rectangles in Practice
(Springer Verlag, 1998)In this paper, we develop a simple technique for constructing a I3inary Space Partition (nSP) for a set of orthogonal rectangles in IR3. OUf algorithm has the novel feature that it tunes its performance to the geometric ... -
Efficient Update of Indexes for Dynamically Changing Web Documents
(Springer Verlag, 2007)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 not immediately searchable, ... -
Dynamic Generation of Discrete Random Variates
(Springer Verlag, 2003)We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in ... -
A Simple and Efficient Parallel Disk Mergesort
(Springer Verlag, 2002)External sorting|the process of sorting a le that is too large to t into the computer's internal memory and must be stored externally on disks|is a fundamental subroutine in database sys- tems [Gra93, IBM90]. Of prime ... -
Compressed Data Structures: Dictionaries and the Data-Aware Measures
(Elsevier, 2007-11-22)We propose measures for compressed data structures, in which space usage is mea- sured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data, where the task is to construct a ... -
External-Memory Computational Geometry
(IEEE, 1993)In this paper we give new techniques for designing e cient algorithms for computational geometry prob- lems that are too large to be solved in internal mem- ory. We use these techniques to develop optimal and practical ... -
Bulk Operations for Space-Partitioning Trees
(IEEE, 2004)The emergence of extensible index structures, e.g., GiST (Generalized Search Tree) [25] and SP-GiST (Space-Partitioning Generalized Search Tree) [3], calls for a set of extensible algorithms to support different operations ... -
Fast Compression with a Static Model in High-Order Entropy
(IEEE, 2004)We report on a simple encoding format called wzip for decompressing block-sorting transforms, such as the Burrows-Wheeler Transform (BWT). Our compressor uses the simple notions of gamma encoding and RLE organized with a ... -
Efficient Cost Measures for Motion Compensation at Low Bit Rates
(IEEE, 1996)We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and video- conferencing applications, where low bit rates are neces- sary, where ... -
Fast and Efficient Lossless Image Compression
(IEEE, 1993)We present a new method for lossless image compression that gives compression comparable to JPEG lossless mode with about ve times the speed. Our method, called FELICS, is based on a novel use of two neighboring pixels ... -
Simple Randomized Mergesorting on Parallel Disks
(Elsevier, 1997)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 ... -
Text Compression Via Alphabet Re-Representation
(Elsevier, 1999)We consider re-representing the alphabet so that a representation of a character re ects its properties as a predictor of future text. This enables us to use an estimator from a restricted class to map contexts to predictions ... -
Complexity Results on Learning by Neural Nets
(Springer Verlag, 1991)We consider the computational complexity of learning by neural nets. We are inter- ested in how hard it is to design appropriate neural net architectures and to train neural nets for general and specialized learning tasks. ... -
A Framework for Index Bulk Loading and Dynamization
(Springer Verlag, 2001)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 wp-trees) for indexing a set of ... -
Lexicographic Bit Allocation for MPEG Video
(Elsevier, 1997)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 bu er and channel constraints imposed by the MPEG Video Bu ering Veri er. ... -
Large-Scale Sorting in Uniform Memory Hierarchies
(Elsevier, 1993)We present several e cient algorithms for sorting on the uniform memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its paral- lelization P-UMH.We give optimal and nearly-optimal algorithms for a wide range ... -
Design and Analysis of Fast Text Compression Based on Quasi-Arithmetic Coding
(Elsevier, 1994)We give a detailed algorithm for fast text compression. Our algorithm, related to the PPM method, simpli es the modeling phase by eliminating the escape mechanism and speeds up coding by using a combination of quasi-arithmetic ...
