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

Y. Luo, G.H.L. Fletcher, A.J.H. Hidders, P.M.E. De Bra

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

20 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Titel2015 IEEE 31st International Conference on Data Engineering (ICDE, Seoul, South Korea, April 13-17, 2015)
Plaats van productiePiscataway NJ
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's303-314
ISBN van geprinte versie978-1-4799-7964-6
DOI's
StatusGepubliceerd - 2015
Evenement31st IEEE International Conference on Data Engineering (ICDE 2015), April 13-17, 2015, Seoul, South Korea - Seoul, Zuid-Korea
Duur: 13 apr. 201517 apr. 2015

Congres

Congres31st IEEE International Conference on Data Engineering (ICDE 2015), April 13-17, 2015, Seoul, South Korea
Verkorte titelICDE 2015
Land/RegioZuid-Korea
StadSeoul
Periode13/04/1517/04/15
Ander2015 IEEE 31st International Conference on Data Engineering

Vingerafdruk

Duik in de onderzoeksthema's van 'Efficient and scalable trie-based algorithms for computing set containment relations'. Samen vormen ze een unieke vingerafdruk.

Citeer dit