Paper Info
Title
Design of a balanced multiple-valued file-organization scheme with the least redundancy
Abstract
A new balanced file-organization scheme of order two for multiple-valued records is presented. This scheme is called HUBMFS2 (Hiroshima University Balanced Multiple-valued File-organization Scheme of order two). It is assumed that records are characterized by m attributes having n possible values each, and the query set consists of queries which specify values of two attributes. It is shown that the redundancy of the bucket (the probability of storing a record in the bucket) is minimized if and only if the structure of the bucket is a partite-claw. A necessary and sufficient condition for the existence of an HUBMFS2, which is composed exclusively of partite-claw buckets, is given. A construction algorithm is also given. The proposed HUBMFS2 is superior to existing BMFS2 (Balanced Multiple-valued File-organization Schemes of order two) in that it has the least redundancy among all possible BMFS2's having the same parameters and that it can be constructed for a less restrictive set of parameters.
Year
DOI
Venue
1977
10.1145/320107.320123
ACM Transactions on Database Systems (TODS)
Keywords
DocType
Volume
restrictive set,file-organization scheme,bucket,query set,balanced multiple-valued file-organization schemes,redundancy,possible bmfs2,balanced multiple,new balanced file-organization scheme,file organization schema,information retrieval,balanced multiple-valued file-organization scheme,graph decomposition,hiroshima university,proposed hubmfs2,multiple-valued attributes,file organization,secondary index,n possible value,balanced filing scheme,partite-claw bucket,multipartite graph,inverted file,claw,information storage
Conference
4
Issue
Citations 
PageRank 
4
13
16.25
References 
Authors
9
4
Name
Order
Citations
PageRank
Sumiyasu Yamamoto14542.61
Shinsei Tazawa22638.78
Kazuhiko Ushio35946.38
Hideto Ikeda4126214.09