TCS-TR-A-13-66

Date: Tue Jun 18 21:13:17 2013

Title: Z-Skip-Links for Fast ZDD Traversal in Handling Large-Scale Sparse Datasets (Revised Ed.)

Authors: Shin-ichi Minato

Contact:

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

Abstract. ZDD (Zero-suppressed Binary Decision Diagram) is known as an efficient data structure for representing and manipulating large-scale sets of combinations. In this article, we propose a method of using {\em Z-Skip-Links} to accelerate ZDD traversals for manipulating large-scale sparse datasets. We discuss average case complexity analysis of our method, and present the optimal parameter setting. Our method can be easily implemented into the existing ZDD packages just by adding one link per ZDD node. Experimental results show that we obtained dozens of acceleration ratio for the instances of the large-scale sparse datasets including thousands of items. (This is a revised edition of TCS-TR-A-13-63.)