TCS-TR-A-14-71

Date: Sat Apr 12 18:24:58 2014

Title: A Compact and Fast Index Structure for Families of Sets

Authors: Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, and Kunihiko Sadakane

Contact:

First name: Shuhei
Last name: Denzumi
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: denzumi@ist.hokudai.ac.jp

Abstract. In many real-life problems, we are often faced with manipulating families of sets. Manipulation of large-scale set families is one of the important fundamental techniques for web information retrieval, integration, and mining. For this purpose, a special type of binary decision diagrams (BDDs), called Zero-suppressed BDDs (ZDDs), is used. However, current techniques for storing ZDDs require a huge amount of memory and membership operations are slow. This paper introduces DenseZDD, a compressed index for static ZDDs. Our technique not only indexes set families compactly but also executes fast member membership operations. We also propose a hybrid method of DenseZDD and ordinary ZDDs to allow for dynamic indices.