Lecture Notes in Computer Science, 2006, Volume 3847/2006, 40-58, DOI: 10.1007/11605126_3

VSOP (Valued-Sum-of-Products) Calculator for Knowledge Processing Based on Zero-Suppressed BDDs

Shin-ichi Minato

View Related Documents

Abstract

Recently, Binary Decision Diagrams (BDDs) are widely used for efficiently manipulating large-scale Boolean function data. BDDs are also applied for handling combinatorial item set data. Zero-suppressed BDDs (ZBDDs) are special type of BDDs which are suitable for implicitly handling large-scale combinatorial item set data. In this paper, we present VSOP program developed for calculating combinatorial item set data specified by symbolic expressions based on ZBDD techniques. Our program supports not only combinatorial set operations but also numerical arithmetic operations based on Valued-Sum-Of-Products algebra, such as addition, subtraction, multiplication, division, numerical comparison, etc. We discuss the data structures and algorithms in our program, and show some typical applications. VSOP calculator will be useful for solving many problems in Computer Science. We show one of the promising application to find a hidden data group related each other under the huge amount of web space. Our method will facilitates knowledge federation over the web, and also useful for many other applications in computer science.

Fulltext Preview

Image of the first page of the fulltext document