Paper Info
Title
Efficient main-memory algorithms for set containment join using inverted lists
Abstract
We present two algorithms for set containment joins based on inverted lists. The first algorithm scans the left relation and determines for each tuple all the qualifying tuples by querying the inverted file for the right relation. The second algorithm employs the common inverted file for both relations. We focus on improving performance of algorithms in main memory by reducing number of L2 cache misses which is achieved by applying such techniques as partitioning and compression. We study algorithms analytically and experimentally and determine which one is better depending on parameters of the input relations. We also demonstrate that both algorithms are superior to some other known methods for set containment joins.
Year
DOI
Venue
2005
10.1007/11547686_11
ADBIS
Keywords
Field
DocType
inverted list,left relation,algorithms analytically,efficient main-memory algorithm,known method,common inverted file,right relation,input relation,set containment,inverted file,l2 cache
Information system,Joins,Database query,CPU cache,Computer science,Theoretical computer science,Distributed computing,Inverted index,Tuple,Algorithm,Database,Containment,Hash table
Conference
Volume
ISSN
ISBN
3631
0302-9743
3-540-28585-7
Citations 
PageRank 
References 
0
0.34
10
Authors
1
Name
Order
Citations
PageRank
Dmitry Shaporenkov1303.73