Skip to Main content Skip to Navigation
New interface
Conference papers

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

Abstract : 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. It also proposes 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 efficient 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 descendance relationship among Bloom filters. Second, the use of a summary prefix tree (SPT), a trie indexing data structure, for keyword-based search over DHT. Third, an 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Bassirou Ngom Connect in order to contact the contributor
Submitted on : Saturday, December 23, 2017 - 12:34:46 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:04 PM
Long-term archiving on: : Saturday, March 24, 2018 - 12:11:46 PM


Files produced by the author(s)



Bassirou Ngom, Mesaac Makpangou. Summary Prefix Tree: An over DHT Indexing Data Structure for Efficient Superset Search. NCA 2017 - 16th IEEE International Symposium on Network Computing and Applications, Oct 2017, Cambridge, MA, United States. pp.1-5, ⟨10.1109/NCA.2017.8171372⟩. ⟨hal-01672052⟩



Record views


Files downloads