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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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