文献

J-GLOBAL ID：201702227588907211   整理番号：17A0003107

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

A Fast Search Method for Run-Based Tries via Pointers

著者 (3件)： 原田崇司 (神奈川大 大学院理学研究科) ,  田中賢 (神奈川大 大学院理学研究科) ,  三河賢治 (新潟大 学術情報基盤機構 情報基盤セ)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 316(MSS2016 38-56)  ページ： 13-18  発行年： 2016年11月17日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： Run-Based Trieは,アルファベット{0,1,*}上の長さwの系列のリストによって定義された函数f:{0,1}^w→Nを計算することができるデータ構造である。パケット分類問題は,ネットワーク機器を通過するパケットと与えられているフィルタリングルールリストの各ルールとを照合して,パケットに合致する優先度の最も高いルールを求める問題である。この問題は,Run-Based Trieを上手く用いることができる問題の一つである。本稿では,Run-Based Trieの全てのノードにポインタを付与することにより,Run-Based Trie探索の時間計算量をルールリストのルール数nに関してO(nw+w²)からO(nw)へと減らす手法を提案する。また,計算機実験により提案手法の有効性を検証する。(著者抄録)

シソーラス用語： 物 ,  *捜索 ,  *高速化 ,  アルファベット ,  データ構造 ,  パケット ,  通信装置 ,  優先度 ,  フィルタリング ,  規則 ,  計算量 ,  節点 ,  ネットワーク機器 ,  *ポインタ ,  時間計算量

分類 (1件)： 人工知能  (JE08000Z)

タイトルに関連する用語 (3件)： ポインタ ,  探索 ,  高速化