講演抄録/キーワード |
講演名 |
2018-03-05 15:55
実ネットワークに対する性質検査のための全域分割アルゴリズムの実装と超有限性の検証 ○本田裕太郎(阪府大)・伊藤大雄(電通大)・笹嶋宗彦(兵庫県立大)・宇野裕之(阪府大) COMP2017-52 |
抄録 |
(和) |
近年の情報技術の発展によりビッグデータが蓄積され, その利活用が必要とされている. それを解析する上では劣線形時間アルゴリズムが求められ, その中でも, 入力データを定数個しか読まずに結果を出力する定数時間アルゴリズムが望まれる. 一方, 近年研究が進んでいるトピックに性質検査がある. その枠組みは, ある種の不正確さを許容することで, 入力データの一部を見るだけでデータ全体の性質を確率的に判定するというものである. グラフに対する性質検査において, その適用可能性を保証する概念に超有限性がある. 超有限性を満たすグラフは性質検査を適用できるグラフ分割を持つ. そこで本研究では, 理論的な成果である性質検査アルゴリズムをネットワーク解析に対して実用することを目指してその実装を試みる. しかしその際に問題となるのが, 実ネットワークが実際に超有限性を有するかどうかである. 本研究の目的は, さまざまな実ネットワークが超有限性を有するかを実験により検証することである. その結果, 平面由来の実ネットワークならば性質検査が実現可能であることを示唆する結果を得られた. |
(英) |
In recent years, the necessity of analyzing big data is increasing to utilize them. In such cases, sublinear-time algorithms are required, and especially, if algorithms can run in constant-time. In theoretical computer science field, a topic called property testing has been actively studied recently. The basic framework of property testing is to decide within some inaccuracy if the input data has a certain property or far from it by only reading some part of the input. Hyperfiniteness is one of the concepts for guaranteeing such locality defined on graphs. This research tries to implement such purely theoretical property testing algorithms for graphs in order to practically analyze real-world networks. However, there is difficulty that if we can actually obtain partitions of networks that satisfy hyperfiniteness. The purpose of this research is to verify if various kinds of networks have that property. As a result, we find that property testing could be realized for networks that are close to planar graphs. |
キーワード |
(和) |
性質検査 / 超有限性 / 定数時間アルゴリズム / ビッグデータ / 実ネットワーク / / / |
(英) |
property testing / hyperfiniteness / constant-time algorithm / big data / real-world networks / / / |
文献情報 |
信学技報, vol. 117, no. 474, COMP2017-52, pp. 43-50, 2018年3月. |
資料番号 |
COMP2017-52 |
発行日 |
2018-02-26 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2017-52 |
|