WEB & NFT ACADEMIE BELGIE I BLOG

"Goed genoeg" indexen voor search op web3 of de blockchain

Hoe de indexering van IPFS-search distribueren? Kunnen we bestaande algoritmen gebruiken om een systeem te maken dat "goed genoeg" is?

Index Constructie

Als index constructie gedaan moet worden voor verschillende platformen met verschillende hardware specs (volledige distributie van de zoekmachine), terwijl het toch schaalbaar moet zijn, lijkt het gebruik van single pass in-memory sorting (SPIMI) een "goed genoeg" kandidaat.

SPIMI gebruikt termen in plaats van term-id's, schrijft het woordenboek van elk blok naar schijf, en start dan een nieuw woordenboek voor het volgende blok. Anders kunnen we gebruik maken van [blocked sort-based indexing (BSBI)].

Blocked sort-based indexing heeft goede eigenschappen voor schaalbaarheid, maar heeft een datastructuur nodig om termen aan term-id te koppelen. Voor zeer grote verzamelingen past dit misschien niet in het geheugen.

PageRank en TrustRank

We kunnen bekende gedistribueerde indexeringsalgoritmen gebruiken. Het probleem is dat MapReduce taken geschreven moeten worden als acyclische dataflow programma's. In essentie, als een stateless mapper gevolgd door een stateless reducer, uitgevoerd een batch job scheduler.

Dit paradigma bemoeilijkt het herhaaldelijk bevragen van datasets en legt beperkingen op aan toepassingen voor machinaal leren (zoals we die wellicht willen gebruiken voor PageRank en TrustRank), waar iteratieve algoritmen die een enkele werkset meerdere malen bezoeken de norm zijn. Het MapReduce-model lijkt gekoppeld aan de Hadoop-infrastructuur.

Het Bulk Synchronous Parallel (BSP)-rekenmodel voor parallel programmeren kan een levensvatbaar alternatief zijn. Apache Hama implementeert BSP.

N-gram index

Pagina's en objecten komen na verloop van tijd binnen en moeten worden ingevoegd, andere pagina's en objecten zijn verwijderd en dit betekent dat ook alle indexen moeten worden gewijzigd: voor documenten betekent dit postings updates voor termen die al in het woordenboek staan, nieuwe termen aan het woordenboek moeten worden toegevoegd, en alle bijbehorende indexen zoals N-gram indexen zullen voor elk toegevoegd of verwijderd document moeten worden bijgewerkt. Dit kan gemakkelijk worden gemaakt door het maken van een hulpindex en logaritmische samenvoeging van de hoofd- en hulpindex.

De Graph

De Graph is een protocol voor het bouwen van gedecentraliseerde toepassingen met behulp van GraphQL. In essentie is de Graph een gedecentraliseerde index die over blockchains heen werkt (het kan gegevens indexeren in meerdere blockchains zoals Ethereum en BTC, maar ook op IPFS en Filecoin). Het controleert de blockchains op nieuwe gegevens en werkt de index bij telkens dit gebeurt.

Zodra de index is bijgewerkt, probeert het consensus te bereiken tussen de nodes die de index onderhouden. Zodra consensus is bereikt, zorgt het ervoor dat de gebruikers van de index de meest recente gegevens tot hun beschikking hebben. Nog niet alle problemen zijn opgelost.

Created with Mobirise ‌

Website Design Software