ポインタ付与によるRun-Based Trie探索の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2016-11-17
• タイトル: ポインタ付与によるRun-Based Trie探索の高速化
• タイトル / 言語: en
• タイトル: A Fast Search Method for Run-Based Tries via Pointers
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神奈川大学大学院理学研究科
• 著者所属: 神奈川大学大学院理学研究科
• 著者所属: 新潟大学学術情報基盤機構情報基盤センター
• 著者所属(英): en
• 著者所属(英): Graduate School of Science, Kanagawa University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science, Kanagawa University
• 著者所属(英): en
• 著者所属(英): Center for Academic Information Service, Niigata University
• 著者名: 原田, 崇司; 田中, 賢; 三河, 賢治
• 著者名(英): Takashi, Harada; Ken, Tanaka; Kenji, Mikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Run-Based Trie は，アルファベット {0 ， 1 ， *} 上の長さ W の系列のリストによって定義された函数 f : {0 , 1} w → N を計算することができるデータ構造である．パケット分類問題は，ネットワーク機器を通過するパケットと与えられているフィルタリングルールリストの各ルールとを照合して，パケットに合致する優先度の最も高いルールを求める問題である． この問題は，Run-Based Trie を上手く用いることができる問題の一つである．本稿では，Run-Based Trie の全てのノードにポインタを付与することにより，Run-Based Trie 探索の時間計算量をルールリストのルール数 n に関して O(nw ＋ w2) から O(nw) へと減らす手法を提案する． また，計算機実験により提案手法の有効性を検証する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Run-Based Trie is a data structure that represents a function f : {0,1} w → N defined by a list of strings on an alphabet {0,1, *}, where w is the length of the string. A packet classification problem is to determine the highest priority rule among all the filtering rules matched with an incoming packet in a networking equipment. Run-Based Trie is well applied to this problem. In this paper, we propose a novel method which reduce the time complexity of Run-Based Trie search from O (nw + w2) to O (nw), where n is a number of rules in the list. In this method, all nodes on Run-Based Trie have both left and right pointers. We show the effectiveness of our algorithm through some experiments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-160, 号 3, p. 1-6, 発行日 2016-11-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会