SPT – Summary Prefix Tree: An over DHT Indexing Data Structure for Efficient Superset Search

Bassirou Ngom (1, 2) , Mesaac Makpangou (1) , Samba Ndiaye (2)

1 DELYS - DistributEd aLgorithms and sYStems
2 département Mathématiques Informatique

This paper presents the summary prefix tree (SPT), a trie data structure that supports efficient superset searches over DHT. Each document is summarized by a Bloom filter which is then used by SPT to index this document. SPT implements an hybrid lookup procedure that is well-adapted to sparse indexing keys such as Bloom filters. We also propose a mapping function that permits to mitigate the impact of the skewness of SPT due to the sparsity of Bloom filters, especially when they contain only few words. To perform superset searches, SPT maintains on each node a local view of the global tree. The main contributions are the following. First, the approximation of the superset relationship among keyword-sets by the descendant relationship among Bloom filters. Second, the use of a summary prefix tree, a trie indexing data structure, for keyword-based search over DHT. Third, a hybrid lookup procedure which exploits the sparsity of Bloom filters to offer good performances. Finally, an algorithm that exploits SPT to efficiently find descriptions that are supersets of query keywords.

Cet article présente un arbre de préfixes SPT, une structure de données qui permet de réaliser efficacement des recherches de sur-ensemble sur DHT. Chaque document est résumé par un filtre Bloom qui est ensuite utilisé par SPT pour indexer ce document. SPT implémente une procédure de recherche hybride qui est bien adaptée aux clés d'indexation éparses telles que les filtres Bloom. Nous proposons aussi une fonction de mapping qui atténue l'impact de l'asymétrie de SPT en raison de la rareté des bit 1 dans les filtres de Bloom, surtout lorsqu'ils ne contiennent que peu de mots. Pour effectuer des recherches de sur-ensemble, SPT maintient sur chaque noeud une vue locale de l'arbre global. Les principales contributions sont les suivantes. Premièrement, l'approximation de la relation de sur-ensemble entre les ensembles de mots-clés par la relation descendance entre les filtres Bloom. Deuxièmement, l'utilisation d'un arbre de préfixes (SPT), une structure d'indexation de données pour la recherche par mot-clé sur DHT. Troisièmement, une procédure de recherche hybride qui exploite la nature éparse des filtres Bloom pour offrir de bonnes performances. Enfin, un algorithme qui exploite SPT pour trouver efficacement des descriptions qui sont des sur-ensembles d'une requête de mots-clés.

Mots clés: SPT; Over-DHT; Data indexing; Superset search

Mots clés: Indexation des données; Recherche de sur-ensembles

Domaines: Recherche d'information [cs.IR]; Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Bassirou Ngom, Mesaac Makpangou, Samba Ndiaye. SPT – Summary Prefix Tree: An over DHT Indexing Data Structure for Efficient Superset Search. 2018. ⟨hal-01757074⟩