Office of the Provost: Recent submissions
Now showing items 61-80 of 95
-
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 ... -
Using Vapnik-Chervonenkis Dimension to Analyze the Testing Complexity of Program Segments
(Elsevier, 1996)We examine the complexity of testing di erent program constructs. We do this by de ning a measure of testing complexity known as VCP-dimension, which is similar to the Vapnik-Chervonenkis dimension, and applying it to ... -
Learning in Parallel
(Elsevier, 1992)In this paper, we extend Valiant's sequential model of concept learning from examples [Valiant 1984] and introduce models for the e cient learning of concept classes from examples in parallel. We say that a concept class ... -
Error Modeling for Hierarchical Lossless Image Compression
(IEEE, 1992)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 models for pixel ... -
Efficient Flow Computation on Massive Grid Terrain Datasets
(Springer Verlag, 2003)As detailed terrain data becomes available, GIS terrain applications target larger geographic areas at ner resolutions. Processing the massive data involved in such applications presents signi cant challenges to GIS systems ... -
Cylindrical Static and Kinetic Binary Space Partitions
(Elsevier, 2000)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 ... -
External-Memory Algorithms for Processing Line Segments in Geographic Information Systems
(Springer Verlag, 1996-09)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 large-scale applications ... -
Efficient Bulk Operations on Dynamic R-trees
(Springer Verlag, 2002-12)In recent years, there has been an upsurge of interest in spatial databases. A major issue is how to efficiently manipulate massive amounts of spatial data stored on disk in multidimensional spatial indexes (data structures). ... -
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments
(Springer Verlag, 1999-01)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 for $1 per unit time or ... -
CAMEL: Concept Annotated iMagE Libraries
(SPIE--The International Society for Optical Engineering, 2001-01)The problem of content-based image searching has received considerable attention in the last few years. Thousands of images are now available on the internet, andmany important applications require searching of images in ... -
Constrained Querying of Multimedia Databases
(SPIE--The International Society for Optical Engineering, 2001-01)This paper investigates the problem of high-level querying of multimedia data by imposing arbitrary domain-specific constraints among multimedia objects. We argue that the current structured query mode, and the query-by-content ... -
Fast Progressive Lossless Image Compression
(SPIE--The International Society for Optical Engineering, 1994-02)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 MLP s pyramid based pixel ... -
Nearly Tight Bounds on the Encoding Length of the Burrows-Wheeler Transform (Extended Abstract)
(Society for Industrial and Applied Mathematics, 2008-01)In this paper, we present a nearly tight analysis of the encoding length of the Burrows-Wheeler Transform (bwt) that is motivated by the text indexing setting.For a text T of n symbols drawn from an alphabet , our encoding ... -
High-Order Entropy-Compressed Text Indexes
(Society for Industrial and Applied Mathematics Philadelphia, 2003)We present a novel implementation of compressed su~x arrays exhibiting new tradeoffs between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet E, where each symbol is encoded by ... -
Theory and Practice of I/O efficient Algorithms for Multidimensional Batched Searching Problems
(Society for Industrial and Applied Mathematics, 1998)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 we call colorable ... -
I/O-Efficient Algorithms for Contour Line Extraction and Planar Graph Blocking
(Society for Industrial and Applied Mathematics, 1998)For a polyhedral terrain C, the contour at z-coordinate h, denoted Ch, is defined to be the intersection of the plane z = h with C. In this paper, we study the contour-line extraction problem, where we want to preprocess ... -
External-Memory Graph Algorithms
(Society for Industrial and Applied Mathematics, 1995)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 specific problems. Our ...
