Parallel searching for binary Cartesian product files

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel searching for binary Cartesian product files

Full text

Pdf (852 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 1985 ACM thirteenth annual conference on Computer Science table of contents

New Orleans, Louisiana, United States

Pages: 163 - 172

Year of Publication: 1985

ISBN:0-89791-150-4

Author

Yuan Y. Sung

Department of Information Systems and Computer Science, National University of Singapore, Kent Ridge, Singapore 0511

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 8, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/320599.320668 What is a DOI?

ABSTRACT

The problem of distributing buckets in a file among m disks to facilitate parallel searching for a set of queries is analysed in this paper. We are particularly concerned with the file distribution problem for binary Cartesian product files, and partial match queries. A method is proposed and shown to be strict optimal under certain conditions. The performance of the proposed method is compared with those of an “ideal” strict optimal and Du's heuristic allocation method.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Jeffrey D. Ullman, Optimal partial-match retrieval when fields are independently specified, ACM Transactions on Database Systems (TODS), v.4 n.2, p.168-179, June 1979 [doi>10.1145/320071.320074]
	2	W. A. Burkhard, Hashing and trie algorithms for partial match retrieval, ACM Transactions on Database Systems (TODS), v.1 n.2, p.175-187, June 1976 [doi>10.1145/320455.320469]
	3	C. C. Chang , R. C. T. Lee , H. C. Du, Some properties of Cartesian product files, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582276]
	4	H. C. Du , J. S. Sobolewski, Disk allocation for Cartesian product files on multiple-disk systems, ACM Transactions on Database Systems (TODS), v.7 n.1, p.82-101, March 1982 [doi>10.1145/319682.319698]
	5	Du, H.C., "A Heuristic Disk Allocation Method for Binary Cartesian Product Files", C~,nputer Science Dept.~ University of Minnesota, Technical Report 82-14(June 1982).
	6	Liou, J.H. and Yao, S.B., '~4ulti-dimensional Clustering for Data Base organizations", Information Systems, vol. 2, 1977, 187-198.
	7	Rivest, R.L., '~artial-match Retrival Algorithms", SIAM J. Ccmput., vol. 15, no. l(March 1976) 19-50.
	8	James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]
	9	Srinivasan B., '~arallel Searching in Distributed Databases", Computer Networks 4 (1980), 157- 166.

CITED BY 7

	Khaled A. S. Abdel-Ghaffar , Amr El Abbadi, On the optimality of disk allocation for Cartesian product files (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.258-264, April 02-04, 1990, Nashville, Tennessee, United States
	C. Faloutsos , D. Metaxas, Declustering using error correcting codes, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.253-258, March 1989, Philadelphia, Pennsylvania, United States
	Christos Faloutsos , Dimitris Metaxas, Disk Allocation Methods Using Error Correcting Codes, IEEE Transactions on Computers, v.40 n.8, p.907-914, August 1991
	Khaled A. S. Abdel-Ghaffar , Amr El Abbadi, Optimal disk allocation for partial match queries, ACM Transactions on Database Systems (TODS), v.18 n.1, p.132-156, March 1993
	Fabio Grandi , Paolo Tiberio , Pavel Zezula, Frame-sliced partitioned parallel signature files, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.286-287, June 21-24, 1992, Copenhagen, Denmark
	Paolo Ciaccia , Paolo Tiberio , Pavel Zezula, Declustering of key-based partitioned signature files, ACM Transactions on Database Systems (TODS), v.21 n.3, p.295-338, Sept. 1996
	Myoung Ho Kim , Sakti Pramanik, Optimal file distribution for partial match retrieval, ACM SIGMOD Record, v.17 n.3, p.173-182, June 1988