Skip to Main content Skip to Navigation
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

https://hal.inria.fr/hal-01672052
Contributor : Bassirou Ngom <>
Submitted on : Saturday, December 23, 2017 - 12:34:46 AM
Last modification on : Friday, January 8, 2021 - 5:46:02 PM
Long-term archiving on: : Saturday, March 24, 2018 - 12:11:46 PM

File

spt_short_final-versionHal.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

233

Files downloads

259