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
Randomized binary searching with tree structures
Full text PdfPdf (273 KB)
Source
Communications of the ACM archive
Volume 7 ,  Issue 3  (March 1964) table of contents
Pages: 163 - 165  
Year of Publication: 1964
ISSN:0001-0782
Author
Harry A. Clampett, Jr.  Univ. of Pittsburgh, PA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 25,   Citation Count: 11
Additional Information:

abstract   cited by   index terms  

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/363958.363987
What is a DOI?

ABSTRACT

A more efficient method of using tree structures is proposed, which utilizes both plus and minus branches in the search path. Very significant gains result when the search key includes alphabetic characters.


CITED BY  11
G. Berman , A. W. Collin, A Modified List Technique Allowing Binary Search, Journal of the ACM (JACM), v.21 n.2, p.227-232, April 1974
Julien Clément , Philippe Flajolet , Brigitte Vallée, The analysis of hybrid trie structures, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.531-539, January 25-27, 1998, San Francisco, California, United States
W. A. Walker , C. C. Gotlieb, Hybrid trees: A data structure for lists of keys, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.189-211, January 1972
David E. Siegel, All searches are divided into three parts: string searches using ternary trees, ACM SIGAPL APL Quote Quad, v.29 n.3, p.57-68, March 1999
C. E. Price, Table Lookup Techniques, ACM Computing Surveys (CSUR), v.3 n.2, p.49-64, June 1971
Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974
S. R. Arora , W. T. Dent, Randomized binary search technique, Communications of the ACM, v.12 n.2, p.77-80, Feb. 1969
Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979
Teofilo F. Gonzalez, The on-line d-dimensional dictionary problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.376-385, September 1992, Orlando, Florida, United States
N. Broutin , L. Devroye, An analysis of the height of tries with random weights on the edges, Combinatorics, Probability and Computing, v.17 n.2, p.161-202, March 2008

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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

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

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process


General Terms:
Design, Languages, Management, Performance, Theory


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