Author name cluster

Rakesh D. Barve

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

FOCS Conference 1999 Conference Paper

A Theoretical Framework for Memory-Adaptive Algorithms

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, statically allocated amount of internal memory. However, with the advent of real-time database system and database systems based upon administratively defined goals, algorithms must increasingly be able to adapt in an online manner when the amount of internal memory allocated to them changes dynamically and unpredictably. We present a theoretical and applicable framework for memory-adaptive algorithms (or simply MA algorithms). We define the competitive worst-case notion of what it means for an MA algorithm to be dynamically optimal and prove fundamental lower bounds on the performance of MA algorithms for problems such as sorting, standard matrix multiplication, and several related problems. Our main tool for proving dynamic optimality is the notion of resource consumption, which measures how efficiently an MA algorithm adapts itself to memory fluctuations. We present the first dynamically optimal algorithm for sorting (based upon mergesort), permuting, FFT, permutation networks, buffer trees, (standard) matrix multiplication, and LU decomposition. In each case, dynamic optimality is demonstrated via a potential function argument showing that the algorithm's resource consumption is within a constant factor of optimal.

Details

I&C Journal 1997 Journal Article

On the Complexity of Learning from Drifting Distributions

Rakesh D. Barve
Philip M. Long

We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in total variation distance by at mostO(ε 3/(d log(1/ε))) between trials, then an algorithm can achieve a probability of a mistake at mostεworse than the best function in a class of VC-dimensiond. We prove a corresponding necessary condition ofO(ε 3/d). Finally, in the case that a fixed function is to be learned from noise-free examples, we show that if the distributions on the domain generating the examples change by at mostO(ε 2/(d log(1/ε))), then any consistent algorithm learns to within accuracyε.

Details DOI

FOCS Conference 1995 Conference Paper

Application-Controlled Paging for a Shared Cache (Extended Abstract)

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 implicitly in the form of good decisions by application processes, we are able to break through the H/sub k/ lower bound on competitive ratio proved for classical paging for a k-sized cache in [FKL/sup +/91]. For a size-k cache shared by P application processes that always make good cache replacement decisions, we develop an online application-controlled paging algorithm with and competitive ratio of 2H/sub P-1/+2 Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P+2 competitive ratio achieved by [CFL94a]. We show for this problem that no on-line algorithm A can have a competitive ratio better than H/sub P-1/ even if the application processes aiding A have perfect knowledge of individual request sequences. Our results are with respect to a worst-case interleaving of the individual request sequences of the P applications. We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm is not only fair, but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.

Details