集合間の相違を明確にする要素辞書

• Item type: Trans(1)
• 公開日: 1999-02-15
• タイトル: 集合間の相違を明確にする要素辞書
• タイトル / 言語: en
• タイトル: Element Dictionary to Specify Difference among Sets
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 八代工業高等専門学校情報電子工学科
• 著者所属: 佐賀大学理工学部知能情報システム学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Electronics Engineering, Yatsushiro National College of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science and Engineering, Saga University
• 著者名: 村田, 美友紀; 掛下, 哲郎
• 著者名(英): Miyuki, Murata; Tetsuro, Kakeshita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 集合検索はDBにおける重要なトピックであり キーワードを用いた文献検索や仕様に基づいたソフトウエア検索等の分野に応用できる. 本論文では集合検索を効果的に行うために要素辞書の概念を定義し 要素辞書の構成アルゴリズムを提案する. 要素辞書を用いることで 以下の特徴が得られる. (l)検索対象集合を特定する検索条件が常に構成できる. (2)任意の集合間の相違に関する質問に答えられる. (3)要素辞書を最適化することで索引のサイズを最小化できる. 互いに異なるn個の集合に対して要素辞書のサイズはlog n以上である. 最小の要素辞書構成問題はNP完全になるが 与えられたn個の集合に対してサイズが高々n-1の要素辞書が多項式時間で構成できる. さらに 検索対象集合の追加削除に伴って要素辞書を多項式時間で再構成するアルゴリズムを提案する.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Set retrieval is an important topic in databases and has many application domains such as document retrieval using keywords and software retrieval based on their specification. In this paper, we define the notion of element dictionary to effectively retrieve sets and propose construction algorithms for the dictionary. The following advantages can be obtained by using the element dictionary. (1) A retrieval condition can always be constructed to identify the target set. (2) Difference among sets can always be specified. (3) Index size can be minized by optimizing the dictionary. The size of an element dictionary is at least log n for n distinct sets. Although the construction of the minimum element dictionary is NP complete, a dictionary of at most n-1 elements can be constructed in polynomial time. Furthermore we propose polynomial time algorithms to reconstruct the element dictionary when a target set is added to or deleted from the database.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 40, 号 SIG03(TOD1), p. 60-67, 発行日 1999-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会