Hierarchical File Organization and Its Application to Similar-String Matching.

Tetsuro Ito, Makoto Kizawa: Hierarchical File Organization and Its Application to Similar-String Matching. ACM Trans. Database Syst. 8(3): 410-433(1983)
  author    = {Tetsuro Ito and
               Makoto Kizawa},
  title     = {Hierarchical File Organization and Its Application to Similar-String
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {3},
  year      = {1983},
  pages     = {410-433},
  ee        = {, db/journals/tods/ItoK83.html},
  bibsource = {DBLP,}


The automatic correction of misspelled inputs is discussed from a viewpoint of similar-string matching. First a hierarchical file organization based on a linear ordering of records is presented for retrieving records highly similar to any input query. Then the spelling problem is attacked by constructing a hierarchical file for a set of strings in a dictionary of English words. The spelling correction steps proceed as follows: (1) find one of the best-match strings which are most similar to a query, (2) expand the search area for obtaining the good-match strings, and (3) interrupt the file search as soon as the required string is displayed. Computational experiments verify the performance of the proposed methods for similar-string matching under the UNIX time-sharing system.

Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
Walter A. Burkhard, Robert M. Keller: Some Approaches to Best-Match File Searching. Commun. ACM 16(4): 230-236(1973) BibTeX
Stuart K. Card, Thomas P. Moran, Allen Newell: The Keystroke-Level Model for User Performance Time with Interactice Systems. Commun. ACM 23(7): 396-410(1980) BibTeX
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
Manuel R. DeSousa: Electronic Information Interchange in an Office Environment. IBM Systems Journal 20(1): 4-22(1981) BibTeX
Clarence A. Ellis, Gary J. Nutt: Office Information Systems and Computer Science. ACM Comput. Surv. 12(1): 27-60(1980) BibTeX
Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Softw. 3(3): 209-226(1977) BibTeX
Patrick A. V. Hall, Geoff R. Dowling: Approximate String Matching. ACM Comput. Surv. 12(4): 381-402(1980) BibTeX
Tetsuro Ito, Makoto Kizawa: The Matrix Rearrangement Procedure for Graph-Theoretical Algorithms and Its Application to the Generation of Fundamental Cycles. ACM Trans. Math. Softw. 3(3): 227-231(1977) BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
James L. Peterson: Computer Programs for Detecting and Correcting Spelling Errors. Commun. ACM 23(12): 676-687(1980) BibTeX
Dennis Ritchie, Ken Thompson: The UNIX Time-Sharing System. Commun. ACM 17(7): 365-375(1974) BibTeX
P. J. Robinson, Dave Singer: Another Spelling Correction Program. Commun. ACM 24(5): 296-297(1981) BibTeX
John Salasin: Hierarchical Storage in Information Retrieval. Commun. ACM 16(5): 291-295(1973) BibTeX
Gerard Salton, A. Wong: Generation and Search of Clustered Files. ACM Trans. Database Syst. 3(4): 321-346(1978) BibTeX
Marvin B. Shapiro: The Choice of Reference Points in Best-Match File Searching. Commun. ACM 20(5): 339-343(1977) BibTeX
William E. Wright: Binary Search Trees in Secondary Memory. Acta Inf. 15: 3-17(1981) BibTeX

Referenced by

  1. Jason Tsong-Li Wang, Dennis Shasha: Query Processing for Distance Metrics. VLDB 1990: 602-613
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:52 2008