NDLI: Biased dictionaries with fast insert/deletes

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

Clustering to minimize the sum of cluster diameters

Approximating min-sum k-clustering in metric spaces

Local search heuristic for k-median and facility location problems

Profit-earning facility location

One-dimensional quantum walks

Quantum walks on graphs

Quantum algorithms for solvable groups

Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Minimax parametric optimization problems and multi-dimensional parametric searching

Algorithms for minimizing weighted flow time

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Stackelberg scheduling strategies

Quantum computers that can be simulated classically in polynomial time

Interaction in quantum communication and the complexity of set disjointness

A new protocol and lower bounds for quantum coin flipping

Loss-less condensers, unbalanced expanders, and extractors

Conditions on input vectors for consensus solvability in asynchronous distributed systems

Spatial gossip and resource location protocols

(1 + εΒ)-spanner constructions for general graphs

Approximate distance oracles

Extractor codes

Excellent codes from modular curves

Sparse polynomial approximation in finite fields

Randomness efficient identity testing of multivariate polynomials

Fully-dynamic min-cut

Computing crossing numbers in quadratic time

Euler paths in series parallel graphs

Decidability of string graphs

Learning mixtures of arbitrary gaussians

Learning DNF in time

Sampling algorithms: lower bounds and applications

Testing metric properties

Testing of matrix properties

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

One line and ε

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

Lower bounds for intersection searching and fractional cascading in higher dimension

Sharp threshold and scaling window for the integer partitioning problem

A sharp threshold in proof complexity

Regular resolution lower bounds for the weak pigeonhole principle

The complexity of analytic tableaux

Applications of approximation algorithms to cooperative games

Approximation algorithms for constrained for constrained node weighted steiner tree problems

A constant factor approximation for the single sink edge installation problems

Provisioning a virtual private network: a network design problem for multicommodity flow

Explicit lower bound of 4.5n - o(n) for boolena circuits

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

A read-once branching program lower bound of $Ω(2^{n/4})$ for integer multiplication using universal hashing

On the cell probe complexity of membership and perfect hashing

On the integrality ratio of semidefinite relaxations of MAX CUT

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

Non-approximability results for optimization problems on bounded degree instances

Colouring graphs when the number of colours is nearly the maximum degree

Data-streams and histograms

Optimal static range reporting in one dimension

Biased dictionaries with fast insert/deletes

Anti-persistence: history independent data structures

Dynamic TCP acknowledgement and other stories about e/(e-1)

The price of selfish routing

Buffer overflow management in QoS switches

Almost optimal permutation routing on hypercubes

Online server allocation in a server farm via benefit task systems

Private approximation of NP-hard functions

Concurrent and resettable zero-knowledge in poly-loalgorithm rounds

Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds

The round complexity of verifiable secret sharing and secure multicast

Communication preserving protocols for secure function evaluation

Some perspectives on computational complexity

A sieve algorithm for the shortest lattice vector problem

Fast computation of low rank matrix approximations

Spectral analysis of data

Optimal outlier removal in high-dimensional

Estimating true evolutionary distances between genomes

On optimal slicing of parallel programs

When is the evaluation of conjunctive queries tractable?

The complexity of maximal constraint languages

Quantitative solution of omega-regular games380872

Distribution functions of probabilistic automata

Compatible sequences and a slow Winkler percolation

Edge isoperimetry and rapid mixing on matroids and geometric Markov chains

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Computing with continuous-time Liapunov systems

Complex tilings

Running time and program size for self-assembled squares

Algorithms, games, and the internet

Automata, circuits and hybrids: facets of continuous time

Biased dictionaries with fast insert/deletes

Content Provider	ACM Digital Library
Author	Sharp, Jonathan Sinha, Rakesh Sahinalp, S. Cenk Ergun, Funda
Abstract	A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O(logn) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality.In many applications, however, the source of nonuniformity in access probabilities is locality of reference: examples include memory, cache, disk and buffer management and emerging applications in internetwork traffic management. In such applications, the access probability of any given key is not i.i.d., but decreases with idle time since the last access to the key.It is possible to adjust the weighted dictionaries to achieve optimal search time even under time dependent distributions; however insert/delete times will be suboptimal at O(logn). In this paper, we present a lazy updating scheme which can be applied to weighted dictionaries to improve their amortized insert/delete performance when access probabilities decrease with time; optimality of search time is preserved. More speci%cally, let r(k) be the number of distinct keys accessed since the last access to key k- that is r(k) is the move-to-front rank of k. Let rmax(k) be the maximum rank of k during its lifetime. Then our lazy update scheme enables the abovementioned data structures to perform search in O(log r(k)) time and insert/delete in O(log rmax(k)) time. We illustrate our lazy update scheme in the context of a new Biased Skip List data structure and show that our bounds are optimal.
Starting Page	483
Ending Page	491
Page Count	9
File Format	PDF
ISBN	1581133499
DOI	10.1145/380752.380843
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-07-06
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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