Adaptive Record Clustering.

Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985)
  author    = {Clement T. Yu and
               Cheing-Mei Suen and
               K. Lam and
               M. K. Siu},
  title     = {Adaptive Record Clustering},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {2},
  year      = {1985},
  pages     = {180-204},
  ee        = {, db/journals/tods/YuSLS85.html},
  bibsource = {DBLP,}


An algorithm for record clustering is presented. It is capable of detecting sudden changes in users' access patterns and then suggesting an appropriate assignment of records to blocks. It is conceptually simple, highly intuitive, does not need to classify queries into types, and avoids collecting individual query statistics. Experimental results indicate that it converges rapidly; its performance is about 50 percent better than that of the total sort method, and about 100 percent better than that of randomly assigning records to blocks.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


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
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
Kapali P. Eswaran: Placement of Records in a File and File Allocation in a Computer. IFIP Congress 1974: 304-307 BibTeX
André Flory, J. Gunther, Jacques Kouloumdjian: Data Base Reorganization by Clustering Methods. Inf. Syst. 3(1): 59-62(1978) BibTeX
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101 BibTeX
Matti Jakobsson: Reducing block accesses in inverted files by partial clustering. Inf. Syst. 5(1): 1-5(1980) BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
J. H. Liou, S. Bing Yao: Multi-dimensional clustering for data base organizations. Inf. Syst. 2(4): 187-198(1977) BibTeX
Ronald L. Rivest: On Self-Organizing Sequential Search Heuristics. Commun. ACM 19(2): 63-67(1976) BibTeX
Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175 BibTeX
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259 BibTeX
Clement T. Yu, Man-Keung Siu, K. Lam, C. H. Chen: Adaptive File Allocation in Star Computer Network. IEEE Trans. Software Eng. 11(9): 959-965(1985) BibTeX

Referenced by

  1. Chye-Lin Chee, Hongjun Lu, Hong Tang, C. V. Ramamoorthy: Adaptive Prefetching and Storage Reorganization In A Log-Structured Storage System. IEEE Trans. Knowl. Data Eng. 10(5): 824-838(1998)
  2. Jong-Hak Lee, Young-Koo Lee, Kyu-Young Whang, Il-Yeol Song: A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations. VLDB 1997: 416-425
  3. Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)
  4. Edward Omiecinski, Liehuey Lee, Peter Scheuermann: Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering. IEEE Trans. Knowl. Data Eng. 6(2): 248-257(1994)
  5. William J. McIver Jr., Roger King: Self-Adaptive, On-Line Reclustering of Complex Object Data. SIGMOD Conference 1994: 407-418
  6. Minyoung Ra, Y.-S. Park: Data Fragmentation and Allocation for PC-Based Distributed Database Design. DASFAA 1993: 90-96
  7. Manolis M. Tsangaris, Jeffrey F. Naughton: On the Performance of Object Clustering Techniques. SIGMOD Conference 1992: 144-153
  8. Edward Omiecinski, Liehuey Lee, Peter Scheuermann: Concurrent File Reorganization for Record Clustering: A Performance Study. ICDE 1992: 265-272
  9. Edward Omiecinski, Peter Scheuermann: A Parallel Algorithm for Record Clustering. ACM Trans. Database Syst. 15(4): 599-624(1990)
  10. Clement T. Yu, Weiyi Meng, S. Park: A Framework for Effective Retrieval. ACM Trans. Database Syst. 14(2): 147-167(1989)
  11. Clement T. Yu, Wei Sun: Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization. IEEE Trans. Knowl. Data Eng. 1(3): 362-375(1989)
  12. George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108
  13. Clement T. Yu, Tsang Ming Jiang: Adaptive Algorithms for Balanced Multidimensional Clustering. ICDE 1988: 386-393
  14. Setrag Khoshafian, Patrick Valduriez, George P. Copeland: Parallel Query Processing for Complex Objects. ICDE 1988: 202-209
  15. Clement T. Yu, Leszek Lilien, Keh-Chang Guh, Marjorie Templeton, David Brill, Arbee L. P. Chen: Adaptive Techniques for Distributed Query Optimization. ICDE 1986: 86-93
  16. Edward Omiecinski: Incremental File Reorganization Schemes. VLDB 1985: 346-357
  17. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:56 2008