Indexing Method for Hierarchical Graphs based on Relation among Interlacing Sequences of Eigenvalues

• Item type: JInfP(1)
• 公開日: 2015-03-15
• タイトル: Indexing Method for Hierarchical Graphs based on Relation among Interlacing Sequences of Eigenvalues
• タイトル / 言語: en
• タイトル: Indexing Method for Hierarchical Graphs based on Relation among Interlacing Sequences of Eigenvalues
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [Regular Papers] index, hierarchical graph, interlace, eigenvalue
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of System Design, Tokyo Metropolitan University
• 著者所属(英): en
• 著者所属(英): Graduate School of System Design, Tokyo Metropolitan University
• 著者名: Kaoru, Katayama; ErnestWekeMaina
• 著者名(英): Kaoru, Katayama; Ernest, WekeMaina
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We propose an indexing method for hierarchical graphs using their eigenvalues in order to detect those that are substructures or superstructures of a hierarchical graph given as a query efficiently. The index construction and the query processing are based on a relation among three interlacing sequences of eigenvalues of hierarchical graphs. We also propose a matrix representation for a hierarchical graph. Hierarchical graphs are decomposed to improve the filtering effect of the index and reduce the computational cost of both the index construction and the query processing. We evaluate the effectiveness of the proposed method by experiments.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose an indexing method for hierarchical graphs using their eigenvalues in order to detect those that are substructures or superstructures of a hierarchical graph given as a query efficiently. The index construction and the query processing are based on a relation among three interlacing sequences of eigenvalues of hierarchical graphs. We also propose a matrix representation for a hierarchical graph. Hierarchical graphs are decomposed to improve the filtering effect of the index and reduce the computational cost of both the index construction and the query processing. We evaluate the effectiveness of the proposed method by experiments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of information processing; 巻 23, 号 2, p. 210-220, 発行日 2015-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会