| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-09-04 14:10 複数主体によって自律分散的に管理されるグラフのアクセス権を考慮したランダムウォーク解析 ○岸 真唯子・小泉創紀・山下剛志・金子晋丈（慶大）  IN2026-47 |
|
| 抄録 | （和） | 近年，複数主体が管理するグラフを横断してランダムウォーク（RW）解析を行う分散グラフ環境が想定 されている．さらに，ノードとエッジの管理主体が異なり，両者を独立した認可対象として扱う二部グラフ環境が新しいアプリケーションとして想定され始めているため, 本研究ではこの二部グラフを対象とする．この環境では，RWがサーバ境界を遷移するたびに対象ノードまたはエッジへの認可通信が必要となるため，多数のRW を実行すると認可問い合わせが頻発する．そこで認可結果をキャッシュして再利用することが有効であるが，限られた容量では，再利用されやすい認可結果を適切に保持する必要がある．しかし，LRU などの既存方式はRW 特有の構造的なアクセス局所性を考慮せず，さらにノードとエッジでは，到達経路の違いにより再利用性を決める構造的要因が異なることも考慮していない．そのため本研究では，始点からの近さ，キャッシュ滞在中の使用回数，およびノードの次数に基づくスコアをLRU の最終アクセス時刻に組み合わせて退去優先度を決定する認可キャッシュ方式を提案する．また，ノードとエッジを独立したキャッシュで管理し，それぞれの再利用特性に応じて構造情報を使い分ける．実世界グラフを用いた評価の結果，提案手法はLRU と比較してキャッシュヒット率を最大7.1 ％改善し，RW の探索条件に応じて改善効果が変化することを確認した． |
| （英） | Recently, distributed graph environments have been envisioned in which random walk (RW) analysis is performed across graphs managed by multiple parties. In addition, bipartite graph environments, in which nodes and edges are managed by different parties and treated as independently authorized objects, are emerging as a new class of applications; this study targets such bipartite graphs. In this setting, every time an RW crosses a server boundary, an authorization request must be sent for the target node or edge, so running many RWs leads to frequent authorization queries. Caching and reusing authorization results is therefore effective, but under limited capacity the cache must retain the results that are most likely to be reused. However, existing policies such as LRU do not account for the structural access locality specific to RWs, nor for the fact that the structural factors determining reusability differ between nodes and edges because of their different access paths. We therefore propose an authorization cache policy that determines eviction priority by combining LRU's last-access time with a score based on proximity to the start node, the number of uses during the cache residency, and node degree. Furthermore, nodes and edges are managed in separate caches, and structural information is applied according to the reuse characteristics of each. Evaluation on real-world graphs shows that the proposed method improves the cache hit rate by up to 7.1% over LRU, and that the magnitude of the improvement varies with the RW exploration conditions. | |
| キーワード | （和） | ランダムウォーク / アクセス制御 / 認可キャッシュ / 分散グラフ処理 / アクセス局所性 / / / |
| （英） | Random Walk / access control / authorization cache / distributed graph processing / access locality / / / | |
| 文献情報 | 信学技報, vol. 126, no. 165, IN2026-47, pp. 83-88, 2026年9月. | |
| 資料番号 | IN2026-47 | |
| 発行日 | 2026-08-27 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2026-47 |
|
| 研究会情報 | |
| 研究会 | NS IN CS NV |
| 開催期間 | 2026-09-03 - 2026-09-04 |
| 開催地（和） | 東北大学 電気通信研究所 + オンライン開催 |
| 開催地（英） | Tohoku University + Online |
| テーマ（和） | セッション管理(SIP・IMS)，相互接続技術/標準化，次世代・新世代・将来ネットワーク，クラウド/データセンタネットワーク，SDN(OpenFlow等)・NFV，IPv6，機械学習のネットワーク適用，一般 |
| テーマ（英） | Session management (SIP/IMS), Interoperability/Standardization, NGN/NwGN/Future networks, Cloud/Data center networks, SDN (OpenFlow, etc.)/NFV, IPv6, Machine learning, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2026-09-NS-IN-CS-NV |
| 本文の言語 | 日本語 |
| タイトル（和） | 複数主体によって自律分散的に管理されるグラフのアクセス権を考慮したランダムウォーク解析 |
| サブタイトル（和） | |
| タイトル（英） | Authorization Cache for Cross-Graph Random Walk Analysis Considering Access Locality |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | アクセス制御 / access control |
| キーワード(3)（和/英） | 認可キャッシュ / authorization cache |
| キーワード(4)（和/英） | 分散グラフ処理 / distributed graph processing |
| キーワード(5)（和/英） | アクセス局所性 / access locality |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岸 真唯子 / Maiko Kishi / キシ マイコ |
| 第1著者 所属（和/英） | 慶應義塾大学大学院理工学研究科 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 小泉 創紀 / Koizumi Soki / |
| 第2著者 所属（和/英） | 慶應義塾大学大学院 (略称： 慶大) Keio University Faculty of Science and Technology (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / |
| 第3著者 所属（和/英） | 慶應義塾大学デジタルメディア・コンテンツ総合研究センター (略称： 慶大) Keio University Research Institute for Digital Media and Content (略称： Keio Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / |
| 第4著者 所属（和/英） | 慶應義塾大学理工学部 (略称： 慶大) Keio University Faculty of Science and Technology (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-09-04 14:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2026-47 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.165 |
| ページ範囲 | pp.83-88 |
| ページ数 | 6 |
| 発行日 | 2026-08-27 (IN) |
[研究会発表申込システムのトップページに戻る]