Search

Showing total 4 results
4 results

1. The Choice of Reference Points in Best-Match File Searching.

Author

Shapiro, Marvin

Subjects
ALGORITHMS, COMPUTER simulation, ELECTROMECHANICAL analogies, MATHEMATICAL models, SIMULATION methods & models, ARITHMETIC, MODELS & modelmaking, ENGINEERING models, MECHANICS (Physics)
Abstract

Improvements to the exhaustive search method of best-match file searching have previously been achieved by doing a preprocessing step involving the calculation of distances from a reference point. This paper discusses the proper choice of reference points and extends the previous algorithm to use more than one reference point. It is shown that reference points should be located outside of data clusters. The results of computer simulations are presented which show that large improvements can be achieved by the proper choice and location of multiple reference points. [ABSTRACT FROM AUTHOR]

Published
1977
Full Text
View/download PDF

2. A Straightforward Model for Computer Performance Prediction.

Author

Boyse, John W. and Warn, David R.

Subjects
*COMPUTER simulation, *MATHEMATICAL models, *ELECTROMECHANICAL analogies, *SIMULATION methods & models, *COMPUTER systems, *ELECTRONIC systems
Abstract

Both simulation and analytic models of computer systems can be very useful for predicting the performance of proposed new systems or proposed changes to existing systems. Unfortunately, many potential users of models are reluctant to use them because of the complexity of many such models and the difficulty of relating the model to the real system. This tutorial paper leads the reader through the development and use of an easily understood analytic model. This is then placed in context with a class of similar analytic models. In spite of the simplicity of these models they have proved useful and quite accurate in predicting performance (utilization, throughput, and response) using only the most basic system data as input. These parameters can either be estimates or measurements from a running system. The model equations and assumptions are defined, and a detailed case study is presented as an example of their use. [ABSTRACT FROM AUTHOR]

Published
1975
Full Text
View/download PDF

3. A Fast String Searching Algorithm.

Author

Boyer, Robert S., Moore, J. Strother, Manacher, G., and Graham, S. L.

Subjects
COMPUTER simulation, ELECTROMECHANICAL analogies, MATHEMATICAL models, SIMULATION methods & models, DATABASE searching, ELECTRONIC information resource searching
Abstract

An algorithm is presented that searches for the location, "i," of the first occurrence of a character string, "pat," in another string, "string," During the search operation, the characters of pat are matched starting with the last character of pat. The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first i characters of string are inspected. The number of characters actually Inspected (on the average) decreases as a function of the length of pat. For a random English pattern of length 5, the algorithm will typically inspect i/4 characters of string before finding a match at i. Furthermore, the algorithm has been implemented so that (on the avenge) fewer than i + patlen machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in i + patlen, assuming the availability of array space for tables linear in pollen plus the size of the alphabet. [ABSTRACT FROM AUTHOR]

Published
1977
Full Text
View/download PDF

4. About This Issue. . .

Subjects
*COMPUTER systems, *PROGRAMMING languages, *COMPUTER software, *COMPUTER simulation, *ELECTROMECHANICAL analogies
Abstract

The September 01, 1996 issue of the journal "ACM Computing Surveys" contains four articles that span object-oriented programming, partial evaluation, error detection and hardware performance. Writer Antero Taivalasaari's comprehensive paper examines many forms and uses of inheritance in a readable way. He distinguishes among classification, generalization, aggregation and grouping between sub-classing and sub-typing and between specification and implementation inheritance. Writer Neil Jones identifies partial evaluation with automatic program specialization with automatic program specialization and shows that some forms of specialization yield program speedup while others do not. Writer Joseph Gallian focuses on the use of check digits for error detection. A nice feature of that article is emphasis on applications like supermarket product cods and credit card, library, blood bank and money bank applications. Writers Peter Soderquist and Miriam Leeser examines area and performance tradeoffs for floating-point divide and square root implementations. This study combines the presentation of algorithms and hardware/software tradeoffs with performance simulation results.

Published
1996