最小キーおよび最適部分構造スクリーンの近似

15 References

Bibliographic Information

Other Title
  • Approximating Minimum Keys and Optimal Substructure Screens

Search this article

Description

化学構造データベースでは検索の効率化のために部分構造スクリーンが用いられるが、本稿ではスクリーンとして使用される最適な部分構造を選択する問題について考察する。この問題は関係データベース理論における最小キー問題と密接に関連しているが、両者ともにNP困難であるので、多項式時間近似アルゴリズムの観点から議論を行う。本稿では、両者ともに近似度はSET COVER問題と同等(θ(log n))であること、Kolmogorov計算量を応用することにより部分構造スクリーン問題が平均的には定数以内の近似が可能であること、などを示す。
In this paper, we consider the problem of selecting an optimal substructure screen, which is important in database systems for chemistry. This problem is closely related to the minimum cardinality key problem. Since both problems are NP-hard, we consider polynomial time approximation algorithms. We show that the performance ratios of both problems are θ(log n) using reductions from/to the SET COVER problem. On the other hand, using Kolmogorov complexity, we show that the optimal substructure screen problem can be approximated within a factor of 2+ε in the average case.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 47 17-24, 1995-09-21

    Information Processing Society of Japan (IPSJ)

References(15)*help

See more

Details 詳細情報について

  • CRID
    1570854177186453760
  • NII Article ID
    110002812315
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top