Image of an arrow

Épisode 1 : Les arbres préfixes (PHT) comme moteur de recherche

Avatar

admin_sflinux

OpenDHT est un système distribué public permettant d’indexer des données sous la forme de paire clé – valeur. La clé représente un identifiant unique et la valeur est le contenant de la donnée.

OpenDHT peut stocker des valeurs tout en répartissant les données sur l’ensemble des nœuds du réseau. La librairie est basée sur l’algorithme « Kademlia » introduit par Maymounkov et Mazières.

technology-x-binary-and-backgrounds-541917

OpenDHT innove en implémentant de nouvelles fonctionnalités comme listen : une opération de notification à la réception de nouvelles valeurs annoncées sur le réseau. Toutefois, les tables de hachage distribuées (DHT) offrent la possibilité d’effectuer uniquement des recherches exactes, sur une clef-précise. Or, l’un des principaux problèmes auxquels le logiciel Ring fait face est la recherche d’utilisateurs. Voici pourquoi l’équipe Ring et une équipe de l’UQAM ont travaillé à la recherche d’une solution pour ce problème.

Le solution utilisée: La PHT ou Prefix Hash Tree

capture2

La solution est inspirée d’un article intitulé Prefix Hash Tree : An Indexing Data Structure over Distributed hash Tables. L’objectif est de créer un arbre dont la structure représente l’information qu’on y ajoute. Les feuilles stockent les clés et les liens de l’arbre servent au routage logique. Le tout repose sur le réseau distribué de la DHT. Cette structure permet une recherche basée sur des mots clefs.

On peut également noter la possibilité de faire exister plusieurs arbres préfixes sur un même réseau. Ce qui servirait par la suite à indexer d’autres données comme des profils Ring ou des services tiers. Il est à noter que l’utilisation du PHT n’est soumise à aucune limitation. En effet, dans un contexte différent, on peut très bien imaginer l’indexation de blogs, d’appareils connectés (domotique), etc.

Cas pratique sur la PHT

Un utilisateur A souhaite rechercher un utilisateur B dont l’identifiant Ring est le suivant : ring:9ad22cac841bed877b8d5f65d4fb2d44bda7fdc4. L’utilisateur A pourra utiliser le PHT pour rechercher l’utilisateur B grâce à des mots clefs comme son prénom, son nom, sa ville de résidence, etc.

À suivre….épisode 2 : l’optimisation des requêtes sur la PHT! 

Comments are closed.


Articles similaires

Image of an arrow

Parce que l’UX ne se limite pas au monde connecté, si vous allez un jour à Miami et que vous devez prendre le train, ne cherchez pas plus loin : optez pour la Brightline. Ce réseau ferroviaire a su inclure l’UX et l’expérience client dans son processus et rend le train extrêmement agréable à emprunter. […]

Avatar
17 Oct. 2018 Lecture de 2 minutes.

Tout le monde UX, abrégé TLM UX, est le rendez-vous UX (User Expericence – Expérience Utilisateur) de la scène Montréalaise. Proposant des conférences sur le sujet tous les 2 mois, TLM UX organise des rencontres entre passionnés, professionnels ou tout simplement curieux du domaine de l’expérience utilisateur. Ayant comme partenaires des grands noms d’agence de […]

Avatar
20 Août. 2018 Lecture de 3 minutes.

Du 28 juillet au 5 août, l’un des membres de notre équipe, Hugo Lefeuvre (également un développeur Debian dans son temps libre), a participé à la DebConf18.  Ceci est LE regroupement annuel de la communauté Debian, à Hsinchu, Taïwan.  Au cours de la semaine, Hugo a passé du temps à préparer sa conférence sur Ring, à […]

Avatar
15 Août. 2018 Lecture de 2 minutes.
Thumbnail image

Travailler chez Savoir-faire Linux, c’est rejoindre 145 experts qui contribuent à la réalisation d’un monde plus libre, mais aussi plus responsable. «Avec une dimension internationale très forte, nous souhaitons attirer en France et au Canada des talents passionnés par leur métier, contribuant déjà aux communautés du libre et ayant à cœur de résoudre les problématiques […]

Avatar
11 Mar. 2018 Lecture de 6 minutes.
Thumbnail image

  Savoir-faire Linux et le CTIC célèbrent les premières cohortes de diplômés dans le cadre de l’Initiative de Numérisation des Petites Entreprises (INPE). Les premiers étudiants ont commencé en janvier dernier le programme de six mois pour devenir la prochaine génération de leaders de la transformation digitale des petites entreprises en Ontario, dans le cadre […]

Avatar
11 Mar. 2018 Lecture de 4 minutes.
Fermer
Fermer