ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Hamming Filters: A Dynamic Signature File Organization for Parallel Stores.

Pavel Zezula, Paolo Ciaccia, Paolo Tiberio: Hamming Filters: A Dynamic Signature File Organization for Parallel Stores. VLDB 1993: 314-327
@inproceedings{DBLP:conf/vldb/ZezulaCT93,
  author    = {Pavel Zezula and
               Paolo Ciaccia and
               Paolo Tiberio},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Hamming Filters: A Dynamic Signature File Organization for Parallel
               Stores},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {314-327},
  ee        = {db/conf/vldb/ZezulaCT93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Partitioning, in general, has become the basic strategy for organizing data files to avoid an exhaustive search when executing queries. However, hardware limitations that constrain the performance of query executionmainly become a problem for partial-match queries, where the size of the resultcan equal the size of the data file. In such situations, a proper application of parallelism can bring the required breakthrough in performance. Hamming Filter is a parallel, partitioned organization of signature files that are stored in fixed size buckets with a guaranteed load and is based on the idea of linear code decomposition. It can efficiently manage dynamic data files by means of a partitioned structure that always grows and shrinks linearly and is appropriate to multidimensionalpartitioning and searching. This paper proves that the organization yields no expected execution skew for partial-match queries, provided the data is not skewed and the degree of parallelism is a power of two.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Disk Allocation for Partial Match Queries. ACM Trans. Database Syst. 18(1): 132-156(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Paolo Ciaccia, Pavel Zezula: Estimating Accesses in Partitioned Signature File Organizations. ACM Trans. Inf. Syst. 11(2): 133-142(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Christos Faloutsos, Stavros Christodoulakis: Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies. VLDB 1985: 165-170 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Christos Faloutsos, Stavros Christodoulakis: Description and Performance Analysis of Signature File Methods for Office Filing. ACM Trans. Inf. Syst. 5(3): 237-257(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
...
[8]
Fabio Grandi, Paolo Tiberio, Pavel Zezula: Frame-Sliced Partitioned Parallel Signature Files. SIGIR 1992: 286-297 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Kien A. Hua, Chiang Lee: Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning. VLDB 1991: 525-535 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Dik Lun Lee: A Word-Parallel, Bit-Serial Signature Processor for Superimposed Coding. ICDE 1986: 352-359 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Dik Lun Lee, Chun-Wu Roger Leng: Partitioned Signature Files: Design Issues and Performance Evaluation. ACM Trans. Inf. Syst. 7(2): 158-180(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Chun-Wu Roger Leng, Dik Lun Lee: Optimal Weight Assignment for Signature Generation. ACM Trans. Database Syst. 17(2): 346-373(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Jianzhong Li, Jaideep Srivastava, Doron Rotem: CMD: A Multidimensional Declustering Method for Parallel Data Systems. VLDB 1992: 3-14 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
...
[19]
Fausto Rabitti, Pavel Zezula: A Dynamic Signature Technique for Multimedia Databases. SIGIR 1990: 193-210 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...
[21]
Craig Stanfill, Brewster Kahle: Parallel Free-Text Search on the Connection Machine System. Commun. ACM 29(12): 1229-1239(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Paolo Tiberio, Pavel Zezula: Selecting Signature Files for Specific Applications. Inf. Process. Manage. 29(4): 487-498(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Pavel Zezula, Fausto Rabitti, Paolo Tiberio: Dynamic Partitioning of Signature Files. ACM Trans. Inf. Syst. 9(4): 336-369(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
...

Copyright © Tue Mar 16 02:22:03 2010 by Michael Ley (ley@uni-trier.de)