Similarity Searching: Towards Bulk-loading Peer-to-Peer Networks

DOHNAL, Vlastislav, Jan SEDMIDUBSKÝ, Pavel ZEZULA a David NOVÁK. Similarity Searching: Towards Bulk-loading Peer-to-Peer Networks. In 1st International Workshop on Similarity Search and Applications (SISAP 2008). Los Alamitos CA, Washington, Tokyo: IEEE Computer Society, 2008, s. 87-94. ISBN 978-0-7695-3101-4.

Základní údaje

Originální název

Similarity Searching: Towards Bulk-loading Peer-to-Peer Networks

Název česky

Podobnostní vyhledávání: směrem k efektivnímu budování P2P sítí

Autoři

DOHNAL, Vlastislav (203 Česká republika, garant, domácí), Jan SEDMIDUBSKÝ (203 Česká republika, domácí), Pavel ZEZULA (203 Česká republika) a David NOVÁK (203 Česká republika, domácí)

Vydání

Los Alamitos CA, Washington, Tokyo, 1st International Workshop on Similarity Search and Applications (SISAP 2008), od s. 87-94, 8 s. 2008

Nakladatel

IEEE Computer Society

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Mexiko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14330/08:00024136

Organizační jednotka

Fakulta informatiky

ISBN

978-0-7695-3101-4

UT WoS

000255509900010

Klíčová slova anglicky

similarity search; p2p network; peer split; index structure

Štítky

DISA, index structure, p2p network, peer split, similarity search

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Due to the exponential growth of digital data and its complexity, we need a technique which allows us to search such collections efficiently. A suitable solution is based on the peer-to-peer (P2P) network paradigm and the metric-space model of similarity. When a large volume of data is being inserted, the P2P network must expand to new peers in order to maintain its efficiency. Thus, many peers must be split. During a peer split, the data is halved and one half is migrated to a new peer. In this paper, we study the problem of peer splits and propose a specialized algorithm for speeding it up. In particular, we use the structured P2P network called the M-Chord. Search performance within a single peer is enhanced by the M-tree. In experimental evaluation, we compare the proposed algorithm with several straightforward solutions on a real network organizing 10 million images. Our algorithm provides a significant performance boost.

Česky

Díky exponenciálnímu nárustu dat a jejich složitosti, potřebujeme nalézt techniku, která nám umožní efektivně prohledávat takové kolekce dat. Vhodné řešení je založeno na P2P sítích a metrickém přístupu pro modelování podobnosti. Když se vkládá velké množství dat, P2P síť se musí postupně rozšiřovat do většího počtu uzlů, aby dokázala udržet požadovanou výkonnost. Během tohoto procesu se tak se musí spousta uzlů rozdělit. Když se štěpí uzel, data jsou rozdělena na polovinu a jedna půlka je pak přesunuta do nově vytvořeného uzlu. V tomto článku studujeme problém štěpení jednoho uzlu a navrhujeme vhodné techniky pro urychlení tohoto procesu. Obzvláště, využíváme P2P síť nazývanou M-Chord. Výkonnost vyhledávání v jednom uzlu je vylepšena lokální indexovou strukturou nazývanou M-tree. V experimentální části porovnáváme navržený algoritmus s několika přímočarými řešeními na skutečné síti indexující 10 miliónů obrázků.

---

Návaznosti

GP201/07/P240, projekt VaV	Název: Distribuované indexační struktury pro podobnostní hledání Investor: Grantová agentura ČR, Distribuované indexační struktury pro podobnostní hledání
1ET100300419, projekt VaV	Název: Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu Investor: Akademie věd ČR, Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu