Efficiency of a Binary Comparison Storage Technique

E. M. Palmer; M. A. Rahimi; R. W. Robinson

doi:10.1145/321832.321836

Efficiency of a Binary Comparison Storage Technique

E. M. Palmer, M. A. Rahimi, R. W. Robinson^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of n items. Surprisingly, the variance approaches 7 - 2/3π₂ for large n.

Original language	English (US)
Pages (from-to)	376-384
Number of pages	9
Journal	Journal of the ACM (JACM)
Volume	21
Issue number	3
DOIs	https://doi.org/10.1145/321832.321836
State	Published - Jul 1 1974

Keywords

binary trees
directory search
generating functions
information retrieval
mean
searching
trees
variance

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Access to Document

10.1145/321832.321836

Cite this

@article{66490f7880cd438896f710873ceca0f2,

title = "Efficiency of a Binary Comparison Storage Technique",

abstract = "The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of n items. Surprisingly, the variance approaches 7 - 2/3π2 for large n.",

keywords = "binary trees, directory search, generating functions, information retrieval, mean, searching, trees, variance",

author = "Palmer, {E. M.} and Rahimi, {M. A.} and Robinson, {R. W.}",

year = "1974",

month = jul,

day = "1",

doi = "10.1145/321832.321836",

language = "English (US)",

volume = "21",

pages = "376--384",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Efficiency of a Binary Comparison Storage Technique

AU - Palmer, E. M.

AU - Rahimi, M. A.

AU - Robinson, R. W.

PY - 1974/7/1

Y1 - 1974/7/1

N2 - The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of n items. Surprisingly, the variance approaches 7 - 2/3π2 for large n.

AB - The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of n items. Surprisingly, the variance approaches 7 - 2/3π2 for large n.

KW - binary trees

KW - directory search

KW - generating functions

KW - information retrieval

KW - mean

KW - searching

KW - trees

KW - variance

UR - http://www.scopus.com/inward/record.url?scp=0016081156&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0016081156&partnerID=8YFLogxK

U2 - 10.1145/321832.321836

DO - 10.1145/321832.321836

M3 - Article

AN - SCOPUS:0016081156

SN - 0004-5411

VL - 21

SP - 376

EP - 384

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 3

ER -

Efficiency of a Binary Comparison Storage Technique

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this