Access methods for text
ACM Computing SurveysPublished 1 March 1985
Christos Faloutsos
Citations321
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper compares text retrieval methods intended for office systems with methods from database systems and from information retrieval systems, and examines the most interesting representatives of each class.
Abstract
This paper compares text retrieval methods intended for office systems. The operational requirements of the office environment are discussed, and retrieval methods from database systems and from information retrieval systems are examined. We classify these methods and examine the most interesting representatives of each class. Attempts to speed up retrieval with special purpose hardware are also presented, and issues such as approximate string matching and compression are discussed. A qualitative comparison of the examined methods is presented. The signature file method is discussed in more detail.
Keywords
Computer Science
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Communications of the ACMMultidimensional binary search trees used for associative searching
7,467 Citations1975Jon Bentley
The multidimensional binary search tree (or k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements.
IEEE Transactions on Information TheoryA universal algorithm for sequential data compression
5,467 Citations1977J. Ziv, A. Lempel
The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable- to-block codes designed to match a completely specified source.
Journal of DocumentationA STATISTICAL INTERPRETATION OF TERM SPECIFICITY AND ITS APPLICATION IN RETRIEVAL
4,442 Citations1972Karen Spärck Jones
It is argued that terms should be weighted according to collection frequency, so that matches on less frequent, more specific, terms are of greater value than matches on frequent terms.
Communications of the ACMEfficient string matching
2,946 Citations1975Alfred V. Aho, Margaret J. Corasick
A simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text that has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Sorting networks and their applications
2,400 Citations1968Kenneth E. Batcher
To achieve high throughput rates today's computers perform several operations simultaneously; not only are I/O operations performed concurrently with computing, but also, in multiprocessors, several computing operations are done concurrently.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
ACM Computing SurveysUbiquitous B-Tree
1,826 Citations1979Douglas E. Comer
The major variations of the B-tree are discussed, especially the B+-tree, contrasting the merits and costs of each implementation and illustrating a general purpose access method that uses a B- tree.
IEEE Transactions on ComputersGraph-Theoretical Methods for Detecting and Describing Gestalt Clusters
1,741 Citations1971C. T. Zahn
A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method.
Communications of the ACMA technique for computer detection and correction of spelling errors
1,573 Citations1964Fred J. Damerau
The method described assumes that a word which cannot be found in a dictionary has at most one error, which might be a wrong, missing or extra letter or a single transposition.
Acta InformaticaOrganization and maintenance of large ordered indexes
1,345 Citations1972Raymond Bayer, Edward M. McCreight
The index organization described allows retrieval, insertion, and deletion of keys in time proportional to logkI where I is the size of the index and k is a device dependent natural number such that the performance of the scheme becomes near optimal.
ACM Transactions on Database SystemsThe Grid File
1,149 Citations1984J. Nievergelt, Hans Hinterberger +1 more
This work discusses in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
Communications of the ACMTrie memory
1,081 Citations1960Edward Fredkin
In this paper several paradigms of trie memory are described and compared with other memory paradigm, their advantages and disadvantages are examined in detail, and applications are discussed.
Communications of the ACMExtended Boolean information retrieval
1,038 Citations1983Gerard Salton, Edward A. Fox +1 more
A new, extended Boolean information retrieval system is introduced which is intermediate between the Boolean system of query processing and the vector processing model, and Laboratory tests indicate that the extended system produces better retrieval output than either the Boolean or thevector processing systems.
The K-D-B-tree
885 Citations1981John T. Robinson
A new data structure, the K-D-B-tree, is presented as a solution to the problem of retrieving multikey records via range queries from a large, dynamic index, and it is expected that the multidimensional search effieciency of balanced K-Ds and the I/O efficiency of B-trees should both be approximated in this structure.
IEEE Transactions on Information TheoryNonrandom binary superimposed codes
700 Citations1964William H. Kautz, Robert R. Singleton
In this paper some basic properties of nonrandom codes of this family are presented, and formulas and bounds relating the principal code parameters are derived.
IEEE Transactions on Information TheoryRun-length encodings.
676 Citations1966Solomon W. Golomb
Run-length encodings are used for determining explicit form of Huffman coding when applied to geometric distribution in the context of discrete geometry.
ACM Transactions on Database SystemsExtendible hashing—a fast access method for dynamic files
669 Citations1979Ronald Fagin, Jürg Nievergelt +2 more
This work studies, by analysis and simulation, the performance of extendible hashing and indicates that it provides an attractive alternative to other access methods, such as balanced trees.
ACM Computing SurveysApproximate String Matching
586 Citations1980Patrick A. V. Hall, Geoff R. Dowling
Organization and Maintenance of Large Ordered Indexes
377 Citations2002Raymond Bayer, Edward M. McCreight
File searching using variable length keys
364 Citations1959Rene De La Briandais
Many computer applications require the storage of large amounts of information within the computer's memory where it will be readily available for reference and updating, and therefore care must be taken when using it to avoid excessive operating time.
Communications of the ACMComputer programs for detecting and correcting spelling errors
334 Citations1980James L. Peterson
Peterson investigates the basic structure of several such existing programs and their approaches to solving the problems which arise when this type of program is created.
ACM Transactions on Information SystemsSignature files
325 Citations1984Christos Faloutsos, Stavros Christodoulakis
In this paper two methods for creating signatures are studied analytically, one based on word signatures and the other on superimposed coding, and performance comparisons of the two methods based on these formulas are provided.
Journal of the ACMAn Extension of the String-to-String Correction Problem
318 Citations1975Robert A. Wagner, Roy Lowrance
The set of allowable edit operations is extended to include the operation of interchanging the positions of two adjacent characters under certain restrictions on edit-operation costs, and it is shown that the extended problem can still be solved in time proportional to the product of the lengths of the given strings.
On extending the functions of a relational database system
251 Citations1982Roger Haskin, Raymond A. Lorie
Additions to System R, a prototypical relational system, are introduced to satisfy demands: long fields, for storing non-coded data, and complex objects, which declare the semantic relationships among data items and provide a means for adequately supporting interactive access.
SIAM Journal on ComputingPartial-Match Retrieval Algorithms
245 Citations1976Ronald L. Rivest
A new class of combinatorial designs (called associative block designs) provides better hash functions with a greatly reduced worst-case number of lists examined, yet with optimal average behavior maintained.
IEEE Transactions on Information TheoryOptimal source codes for geometrically distributed integer alphabets (Corresp.)
232 Citations1975Robert G. Gallager, D. van Voorhis
An approach is shown for using the Huffman algorithm indirectly to prove the optimality of a code for an infinite alphabet if an estimate concerning the nature of the code can be made.
IEEE Transactions on Information TheoryOptimal Source Codes for Geometrically Distributed Integer Alphabets
189 Citations1975Robert G. Gallager, David C. Van Voorhis
BIT Numerical MathematicsDynamic hashing
184 Citations1978Per-Åke Larson
A new file organisation called dynamic hashing is presented, based on normal hashing, but the allocated storage space can easily be increased and decreased without reorganising the file, according to the number of records actually stored in the file.
Proceedings of the IEEEPartial-match retrieval via the method of superimposed codes
178 Citations1979Charles S. Roberts
It is shown that organizing the bits of the superimposed code words properly in storage leads to the property that only a small fraction of these bits need be retrieved and processed on each query, which substantially reduces the time required to execute a query.
Information Processing & ManagementAutomatic spelling correction using a trigram similarity measure
177 Citations1983Richard C. Angell, George E. Freund +1 more
Experiments suggest that the nearest neighbour search procedure results in the unique identification of the correct spelling for over 75% of the misspellings if the correct form of the word is in the dictionary, and that this figure may be increased to over 90% if near, rather than nearest, neighbours are acceptable.
Communications of the ACMAttribute based file organization in a paged memory environment
143 Citations1974James B. Rothnie, Tomás Lozano‐Pérez
A method called multiple key hashing is proposed which attempts to minimize the high cost of page accessing and can often improve on a simple inversion technique by a factor of 2 or 3.
Information SystemsA model of cluster searching based on classification
143 Citations1980W. Bruce Croft
A probabilistic model of cluster searching based on query classification is described and it is tested with retrieval experiments which indicate that it can be more effective than heuristic cluster searches and cluster searches based on other models.
Information Storage and RetrievalThe SMART retrieval system; experiments in automatic document processing
136 Citations1973Robert M. Hayes
IEEE Transactions on CommunicationsDevelopment of a Spelling List
134 Citations1982Marie McIlroy
How the spelling checker works, how the words were chosen, how it was used to improve itself, and how the (reduced) list of 30000 English words was squeezed into 26000 16-bit machine words are told.
ACM Transactions on Database SystemsOptimal partial-match retrieval when fields are independently specified
118 Citations1979Alfred V. Aho, Jeffrey D. Ullman
This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields.
ACM Transactions on Database SystemsGeneration and search of clustered files
107 Citations1978Gerard Salton, Anita M.-Y. Wong
An abstract model is introduced to predict the retrieval effectiveness of various search methods in a clustered file environment and to demonstrate the role of various parameters in the cluster search process.
IEEE Transactions on Software EngineeringDesign Considerations for a Message File Server
103 Citations1984Stavros Christodoulakis, Christos Faloutsos
A message server facility for handling large organizational archives of messages in an office information system environment and derive analytic formulas for the optimal choice of the parameters of the message file organization is described.
Communications of the ACMImplementation of the substring test by hashing
98 Citations1971Malcolm C. Harrison
Tradeoff curves are developed to show minimal cost of file usage by grouping various partially combined indices under conditions offile usage with different fractions of retrieval and update.
Communications of the ACMPartial-match retrieval using indexed descriptor files
87 Citations1980John L. Pfaltz, W. J. Berman +1 more
A practical method of partial-match retrieval in very large data files, where a binary code word is associated with each record of the file to form a derived descriptor, which will serve as an index for the block as a whole.
ComputerText Retrieval Computers
73 Citations1979Hollaar
The hardware required for efficient text retrieval differs from that required for retrieval of formatted data, particularly term comparators.
ACM Transactions on Information SystemsMessage files
70 Citations1983Dennis Tsichritzis, Stavros Christodoulakis
Signature files
58 Citations1985Christos Faloutsos
This paper presents three old and one new signature extraction methods and compares the screening capacities and derives exact and approximate formulas for the false drop probabtlrty of each method and dtscuss the new method in more detail.
Journal of the ACMTerm Weighting in Information Retrieval Using the Term Precision Model
57 Citations1982C. Yu, K.C. Lam +1 more
A mathematscal model is used in the present study to relate the term precision weights to the frequency of occurrence of the terms in a given document collecuon and to the number of relevant documents a user wishes to retrieve in response to a query.
ACM Computing SurveysIdentifier Search Mechanisms: A Survey and Generalized Model
53 Citations1974Dennis G. Severance
A number of important techniques which are used to retrieve individually identified data records from a computer memory space are discussed, specifically, the areas of compiler construction and of data base management.
Communications of the ACMLaser optical disk
51 Citations1984Larry Fujitani
Commercially available only recently, the optical disk drive uses a laser beam to burn impressions onto a plastic disk that yields storage densities up to 10 times those of magnetic disks.
American DocumentationMathematical analysis of various superimposed coding methods
49 Citations1960Simon Stiassny
It is shown that for a given field and a given number of words to be punched therein, the chain‐spelling and random‐number superimposed coding methods are equivalent as far as the probability of a match being false is concerned.
Information Processing & ManagementFrequency and impact of spelling errors in bibliographic data bases
45 Citations1977Charles P. Bourne
Estimates were made of the spelling error frequencies of each of these data bases, as well as the frequency of posting to misspelled terms, using a composite sample of over 3600 index terms drawn from 11 different machine-readable bibliographic data bases.
Journal of the ACMRecent Studies in Automatic Text Analysis and Document Retrieval
44 Citations1973Gerard Salton
An attempt is made to identify those automatic procedures which appear most effective as a replacement for the missing language analysis procedures, and it is shown that the fully automatic methodology is superior in effectiveness to the conventional procedures in normal use.
Associative/parallel processors for searching very large textual data bases
44 Citations1977Richard M. Bird, Jui-Che Tu +1 more
The system, called the Associative File Processor (AFP), utilizes a conventional minicomputer for control, off-the-shelf high density disks for storage, a special purpose parallel search module as a text term detector, and query and retrieval software.
BIT Numerical MathematicsPartial-match retrieval for dynamic files
41 Citations1982John W. Lloyd, Kotagiri Ramamohanarao
A general method whereby certain primary key hasing schemes can be extended to partial-match retrieval schemes that can handle arbitrarily dynamic files and can be optimized with respect to the number of page faults required to answer a query is proposed.
Warwick Research Archive Portal (University of Warwick)Spiral Storage: Incrementally Augmentable Hash Addressed Storage
37 Citations1979G. N.N. Martin
A simple mapping function that minimises the impact of reorganisation of data items stored in the data space using a function that maps all possible values of the key attribute onto the integers 0 to k-1.
ACM Transactions on Database SystemsOperational characteristics of a harware-based pattern matcher
34 Citations1983Roger Haskin, Lee A. Hollaar
The design and operation of a new class of hardware-based pattern matchers, such as would be used in a backended database processor in a full-text or other retrieval system, is presented, based on a unique implementation technique for finite state automata consisting of partitioning the state table among a number of simple digital machines.
Communications of the ACMAn information-theoretic approach to text searching in direct access systems
33 Citations1974Ian J. Barton, Susan E. Creasey +2 more
Using direct access computer files of bibliographic information, an attempt is made to overcome one of the problems often associated with information retrieval, namely, the maintenance and use of large dictionaries.
Information SystemsA data base management system for document retrieval applications
33 Citations1981Ian A. Macleod
The capabilities of the Mistral/11 document retrieval system, which is based on the relational data model and designed for general document retrieval applications, are outlined.
ComputerAutomatic Information Retrieval
31 Citations1980Salton
Advances such as specialized parallel hardware and new algorithms for text searching will improve the effectiveness of information retrieval systems.
Journal of the American Society for Information ScienceFIRST: Flexible Information Retrieval System for Text
30 Citations1979Robert T. Dattola
An on‐line document retrieval system is described which combines a data base management system with automatic processing of natural language queries and abstracts, providing direct access to documents with specified bibliographic or descriptor items.
An associative/parallel processor for partial match retrieval using superimposed codes
28 Citations1980Sudhir R. Ahuja, Charles S. Roberts
The implementation has shown that a performance gain of two orders of magnitude over conventional software implementations is obtained by using the special hardware, making the method of superimposed codes extremely attractive for data base system requiring partial match retrieval.
BIT Numerical MathematicsOptimal partial-match retrieval
25 Citations1980John W. Lloyd
This paper studies the design of a system to handle partial-match queries from a file and presents an efficient algorithm for solving this optimization problem.
IEEE Transactions on ComputersA Hardware Hashing Scheme in the Design of a Multiterm String Comparator
24 Citations1982Burkowski
This paper discusses the hardware design of a term detection unit which may be used in the scanning of text emanating from a serial source such as disk or bubble memory and incorporates "off-the-shelf" currently available chips.
IEEE Transactions on ComputersAn Inverted File Processor for Information Retrieval
23 Citations1977Stellhorn
Using this equipment, a complicated sample search involving 70 terms and over 67 000 document references can be performed from 13 to 60 times faster than with a conventional machine.
The Computer JournalAn algorithm for information structuring and retrieval
22 Citations1971C. J. van Rijsbergen
ACM SIGMIS Database the DATABASE for Advances in Information SystemsA method for speeding up text retrieval
21 Citations1984Per-Åke Larson
A simple method for speeding up the term detection phase of retrieval from a full-text document database is presented that makes use of a surrogate database, in which a document is represented as a sequence of hash signatures.
Elements of the randomized combinatorial file structure
18 Citations1971Richard A. Gustafson
A storage and retrieval system utilizing the combinatorial file structure is developed and the new file organization is shown to have marked value with respect to minimum storage overhead and high retrieval speed.
ACM Transactions on Database SystemsSpecialized merge processor networks for combining sorted lists
17 Citations1978Lee A. Hollaar
In inverted file database systems, index lists consisting of pointers to items within the database are combined to form a list of items which potentially satisfy a user's query, and the programming and operation of these processors and networks is discussed.
An information retrieval system based on superimposed coding
16 Citations1969John R. Files, Harry D. Huskey
The cost of storing information in machine-accessible form has declined markedly in the last decade, and promises are such that one can look forward to having complete libraries available in such form.
Journal of the ACMAnalysis of Effectiveness of Retrieval in Clustered Files
15 Citations1977C. Yu, Wo-Shun Luk
A probabihstlc model which allows the ratio of the number of desired records m one cluster to that of another is presented and the results provide guidelines for the rejection of a cluster under appropriate situations.
Journal of DocumentationA THEORY FOR PRACTICAL EDUCATION IN LIBRARIANSHIP
14 Citations1972Ronald Staveley
IBM Systems JournalNational Westminster Bank mass storage archiving
13 Citations1978C. M. Gravina
An application, in which a large bank in the United Kingdom uses the IBM 3850 Mass Storage System for storing and retrieving customer account statements, is described.
Information Processing & ManagementQuery processing in a retrospective document retrieval system that uses word fragments as language elements
12 Citations1976Ernst J. Schuegraf, H. S. Heaps
The structure of a retrospective information retrieval system that uses equifrequent word or text fragments is described, and its advantages over word oriented systems are mentioned briefly.
Journal of DocumentationSOME PROBABILITY PROBLEMS CONCERNING THE MARKING OF CODES INTO THE SUPERIMPOSITION FIELD
12 Citations1956György Orosz, L. Takács
International ACM SIGIR Conference on Research and Development in Information RetrievalFramework for the development of an experimental mixed-mode message system
12 Citations1984Stavros Christodoulakis
A framework for the development of a mixed-mode message system for an office environment that may be composed of attributes, text, images, and voice is described.
Journal of the American Society for Information ScienceOn deriving design equations for information retrieval systems
11 Citations1970William S. Cooper
The question of how design equations, when and if they become available, will be the keystones of retrieval system theory, are derived is investigated in three case studies corresponding to three different types of retrieval systems.
Formal models for string similarity
10 Citations1983John H. Johnson
The theory of rational relations provides a formal model for describing errors in a natural way and algorithms suggested by this theory are efficient and therefore can be used in practical applications.
…