Declustering Using Error Correcting Codes.

Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258

@inproceedings{DBLP:conf/pods/FaloutsosM89,
  author    = {Christos Faloutsos and
               Dimitris N. Metaxas},
  title     = {Declustering Using Error Correcting Codes},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {253-258},
  ee        = {http://doi.acm.org/10.1145/73721.73747, db/conf/pods/FaloutsosM89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem examined is to distribute a binary cartesian product file on multiple disks to maximize the parallelism for partial match queries. Cartesian product files appear as a result of some secondary key access methods, such as the multiattribute hashing [1o], the grid file [6] etc.. For the binary case, the problem is reduced into grouping the 2ⁿ binary strings on n bits in m groups of unsimilar strings. The main idea proposed in this paper is to group the strings such that the group forms an Error Correcting Code (ECC). This construction guarantees that the strings of a given group will have large Hamming distances, ie., they will differ in many bit positions. Intuitively, this should result into good declustering. We briefly mention previous heuristics for declustering, we describe how exactly to build a declustering scheme using an ECC, and we prove a theorem that gives a necessary condition for our method to be optimal. Analytical results show that our method is superior to older heuristics, and that it is very close to the theoretical (non-tight) bound.

Copyright © 1989 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. 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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. 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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents

Online Edition: ACM Digital Library

References

[1]: Alfred V. Aho, Jeffrey D. Ullman: Optimal Partial-Match Retrieval When Fields Are Independently Specified. ACM Trans. Database Syst. 4(2): 168-179(1979)
[2]: George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108
[3]: David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237
[4]: ...
[5]: 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)
[6]: 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)
[7]: David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD Conference 1988: 109-116
[8]: ...
[9]: ...
[10]: James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974)
[11]: Craig Stanfill, Brewster Kahle: Parallel Free-Text Search on the Connection Machine System. Commun. ACM 29(12): 1229-1239(1986)
[12]: ...