Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Organization of clustered files for consecutive retrieval
Deogun J., Raghavan V., Tsou T. ACM Transactions on Database Systems9 (4):646-671,1984.Type:Article
Date Reviewed: Jun 1 1985

Assume that a set of objects is clustered; each object belongs to one or more clusters. The question is under which conditions the objects can be arranged linearly in such a way that each cluster consists of a consecutive section of this arrangement (this is called the consecutive retrieval property). This is already impossible for three objects with each pair forming a cluster.

The paper is mostly concerned with level clusterings defined by the restriction that no cluster be a proper subset of another cluster. An algorithm is developed which checks in linear time (linear in the sum of objects, clusters, and cluster sizes) whether a given set of objects has the consecutive retrieval property; in the positive case, a fitting arrangement is found.

If a set of objects does not have the consecutive retrieval property, one might wish to store some objects at several places such that each cluster is arranged consecutively. Even for level clusterings, the problem of finding the arrangement with minimum redundancy is shown to be NP-complete. An efficient algorithm to generate a reasonable arrangement is developed. Some special results are added for multilevel clusterings.

Reviewer:  F. Gebhardt Review #: CR109098
Bookmark and Share
 
Clustering (H.3.3 ... )
 
 
File Organization (H.3.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Clustering": Date
Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases
Can F. (ed), Ozkarahan E. ACM Transactions on Database Systems 15(3): 483-517, 1990. Type: Article
Dec 1 1992
A parallel algorithm for record clustering
Omiecinski E., Scheuermann P. ACM Transactions on Database Systems 15(3): 599-624, 1990. Type: Article
Nov 1 1992
Clustering analysis for graphs with multiweighted edges: a unified approach to the threshold problem
Roy J. Journal of the American Society for Information Science 38(3): 156-161, 1987. Type: Article
Apr 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy