Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique.

Shinya Fushimi, Masaru Kitsuregawa, Masaya Nakayama, Hidehiko Tanaka, Tohru Moto-Oka: Algorithm and Performance Evaluation of Adaptive Multidimensional Clustering Technique. SIGMOD Conference 1985: 308-318

@inproceedings{DBLP:conf/sigmod/FushimiKNTM85,
  author    = {Shinya Fushimi and
               Masaru Kitsuregawa and
               Masaya Nakayama and
               Hidehiko Tanaka and
               Tohru Moto-Oka},
  editor    = {Shamkant B. Navathe},
  title     = {Algorithm and Performance Evaluation of Adaptive Multidimensional
               Clustering Technique},
  booktitle = {Proceedings of the 1985 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 28-31, 1985},
  publisher = {ACM Press},
  year      = {1985},
  pages     = {308-318},
  ee        = {http://doi.acm.org/10.1145/318898.318928, db/conf/sigmod/FushimiKNTM85.html},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

This paper proposes the multidimensional clustering technique called GKD-tree method which is fully adaptive to both of tuple and query distributions. The method is based on the theoretical analysis of the performance of multldimensional clustering. Its algorithm and performance are described. It is shown that GKD tree method can largely reduce the average number of page accesses. For several distributions its behavior is analyzed and the modification to the algorithm is suggested to further improve the performance. GKD tree method was frst developed as the physical database organization of the relational database machine GRACE. The implementation issues of GKD-tree method in the database machine are also discussed.

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

BibTeX

Printed Edition

Shamkant B. Navathe (Ed.): Proceedings of the 1985 ACM SIGMOD International Conference on Management of Data, Austin, Texas, May 28-31, 1985. ACM Press 1985 BibTeX , SIGMOD Record 14(4)
Contents

Online Edition: ACM Digital Library

References

[1]: ...
[2]: Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) BibTeX
[3]: ...
[4]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[5]: Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
[6]: Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
[7]: ...
[8]: 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) BibTeX
[9]: John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[10]: Aris M. Ouksel, Peter Scheuermann: Multidimensional B-Trees: Analysis of Dynamic Behavior. BIT 21(4): 401-418(1981) BibTeX
[11]: Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) BibTeX
[12]: Yuzuru Tanaka: Adaptive Segmentation Schemes for Large Relational Database Machines. IWDM 1983: 293-318 BibTeX
[13]: D. T. Lee, C. K. Wong: Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees. Acta Inf. 9: 23-29(1977) BibTeX
[14]: Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979) BibTeX
[15]: Shinya Fushimi, Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Multidimensional Clustering Techniques for Large Relational Database Machines. FODO 1985: 293-308 BibTeX
[16]: ...
[17]: Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984) BibTeX

Referenced by

Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
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
Clement T. Yu, Tsang Ming Jiang: Adaptive Algorithms for Balanced Multidimensional Clustering. ICDE 1988: 386-393
Shinya Fushimi, Masaru Kitsuregawa, Hidehiko Tanaka: An Overview of The System Software of A Parallel Relational Database Machine GRACE. VLDB 1986: 209-219

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]