ACM SIGMOD Anthology TODS dblp.uni-trier.de

Organization of Clustered Files for Consecutive Retrieval.

Jitender S. Deogun, Vijay V. Raghavan, Thomas K. W. Tsou: Organization of Clustered Files for Consecutive Retrieval. ACM Trans. Database Syst. 9(4): 646-671(1984)
@article{DBLP:journals/tods/DeogunRT84,
  author    = {Jitender S. Deogun and
               Vijay V. Raghavan and
               Thomas K. W. Tsou},
  title     = {Organization of Clustered Files for Consecutive Retrieval},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {4},
  year      = {1984},
  pages     = {646-671},
  ee        = {http://doi.acm.org/10.1145/1994.2208, db/journals/tods/DeogunRT84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper studies the problem of storing single-level and multilevel clustered files. Necessary and sufficient conditions for a single-level clustered file to have the consecutive retrieval property (CRP) are developed. A linear time algorithm to test the CRP for a given clustered file and to identify the proper arrangement of objects, if CRP exists, is presented. For the single-level clustered files that do not have CRP, it is shown that the problem of identifying a storage organization with minimum redundancy is NP-complete.

Consequently, an efficient heuristic algorithm to generate a good storage organization for such files is developed. Furthermore, it is shown that, for certain types of multilevel clustered files, there exists a storage organization such that the objects in each cluster, for all clusters in each level of the clustering, appear in consecutive locations.

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

References

[1]
Kellogg S. Booth, George S. Lueker: Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms. J. Comput. Syst. Sci. 13(3): 335-379(1976) BibTeX
[2]
Kellogg S. Booth, George S. Lueker: Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property. STOC 1975: 255-265 BibTeX
[3]
...
[4]
W. Bruce Croft: A model of cluster searching bases on classification. Inf. Syst. 5(3): 189-195(1980) BibTeX
[5]
...
[6]
...
[7]
...
[8]
Kapali P. Eswaran: Faithful Representation of a Family of Sets By a Set of Intervals. SIAM J. Comput. 4(1): 56-68(1975) BibTeX
[9]
...
[10]
Sakti P. Ghosh: File Organization: The Consecutive Retrieval Property. Commun. ACM 15(9): 802-808(1972) BibTeX
[11]
...
[12]
...
[13]
C. C. Gotlieb, S. Kumar: Semantic Clustering of Index Terms. J. ACM 15(4): 493-513(1968) BibTeX
[14]
Udaiprakash Gupta: Bounds on Storage for Consecutive Retrieval. J. ACM 26(1): 28-36(1979) BibTeX
[15]
...
[16]
...
[17]
...
[18]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[19]
Lawrence T. Kou: Polynomial Complete Consecutive Information Retrieval Problems. SIAM J. Comput. 6(1): 67-75(1977) BibTeX
[20]
...
[21]
...
[22]
Gerard Salton, A. Wong: Generation and Search of Clustered Files. ACM Trans. Database Syst. 3(4): 321-346(1978) BibTeX
[23]
R. Sibson: SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method. Comput. J. 16(1): 30-34(1973) BibTeX
[24]
...
[25]
Katsumi Tanaka, Yahiko Kambayashi, Shuzo Yajima: Organization of quasi-consecutive retrieval files. Inf. Syst. 4(3): 23-33(1979) BibTeX
[26]
...
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:55 2008