Declustering using error correcting codes

Christos Faloutsos; Dimitrios Metaxas

doi:https://doi.org/10.1145/73721.73747

Declustering using error correcting codes

Christos Faloutsos, Dimitrios Metaxas

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

24 Scopus citations

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, the grid file etc. For the binary case, the problem is reduce 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.

Original language	English (US)
Title of host publication	Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst
Publisher	Publ by ACM
Pages	253-258
Number of pages	6
ISBN (Print)	0897913086, 9780897913089
DOIs	https://doi.org/10.1145/73721.73747
State	Published - 1989
Externally published	Yes
Event	Proceedings of the Eight ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - Philadelphia, PA, USA Duration: Mar 29 1989 → Mar 31 1989

Publication series

Name	Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst

Other

Other	Proceedings of the Eight ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
City	Philadelphia, PA, USA
Period	3/29/89 → 3/31/89

ASJC Scopus subject areas

Engineering(all)

Access to Document

https://doi.org/10.1145/73721.73747

Cite this

@inproceedings{d2d059e91c42460f9e73ed80fef0116f,

title = "Declustering using error correcting codes",

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, the grid file etc. For the binary case, the problem is reduce into grouping the 2n 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.",

author = "Christos Faloutsos and Dimitrios Metaxas",

year = "1989",

doi = "https://doi.org/10.1145/73721.73747",

language = "English (US)",

isbn = "0897913086",

series = "Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst",

publisher = "Publ by ACM",

pages = "253--258",

booktitle = "Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst",

note = "Proceedings of the Eight ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems ; Conference date: 29-03-1989 Through 31-03-1989",

}

Faloutsos, C & Metaxas, D 1989, Declustering using error correcting codes. in Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst. Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst, Publ by ACM, pp. 253-258, Proceedings of the Eight ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, PA, USA, 3/29/89. https://doi.org/10.1145/73721.73747

TY - GEN

T1 - Declustering using error correcting codes

AU - Faloutsos, Christos

AU - Metaxas, Dimitrios

PY - 1989

Y1 - 1989

N2 - 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, the grid file etc. For the binary case, the problem is reduce into grouping the 2n 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.

AB - 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, the grid file etc. For the binary case, the problem is reduce into grouping the 2n 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.

UR - http://www.scopus.com/inward/record.url?scp=0024864668&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024864668&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/73721.73747

DO - https://doi.org/10.1145/73721.73747

M3 - Conference contribution

SN - 0897913086

SN - 9780897913089

T3 - Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst

SP - 253

EP - 258

BT - Proc Eighth ACM SIGACT-SIGMOD-SIGART Symp Princ Database Syst

PB - Publ by ACM

T2 - Proceedings of the Eight ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Y2 - 29 March 1989 through 31 March 1989

ER -

Declustering using error correcting codes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this