Walter A. Burkhard
Abstract
File designs suitable for retrieval from a file of k-field records when queries may be partially specified are examined. Storage redundancy is introduced to obtain improved worst-case and average-case performances. The resulting storage schemes are appropriate for replicated distributed database environments; it is possible to improve the overall average and worst-case behavior for query response as well as provide an environment with very high reliability. Within practical systems it will be possible to improve the query response time performance as well as reliability over comparable systems without replication.
- 1 AHO, A.V., AND CORASICK, M.J. Efficient string matching: An aid to bibliographical search. Comm. ACM 18, 6 (June 1975), 333-340. Google Scholar
Digital Library
- 2 AHO, A.V., AND ULLMAN, J.D. Optimal partial-match retrieval when fields are independently specified. ACM Trans. Database Syst. 4, 2 (June 1979), 168-179. Google ScholarDigital Library
- 3 BOLOUR, A. Optimality properties of multiple key hashing functions. J. ACM 26, 2 (April 1979) pp. 196-210. Google ScholarDigital Library
- 4 BURKHARD, W.A. Partial-match retrieval. BIT 16 {1976), 13-31.Google Scholar
- 5 BURKHARD, W.A. Hashing and trie algorithms for partial-match retrieval. ACM Trans. Database Syst. 1 (1976), 175-187. Google ScholarDigital Library
- 6 BURKHARD, W.A. Associative retrieval trie hash-coding. ACM SIGACT Conf. Record, 1976, pp. 211-219; and J. Comptr. and Syst. Sci. 15 (1977), 280-299. Google ScholarDigital Library
- 7 BURKHARD, W.A. Non-uniform partial-match file designs. Theoret. Comptr. Sci. 5 (1977), 1-23.Google ScholarCross Ref
- 8 BURKHARD, W.A. Partial-match hash coding: Benefits of redundancy. UCSD Comptr. Sci. Tech. Rep. 17, U. of California at San Diego, La Jolla, Calif., 1977, p. 43.Google Scholar
- 9 CHU, W.W. Optimal fde allocation in a multiple computer system. IEEE Trans. on Computers C-18 (1969), 885-889.Google ScholarDigital Library
- 10 COMER, D., AND SETHI, R. NP-completeness of tree structured index minimization.TR #167, The Pennsylvania State University, University Park, Pa., 1975, p. 43.Google Scholar
- 11 GHOSH, S.P. Data Base Organization for Data Management. Academic Press, New York, 1977. Google ScholarDigital Library
- 12 GUSTAFSON, R.A. A randomized combinatorial file structure for storage and retrieval systems. Ph.D. Th., U. of South Carolina, Columbia, S.C., 1969, p. 92.Google Scholar
- 13 HARRISON, M.C. Implementation of the substring test by hashing. Comm. ACM 14, 12 (Dec. 1971), 777-779. Google ScholarDigital Library
- 14 KNUTH, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison- Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 15 KNUTH, D.E., MORRIS, J., AND PRATT, V. Fast pattern matching in strings. SIAM J. Cornptg. 6 (1977), 323-350.Google ScholarCross Ref
- 16 MILLS, W.H. Covering problems. Proc. Fourth Southeastern Conf. on Combinatorics, Graph Theory and Computing, 1973, pp. 23-52.Google Scholar
- 17 RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comptg. 5 {1976), 19-50.Google Scholar
Index Terms
- Partial-match hash coding: benefits of redundancy
Recommendations
Hashing and trie algorithms for partial match retrieval
File designs suitable for retrieval from a file of k-letter words when queries may be only partially specified are examined. A new class of partial match file designs (called PMF designs) based upon hash coding and trie search algorithms which provide ...
An Efficient Multiversion Access Structure
An efficient multiversion access structure for a transaction-time database is presented. Our method requires optimal storage and query times for several important queries and logarithmic update times. Three version operations inserts, updates, and ...
Range queries on uncertain data
Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...
Comments