Composite Bit-Sliced Signature File: An Efficient Access Method for Set-valued Object Retrieval

Hiroyuki Kitagawa (Institute of Information Sciences and Electronics, University of Tsukuba),
Kohei Fukushima (College of Information Sciences, University of Tsukuba),

PS file (8 pages, 370,051 bytes)


Abstract

Advanced database systems have to support complex object structures. Efficient processing of set-valued object retrieval (simply, set retrieval) based on the set containment conditions is important for such systems. In our previous work, we have shown the potential capability of Bit-Sliced Signature File (BSSF) in handling ``has-subset'' and ``is-subset'' queries. When parameter values are properly tuned, BSSF attains more efficient query processing. However, ``has-subset'' and ``is-subset'' queries present somewhat conflicting requirements for desirable parameter values. Therefore, it is not an easy task to tune the BSSF organization to both ``has-subset'' and ``is-subset'' queries. In this paper, we present a new signature file organization named Composite Bit-Sliced Signature File (C-BSSF) to alleviate the problem, and analyze its basic properties. According to the analysis result, proper C-BSSF outperforms BSSF in environments where both ``has-subset'' and ``is-subset'' queries are probable.

[BACK]Go to the Publication List