ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Dynamic Clustering Technique for Physical Database Design.

Jo-Mei Chang, King-sun Fu: A Dynamic Clustering Technique for Physical Database Design. SIGMOD Conference 1980: 188-199
@inproceedings{DBLP:conf/sigmod/ChangF80,
  author    = {Jo-Mei Chang and
               King-sun Fu},
  editor    = {Peter P. Chen and
               R. Clay Sprowls},
  title     = {A Dynamic Clustering Technique for Physical Database Design},
  booktitle = {Proceedings of the 1980 ACM SIGMOD International Conference on
               Management of Data, Santa Monica, California, May 14-16, 1980},
  publisher = {ACM Press},
  year      = {1980},
  pages     = {188-199},
  ee        = {http://doi.acm.org/10.1145/582250.582280, db/conf/sigmod/ChangF80.html},
  crossref  = {DBLP:conf/sigmod/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this study, a technique of performing multiple attribute clustering in dynamic databases has been investigated. We have transformed the problem of performing, multiple attribute clustering into a problem of dynamically partitioning the attribute space. The optimal number of partitioning of the attribute space in a dynamic database environment has been analyzed, the partitioning direction is controlled by a discriminator sequence. The design of the discriminator sequence to obtain the optimal partitioning is presented. The selection of the directory attributes has also been discussed. Using the extended K-d tree to direct the partitioning, we have presented the extended K-d tree method. Empirical results have justified the improvement of the performance using the extended K-d tree method, when compared with that using the single attribute clustering or using inverted file method without any clustering index.

Copyright © 1980 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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

Peter P. Chen, R. Clay Sprowls (Eds.): Proceedings of the 1980 ACM SIGMOD International Conference on Management of Data, Santa Monica, California, May 14-16, 1980. ACM Press 1980 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
Contents

Online Edition: ACM Digital Library


References

[Aho79]
Alfred V. Aho, Jeffrey D. Ullman: Optimal Partial-Match Retrieval When Fields Are Independently Specified. ACM Trans. Database Syst. 4(2): 168-179(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ast76]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ben75]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ben79]
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bla76]
...
[Bur76]
Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cha78]
...
[Cha79a]
...
[Cha79b]
Jo-Mei Chang, King-sun Fu: Extended K-d Tree Database Organization: A Dynamic Multiattribute Clustering Method. IEEE Trans. Software Eng. 7(3): 284-290(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lio77]
J. H. Liou, S. Bing Yao: Multi-dimensional clustering for data base organizations. Inf. Syst. 2(4): 187-198(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Riv76]
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rot74]
James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wil80]
...

Referenced by

  1. Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai: Efficient Search of Multi-Dimensional B-Trees. VLDB 1995: 710-719
  2. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  3. Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70
  4. Masaru Kitsuregawa, Lilian Harada, Mikio Takagi: Join Strategies on KB-Tree Indexed Relations. ICDE 1989: 85-93
  5. D. A. Beckley, Martha W. Evens, V. K. Raman: Multikey Retrieval from K-d Trees and Quad-Trees. SIGMOD Conference 1985: 291-301

Copyright © Mon Nov 2 21:10:58 2009 by Michael Ley (ley@uni-trier.de)