Declustering of key-based partitioned signature files

• Published in: ACM transactions on database systems 1996-09, Vol.21 (3), p.295-338
• Main Authors: Ciaccia, Paolo, Tiberio, Paolo, Zezula, Pavel
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; Computer science; control theory; systems; Computer systems performance. Reliability; Contextual software domains; Data access methods; Data management systems; Data structures; Data structures design and analysis; Database management system engines; Database query processing; Database query processing and optimization (theory); Database theory; Design and analysis of algorithms; Exact sciences and technology; File systems management; Hashed file organization; Indexed file organization; Information retrieval. Graph; Information storage systems; Information systems; Information systems. Data bases; Memory organisation. Data processing; Operating systems; Record storage alternatives; Record storage systems; Software; Software and its engineering; Software organization and properties; Sorting and searching; Theoretical computing; Theory and algorithms for application domains; Theory of computation
• ISSN: 0362-5915; 1557-4644
• DOI: 10.1145/232753.232755

Access methods based on signature files can largely benefit from possibilities offered by parallel environments. To this end, an effective declustering strategy that would distribute signatures over a set of parallel independent disks has to be combined with a synergic clustering which is employed to avoid searching the whole signature file while executing a query. This article proposes two parallel signature file organizations, Hamming Filter (HF) and Hamming + Filter (H+F), whose common declustering strategy is based on error correcting codes, and where clustering is achieved by organizing signatures into fixed-size buckets, each containing signatures sharing the same key value. HF allocates signatures on disks in a static way and works well if a correct relationship holds between the parameters of the code and the size of the file. H+F is a generalization of HF suitable to manage highly dynamic files. It uses a dynamic declustering, obtained through a sequence of codes, and organizes a smooth migration of signatures between disks so that high performance levels are retained regardless of current file size. Theoretical analysis characterizes the best-case, expected, and worst-case behaviors of these organizations. Analytical results are verified by experiments on prototype systems.