Khaled A. S. Abdel-Ghaffar
Amr El Abbadi
Abstract
The problem of disk allocation addresses the issue of how to distribute a file on several disks in order to maximize concurrent disk accesses in response to a partial match query. In this paper a coding-theoretic analysis of this problem is presented, and both necessary and sufficient conditions for the existence of strictly optimal allocation methods are provided. Based on a class of optimal codes, known as maximum distance separable codes, strictly optimal allocation methods are constructed. Using the necessary conditions proved, we argue that the standard definition of strict optimality is too strong and cannot be attained, in general. Hence, we reconsider the definition of optimality. Instead of basing it on an abstract definition that may not be attainable, we propose a new definition based on the best possible allocation method. Using coding theory, allocation methods that are optimal according to our proposed criterion are developed.
- 1 ABDEL-GHAFFAR, K. A. S., AND EL ABBADI, A. On the optimality of disk allocation for Cartesian product files. In Proceedings of ACM Symposium on Principles of Database Systems (Nashville, Tenn., Apr. 2-4). ACM, New York, 1990, pp. 258 264. 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 DINES, J., AND KEEUWELL, A.D. Latin Squares and Their Applicatmns. Academic Press, New York, 1974.Google Scholar
- 4 Du, H. C. Disk allocation method for binary cartesian product files. BIT 26, 2 (1986), 138-147. Google ScholarDigital Library
- 5 nu, H. C., AND SOBOLEWSKI, J.S. Disk allocation for Cartesian product files on multiple-disk systems. ACM Trans. Database Syst. 7, i (Mar. 1982), 82-101. Google ScholarDigital Library
- 6 FALOUTSOS, C., AND METAXAS, D. Declustering using error correcting codes. In Proceedings of ACM Symposium on Principles of Database Systems (Philadelphia, Penn., Mar. 29 31). ACM, New York, 1989, pp. 253-258. Google ScholarDigital Library
- 7 FUJIWARA, T., ITO, M., KASAMI, T., KATAOKA, M., AND OKUI, J. Performance analysis of disk allocation method using error-correcting codes. IEEE Trans. Inf. Theory. 37, 2 (Mar, 1991), 379 384.Google Scholar
- 8 KIM, M. H., AND PRAMANIK, S. Optimal file distribution for partial match retrieval. In Proceedings of the ACM-SIGMOD Internattonal Conference on Management of Data (Chicago, Ill., June 1-3). ACM, New York, 1988, pp. 173-182. Google ScholarDigital Library
- 9 MACWILLLtMS, F. J., AND SLOANE~ N. J.A. The Theory of Error-Correcting Codes. North- Holland, Amsterdam, 1977.Google Scholar
- 10 MANERI, C., AND SmVERMAN, R. A vector-space packing problem. J. Algebra 4, 3 (1966), 321 330.Google ScholarCross Ref
- 11 McELmCE, R. J. Flnzte Fields for Computer Sc~entzsts and Engineers. Kluwer, Boston, Mass., 1987.Google Scholar
- 12 NORDSTROM, A. W., AND ROBINSON, J. P. An optimum nonlinear code. Inf. Control 11 (Nov.-Dec. 1967), 613-616.Google ScholarCross Ref
- 13 PATTERSON, D., GIBSON, G., AND KATZ, R. A case for redundant arrays of inexpensive disks. In Proceedings of the ACM-SIGMOD International Conference on Management of Data (Chicago, Ill., June 1-3). ACM, New York, 1988, pp. 109-116. Google ScholarDigital Library
- 14 RIVEST, R.L. Partial-match retrieval algorithms. SIAM J. Comput. 5, 1 (Mar. 1976), 19-50.Google ScholarCross Ref
- 15 ROTHNIE, J. B., AND LOZANO, T. Attribute based file organization in a paged memory environment. Commun. ACM 17, 2 (Feb. 1974), 63-69. Google ScholarDigital Library
- 16 SINGLETON, R. C. Maximum distance q-nary codes. IEEE Trans. Inf. Theory 10, 2 (Apr. 1964), 116-118.Google ScholarDigital Library
- 17 SUNG, Y. Y. Parallel searching for binary Cartesian product files. In Proceedings of the ACM Computer Science Conference (New Orleans, La., Mar. 12-14). ACM, New York, 1985, pp. 163-172. Google ScholarDigital Library
- 18 SUNG, Y.Y. Performance analysis of disk modulo allocation method for Cartesian product files. IEEE Truns. Softw. Eng. 13, 9 (Sept. 1987), 1018-1026. Google ScholarCross Ref
- 19 VERHOEFF, T. An updated table of minimum-distance bounds for binary linear codes. IEEE Trans. Inf. Theory 33, 5 (Sept. 1987), 665-680. Google ScholarDigital Library
Index Terms
- Optimal disk allocation for partial match queries
Recommendations
Optimal Bucket Allocation Design of k-ary MKH Files for Partial Match Retrieval
This paper first shows that the bucket allocation problem of an MKH (Multiple Key Hashing) file for partial match retrieval can be reduced to that of a smaller sized subfile, called the remainder of the file. And it is pointed out that the remainder type ...
Disk allocation for Cartesian product files on multiple-disk systems
Cartesian product files have recently been shown to exhibit attractive properties for partial match queries. This paper considers the file allocation problem for Cartesian product files, which can be stated as follows: Given a k-attribute Cartesian ...
The Optimality of Allocation Methods for Bounded Disagreement Search Queries: The Possible and the Impossible
Data Allocation on multiple I/O devices manifests itself in many computing systems, both centralized and distributed. Data is partitioned on multiple I/O devices and clients issue various types of queries to retrieve relevant information. In this paper, ...
Reviews
Caroline Merriam Eastman
The question of optimal disk allocation for Cartesian product files is considered. Coding theory is used to analyze disk allocation methods and their optimality under certain conditions. The approach is strictly mathematical, and realistic workloads and performance measures are not considered. The conventional assumptions about the uniformity of query and attribute distributions are made. Since these assumptions do not match realistic applications, it is not clear how useful the results would be in practice. This paper is a slightly expanded version of a conference paper [1]. Although this conference paper is included in the references, it is not acknowledged as an earlier publication of essentially the same material. It should have been. The utility of our archival literature is degraded by the all-too-common practices of duplicate publication and failure to acknowledge earlier versions. The paper should interest theoretical researchers in the area of file organization.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments