| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-11-04 13:50 ［ポスター講演］A Study on Random Walks on Graphs Using Sliding Bloom Filters ○Ren Inayoshi・Han Hay Aung・Hiroyuki Ohsaki（Kwansei Gakuin Univ）  IA2025-45 |
|
| 抄録 | （和） | ランダムウォークはグラフ解析における基盤技術であるが、効率的な探索を目 的として訪問履歴を保持する場合、そのメモリ消費が課題となる。特に、ソー シャルネットワークのような巨大なグラフ構造において未探索領域を網羅し、 同じノードへの無駄な再訪を避けるためには履歴管理が不可欠であり、そのメ モリコストが解析の適用範囲を著しく制限している。 このメモリ問題に対し、我々は確率的データ構造であるブルームフィルタを用 いた省メモリな手法「BloomWalk」を提案した。 BloomWalk はメモリ使用量を大幅に削減できる一方、確率的判定に起因する誤 判定、すなわち「偽陽性」が避けられない。 BloomWalk はフィルタ飽和による偽陽性を抑えるためランダムリセット機構を 採用している。しかし、単純なランダムウォークに基づく探索では直近の訪問 履歴が未探索領域への到達に重要だが、 BloomWalk は訪問履歴の時系列的な重要度を無 視してランダムに削除するため、重要な直近履歴まで失われ、非効率を招く。 そこで本稿では、訪問履歴の時系列的な重要度に着目した新たな手法 「Sliding Bloom Filter Walk (SBF-Walk)」を提案する。SBF-Walk は、古い 情報から順次破棄する FIFO (First-In First-Out) 特性を持つ Sliding Bloom Filter を履歴管理に応用する。これにより、重要な直近の履歴を優先 的に保持しつつ、古い履歴を時系列に沿って破棄することでフィルタの飽和を 継続的に抑制する。 |
| （英） | Random walks are a fundamental technique for graph analysis. However, when maintaining visit histories to achieve efficient exploration, memory consumption becomes a critical issue. In particular, for large-scale graph structures such as social networks, history management is essential to cover unexplored areas and avoid redundant revisits, but its memory cost severely limits the scope of analysis. To address this memory issue, we previously proposed “BloomWalk,” a memory-efficient method using the probabilistic data structure Bloom filter. While BloomWalk significantly reduces memory usage, it inevitably suffers from false positives caused by probabilistic decisions. BloomWalk employs a random reset mechanism to suppress false positives resulting from filter saturation. However, in exploration based on simple random walks, the most recent visit history is crucial for reaching unexplored areas. Because BloomWalk randomly deletes entries without considering the temporal importance of visit histories, even important recent information can be lost, potentially reducing efficiency. In this paper, we propose a new method, “Sliding Bloom Filter Walk (SBF-Walk),” which takes the temporal importance of visit histories into account. SBF-Walk applies the FIFO (First-In, First-Out) property of the Sliding Bloom Filter to manage histories. This allows the method to preferentially retain recent histories while sequentially discarding older ones along the time axis, thereby continuously suppressing filter saturation. |
|
| キーワード | （和） | ランダムウォーク / FIFO / ブルームフィルタ / / / / / |
| （英） | Random Walk / FIFO / Bloom Filter / / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 222, IA2025-45, pp. 35-35, 2025年11月. | |
| 資料番号 | IA2025-45 | |
| 発行日 | 2025-10-28 (IA) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IA2025-45 |
|
| 研究会情報 | |
| 研究会 | IA |
| 開催期間 | 2025-11-04 - 2025-11-04 |
| 開催地（和） | Kantary Hills Hotel,Thailand |
| 開催地（英） | Kantary Hills Hotel,Thailand |
| テーマ（和） | IA2025 - Workshop on Internet Architecture and Applications 2025 |
| テーマ（英） | IA2025 - Workshop on Internet Architecture and Applications 2025 |
| 講演論文情報の詳細 | |
| 申込み研究会 | IA |
| 会議コード | 2025-11-IA |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | A Study on Random Walks on Graphs Using Sliding Bloom Filters |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | FIFO / FIFO |
| キーワード(3)（和/英） | ブルームフィルタ / Bloom Filter |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 稲吉 蓮 / Ren Inayoshi / イナヨシ レン |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ) |
| 第2著者 氏名（和/英/ヨミ） | ハン ネー アウン / Han Hay Aung / ハン ネー アウン |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ) |
| 第3著者 氏名（和/英/ヨミ） | 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-11-04 13:50:00 |
| 発表時間 | 45分 |
| 申込先研究会 | IA |
| 資料番号 | IA2025-45 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.222 |
| ページ範囲 | p.35 |
| ページ数 | 1 |
| 発行日 | 2025-10-28 (IA) |
[研究会発表申込システムのトップページに戻る]