Paralelní a distribuované Paralelní a distribuované MAMMAM
Jakub LokočJakub Lokoč
OsnovaOsnova
Úvod do problematikyÚvod do problematiky
Paralelní MAMParalelní MAM M-TreeM-Tree
Distribuované MAMDistribuované MAM GHT*GHT* VPT*VPT* MCANMCAN M-ChordM-Chord
Úvod do problematikyÚvod do problematiky
U centralizovaných indexů je silná korelace mezi velikostí DB a U centralizovaných indexů je silná korelace mezi velikostí DB a náklady na vyhodnocení podobnostních dotazů (lineární závislost, náklady na vyhodnocení podobnostních dotazů (lineární závislost, limituje škálovatelnost)limituje škálovatelnost)
Objem indexovatelných MM dat roste exponenciálně (jen 1Objem indexovatelných MM dat roste exponenciálně (jen 1% dat na % dat na InternetuInternetu jsou texty jsou texty))
VVývoj HW narazil na fyzikální hranice, trendem je paralelizace (více ývoj HW narazil na fyzikální hranice, trendem je paralelizace (více jader v CPU atp.)jader v CPU atp.)
Řešením je vývoj efektivnějších indexačních struktur, nebo využití Řešením je vývoj efektivnějších indexačních struktur, nebo využití více zdrojů (CPU, HDD, …) při řešení dotazů stávajícími metodamivíce zdrojů (CPU, HDD, …) při řešení dotazů stávajícími metodami
Zákony paralelizaceZákony paralelizace
Ne vždy lze paralelizací vylepšit stávající algoritmus navržený původně pro Ne vždy lze paralelizací vylepšit stávající algoritmus navržený původně pro sekvenční zpracování – Amdahl's law sekvenční zpracování – Amdahl's law
Algoritmus se skládá z částí, které nelze paralelizovat – nelze urychlitAlgoritmus se skládá z částí, které nelze paralelizovat – nelze urychlit Zvyšováním počtu výpočetních jednotek se urychluje jen část algoritmuZvyšováním počtu výpočetních jednotek se urychluje jen část algoritmu Vztahuje se ke konstantnímu problému – výsledný čas se přidáváním zdrojů blíží Vztahuje se ke konstantnímu problému – výsledný čas se přidáváním zdrojů blíží
limitně k času sériově zpracovávané části (100limitně k času sériově zpracovávané části (100;100;100)), (100;50-50), (100;25-25-25-, (100;50-50), (100;25-25-25-25), …, (100; 1-1-1-1…)25), …, (100; 1-1-1-1…)
Každý dostatečně velký problém se dá paralelizovat - Gustafson's lawKaždý dostatečně velký problém se dá paralelizovat - Gustafson's law Zvětšováním problému (paralelní části) se dá dosáhnout stejného času při využití Zvětšováním problému (paralelní části) se dá dosáhnout stejného času při využití
více zdrojůvíce zdrojů Důležitý faktor pro návrhDůležitý faktor pro návrh škálovatelných systémůškálovatelných systémů S rostoucí velikostí problému se snižuje význam času sériově zpracovávané S rostoucí velikostí problému se snižuje význam času sériově zpracovávané
částičásti (100;100), (100;100-100), (100;100-100-100-100), … (100;100), (100;100-100), (100;100-100-100-100), …
Efektivita paralelizaceEfektivita paralelizace
Speed-up = ST / BT (small/big system time)Speed-up = ST / BT (small/big system time) Lineární, pokud n x věší systém je n x rychlejší (pro stejnou Lineární, pokud n x věší systém je n x rychlejší (pro stejnou
úlohu)úlohu)
Scale-up = STSP / BTBP (small/big system time Scale-up = STSP / BTBP (small/big system time small/big problem)small/big problem)
Lineární, pokud se rovná/blíží 1Lineární, pokud se rovná/blíží 1
Paralelní MAMParalelní MAM
Paralelní zařízeníParalelní zařízení Skládá se z několika procesorů a diskůSkládá se z několika procesorů a disků Sdílí paměť a komunikační kanálySdílí paměť a komunikační kanály
Paralelní index – požadavkyParalelní index – požadavky Data (DB objekty) jsou sdílena všemi procesory, tzn. každý CPU může Data (DB objekty) jsou sdílena všemi procesory, tzn. každý CPU může
v každém okamžiku číst/měnit libovolná data (s výjimkou vzájemného v každém okamžiku číst/měnit libovolná data (s výjimkou vzájemného vyloučení při vstupu do kritické sekce)vyloučení při vstupu do kritické sekce)
Lze spustit součastně více operací na různých CPULze spustit součastně více operací na různých CPU Data jsou paralelně ukládána na více diskůData jsou paralelně ukládána na více disků
Paralelní M-TreeParalelní M-Tree
Základní typy paralelismuZákladní typy paralelismu CPU paralelismusCPU paralelismus I/O paralelismusI/O paralelismus
Limitující faktory pro zpracování dotazuLimitující faktory pro zpracování dotazu Stromová struktura – nelze zpracovat objekty v potomkovi, Stromová struktura – nelze zpracovat objekty v potomkovi,
pokud nebyl zpracován příslušný objekt v rodičovském uzlupokud nebyl zpracován příslušný objekt v rodičovském uzlu Sériové odebírání požadavků z fronty (PQ) u kNN dotazůSériové odebírání požadavků z fronty (PQ) u kNN dotazů
CPU paralelizaceCPU paralelizace
DotazováníDotazování Pořadí zpracování uzlů je dáno dynamicky budovanou frontouPořadí zpracování uzlů je dáno dynamicky budovanou frontou Z koordinačních důvodů je zpracovávána dedikovaným procesoremZ koordinačních důvodů je zpracovávána dedikovaným procesorem Zbylé procesory se používají pouze pro paralelizaci výpočtů vzdáleností Zbylé procesory se používají pouze pro paralelizaci výpočtů vzdáleností
k jednotlivým směrovacím/listovým záznamům v aktuálně k jednotlivým směrovacím/listovým záznamům v aktuálně zpracovávaném uzluzpracovávaném uzlu
Tvorba stromu – štěpení uzluTvorba stromu – štěpení uzlu
Omezení CPU paralelizaceOmezení CPU paralelizace Počet klíčů v uzluPočet klíčů v uzlu Sériové odebírání prvků z PQSériové odebírání prvků z PQ
I/O paralelizaceI/O paralelizace
Načítání uzlů do paměti – v jednom výpočetním kroku se snaží Načítání uzlů do paměti – v jednom výpočetním kroku se snaží načíst co nejvíce uzlů z různých disků do pomocné struktury TEMPnačíst co nejvíce uzlů z různých disků do pomocné struktury TEMPMíra paralelizace načítání během zpracování dotazu závisí na Míra paralelizace načítání během zpracování dotazu závisí na metodě/strategii ukládání uzlů na disk (tzn. jejich rozložení)metodě/strategii ukládání uzlů na disk (tzn. jejich rozložení)
Globální alokaceGlobální alokaceRandom (náhodně rozděluje)Random (náhodně rozděluje)Round-robin (rovnoměrné rozložení uzlů)Round-robin (rovnoměrné rozložení uzlů)
Proximity-based alokace (bere v potaz rozložení okolních regionů)Proximity-based alokace (bere v potaz rozložení okolních regionů)Simple-proximity – součet poloměrů mínus vzdálenostSimple-proximity – součet poloměrů mínus vzdálenostComplex-proximity – pravděpodobnost, že dotaz protne oba regionyComplex-proximity – pravděpodobnost, že dotaz protne oba regiony
K určení disku dochází po štěpení uzluK určení disku dochází po štěpení uzluU kNN dotazu nemusí vadit, že byl upřednostněn jiný uzel z důvodu U kNN dotazu nemusí vadit, že byl upřednostněn jiný uzel z důvodu zajištění paralelizace I/Ozajištění paralelizace I/OFiltrování uzlů probíhá i v TEMP Filtrování uzlů probíhá i v TEMP
I/O paralelizace – vylepšení ?I/O paralelizace – vylepšení ?
Mezi jednotlivé disky se rozdělují záznamy v listu (a ne uzly)Mezi jednotlivé disky se rozdělují záznamy v listu (a ne uzly)
Listový uzel obsahuje pouze adresy objektů na jednotlivých HDDListový uzel obsahuje pouze adresy objektů na jednotlivých HDD
Objekty jsou distribuovány mezi disky vzhledem ke globálnímu Objekty jsou distribuovány mezi disky vzhledem ke globálnímu rozdělení objektůrozdělení objektů
Vložení objektuVložení objektu Po nalezení listového uzlu se položí rozsahový dotaz (poloměr je Po nalezení listového uzlu se položí rozsahový dotaz (poloměr je
vzdálenost k pivotu listového uzlu a střed je nový objekt)vzdálenost k pivotu listového uzlu a střed je nový objekt) Z vrácených odpovědí se zjistí nejméně frekventovaný disk, na který se Z vrácených odpovědí se zjistí nejméně frekventovaný disk, na který se
uloží nově vkládaný objektuloží nově vkládaný objekt
Vede k téměř optimálnímu rozdělení objektů mezi HDDVede k téměř optimálnímu rozdělení objektů mezi HDD
Vliv na rychlost dotazů nebyl v článku uvedenVliv na rychlost dotazů nebyl v článku uveden
Distribuované MAMDistribuované MAM
Distribuované prostředí (DP)Distribuované prostředí (DP) Počítače (uzly) propojené vysokorychlostní sítí – využívají vzájemně Počítače (uzly) propojené vysokorychlostní sítí – využívají vzájemně
výpočetní sílu svých CPU a svá datová úložištěvýpočetní sílu svých CPU a svá datová úložiště Každý počítač má vlastní pamět (volně vázané systémy)Každý počítač má vlastní pamět (volně vázané systémy) Je zapotřebí infrastruktura pro alokaci a zpracování objektů v DPJe zapotřebí infrastruktura pro alokaci a zpracování objektů v DP Zajištění základních operací je realizováno zasíláním požadavků mezi Zajištění základních operací je realizováno zasíláním požadavků mezi
uzly pomocí směrovacích mechanismůuzly pomocí směrovacích mechanismů Není omezena škálovatelnost jako u paralelního zpracováníNení omezena škálovatelnost jako u paralelního zpracování Síť několika počítačů je levnější než jeden superpočítačSíť několika počítačů je levnější než jeden superpočítač
Základní paradigmata distribuovaných indexůZákladní paradigmata distribuovaných indexů SDDS (scalable and distributed data structures)SDDS (scalable and distributed data structures) P2PP2P
Požadavky na SDDS a P2PPožadavky na SDDS a P2P
SDDS (servery obsahují data a klienti provádí operace)SDDS (servery obsahují data a klienti provádí operace) Scalability – efektivní migrace dat na nové uzly (jen pokud jsou Scalability – efektivní migrace dat na nové uzly (jen pokud jsou
stávající dostatečně zaplněné)stávající dostatečně zaplněné) No hotspot – bez centralizovaného adresáře s adresami objektůNo hotspot – bez centralizovaného adresáře s adresami objektů Independence – operace nevyžadují atomické změny více uzlůIndependence – operace nevyžadují atomické změny více uzlů
P2PP2P Peer – každý uzel struktury se chová jako klient i jako server, tzn. může Peer – každý uzel struktury se chová jako klient i jako server, tzn. může
zasílat dotazy a součastně ukládat datazasílat dotazy a součastně ukládat data Fault tolerance – pokud uzel vypadne, tak se dají zpracovávat všechny Fault tolerance – pokud uzel vypadne, tak se dají zpracovávat všechny
operace dál, jen dočasně neuvidí na všechna dataoperace dál, jen dočasně neuvidí na všechna data Redundancy – replikace dat za účelem zvýšení dostupnosti, využíváno Redundancy – replikace dat za účelem zvýšení dostupnosti, využíváno
algoritmy pro vyhledáváníalgoritmy pro vyhledávání
GHT*, VPT*GHT*, VPT*
ZaloZaložený na GHT (VPT), využívá P2P paradigmažený na GHT (VPT), využívá P2P paradigmaSplňuje základní vlastnosti SDDS a P2P přístupůSplňuje základní vlastnosti SDDS a P2P přístupů
Scalability – každý uzel (peer) se může kdykoliv nezávisle rozštěpit a Scalability – každý uzel (peer) se může kdykoliv nezávisle rozštěpit a distribuovat data na jiné uzlydistribuovat data na jiné uzly
No hotspot – každý peer udržuje vlastní adresní schéma, aktualizace No hotspot – každý peer udržuje vlastní adresní schéma, aktualizace probíhá pouze lokálně (štěpení nezahlcuje síť)probíhá pouze lokálně (štěpení nezahlcuje síť)
Peer – každý uzel může ukládat data a součastně klást dotazyPeer – každý uzel může ukládat data a součastně klást dotazy
ArchitekturaArchitektura Každý uzel (peer) obsahuje úložiště pro data tzv. „kapsu“ (bucket) – Každý uzel (peer) obsahuje úložiště pro data tzv. „kapsu“ (bucket) –
počet a kapacita závisí na možnostech uzlu (nemusí mít vůbec).počet a kapacita závisí na možnostech uzlu (nemusí mít vůbec). Po zaplnění kapsy dojde k jejímu štěpení, nová kapsa může být Po zaplnění kapsy dojde k jejímu štěpení, nová kapsa může být
umístěna na jiný uzel. Je možné i slučovat kapsy.umístěna na jiný uzel. Je možné i slučovat kapsy. Základní struktura pro lokalizaci objektů je AST (address search tree), Základní struktura pro lokalizaci objektů je AST (address search tree),
uložená v každém uzlu tzn. vyhodnocování adres je lokální záležitostuložená v každém uzlu tzn. vyhodnocování adres je lokální záležitost AST se automaticky aktualizuje v průběhu vyhodnocování dotazůAST se automaticky aktualizuje v průběhu vyhodnocování dotazů
AST – address search treeAST – address search tree
Vychází z GHT (VPT)Vychází z GHT (VPT)
Vnitřní uzly obsahují 2 směrovací objektyVnitřní uzly obsahují 2 směrovací objekty
Každý list reprezentuje buď ukazatel na lokální úložiště tzv. kapsu (pomocí Každý list reprezentuje buď ukazatel na lokální úložiště tzv. kapsu (pomocí BID) nebo na jiný uzel sítě (pomocí NNID), kde se data nachází.BID) nebo na jiný uzel sítě (pomocí NNID), kde se data nachází.
Pro zjištění nekonzistence mezi AST na různých uzlech sítě je u každého Pro zjištění nekonzistence mezi AST na různých uzlech sítě je u každého vnitřního uzlu jeho sériové číslo, které se mění při změně části stromu.vnitřního uzlu jeho sériové číslo, které se mění při změně části stromu.
Změny v AST jsou vyvolány štěpením nebo sléváním kapes.Změny v AST jsou vyvolány štěpením nebo sléváním kapes.
Problém s lineární závislostí replikovaných pivotů – logaritmická replikace – Problém s lineární závislostí replikovaných pivotů – logaritmická replikace – stromy obsahují jen nezbytné pivoty – větve vedoucí jen na NNID se zkrátístromy obsahují jen nezbytné pivoty – větve vedoucí jen na NNID se zkrátí
Štěpení kapsyŠtěpení kapsy
Alokace nové kapsy – pokud možno na stejném uzluAlokace nové kapsy – pokud možno na stejném uzlu
Výberou se dva noví pivotiVýberou se dva noví pivoti Výpočetně náročnéVýpočetně náročné Inkrementální výběr pivotů – hypotéza, že GHT je lepší pro vzdálené pivotyInkrementální výběr pivotů – hypotéza, že GHT je lepší pro vzdálené pivoty První dva objekty jsou kandidáti, každý nový objekt se porovná jen s kandidátyPrvní dva objekty jsou kandidáti, každý nový objekt se porovná jen s kandidáty
Přesun vybraných objektů do nové kapsyPřesun vybraných objektů do nové kapsy
Vkládání a změny v GHT*Vkládání a změny v GHT*
Traverzuje AST v aktuálním uzluTraverzuje AST v aktuálním uzlu
Pokud nalezne BID, tak vloží (může se štěpit)Pokud nalezne BID, tak vloží (může se štěpit)
Pro NNID přeposílá požadavek příslušnému uzlu v sítiPro NNID přeposílá požadavek příslušnému uzlu v síti
Aby se zabránilo redundantním výpočtům vzdáleností, tak se zašle i Aby se zabránilo redundantním výpočtům vzdáleností, tak se zašle i BPATH (bit path 0-left, 1-right + serial numbers)BPATH (bit path 0-left, 1-right + serial numbers)
Změna objektu = smazat původní a znovu vložit novýZměna objektu = smazat původní a znovu vložit nový
Smazání objektuSmazání objektu Vyhledání kapsy v AST a odebráníVyhledání kapsy v AST a odebrání Pokud je kapsa dostatečně prázdná, hledá kapsu pro sloučení (kapsa nalevo v Pokud je kapsa dostatečně prázdná, hledá kapsu pro sloučení (kapsa nalevo v
AST – inverzní ke štěpení)AST – inverzní ke štěpení)
DotazyDotazy
RangeRange Prochází AST, vyhovovat může více větví, v listu se pro BID prohledá lokální Prochází AST, vyhovovat může více větví, v listu se pro BID prohledá lokální
úložiště, jinak zasílá požadavek na NNID (včetně BPATH), pro více stejných úložiště, jinak zasílá požadavek na NNID (včetně BPATH), pro více stejných NNID se zašle pouze jeden dotaz a čeká na odpověďNNID se zašle pouze jeden dotaz a čeká na odpověď
KNNKNN Na rozdíl od centralizovaných indexů nezačíná velkým poloměrem, ale položí Na rozdíl od centralizovaných indexů nezačíná velkým poloměrem, ale položí
bodový dotaz a vybere nejvhodnější kapsu, ze které vezme prvních k obejktů. bodový dotaz a vybere nejvhodnější kapsu, ze které vezme prvních k obejktů. Tím je definován poloměr pro rozsahový dotaz z jehož výsledku se vybere k Tím je definován poloměr pro rozsahový dotaz z jehož výsledku se vybere k nejbližších.nejbližších.
Pokud nebylo prvním bodovým dotazem získáno alespoň k objektů, zkusí položit Pokud nebylo prvním bodovým dotazem získáno alespoň k objektů, zkusí položit rozsahový dotaz negarantující nalezení k objektů. Pokud jich opět nevrátí dost, rozsahový dotaz negarantující nalezení k objektů. Pokud jich opět nevrátí dost, musí se zvětšovat poloměr pomocí jedné ze strategiímusí se zvětšovat poloměr pomocí jedné ze strategií
Optimistická – zvětší poloměr málo, riskuje další iteraceOptimistická – zvětší poloměr málo, riskuje další iterace
Pesimistická – zvětší poloměr hodně, nižší pravděpdodobnost opakovaných dotazůPesimistická – zvětší poloměr hodně, nižší pravděpdodobnost opakovaných dotazů
Aktualizace ASTAktualizace AST
Lokální změny AST se nemusí šířit k ostatním uzlům sítěLokální změny AST se nemusí šířit k ostatním uzlům sítě
K detekci rozdílů a aktualizaci dochází během operací vkládání, K detekci rozdílů a aktualizaci dochází během operací vkládání, mazání a dotazování – se zaslaným požadavkem jde i BPATHmazání a dotazování – se zaslaným požadavkem jde i BPATH
Různá délka cestyRůzná délka cesty Různá sériová číslaRůzná sériová čísla
Uzel, který vyhodnocuje BPATH, zjistí část AST, kterou potřebuje Uzel, který vyhodnocuje BPATH, zjistí část AST, kterou potřebuje odesílatel aktualizovat (pro více zpracovávaných požadavků zašle odesílatel aktualizovat (pro více zpracovávaných požadavků zašle více částí)více částí)
Peer serializuje části stromu a zašle IAM (Image Adjustment Peer serializuje části stromu a zašle IAM (Image Adjustment Message)Message)
Při rekurzivním volání NNID se rekurzivně zasílají i IAMPři rekurzivním volání NNID se rekurzivně zasílají i IAM
MCANMCAN
Založen na CAN (Content Addressable Network)Založen na CAN (Content Addressable Network) Distribuovaná hash tabulka – prvky jsou uzly sítě, mapování objektůDistribuovaná hash tabulka – prvky jsou uzly sítě, mapování objektů Každý uzel je dynamicky asociován s částí d-dimenzionálního Kartézského Každý uzel je dynamicky asociován s částí d-dimenzionálního Kartézského
prostoru (může mu být přiřazena pouze jedna)prostoru (může mu být přiřazena pouze jedna) Podporuje vkládání, vyhledávání a mazání objektů (K, V)Podporuje vkládání, vyhledávání a mazání objektů (K, V) Uzel uchovává objekty, které jsou mapovány do jeho regionu, má ukazatele na Uzel uchovává objekty, které jsou mapovány do jeho regionu, má ukazatele na
sousední uzly (vzhledem k pozici v mapovaném prostoru)sousední uzly (vzhledem k pozici v mapovaném prostoru)
Zobecnění na metrické prostory - MCANZobecnění na metrické prostory - MCAN K mapování objektů (fce F) do vektorového prostoru se použije sada n pivotůK mapování objektů (fce F) do vektorového prostoru se použije sada n pivotů Objekt O je přiřazen uzlu, do jehož prostoru padne F(O)Objekt O je přiřazen uzlu, do jehož prostoru padne F(O) Vzdálenost objektů v RVzdálenost objektů v Rnn se počítá kontraktivní L se počítá kontraktivní Lmaxmax metrikou metrikou Uzel MCAN struktury obsahuje IP adresy a virtuální souřadnice zón svých sousedůUzel MCAN struktury obsahuje IP adresy a virtuální souřadnice zón svých sousedů Jednotlivé zóny se nepřekrývají, prvotní inicializace je inkrementální selekcíJednotlivé zóny se nepřekrývají, prvotní inicializace je inkrementální selekcí Dodatečné filtrování pomocí dalších pivotůDodatečné filtrování pomocí dalších pivotů
Operace v MCANOperace v MCAN
Vkládání – může začít v lib. uzlu U – vypočítá se jeho pozice ve virtuálním Vkládání – může začít v lib. uzlu U – vypočítá se jeho pozice ve virtuálním vektorovém prostou. Otestuje se, zda se nachází přímo v U, pokud ne tak se vektorovém prostou. Otestuje se, zda se nachází přímo v U, pokud ne tak se požadavek na vložení směruje na souseda, jenž je nejblíže novému objektu požadavek na vložení směruje na souseda, jenž je nejblíže novému objektu (L(Lmaxmax), což může opět vést k dalšímu směrování. Uzel do kterého se nakonec ), což může opět vést k dalšímu směrování. Uzel do kterého se nakonec objekt vložil zasílá zprávu uzlu U.objekt vložil zasílá zprávu uzlu U.
Štěpení – pokud je objekt vložen do plného uzlu, tak dojde k balancovanému Štěpení – pokud je objekt vložen do plného uzlu, tak dojde k balancovanému disjunktnímu štěpení – polovina objektů se vloží do nového uzlu (ze seznamu disjunktnímu štěpení – polovina objektů se vloží do nového uzlu (ze seznamu volných uzlů připravených k rozšíření sítě). Na závěr se aktualizuje seznam volných uzlů připravených k rozšíření sítě). Na závěr se aktualizuje seznam sousedů.sousedů.
Rozsahový dotaz – dotaz je mapován fcí F do vektorového prostoru, kde se Rozsahový dotaz – dotaz je mapován fcí F do vektorového prostoru, kde se porovná s aktuálním uzlem. V případě průniku zpracuje dotaz, jinak směruje porovná s aktuálním uzlem. V případě průniku zpracuje dotaz, jinak směruje dotaz na souseda, který je „blíže“ k regionu dotazu. Jakmile se najde průnik, dotaz na souseda, který je „blíže“ k regionu dotazu. Jakmile se najde průnik, tak se vyhodnotí dotaz (vlastní struktura na uložení dat) a přepošle se tak se vyhodnotí dotaz (vlastní struktura na uložení dat) a přepošle se sousedům, kteří také „protínají“ dotaz. Uzel předává seznam navštívených sousedům, kteří také „protínají“ dotaz. Uzel předává seznam navštívených uzlů INL, po vyhodnocení zasílá zpět volajícímu výsledek a INL rozšířený o uzlů INL, po vyhodnocení zasílá zpět volajícímu výsledek a INL rozšířený o nově kontaktované uzly. Každý dotaz má vlastní identifikátor – nedochází k nově kontaktované uzly. Každý dotaz má vlastní identifikátor – nedochází k duplicitnímu hledání v uzlech.duplicitnímu hledání v uzlech.
M-Chord – z čeho vycházíM-Chord – z čeho vychází
iDistanceiDistance Metoda pro podobnostní vyhledávání ve vektorových prostorechMetoda pro podobnostní vyhledávání ve vektorových prostorech Mapuje objekty do clusterů, pro každý vybírá referenční objekt PMapuje objekty do clusterů, pro každý vybírá referenční objekt P Každému objektu je přiřazeno číslo (iDistance key) = vzdálenost k PKaždému objektu je přiřazeno číslo (iDistance key) = vzdálenost k P Konstanta c pro oddělení clusterů -Konstanta c pro oddělení clusterů -> iDist(x) = d(p> iDist(x) = d(pii, x) + i*c, x) + i*c KlKlíče jsou ukládány v B+-treeíče jsou ukládány v B+-tree Vyhledávání – berou se pouze ty intervaly, které protne dotaz (+ další ořezání)Vyhledávání – berou se pouze ty intervaly, které protne dotaz (+ další ořezání)
Chord (P2P protokol) – lokalizace uzlu pouze O(log n) zprávChord (P2P protokol) – lokalizace uzlu pouze O(log n) zpráv Efektivní lokalizace uzlu, který obsahuje data (vzhledem k odpovídajícímu klíči)Efektivní lokalizace uzlu, který obsahuje data (vzhledem k odpovídajícímu klíči) Dynamická struktura (přidání, odebrání uzlu) založená na zasílání zprávDynamická struktura (přidání, odebrání uzlu) založená na zasílání zpráv Mapuje doménu vyhledávacích klíčů do Chord domény Mapuje doménu vyhledávacích klíčů do Chord domény [[0, 20, 2mm)) Každý Chord uzel má přiřazen klíč KKaždý Chord uzel má přiřazen klíč K ii ze stejné domény ze stejné domény [[0, 20, 2mm), uzly jsou ), uzly jsou
setříděny dle vztahu Ksetříděny dle vztahu K ii<K<Kjj <=> i<j, uzel Ni je zodpov <=> i<j, uzel Ni je zodpověědndnýý za hodnoty za hodnoty
(K(Ki-1i-1, K, Kii] mod 2] mod 2mm a obsahuje ukazatel a obsahuje ukazatele nae na n následníka a předchůdce + finger tableásledníka a předchůdce + finger table
M-ChordM-Chord
Namísto referenčních objektů se z objektů vybírají pivotiNamísto referenčních objektů se z objektů vybírají pivoti
Pomocí nich se mapují objekty do jednorozměrného prostoruPomocí nich se mapují objekty do jednorozměrného prostoru
iDistance doména představuje klíče v Chord protokolu – tzn. musí iDistance doména představuje klíče v Chord protokolu – tzn. musí se transformovat do se transformovat do [[0, 20, 2mm) pomocí uniformní hash fce h ) pomocí uniformní hash fce h zachovávající pořadí – m-chord(x) = h(zachovávající pořadí – m-chord(x) = h(d(pd(pii, x) + i*c, x) + i*c))
Každý uzel sítě je zodpovědný za interval klíčů (i více intervalů iDist)Každý uzel sítě je zodpovědný za interval klíčů (i více intervalů iDist)
Vkládání – oslovený uzel vypočítá m-chord(x) a zašle mu Vkládání – oslovený uzel vypočítá m-chord(x) a zašle mu požadavek. Po vložení uzel zašle potvrzení. Pokud dojde ke požadavek. Po vložení uzel zašle potvrzení. Pokud dojde ke štěpení, tak se přibere nový uzel a interval se rozpůlíštěpení, tak se přibere nový uzel a interval se rozpůlí
Pokud je rozsah intervalu klíčů přes více intervalů iDist tak vybírá prostřední iDist hraniciPokud je rozsah intervalu klíčů přes více intervalů iDist tak vybírá prostřední iDist hranici Jinak dělí na dvě polovinyJinak dělí na dvě poloviny
K ukládání m-chord klíčů používá BK ukládání m-chord klíčů používá B++-tree, ukládá se i vzd. k pivotům-tree, ukládá se i vzd. k pivotům
Vyhledávání – uzel spočítá k dotazu intervaly (pro všechny pivoty) a Vyhledávání – uzel spočítá k dotazu intervaly (pro všechny pivoty) a zašle zprávy uzlům k vyhodnocenízašle zprávy uzlům k vyhodnocení
PorovnáníPorovnání
Systém 300 aktivních uzlůSystém 300 aktivních uzlů Pro GHT* (VPT*) uzel 5 kapes pro 1000 objPro GHT* (VPT*) uzel 5 kapes pro 1000 obj Uzly MCAN a M-Chord s kapacitou 5000 objUzly MCAN a M-Chord s kapacitou 5000 obj
MCAN – 4 pivoty pro mapování, 40 pivotů pro filtrováníMCAN – 4 pivoty pro mapování, 40 pivotů pro filtrování
M-Chord – používá 40 pivotůM-Chord – používá 40 pivotů
Propojeno vysokorychlostní LANPropojeno vysokorychlostní LAN
Datové sady – 500.000 objektůDatové sady – 500.000 objektů 45 dim vektory (color image features), kvadratická forma45 dim vektory (color image features), kvadratická forma Názvy a podnázvy českých knížek a časopisů, editační vzdálenostNázvy a podnázvy českých knížek a časopisů, editační vzdálenost DNA sekvence délky 16, vážená editační vzdálenost (vrací hodnoty 0-100)DNA sekvence délky 16, vážená editační vzdálenost (vrací hodnoty 0-100)
Výsledky porovnáníVýsledky porovnání
ReferenceReference
Články Processing M-trees with Parallel Resources A Parallel Similarity Search in High Dimensional Metric Space Using M-Tree On Scalability of the Similarity Search in the World of Peers Fast Parallel Similarity Search in Multimedia Databases A Content–Addressable Network for Similarity Search in Metric Spaces M-Chord: A Scalable Distributed Similarity Search Structure
Knihy Similarity Search The Metric Space Approach