[dich]the Minerva Project

The MINERVA∗Project: Database Selection in the Context of P2P Search Dự án MINEVA là dự án đầu tiên dùng công cụ tìm kiếm phân tán trên nền P2P. MINEVA là tần trên cùng của loại mạng Chord và sử dụng 1 crawling mạnh, chỉ mục và công cụ tìm kiếm trên mỗi peer tự trị. 1/ Relate work Các nghiên cứu gần đây trên hệ thống P2P như CAN, Chord Pastry, P2P-NET hay P-Grid dựa vào các form khác nhau của DHT(bảng băm phân tán) và hỗ trợ ánh xạ từ các khóa, như tiêu đề hay tác giả, để định vị trong 1 kiểu phân quyền như phạm vi định tuyến tốt với 1 số lượng peer trong hệ thống. Điển hình 1 key phù hợp để tìm kiếm có thể định tuyến tới đúng peer thích hợp trong hop (bước), và ko có peer cần để chứa hơn thông tin định tuyến. Galanx là công cụ tìm kiếm P2P thực thi bằng việc sử dụng Apache HTTP server và BẻkeleyDB. Nó quản lý các truy vấn người dùng có liên quan tới các nút bằng cách hỏi các chỉ mục của peer lân cận PlanetP là 1 dịch vụ thuê bao xuất bản cho cộng đồng P2P và hệ thống đầu tiên hỗ trợ tìm kiếm vị trí content. PlanetP phân biệt chỉ mục cục bộ và chỉ mục toàn cục để diễn tả tất cả các peer và thông tin chia sẻ của chúng. Chỉ mục toàn cục đc trùng lặp sử dụng 1 thuật toán gossiping(tầm phào). Hệ thống này tuy nhiên bị giới hạn khoảng vài nghìn peer. Tổng quát của công nghệ metasearch đc định rõ bởi [MYL02]. [WMYL01] nói đến kế hoạch cụ thể để xác định khả năng hữu dụng của các công cụ tìm kiếm cục bộ cho truy vấn của người dùng. 2/ Chord - A Scalable P2P Lookup Service (dịch vụ tìm kiếm P2P mở rộng) Hiệu quả của các nút trong 1 kiến trúc P2P là 1 vấn đề chủ yếu cần đc giải quyết từ nhiều phương diện khác nhau. Các hệ thống gần đây như Gnutella dựa vào kiến trúc ko có cấu trúc trong đó 1 peer thông báo cho tất cả các peer đc biết là hàng xóm của nó. Đặc biệt các thông báo này có 1 trường TTL(time to live) đc giảm khi mà thông báo đó đc chuyển tới peer khác.Thông điệp flooding này hay gossiping làm việc đặc biệt tốt trong 1 số trường hợp, ở đây ko có sự bảo đảm cho tất cả các nút có liên quan mà cuối cùng sẽ đạt đc. Thêm đó, thực tế nhiều thông điệp ko cần thiết đc gửi gây trở ngại tới mục tiêu của 1 kiến trúc mở rộng cao. Chord là 1 giao thức tìm kiếm phân tán đánh địa chỉ. Nó cung cấp chức năng của 1 DHT bằng cách hỗ trợ tìm kiếm : đưa ra 1 key, nó ánh xạ key đó vào 1 nút. Mục đích của Chord là dùng kỹ thuật băm phù hợp. Consistent hashing giữ cho cân bằng tải, khi 1 nút nhận 1 số lượng khóa xấp xỉ nhau. Hơn nữa, cân bằng tải làm việc trc 1 dải băm thay đổi động, như khí các nút lỗi hoặc rời khỏi hệ thống hay khi nút mới join vào.

1

Chord ko chỉ bảo đảm cho việc tìm nút có trách nhiệm cho 1 key đã đưa, nhưng có thể làm điều đó với nhiều ảnh hưởngl trong 1 hệ thống vững chắc N nút, mỗi nút chỉ chứa thông tin về nút khác, và giải quyết tất cả tìm kiếm nhiều thông điệp tới các nút khác. Các thuộc tính cung cấp khả năng cho hiệu quả hệ thống mở rộng lớn. Khái niệm đằng sau Chord là : tất cả các nút pi và tất cả khác ki đc ánh xạ vào trong ko gian ID tuần hoàn. Dùng các khóa và số peer nếu hàm băm đc chấp nhận, nhưng ko chỉ ra rõ ràng hàm băm cho các trình bày đơn giản hơnn. Với mỗi khóa ki đc gán cho successor của pi trong ko gian ID ( mõi nút chịu trách nhiệm cho tất cả các key để nhận biết giữa ID predecessor của nó và ID sở hữu của nó. Trong hình trên 10 nút đc phân tán qua ko gian ID, key k54 đc gán cho nút p56 như là successor của nó. Một cách tiếp cận của định vị peer có trách nhiệm cho 1 key đc minh họa, khi mỗi peer biết làm cách nào để tiếp xúc với successor hiện thời của nó trên vòng tròn ID, 1 truy vấn cho k54 khởi tạo bởi peer p8 vượt qua vòng tròn cho đến khi nó bắt gặp 1 cặp nút straddle mong muốn nhận ra; cặp thứ 2 p56 là nút chịu trách nhiệm đến key đó. Tiến trình tìm kiếm giống với tìm kiếm theo đường thẳng trong danh sách và có 1 số hop để tìm nút đích, trong khi chỉ yêu cầu thông tin về các nút khác. Để làm nhanh việc tìm kiếm , Chord chưa thêm thông tin định tuyến : mỗi peer pi chứa 1 bảng định truyến gọi là finger table... Entry thứ m trong bảng của nút pi chứa 1 con trỏ tới nút pi đầu tiên nối tiếp pi bởi ít nhất 2m-1 trên vòng tròn tạo. Trong sơ đồ : đầu tiên mỗi nút chỉ chứa thông tin về 1 số lượng nhỏ các nút khác, và biết nhiều hơn về các nút xa hơn bằng cách hỏi các nút gần nó trên vòng tròn định danh, thứ 2 1 nút finger table ko cần thiết chứa đầy đủ thông tin để xác định trực tiếp nút có trách nhiệm đến 1 khóa ki . Tuy nhiên, khi mà mỗi peer có các entry finger bằng lũy thừa 2 khoảng cách vòng tròn định danh, mỗi nút có thể đẩy 1 truy vấn tại nửa cuối dọc theo khoảng cách giữa nó với nút đích. Thuộc tính này đc minh họa trong hình 2 của nút p8. Số các nút bị tiếp xúc để tìm kiếm nút đích trong 1 hệ thống N nút là Chord thực thi 1 giao thức ổn định với mỗi peer chạy định kỳ trong nền và nó cập nhập bảng finger table và con trỏ successor trong thứ tự để đảm bảo tìm kiếm thực thi chính xác thiết lập thay đổi của các peer liên quan. Chord có thể cung cấp dịch vụ tìm kiếm cho nhiều ứng dụng, như phân tán file hệ thống hay các dữ liệu cộng tác. Tuy nhiên Chord ko phải là 1 công cụ tim kiếm, nó chỉ hỗ trợ các truy vấn single-term exactmatch(đơn-giới hạn- chính xác-phù hợp) và ko hỗ trợ bất kỳ form thứ bậc nào. 4/ Information Retrieval Basics – cơ bản thông tin phục hồi 2

Hệ thống thông tin phục hồi (IR) giữ 1 số lượng lớn dữ liệu ko cấu trúc hay cấu trúc yếu, như là các văn bản text hay trang HTML và cung cấp các chức năng tìm kiếm bao gồm các công cụ tìm kiếm web hay thư viện điện tử, trong thời gian trc đây, cơ sở dữ liệu liên quan đến các hệ thống đc tích hợp chức năng IR khá tốt. Chức năng tìm kiếm là đặc trưng hoàn thiện bởi thước đo đánh giá sự giống nhau giữa truy vấn và các tài liệu. Nền text IR với từ khóa truy vấn, chức năng tương tự điển hình đưa vào tài khoản tính số lần xuất hiện và những vị trí liên quan với mỗi truy vấn trong tài liệu. 4.1/ Inverted Index Lists – danh sách chỉ mục đảo ngược Khái niệm của Inverted Index Lists đc phát triển trong thứ hạng ảnh hưởng tới định danh các tài liệu trong dataset chứa 1 số hạng truy vấn đặc biệt. Với mục đích tất cả các quan hệ xuất hiện trong form thu thập đc là 1 cây chỉ mục có cấu trúc ( thường là 1 cây B+ hay 1 trie) nơi mà lá của nó chứa 1 danh sách các định danh duy nhất của dữ liệu cho tất cả các tài liệu mà chứa số hạng đó. Dựa trên các khái niệm, các danh sách đc combine bởi chỗ cắt hoặc duy nhất cho tất cả các số hạng truy vấn để tìm các tài liệu thích hợp cho 1 truy vấn đặc biệt. Phụ thuộc vào chính xác kế hoạch thực hiện truy vấn , danh sách các tài liệu định danh có thể đc sắp xếp theo các tài liệu định danh hay theo 1 giá trị cho phép xén bớt có hiệu quả.

4.2/ Đo TF * IDF Số lượng biến thể của 1 số hạng t trong 1 tài liệu d đc gọi là term frequency và biểu hiện như . Ý nghĩa của 1 tài liệu tăng lên với số lượng các bản thể của 1 số hạng truy vấn. Số lượng các tài liệu trong tập hợp chứa số hạng t đc gọi là document frequency ; inverse document frequency là số lượng các tài liệu chứa số hạng đó tăng lên, ví dụ số hạng cung cấp giảm sự phân biệt giữa cá tài liệu. 1 đặc trưng tiêu biểu của công thức đc tính là trọng lượng của số hạng thứ i trong tài liệu thứ j là

4.3/ Top-k Index Processing Một thuật toán tốt nên tránh đọc danh sách invert index list, nhưng giới hạn của sự cố gắng tới O(k) mà k là số lượng yêu cầu. Trong IR và tài liệu tìm kiếm multimedia, nhiều thuật toán đã đưa ra thực hiện điều đó. Phương thức đưa ra cho top k truy vấn là thuật toán ngưỡng Fagin. Nó sử dụng danh sách chỉ mục đc sắp xếp trong thứ tự giảm của tỷ số số hạng dưới sự thêm vào giả định rằng tý số cuối cho 1 tài liệu đc tính sử dụng 1 chức năng kết hợp đều ( như là chức năng tính tổng ). TA nghiên cứu toàn bộ danh sách invert index trong 1 kiểu vòng robin. Cho mỗi tài liệu mới d đc đếm, TA dùng truy cập ngẫu nhiên để tính tỷ số cuối cho d và giữ thông tin trong 1 tài liệu thiết lập thích hợp. Khi TA thêm việc giữ track của ranh giới

3

cao hơn cho các tài liệu ko đc đếm, thuật toán đinh giới hạn như ranh giới bảo đảm rằng ko tài liệu ko thấy nào có thể vào thiết lập thích hợp đó. 5 / Thiết kế hệ thống Tiếp cận tầng trên cùng của Chord và theo 1 mô hình thuê bao xuất bản. Tài liệu cho rằng mỗi database tổ chức 1 peer là hoàn toàn tự trị và có 1 chỉ số cục bộ. Sử dụng bảng băm phân tán để phân vùng khoảng số hạng, như mỗi peer chịu trách nhiêm 1 subset ngẫu nhiên của quan hệ bên trong thư mục toàn cục. Mỗi peer xuất bản 1 tóm lược (post) cho mỗi số hạng(term) trong chỉ số cục bộ của nó tới mạng nằm dưới mạng overlay, đc định tuyến tới peer hiện thời chịu trách nhiệm về số hạng đó. Peer đó chứa 1 PeerList của tất cả các phần gửi cho số hạng đó tới mạng bên kia ( lỗi resilience và sẵn có, PeerList có thể bị trùng lặp với nhiều peer phía bên kia) . Post bao gồm các thông tin liên hệ về peer mà gửi tóm lược với nhau để tính toán IR-style đc đo nhưng trong phần 4 . Truy vấn xử lý cho 1 multi-term truy vấn xử lý : đầu tiên , peer truy vấn nhận 1 danh sách các peer hữu dụng bằng cách đưa ra 1 yêu cầu PeerList cho mỗi truy vấn term tới bên dưới mạng overlay. Dùng database lựa chọn phương thức, 1 số lượng peer triển vọng chp hoàn thiện truy vấn đc tính từ các PeerList. Sau đó truy vấn đc forward lại các peer và thực thi dựa trên các chỉ số cục bộ của chúng. Nhớ rằng cách giao tiếp này đc hoàn thành trong 1 pairwise theo kiểu point-to-point giữa các peer, cho phép ảnh hưởng của cách giao tiếp và giới hạn tải trên thư mục cục bộ. Cuối cùng, kết quả từ nhiều peer đc combine tại peer truy vấn vào trong 1 danh sách kết quả (Result Merging). Mục tiêu của tím kiếm nâng cao chất lượng kết quả tìm kiếm với đánh giá cao về độ chính xác và gọi lại ko thể dễ dàng làm tương thích với mục tiêu thiết kế của khả năng mở rộng ko giới hạn, như kỹ thuật phục hồi thông tin tốt nhất cho thực thi truy vấn phụ thuộc vào khối lượng lớn của tài liệu metadata. Chỉ post các thông tin cô đọng, thông tin toàn thể về các chỉ mục cục bộ và dùng database lựa chọn các phương thức để giới hạn số lượng các peer thực hiện mỗi truy vấn giới hạn kích thước của thư mục toàn cục và giảm lưu lượng mạng. Cách tiếp cận này có thể dễ dàng mởi rộng trong 1 cách mà các thư mục phân tán đc tạo để lưu trữ thông tin ngoại trừ tóm lược chỉ mục cục bộ, như thông tin về bookmark cục bộ, thông tin về các assessment liên quan, hay feedback của người dùng. Thông tin này có thể leveraged(tác dụng đòn bẩy) khi thực thi 1 truy vấn để tăng cường chất lượng kết quả.

4

6 / System Model là thiết lập của các peer hiện thời kết nối tới hệ thống. là thiết lập toàn cục của tất cả các tài liệu. là thiết lập của tất cả các term Mỗi peer pi có 1 chỉ mục cục bộ cho các term trong bộ chứa IR-style thống kê

( thường là

cho mỗi term t trong thiết lập của tài liệu chỉ mục

) Chỉ mục cục ( thường là

) 1 hàm băm đc dùng trong trình tự để phân phát các term qua các peer sẵn có bằng cách gán định danh cho các term. Bên dưới bảng băm phân tán đưa ra 1 chức năng trả lại peer p hiện thời chịu trách nhiệm cho 1 định danh. 1 PeerList yêu cầu plr để 1 peer pi về 1 term t có thể định nghĩa ngay lập tức như 1 chức năng , trả về 1 danh sách các peer đã post tập hợp về term t tới peer pi . Chức năng đó gọi là

đc dùng để xác định peer nào chịu trách nhiệm hosting các tập hợp về 1 term . Trong trình tự để làm mẫu thư mục phân tán, mỗi peer pi post st cho tất cả các

subset của

(

là

mà peer pi có thể lựa chọn 1 cách tự do) forming thư mục cục bộ :

Thư mục cung cấp 1 ánh xạ từ các term tới PeerList và có thể dùng để định danh các peer mà chứa 1 danh sách các Post cho 1 term t bên trong thư mục. Chúng tôi coi 1 truy vấn q như 1 thiết lập của cặp và thiết lập của các truy vấn tồn tại như . Trong trình tự xử lý 1 truy vấn q, 1 thiết lập của các peer triển vọng cho truy vấn này phải đc xác định trong 1 database lựa chọn bước dùng 1 chức năng :

Việc thực thi 1 truy vấn q là 1 hàm : định bởi

mà gửi truy vấn để các peer trc đó xác

combine kết quả peer cục bộ vào trong 1 thiết lập kết quả cuối cùng (kết quả hợp

nhất). Cuối cùng chúng tôi định nghĩa truy vấn toàn cục thực thi chức năng :

mà đc đánh

giá : 7/ Implementation

5

Peer đc sắp trên cùng của bảng băm phân tán DHT mà xây dựng thư mục toàn cục bằng điều kiện ánh xạ từ các term vào các peer. Thư mục trả lại 1 đối tượng PeerDescriptor miêu tả peer hiện thời chịu trách nhiệm cho 1 term. 1 Cominicator có thể đc thiết lập để gửi các thông điệp tới các peer khác. Mỗi peer có 1 EventHandler để nhận các thông điệp đi vào và forward chúng tới thành phần cục bộ thích hợp. Mỗi peer có 1 chỉ mục cục bộ. Chỉ mục đc dùng bởi thành phần LocalQueryProcessor để trả lời các truy vấn và bởi thành phần Poster để xuất bản các tóm lược per-term (Post) tới thư mục toàn cục. Để làm điều đó, Poster dùng underlying DHT để tìm peer chịu trách nhiệm; PeerListProcessor tại peer đó chứa 1 PeerList của tất cả các Posts cho term đó qua mạng. Khi người dùng đưa ra 1 truy vấn, thành phần Global QueryProcessor tương tự dùng DHT để tìm kiếm peer chịu trách nhiệm và nhận PeerList tương ứng từ các PeerList Processor dùng các thành phần Communicator. Sau khi chạy peer lựa chọn kế hoạch trên các list, GlobalQueryProcessor forward lại truy vấn hoàn thành để lựa chọn các peer, trong lượt xử lý truy vấn dùng LocalQueryProcessor và trả về kết quả. Cuối cùng GlobalQueryProcessor kết hợp các kết quả và đưa chúng tới người dùng.

6

MINEVA dùng 1 nền Java sự thi hành lại Chord như bên dưới DHT, nhưng có thể dễ dàng đc dùng với cung cấp DHT khác : 1 phương thức . Communication đc quản lý bởi nền socket, nhưng nền dịch vụ Web dựa trên peer có thể dễ dàng bao gồm hỗ trợ 1 môi trường ko đồng nhất. Hình 6 biểu diễn giao diện người dùng MINEVA. Người dùng bắt đầu 1 peer bằng cách tạo 1 vòng Chord hoặc bằng cách join vào hệ thống đã tồn tại. Cả 2 hành động yêu cầu đặc tả 1 cổng Chord cục bộ cho giao tiếp liên quan đến thư mục toàn cục và 1 cổng ứng dụng toàn cục cho việc điều khiển giao tiếp peer-to-peer. Join vào 1 hệ thống tồn tại yêu cầu thêm thông tin về 1 peer đã tồn tại. Thông tin trạng thái về vòng Chord đc hiển thị và cập nhật thường xuyên. Đoạn Post cung cấp thông tin về các term mà peer hiện thời chịu trách nhiệm với nó. Nút Post để gửi thông tin chứa trong 1 chỉ số cục bộ tới thư mục. Đoạn Queries thực hiện các truy vấn với các từ khóa dc nhập vào 1 trường mẫu bên dưới. Các kết quả đc hiện thị sắp xếp theo kết quả đạt đc. 8/ Peer Selection Strategies

7

Peer selection là vấn để của định danh các peer mà có thể trả lời truy vấn của 1 peer đưa ra p0 với kết quả chất lượng cao mà chi phí thực hiện thấp. Cách tiếp cận bao gồm 2 bước : 1.Tìm kiếm các peer có tiềm năng 2.Định danh các peer tốt nhất k (k là 1 thông số cấu hình hệ thống) bởi đánh giá tất cả các peer tiềm năng sử dụng 1 tỷ lệ Bươc đầu tiên đc quản lý bằng cách nhận tất cả các Posts cho mỗi truy vấn term từ thư mục toàn cục. Để có hiệu quả, chúng tôi có thể giới hạn thư mục tìm kiếm để chỉ trả lại các peer tốt nhất cho 1 từ khóa, dựa vào 1 điểm đo. Trong bước 2, tất cả các Post của 1 peer đc combine để đánh giá chất lượng kết quả mong muốn của peer cho truy vấn đó. Trong bước này lợi ích đánh giá đề cập đến sự đóng góp của 1 peer để làm kết quả tìm kiếm tốt hơn, và cho phí đánh giá nói đến nguồn đóng góp và sự đáp lại của các peer mà có liên quan trong 1 truy vấn và cấu hình của mạng. Vì chi phí đánh giá động, nên nhiều đề xuất tồn tại trong tài liệu trên tải chia sẻ phân tán. 8.1 /

Approach

Collection document frequency (cdf) với maximun collection term frequancy ( ) ( số lớn nhất của term xảy ra trong các tài liệu thu thập) và tóm lược qua tất cả các truy vấn term. CDF cho term t của peer pi là số lượng các tài liệu chứa t mà pi giữ trong chỉ số index của nó, và giá trị cho term t của peer pi là tần xuất term (tf) của t trong tài liệu d tại pi mà tf lớn nhất của t nằm trong tất cả các pi. Socre thu thập si cuar peer thứ I với sự quan tâm đến truy vấn q đc tính :

với

Giá trị của thông số có thể đc chọn từ 0 đến 1 và đc dùng để nhấn mạnh tầm quan trọng của cfd . Các score si đc tính cho tất cả các peer và sắp xếp giảm dần theo thứ bậc đạt đc của peer.

8.2 / CORI-like Approaches 8.2.1 / CORI 1 Score thu thập si của peer thứ I với sự quan tâm tới 1 truy vấn q trong loại sau :

Sự tính toán của và sử dụng kích thước của ko gian định danh Chord cơ bản như giới hạn trên cho số lượng các peer trong hệ thống, biểu thị là np, cdf và :

8

Trong đó là số lượng các peer mà chứa term t, lấy gần đúng giá trị bởi số lượng ccacs peer đã xuất bản Post cho term t(ví dụ độ dài của PeerList cho t). Các giá trị và đc chọn : 8.2.2 / CORI 2 Size Vi của ko gian term cua 1 peer và cỡ ko gian trung bình term

trên tất cả các peer mà chứa

term t :

Thực tế là khó để tính kích thước trung bình của ko gian term trên tất cả các peer trong hệ thống. 8.3 / GlOSS-like Approach Đầu tiên, cần phải sắp xếp truy vấn các term các cặp

trong thứ tự tăng của giá trị cdf, như là nó giữ

mà Trong bước thứ 2, tần xuất trung bình của term cho tài liệu trong 1 tập hợp

cách combine collection term frequency ( document frequency (

đc tính bằng

- số sự cố của 1 term trong toàn bộ tập hợp) và collection

):

Tính tập hợp score cuối cùng của peer thứ I với sự quan tâm tới truy vấn q :

ở đó

và

là số lượng các tài liệu trong tập hợp thứ i.

8.4 / Language-Model (LM) based Approaches 8.4.1 / LM of Callan

9

Trong đó là 1 kiểu thống kê của Genetal English và là 1 tham số chỉnh. Tính gần đúng bằng cách tính số sự cố của term tỏng các tập hợp đc chia bởi toàn bộ số lượng các term trong tập hợp. Chọn và tính :

Trong đó

là kích thước của peer thứ i đc đếm trong các sự cố term ( ko trừ term )

8.4.2 / LM of Xu & Croft Loại ngôn ngữ thứ 2 : tính khoảng cách giữa kiểu truy vấn và kiểu tập hợp :

9 / Experiments 9.1 / Experimental Setup Mỗi truy vấn chúng tôi thu đc ideal peer ranking ( ý tưởng thứ bậc peer ) : truy vấn đc thực hiện trên tập hợp tham chiếu với thước đo trong phần 4 để thu đc 1 kết quả truy vấn tham chiếu

10

Sau đó, truy vấn đc thực thi trên mỗi tập hợp riêng biệt, sử dụng cùng cách. Các kết quả cục bộ đc so sánh với kết quả truy vấn tham chiếu dùng hàm rank distance trong 9.2. 1 hệ thống các tham số mà ảnh hưởng tới các kết quả của thí nghiệm : - Số lượng peer đc trả lại bởi peer đc chọn trong kế hoạch - Số lượng các tài liệu nhận đc từ mõi peer - Số lượng tài liệu nhận đc từ combine tập hợp ( ý tưởng bậc tài liệu ) - Số lượng các peer trong ý tưởng peer ranking Tất cả các thực nghiệm đc kiểm soát dùng 10 peer chạy xử lý tách rời trên 1 notebook riêng với Pentium M 1.6GHz và 1G bộ nhớ. Tất cả các peer chia sẻ 1 cơ sở dữ liệu 10G đc cài đặt vào trong 1 DualPentium Xeon 3GHz với 4G bộ nhớ. Các peer đc kết nối tới cơ sở dữ liệu qua mạng 100Mbit. 9.2 / Rank Distance Function 1 ranking là 1 bijection từ 1 domain tới mà và . So sánh phép hoán vị đc học mạnh mẽ từ rất lâu. 1 trong hầu hết các metric nổi bật là footrule metric của Spearman tính sự khác nhau giữa 2 phép hoán vị

và

với

:

(1)

11

Các domain và ko cần thiết giống nhau, vì sự lựa chọn peer trong kế hoạch ko thể trả lại tất cả các peer. Công thức để tính khoảng cách giữa 2 cấp và : (2) Dù công thức này tương tự với (1), nhưng nó chỉ tính tổng qua các phần tử chứa trong nữa (2) chỉ đúng nếu đó cần phải mở rộng

là 1 superset của của như sau :

Phần mở rộng này của

bởi

ko xác định cho tất cả các

. Hơn . Do

thêm vào 1 bất lợi đặc biệt lớn cho các entry ko đúng chỗ nằm trong top

rank của . Vì ko cần mở rộng do chỉ tính tổng đến các phần tử trong nên F’ là ko đối xứng. Một kết quả quan trọng khác xuất hiện khi thử đánh giá vài rank với kích thước khác nhau tới 1 rank tham chiếu. Để tránh sự so sánh ko cân bằng của danh sách các kết quả ngắn và match tốt tương phản với danh sách các kết quả dài và các match ko tốt tại rank thấp, thì yêu cầu 1 kích thước nhỏ nhất cho mỗi danh sách kết quả truy vấn từ mỗi peer và bổ xung ngắn hơn nữa các danh sách bởi tài liệu “dummy” có thể tương ứng với rank

trong tập hợp tham chiếu.

9.3 / Experimental Results

Hình 8 chỉ ra khoảng cách giữa các rank của peer trả lại bởi peer lựa chọn chiến lược và rank của peer ý tưởng. Khoảng cách này cho mỗi strategy đc lấy trung bình trên 10 truy vấn trong phép đo chuẩn, dựa vào khoáng cách rank định nghĩa trong 9.2. Với các truy vấn test, CORI 2 đưa ra kết quả tốt nhất làm

12

tốt hơn GLOSS cơ sở strategy(chiến lược) và cả tiếp cận Langguage Modeling. Tiếp cận đặc biệt tốt với điều kiện đủ nhỏ. Dùng cùng thiết lập của các tập hợp và các truy vấn, chúng tôi cố ý gọi lại liên quan tới top 30 tài liệu từ việc combine tập hợp khi mà chúng tôi truy vấn các peer theo vị trí trong ranking peer ý tưởng. Hình 8 cho biết chỉ gửi truy vấn tới peer tốt nhất sẵn sàng mang lại 1 giá trị trung bình khoảng 60% của tất cả tài liệu có liên quan, ngược lại bên dưới các peer điển hình ko đóng góp bất cứ tài liệu mới nào cho kết quả truy vấn. Nhớ rằng điều đó ko có nghĩa chúng ko chứa bất kỳ tài liệu liên quan nào, nhưng đúng hơn là các tài liệu liên quan của nó đã đóng góp bởi các peer khác trc đó. Vì vậy đưa vào acc thì khả năng overlap(chồng lấp) của các content các peer cục bộ là chủ yếu. Tầm quan trọng của sự phân chia với nguyên nhân dư thừa bằng chồng lấp các chỉ mục của các peer khác nhau trở lên trọn vẹn hơn khi thấy thời gian thực hiện truy vấn và số lượng các tài liệu liên quan đạt đc, như là số lượng các peer truy vấn tăng lên. Hình 9c chỉ ra các thực nghiệm quản lý trên 1 máy đơn, thời gian thực hiện truy vấn tăng lên theo 1 đường; trong 1 kịch bản thế giới thực, thời gian thực hiện đc trông đợi để giữ nguyên hằng số gần sát như tải đc trải rộng trên 1 số lượng các bộ xử lý độc lập. 1 truy vấn đc thực hiện trong 1 thời gian hợp lý 2 giây cho mỗi peer, đó là thời gian chi phối bởi thời gian thực thi tại các peer; hệ thống overhead hầu như ko đáng kể . Hình 9 chỉ ra số lượng các tài liệu liên quan đạt đc khi tăng số lượng các peer xác thực và thêm vào. Tý số giữa số lượng các tài liệu liên quan và thời gian thực thi biểu thị điều đó ( hình 9 a), trong thiết lập thực nghiệm, tý số tốt nhất đạt đc khi hỏi chỉ 1 peer từ xa ( trong việc thêm vào đánh giá cục bộ tại peer truy vấn) // dịch xong đoạn này dek hiểu j cả 

13

Kích thước của 1 Post trong khoảng 10 đến 20 byte cho từ khóa điển hình. Toàn bộ tài nguyên của dữ liệu mà đã truyền trên mạng trong suốt 1 tiến trình post cho 1 tập hợp chứa 45 000 term khoảng 650KB. 1 PeerList yêu cầu và truy vấn của nó chỉ coi như 100-200 byte cho 1 truy vấn từ khóa đôi.Sự phức tạp của truy vấn định tuyến strategy mà đạt đc PeerList từ bước có trc : trong đó n là số lượng các truy vấn term và l là độ dài lớn nhất của PeerList, nl là 1 giới hạn trên cho số lượng các Post mà phải xử lý trc khi ranking peer phải đc sắp xếp trong , trong đó m là số lượng các peer riêng tìm trong PeerList. 10/ Kết luận và công việc mai sau ko thèm dịch đoạn này :D

14