ACM SIGMOD Anthology TODS dblp.uni-trier.de

Declustering of Key-Based Partitioned Signature Files.

Paolo Ciaccia, Paolo Tiberio, Pavel Zezula: Declustering of Key-Based Partitioned Signature Files. ACM Trans. Database Syst. 21(3): 295-338(1996)
@article{DBLP:journals/tods/CiacciaTZ96,
  author    = {Paolo Ciaccia and
               Paolo Tiberio and
               Pavel Zezula},
  title     = {Declustering of Key-Based Partitioned Signature Files},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {3},
  year      = {1996},
  pages     = {295-338},
  ee        = {http://doi.acm.org/10.1145/232753.232755, db/journals/tods/CiacciaTZ96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Access methods based on signature files can largely benefit from possibilities offered by parallel environments. To this end, an effective declustering strategy that would distribute signatures over a set of parallel independent disks has to be combined with a synergic clustering which is employed to avoid searching the whole signature file while executing a query. This article proposes two parallel signature file organizations, Hamming Filter (HF) and Hamming + Filter (H+F), whose common declustering strategy is based on error correcting codes, and where clustering is achieved by organizing signatures into fixed-size buckets, each containing signatures sharing the same key value. HF allocates signatures on disks in a static way and works well if a correct relationship holds between the parameters of the code and the size of the file. H+F is a generalization of HF suitable to manage highly dynamic files. It uses a dynamic declustering, obtained through a sequence of codes, and organizes a smooth migration of signatures between disks so that high performance levels are retained regardless of current file size. Theoretical analysis characterizes the best-case, expected, and worst-case behaviors of these organizations. Analytical results are verified by experiments on prototype systems.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2516 KB]

References

[Abdel-Ghaffar and El Abbadi 1993]
Khaled A. S. Abdel-Ghaffar, Amr El Abbadi: Optimal Disk Allocation for Partial Match Queries. ACM Trans. Database Syst. 18(1): 132-156(1993) BibTeX
[Ahuja and Roberts 1980]
...
[Ciaccia and Zezula 1993]
Paolo Ciaccia, Pavel Zezula: Estimating Accesses in Partitioned Signature File Organizations. ACM Trans. Inf. Syst. 11(2): 133-142(1993) BibTeX
[Deppisch 1986]
Uwe Deppisch: S-Tree: A Dynamic Balanced Signature Index for Office Retrieval. SIGIR 1986: 77-87 BibTeX
[DeWitt and Gray 1992]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX
[Du and Sobolewski 1982]
David Hung-Chang Du, J. S. Sobolewski: Disk Allocation for Cartesian Product Files on Multiple-Disk Systems. ACM Trans. Database Syst. 7(1): 82-101(1982) BibTeX
[Faloutsos 1992]
...
[Faloutsos and Christodoulakis 1987]
Christos Faloutsos, Stavros Christodoulakis: Optimal Signature Extraction and Information Loss. ACM Trans. Database Syst. 12(3): 395-428(1987) BibTeX
[Faloutsos and Christodoulakis 1984]
Christos Faloutsos, Stavros Christodoulakis: Signature Files: An Access Method for Documents and Its Analytical Performance Evaluation. ACM Trans. Inf. Syst. 2(4): 267-288(1984) BibTeX
[Faloutsos and Metaxas 1991]
Christos Faloutsos, Dimitris N. Metaxas: Disk Allocation Methods Using Error Correcting Codes. IEEE Trans. Computers 40(8): 907-914(1991) BibTeX
[Fujiwara et al. 1991]
...
[Grandi et al. 1992]
Fabio Grandi, Paolo Tiberio, Pavel Zezula: Frame-Sliced Partitioned Parallel Signature Files. SIGIR 1992: 286-297 BibTeX
[Lee 1986]
Dik Lun Lee: A Word-Parallel, Bit-Serial Signature Processor for Superimposed Coding. ICDE 1986: 352-359 BibTeX
[Lee and Leng 1990]
Dik Lun Lee, Chun-Wu Leng: A Partitioned Signature File Structure for Multiattribute and Text Retrieval. ICDE 1990: 389-397 BibTeX
[Lee and Leng 1989]
Dik Lun Lee, Chun-Wu Leng: Partitioned Signature Files: Design Issues and Performance Evaluation. ACM Trans. Inf. Syst. 7(2): 158-180(1989) BibTeX
[Lin 1993]
Zheng Lin: Concurrent Frame Signature Files. Distributed and Parallel Databases 1(3): 231-249(1993) BibTeX
[Lin and Faloutsos 1992]
Zheng Lin, Christos Faloutsos: Frame-Sliced Signature Files. IEEE Trans. Knowl. Data Eng. 4(3): 281-289(1992) BibTeX
[MacWilliams and Sloane 1988]
...
[Peterson and Weldon 1972]
...
[Pogue and Willett 1987]
...
[Roberts 1979]
Charles S. Roberts: Partial-Match Via the Method of Superimposed Codes. Proceedings of the IEEE 67(12): 1624-1642(1979) BibTeX
[Stanfill and Kahle 1986]
Craig Stanfill, Brewster Kahle: Parallel Free-Text Search on the Connection Machine System. Commun. ACM 29(12): 1229-1239(1986) BibTeX
[Sung 1985]
...
[Tiberio and Zezula 1993]
Paolo Tiberio, Pavel Zezula: Selecting Signature Files for Specific Applications. Inf. Process. Manage. 29(4): 487-498(1993) BibTeX
[Verhoeff 1987]
...
[Zezula et al. 1993]
Pavel Zezula, Paolo Ciaccia, Paolo Tiberio: Hamming Filters: A Dynamic Signature File Organization for Parallel Stores. VLDB 1993: 314-327 BibTeX
[Zezula et al. 1991]
Pavel Zezula, Fausto Rabitti, Paolo Tiberio: Dynamic Partitioning of Signature Files. ACM Trans. Inf. Syst. 9(4): 336-369(1991) BibTeX

Referenced by

  1. Justin Zobel, Alistair Moffat, Kotagiri Ramamohanarao: Inverted Files Versus Signature Files for Text Indexing. ACM Trans. Database Syst. 23(4): 453-490(1998)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:19 2008