自己組織化型P2P検索システム : TellaGate 小島 一浩 独立行政法人 産業技術総合研究所

Presentation on theme: "自己組織化型P2P検索システム : TellaGate 小島 一浩 独立行政法人 産業技術総合研究所"— Presentation transcript:

1 自己組織化型P2P検索システム : TellaGate 小島 一浩 独立行政法人 産業技術総合研究所
背景 Community Netの提案 TellaGateの概要と詳細 今後の課題 デモ

2 Background 既存のP2Pに対する不満点： 1. P2Pの検索機能を強化するには？ 2. ネットワーク負荷を減らしたい．
3. 回線速度を重視しすぎなのでは？ 4. 匿名性を重視しすぎでは？ 　5. そもそもファイル交換以外の使い方はないのか？ 新たな方向性の提案： 1. 回線速度ではなく，コンテンツ，人主体にすべきでは？ 2. 人のつながり，コミュニティー 3. 魅力あるコンテンツ生成能力のある人は，中心へ．

3 Community Net TellaGate Net TellaGate Net TellaGate Net TellaScope
発見！ TellaGate Net TellaGate Net TellaGate Net TellaScope エントリーへアクセス 情報共有 ・ 情報検索 ・ 情報配信 コミュニティーに参加＝ コミュニティーの自己組織化 問題発生！

4 Application Image コミュニティー構造が期待できる対象 分散論文検索 分散掲示板

5 Hint そもそも現実世界では？ AはBと友人である BはCと友人である AはBの友人にCがいることを知っている
BはCの友人にD,E,Fがいることを知っている AはBにCを紹介してもらう. AはCと友人になる 紹介の連鎖　= 「人つて」による検索 連鎖を繰り返し，その関係を維持すると コミュニティーが形成される A B C Cの友人

6 Proposed Method: TellaGate Protocol
1.PeerDigest => Preference 2.Pong Proxy => Exchange PeerDigest 3.QRP with Firework => Query Routing Protocol 4.Backward Learning => Update Query Routing Table 5.Community Self-Organization Algorithm

7 Performance a) Success rate b) Network load

8 TellaGateの概要 2. Query/QueryHit 転送による学習 3. Networkの再構成 1.2. が3.に影響を与える
Downloadによる嗜好状態の変化 2. Query/QueryHit 転送による学習 3. Networkの再構成 1.2. が3.に影響を与える QueryHit D C QueryErr E Bは，自身が持つC,Eの内部モデルを変化 Bは，C,Eの内部モデルをAに伝える B Query A

9 TellaGateの構成 TellaGate Octopus module - P2P Routing TellaPeer
接続要求 TellaGate Octopus module - P2P Routing 登録・経路問合せ 生成・管理 TCP:6699 TellaPeer (QThread) SearchEngine module - Search Engine 検索 HTTP module - HTTP Server - HTTP Client PeerDigest作成 - Indexer ChaSen(形態素解析器) TCP:8080

10 PeerDigest … text ward hash function M-bits array Bloom filter 1
1 … Index Table Digest file guid size path+name 00 : … : ab 1c : … : e3 45000 自律分散.pdf 00 : … : ff c4 : … : 23 32150 TellaGate.ps dd : … : c1 ae : … : 21 1600 Index.html Definition of similarity

11 Octopus : P2P Routing Module
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port A B C D E 2nd Neighbors digest peer guid ip port Message Cache Table message guid src. query words des. 0 …

12 Ex. Ping-Pong and Pong Proxy : step 1
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port ExPing A B C D E 2nd Neighbors digest peer guid ip port Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

13 Ex. Ping-Pong and Pong Proxy : step 2
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d ExPong(D) A B C D E ExPong(C) 2nd Neighbors digest peer guid ip port Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

14 Ex. Ping-Pong and Pong Proxy : step 3
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d ExPong(E) A B C D E 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

15 Query Routing (QRPwF) : step 0
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E Query network = {0, 101, 1858, 25007} 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

16 Query Routing (QRPwF) : step 1
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E Query network = {0, 101, 1858, 25007} 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

17 Query Routing (QRPwF) : step 2
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E QueryErr network = {0, 101, 1858, 25007} 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

18 Query Routing (QRPwF) : step 3
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E network = {0, 101, 1858, 25007} Query 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

19 Query Routing (QRPwF) : step 4
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 00 : … : 01 da : … : 21 d.d.d.d A B C D E network = {0, 101, 1858, 25007} QueryHit 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

20 Query Routing (QRPwF) : step 5
B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 00 : … : 01 da : … : 21 d.d.d.d A B C D E network = {0, 101, 1858, 25007} QueryHit 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

21 Community Self-Organization Algorithm (CSOA)
A’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 64 : … : 00 00 : … : 01 c5 : … : 8e b.b.b.b 6699 A B C D E 2nd Neighbors digest peer guid ip port 3b : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 01 da : … : 21 d.d.d.d Message Cache Table message guid src. query words des. 0 … 61 : … : f9 A network B

22 CSOA : step 1 C B D E A A’s Octopus : 1st Neighbors 2nd Neighbors
org. digest adap. digest peer guid ip port 64 : … : 00 00 : … : 01 c5 : … : 8e b.b.b.b 6699 A B C D E 2nd Neighbors digest peer guid ip port 3b : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 01 da : … : 21 d.d.d.d Handshake Message Cache Table message guid src. query words des. 0 … 61 : … : f9 A network B

23 CSOA : step 2 C B D E A A’s Octopus : 1st Neighbors 2nd Neighbors
org. digest adap. digest peer guid ip port 64 : … : 00 00 : … : 01 c5 : … : 8e b.b.b.b 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E 2nd Neighbors digest peer guid ip port 3b : … : 00 c5 : … : 8e c.c.c.c 6699 ExPing-ExPong Message Cache Table message guid src. query words des. 0 … 61 : … : f9 A network B

24 Small World ? Networkの特徴： 1. Diameter 2. Clustering係数(WS-model)
Handshake

25 Conclusions and Future Works
□htmlへの対応 -> Apache + Namazu + Squid + Browser? □最近は，海外でもSocial Network(出会い系)がWebサービス として流行っている -> Friendstar, Googleの新サービス Friend Rank 　　P2Pで，主観的Rankを計算できないか？ □数理解析 ->簡単なモデルを作成 □ユーザは使えれば，P2Pでなくてもいい．．． ->ユーザにアピールできるのは？