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 ...

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/smod7592 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

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

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)
[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)
[Ben75]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975)
[Ben79]: Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979)
[Bla76]: ...
[Bur76]: Walter A. Burkhard: Hashing and Trie Algorithms for Partial Match Retrieval. ACM Trans. Database Syst. 1(2): 175-187(1976)
[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)
[Lio77]: J. H. Liou, S. Bing Yao: Multi-dimensional clustering for data base organizations. Inf. Syst. 2(4): 187-198(1977)
[Riv76]: Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976)
[Rot74]: James B. Rothnie Jr., Tomas Lozano: Attribute Based File Organization in a Paged Memory Environment. Commun. ACM 17(2): 63-69(1974)
[Wil80]: ...

Referenced by

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