ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Efficiency of a Binary Comparison Storage Technique
Full text PdfPdf (510 KB)
Source Journal of the ACM (JACM) archive
Volume 21 ,  Issue 3  (July 1974) table of contents
Pages: 376 - 384  
Year of Publication: 1974
ISSN:0004-5411
Authors
E. M. Palmer  Department of Mathematics, Michigan State University, East Lansing, MI
M. A. Rahimi  Computer Science Department, Michigan State University, East Lansing MI
R. W. Robinson  Department of Mathematics, University of Newcastle, Newcastle, NSW 2308, Australia and University of Michigan, Ann Arbor, Michigan
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 14,   Citation Count: 1
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/321832.321836
What is a DOI?

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&pgr;2 for large n.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Thomas N. Hibbard, Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting, Journal of the ACM (JACM), v.9 n.1, p.13-28, Jan. 1962  [doi>10.1145/321105.321108]
2
W. A. Martin , D. N. Ness, Optimizing binary trees grown with a sorting algorithm, Communications of the ACM, v.15 n.2, p.88-93, Feb. 1972  [doi>10.1145/361254.361259]
 
3
WINDLEY, P.F. Trees, forests and rearranging. Computer J. S (1960), 84-88.

CITED BY
Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees


General Terms:
Performance, Theory, Verification

Collaborative Colleagues:
E. M. Palmer: colleagues
M. A. Rahimi: colleagues
R. W. Robinson: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player