NDLI: Entropy-based bounds for online algorithms

Please wait, while we are loading the content...

Entropy-based bounds for online algorithms

Content Provider	ACM Digital Library
Author	Upfal, Eli Pandurangan, Gopal
Copyright Year	2009
Abstract	We focus in this work on an aspect of online computation that is not addressed by standard competitive analysis, namely, identifying request sequences for which nontrivial online algorithms are useful versus request sequences for which all algorithms perform equally poorly. The motivations for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. To utilize these features, the operating system needs to identify data streams that can benefit from more resources. Our approach in this work is based on the relation between entropy, compression, and gambling, extensively studied in information theory. It has been shown that in some settings, entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. Our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. We study bounds based on entropy for three classical online problems---list accessing, prefetching, and caching. Our bounds relate the performance of the best online algorithm to the $\textit{entropy},$ a parameter intrinsic to characteristics of the request sequence. This is in contrast to the competitive ratio parameter of competitive analysis, which quantifies the performance of the online algorithm with respect to an optimal offline algorithm. For the prefetching problem, we give explicit upper and lower bounds for the performance of the best prefetching algorithm in terms of the entropy of the request sequence. In contrast, we show that the entropy of the request sequence alone does not fully capture the performance of online list accessing and caching algorithms.
Starting Page	1
Ending Page	19
Page Count	19
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/1186810.1186817
Volume Number	3
Issue Number	1
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-02-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Online algorithms Caching Entropy List accessing Performance bounds Prefetching Stochastic process
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal lower bounds for projective list update algorithms

Online algorithms for prefetching and caching on parallel disks

The performance impact of kernel prefetching on buffer cache replacement algorithms

Online list accessing algorithms and their evidence.

An SPN-Based Integrated Model for Web Prefetching and Caching

A Universal Online Caching Algorithm Based on Pattern Matching

Calculating lower bounds for caching problems

Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling

Space-Constrained Interval Selection

Entropy-based bounds for online algorithms

Similar Documents

Optimal lower bounds for projective list update algorithms

Online algorithms for prefetching and caching on parallel disks

The performance impact of kernel prefetching on buffer cache replacement algorithms

Online list accessing algorithms and their evidence.

An SPN-Based Integrated Model for Web Prefetching and Caching

A Universal Online Caching Algorithm Based on Pattern Matching

Calculating lower bounds for caching problems

Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling

Space-Constrained Interval Selection

Entropy-based bounds for online algorithms