Electrical Engineering and Computer Science Scholarly Works: Recent submissions
Now showing items 201-220 of 309
-
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 ... -
Analysis of Arithmetic Coding for Data Compression
(Elsevier, 1992)Arithmetic coding, in conjunction with a suitable probabilistic model, can pro- vide nearly optimal data compression. In this article we analyze the e ect that the model and the particular implementation of arithmetic ... -
Competitive Parallel Disk Prefetching and Buffer Management
(Elsevier, 2000)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 applicability to key I/O-bound ... -
Parallel Lossless Image Compression Using Huffman and Arithmetic Coding
(Elsevier, 1996)We show that high-resolution images can be encoded and decoded e ciently in parallel. We present an algorithm based on the hierarchical MLP method, used either with Hu man coding or with a new variant of arithmetic coding ... -
Approximation Algorithms for Geometric Median Problems
(Elsevier, 1992)In this paper we present approximation algorithms for median problems in metric spaces and xed-dimensional Euclidean space. Our algorithms use a new method for transforming an optimal solution of the linear program ...