Compressible infinite information systems

Mikhail Ju Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We investigate infinite information systems. Such systems are widely used in pattern recognition, data mining, discrete optimization, computational geometry. An information system is called compressible relatively to a given weight function if for each problem over the information system with sufficiently large weight (i.e., total weight of attributes in the problem description) there exists a decision tree (i) solving this problem and (ii) having the weighted depth less than the problem weight. In the paper all pairs (information system, weight function) such that the information system is compressible relatively to the weight function are described. For each such pair the behavior of Shannon type function is investigated characterizing the growth in the worst case of the minimal weighted depth of decision trees with the growth of problem weight.

Original languageEnglish (US)
Pages (from-to)51-61
Number of pages11
JournalFundamenta Informaticae
Volume55
Issue number1
StatePublished - Apr 2003
Externally publishedYes

Keywords

  • Decision tree
  • Information system
  • Weighted depth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Compressible infinite information systems'. Together they form a unique fingerprint.

Cite this