We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K/B) block transfers in the worst case, where K is the size of the query output.

We present cache-oblivious solutions to two important variants of range searching: range reporting and approximate range counting. The main contribution of our paper is a general approach for constructing cache-oblivious data structures that provide relative (1+ε)-approximations for a general class of range counting queries. This class includes three-sided range counting, 3-d dominance counting, and 3-d halfspace range counting. Our technique allows us to obtain data structures that use linear space and answer queries in the optimal query bound of O(logB(N/K)) block transfers in the worst case, where K is the number of points in the query range. Using the same technique, we also obtain the first approximate 3-d halfspace range counting and 3-d dominance counting data structures with a worst-case query time of O(log(N/K)) in internal memory.

Space-filling curves, particularly Hilbert curves, have proven to be a powerful paradigm for maintaining spatial groupings of multi-dimensional data in a variety of application areas including database systems,data structures and distributed information systems. One significant limitation in the standard definition of Hilbert curves is the requirement that the grid size (i.e. the cardinality) in each dimension be the same. In the real world, not all dimensions are of equal size and the work-around of padding all dimensions to the size of the largest dimension wastes memory and disk space, while increasing the time spent manipulating and communicating these "inflated" values. In this paper we define a new compact Hilbert index which, maintains all the advantages of the standard Hilbert curve and permits dimension cardinalities of varying sizes. This index can be used in any application that would have previously relied on Hilbert curves but, in the case of unequal side lengths, provides a more memory efficient representation. This is particularly important in distributed applications (parallel, P2P and grid), in which not only is memory space saved but communication volume reduced

Convex optimization is a branch of mathematics dealing with non-linear optimization problems with additional geometric structure. This area has been the focus of considerable recent research due to the fact that convex optimization problems are scalable and can be efficiently solved by interior-point methods. Over the last ten years or so, convex optimization has found new applications in many areas including control theory, signal processing, communications and networks, circuit design, data analysis and finance.Of key importance in convex optimization is the notion of duality, and in particular that of Fenchel duality. This work explores algorithms for calculating symbolic Fenchel conjugates of a class of real-valued functions defined on Rn, extending earlier work to the non-separable multi-dimensional case. It also explores the potential application of the developed algorithms to automatic inequality proving.

In this paper, we report a novel heuristic for requantizing JPEG images. The resulting images are generally smaller and often have improved perceptual image quality over a "blind" requantization approach, that is, one that does not consider the properties of the quantization matrices. The heuristic is supported by a detailed mathematical treatment which incorporates the well-known Laplacian distribution of the AC discrete cosine transform (DCT) coefficients with an analysis of the error introduced by requantization. We note that the technique is applicable to any image compression method which employs discrete cosine transforms and quantization.

We propose a new method for requantizing JPEG images, based on the well-known Laplacian distribution of the AC discrete cosine transform (DCT) coefficients and on an analysis of the error introduced by requantization. The resulting images have improved perceptual image quality over a “blind” requantization approach, that is, one that does not consider the properties of the quantization matrices.