お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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

研究会情報
研究会 COMP  
開催期間 2018-03-05 - 2018-03-05 
開催地(和) 大阪府立大学 
開催地(英) Osaka Prefecture Univ. 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2018-03-COMP 
本文の言語 日本語 
タイトル(和) 実ネットワークに対する性質検査のための全域分割アルゴリズムの実装と超有限性の検証 
サブタイトル(和)  
タイトル(英) Implementation of global partition algorithm and verification of hyperfiniteness for property testing of real-world networks 
サブタイトル(英)  
キーワード(1)(和/英) 性質検査 / property testing  
キーワード(2)(和/英) 超有限性 / hyperfiniteness  
キーワード(3)(和/英) 定数時間アルゴリズム / constant-time algorithm  
キーワード(4)(和/英) ビッグデータ / big data  
キーワード(5)(和/英) 実ネットワーク / real-world networks  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 本田 裕太郎 / Yutaro Honda / ホンダ ユウタロウ
第1著者 所属(和/英) 大阪府立大学 (略称: 阪府大)
Osaka Prefecture University (略称: Osaka Pref. Univ.)
第2著者 氏名(和/英/ヨミ) 伊藤 大雄 / Hiro Ito / イトウ ヒロオ
第2著者 所属(和/英) 電気通信大学 (略称: 電通大)
University of Electro-Communications (略称: UEC)
第3著者 氏名(和/英/ヨミ) 笹嶋 宗彦 / Munehiko Sasajima / ササジマ ムネヒコ
第3著者 所属(和/英) 兵庫県立大 (略称: 兵庫県立大)
University of Hyogo (略称: Univ. of Hyogo)
第4著者 氏名(和/英/ヨミ) 宇野 裕之 / Yushi Uno / ウノ ユウシ
第4著者 所属(和/英) 大阪府立大学 (略称: 阪府大)
Osaka Prefecture University (略称: Osaka Pref. Univ.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2018-03-05 15:55:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2017-52 
巻番号(vol) IEICE-117 
号番号(no) no.474 
ページ範囲 pp.43-50 
ページ数 IEICE-8 
発行日 IEICE-COMP-2018-02-26 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会