Efficient and scalable trie-based algorithms for computing set containment relations

Yongming Luo, George H. L. Fletcher, Jan Hidders, Paul De Bra

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

19 Citations (Scopus)

Abstract

Computing containment relations between massive collections of sets is a fundamental operation in data management, for example in graph analytics and data mining applications. Motivated by recent hardware trends, in this paper we present two novel solutions for computing set-containment joins over massive sets: the Patricia Trie-based Signature Join (PTSJ) and PRETTI+, a Patricia trie enhanced extension of the state-of-the-art PRETTI join. The compact trie structure not only enables efficient use of main-memory, but also significantly boosts the performance of both approaches. By carefully analyzing the algorithms and conducting extensive experiments with various synthetic and real-world datasets, we show that, in many practical cases, our algorithms are an order of magnitude faster than the state-of-the-art.
Original languageEnglish
Title of host publication31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015
EditorsJohannes Gehrke, Wolfgang Lehner, Kyuseok Shim, Sang Kyun Cha, Guy M. Lohman
PublisherIEEE
Pages303-314
Number of pages12
DOIs
Publication statusPublished - 2015
EventICDE 2015: International Conference on Data Engineering - Seoul, Korea, Democratic People's Republic of
Duration: 13 Apr 201517 Apr 2015
Conference number: 31

Conference

ConferenceICDE 2015: International Conference on Data Engineering
Country/TerritoryKorea, Democratic People's Republic of
CitySeoul
Period13/04/1517/04/15

Fingerprint

Dive into the research topics of 'Efficient and scalable trie-based algorithms for computing set containment relations'. Together they form a unique fingerprint.

Cite this