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

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

doi:10.1109/ICDE.2015.7113293

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

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

Web Information Systems

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

22 Citations (SciVal)

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 language	English
Title of host publication	31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015
Editors	Johannes Gehrke, Wolfgang Lehner, Kyuseok Shim, Sang Kyun Cha, Guy M. Lohman
Publisher	IEEE
Pages	303-314
Number of pages	12
DOIs	https://doi.org/10.1109/ICDE.2015.7113293
Publication status	Published - 2015
Event	ICDE 2015: International Conference on Data Engineering - Seoul, Korea, Democratic People's Republic of Duration: 13 Apr 2015 → 17 Apr 2015 Conference number: 31

Conference

Conference	ICDE 2015: International Conference on Data Engineering
Country/Territory	Korea, Democratic People's Republic of
City	Seoul
Period	13/04/15 → 17/04/15

Access to Document

10.1109/ICDE.2015.7113293

Cite this

Luo, Y., Fletcher, G. H. L., Hidders, J., & Bra, P. D. (2015). Efficient and scalable trie-based algorithms for computing set containment relations. In J. Gehrke, W. Lehner, K. Shim, S. K. Cha, & G. M. Lohman (Eds.), 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015 (pp. 303-314). IEEE. https://doi.org/10.1109/ICDE.2015.7113293

@inproceedings{157c514ef40a46a9a0ebdaa65821c6fd,

title = "Efficient and scalable trie-based algorithms for computing set containment relations",

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.",

author = "Yongming Luo and Fletcher, \{George H. L.\} and Jan Hidders and Bra, \{Paul De\}",

year = "2015",

doi = "10.1109/ICDE.2015.7113293",

language = "English",

pages = "303--314",

editor = "Johannes Gehrke and Wolfgang Lehner and Kyuseok Shim and Cha, \{Sang Kyun\} and Lohman, \{Guy M.\}",

booktitle = "31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015",

publisher = "IEEE",

address = "United States",

note = "ICDE 2015: International Conference on Data Engineering ; Conference date: 13-04-2015 Through 17-04-2015",

}

Luo, Y, Fletcher, GHL, Hidders, J & Bra, PD 2015, Efficient and scalable trie-based algorithms for computing set containment relations. in J Gehrke, W Lehner, K Shim, SK Cha & GM Lohman (eds), 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015. IEEE, pp. 303-314, ICDE 2015: International Conference on Data Engineering, Seoul, Korea, Democratic People's Republic of, 13/04/15. https://doi.org/10.1109/ICDE.2015.7113293

Efficient and scalable trie-based algorithms for computing set containment relations. / Luo, Yongming; Fletcher, George H. L.; Hidders, Jan et al.
31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015. ed. / Johannes Gehrke; Wolfgang Lehner; Kyuseok Shim; Sang Kyun Cha; Guy M. Lohman. IEEE, 2015. p. 303-314.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - Luo, Yongming

AU - Fletcher, George H. L.

AU - Hidders, Jan

AU - Bra, Paul De

N1 - Conference code: 31

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84940829290

U2 - 10.1109/ICDE.2015.7113293

DO - 10.1109/ICDE.2015.7113293

M3 - Conference contribution

SP - 303

EP - 314

BT - 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015

A2 - Gehrke, Johannes

A2 - Lehner, Wolfgang

A2 - Shim, Kyuseok

A2 - Cha, Sang Kyun

A2 - Lohman, Guy M.

PB - IEEE

T2 - ICDE 2015: International Conference on Data Engineering

Y2 - 13 April 2015 through 17 April 2015

ER -

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

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this