Partial-match Retrieval using Multiple-Key Hashing with Multiple File Copies.

Kotagiri Ramamohanarao, John Shepherd, Ron Sacks-Davis: Partial-match Retrieval using Multiple-Key Hashing with Multiple File Copies. DASFAA 1989: 225-232
  author    = {Kotagiri Ramamohanarao and
               John Shepherd and
               Ron Sacks-Davis},
  editor    = {Sukho Lee and
               Hideko S. Kunii and
               Won Kim and
               In Sup Paik and
               Yahiko Kambayashi},
  title     = {Partial-match Retrieval using Multiple-Key Hashing with Multiple
               File Copies},
  booktitle = {International Symposium on Database Systems for Advanced Applications,
               Seoul, Korea, April 10-12, 1989},
  publisher = {Dept. of Computer Science, KAIST, P.O. Box 150, ChongRyang, Seoul,
               131-650, Korea},
  year      = {1989},
  pages     = {225-232},
  ee        = {db/conf/dasfaa/RamamohanaraoSS89.html},
  crossref  = {DBLP:conf/dasfaa/89},
  bibsource = {DBLP,}


The average cost for answering partial-match queries can be dramatically reduced by storing multiple copies of the data, each with a different clustering. We analyse the cost benefits (in terms of disk accesses) of this arrangement and present algorithms for determining a minimal cost file organisation for a given probability distribution of queries. We also show how constraining the range of values for specific attributes affects the usefulness of maintaining multiple copies.

Copyright © 1989 by The Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. Permission to copy without all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the DASFAA copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. To copy otherwise, or to republish, requires a fee and/or special permission from the Organizing Commitee.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 2, EDBT, ICDT, MFDBS, DASFAA" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX


Alfred V. Aho, Jeffrey D. Ullman: Optimal Partial-Match Retrieval When Fields Are Independently Specified. ACM Trans. Database Syst. 4(2): 168-179(1979) BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
John W. Lloyd: Optimal Partial-Match Retrieval. BIT 20(4): 406-413(1980) BibTeX
John W. Lloyd, Kotagiri Ramamohanarao: Partial Match Retrieval for Dynamic Files. BIT 22(2): 150-168(1982) BibTeX
Shlomo Moran: On the Complexity of Designing Optimal Partial-Match Retrieval Systems. ACM Trans. Database Syst. 8(4): 543-551(1983) BibTeX
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
Kotagiri Ramamohanarao, John W. Lloyd: Partial-Match Retrieval Using Hashing and Descriptors. ACM Trans. Database Syst. 8(4): 552-576(1983) BibTeX
Kotagiri Ramamohanarao, Ron Sacks-Davis: Recursive Linear Hashing. ACM Trans. Database Syst. 9(3): 369-391(1984) BibTeX
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX
Charles S. Roberts: Partial-Match Via the Method of Superimposed Codes. Proceedings of the IEEE 67(12): 1624-1642(1979) BibTeX
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) BibTeX
James A. Thom, Kotagiri Ramamohanarao, Lee Naish: A Superjoin Algorithm for Deductive Databases. VLDB 1986: 189-196 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:05:13 2009