Towards Constructing Destination Node Index for Repetition Paths

• Item type: SIG Technical Reports(1)
• 公開日: 2022-09-02
• タイトル: Towards Constructing Destination Node Index for Repetition Paths
• タイトル / 言語: en
• タイトル: Towards Constructing Destination Node Index for Repetition Paths
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Doshisha University, Graduate School of Culture and Information Science
• 著者所属: Nagoya University, Mathematical and Data Science Center
• 著者所属: Doshisha University, Faculty of Culture and Information Science
• 著者所属(英): en
• 著者所属(英): Doshisha University, Graduate School of Culture and Information Science
• 著者所属(英): en
• 著者所属(英): Nagoya University, Mathematical and Data Science Center
• 著者所属(英): en
• 著者所属(英): Doshisha University, Faculty of Culture and Information Science
• 著者名: Kazuma, Kusu; Takahiro, Komamizu; Kenji, Hatano
• 著者名(英): Kazuma, Kusu; Takahiro, Komamizu; Kenji, Hatano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Graph database management systems (GDBMSs) enable users to traverse one edge at a fixed computing cost for vast and complex graph data. However, GDBMSs cannot avoid reaching already-scanned nodes from different starting nodes by repeatedly traversing edges, which we name a repetition path, with a specific relationship type. Therefore, when a GDBMS reaches a high degree node (HDN), the number of graph traversals increases in proportion to the number of its adjacent nodes. Consequently, the cost of traversing repetition paths extremely increases affected by HDNs in conventional GDBMSs. In this paper, we propose a graph index structure to repeatedly traverse edges belonging to a specific relationship type by distinguishing between HDNs and other nodes. Moreover, we also propose a method for compressing our index to take advantage of the characteristics of real-world networks so that a graph index tends to be the easily huge size of index files.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Graph database management systems (GDBMSs) enable users to traverse one edge at a fixed computing cost for vast and complex graph data. However, GDBMSs cannot avoid reaching already-scanned nodes from different starting nodes by repeatedly traversing edges, which we name a repetition path, with a specific relationship type. Therefore, when a GDBMS reaches a high degree node (HDN), the number of graph traversals increases in proportion to the number of its adjacent nodes. Consequently, the cost of traversing repetition paths extremely increases affected by HDNs in conventional GDBMSs. In this paper, we propose a graph index structure to repeatedly traverse edges belonging to a specific relationship type by distinguishing between HDNs and other nodes. Moreover, we also propose a method for compressing our index to take advantage of the characteristics of real-world networks so that a graph index tends to be the easily huge size of index files.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10114171
• 書誌情報: 研究報告情報基礎とアクセス技術（IFAT）; 巻 2022-IFAT-148, 号 15, p. 1-6, 発行日 2022-09-02
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8884
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会