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