Efficient External Table Reordering

A novel extension to binary-tree table organization suitable for external storage providing successful searches for nearly full tables requiring less than two accesses is presented. The generalizes the "efficient ordering of hash tables" effort presented in 1979. Both the experimental and...

Full description

Saved in:
Bibliographic Details
Main Author: Burkhard, W.A.
Format: Conference Proceeding
Language:English
Subjects:
Binary trees
Computational modeling
Computer science
Disk drives
Indexing
Laboratories
Organizing
Performance analysis
Probes
Runtime
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A novel extension to binary-tree table organization suitable for external storage providing successful searches for nearly full tables requiring less than two accesses is presented. The generalizes the "efficient ordering of hash tables" effort presented in 1979. Both the experimental and analytical results demonstrate the reductions possible. This method places no restrictions on the the table configuration parameters and requires no additional space per bucket. The insertion runtime is larger slightly than for ordinary external double hashing.
ISSN:1526-7539
2375-0227
DOI:10.1109/MASCOTS.2007.21