NDLI: Performance guarantees for B-trees with different-sized atomic keys

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

Datalog redux: experience and conjecture

Expressive languages for path queries over graph-structured data

The ACM PODS Alberto O. Mendelzon test-of-time-award 2010

From information to knowledge: harvesting entities and relationships from web sources

Optimal sampling from distributed streams

Optimizing linear counting queries under differential privacy

Information complexity: a tutorial

On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases

Foundations of schema mapping management

Characterizing schema mappings via data examples

Cache-oblivious hashing

Transducing Markov sequences

An optimal algorithm for the distinct elements problem

Incremental query evaluation in a ring of databases

Universally optimal privacy mechanisms for minimax agents

Capturing missing tuples and missing values

Certain answers for XML queries

Schema design for XML repositories: complexity and tractability

Understanding queries in a search database system

Performance guarantees for B-trees with different-sized atomic keys

Positive higher-order queries

Understanding cardinality estimation using entropy maximization

Fast Manhattan sketches in data streams

Towards an axiomatization of statistical privacy and utility

Computing query probability with incidence algebras

Simplifying XML schema: single-type approximations of regular tree languages

A learning algorithm for top-down XML transformations

When data dependencies over SQL tables meet the logics of paradox and S-3

Semantic query optimization in the presence of types

On probabilistic fixpoint and Markov chain query languages

The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability

Performance guarantees for B-trees with different-sized atomic keys

Content Provider	ACM Digital Library
Author	Hu, Haodong Bender, Michael A. Kuszmaul, Bradley C.
Abstract	Most B-tree papers assume that all N keys have the same size K, that F = B/K keys fit in a disk block, and therefore that the search cost is $O(log_{f}+1$ N) block transfers. When keys have variable size, however, B-tree operations have no nontrivial performance guarantees. This paper provides B-tree-like performance guarantees on dictionaries that contain keys of different sizes in a model in which keys must be stored and compared as opaque objects. The resulting atomic-key dictionaries exhibit performance bounds in terms of the average key size and match the bounds when all keys are the same size. Atomic key dictionaries can be built with minimal modification to the B-tree structure, simply by choosing the pivot keys properly. This paper describes both static and dynamic atomic-key dictionaries. In the static case, if there are N keys with average size K, the search cost is O(⌈K/B⌉ $log_{1+⌈K/B⌉}$ N) expected transfers. The paper proves that it is not possible to transform these expected bounds into worst-case bounds. The cost to build the tree is O(NK) operations and O(NK/B) transfers if all keys are presented in sorted order. If not, the cost is the sorting cost. For the dynamic dictionaries, the amortized cost to insert a key κ of arbitrary length at an arbitrary rank is dominated by the cost to search for κ. Specifically the amortized cost to insert a key κ of arbitrary length and random rank is O(⌈K/B⌉ $log_{1+⌈K/B⌉}$ N + \|κ\| /B) transfers. A dynamic-programming algorithm is shown for constructing a search tree with minimal expected cost.
Starting Page	305
Ending Page	316
Page Count	12
File Format	PDF
ISBN	9781450300339
DOI	10.1145/1807085.1807125
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Atomic keys Dynamic programming B-tree with different-sized keys
Content Type	Text
Resource Type	Article

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

B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic Keys

A New Algorithm for the Construction of Optimal B-Trees (1994)

Performance guarantees for b-trees. (2010).

Adaptive Genetic Programming for dynamic classification problems

Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees

Nordic Journal of Computing 1(1994), 389–401. A NEW ALGORITHM FOR THE CONSTRUCTION OF OPTIMAL B-TREES

Main-memory index structures with fixed-size partial keys

Optimal Tree Structures for Group Key Management with Batch Updates

PerfEnforce Overview: A Dynamic Scaling Engine for Analytics with Performance Guarantees

Performance guarantees for B-trees with different-sized atomic keys

Similar Documents

B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic Keys

A New Algorithm for the Construction of Optimal B-Trees (1994)

Performance guarantees for b-trees. (2010).

Adaptive Genetic Programming for dynamic classification problems

Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees

Nordic Journal of Computing 1(1994), 389–401. A NEW ALGORITHM FOR THE CONSTRUCTION OF OPTIMAL B-TREES

Main-memory index structures with fixed-size partial keys

Optimal Tree Structures for Group Key Management with Batch Updates

PerfEnforce Overview: A Dynamic Scaling Engine for Analytics with Performance Guarantees

Performance guarantees for B-trees with different-sized atomic keys