Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Database Modelling and Physical Database Design

Efficient Main-Memory Algorithms for Set Containment Join Using Inverted Lists

Dmitry ShaporenkovContact Information

(1)  University of Saint-Petersburg, Russia
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.

Contact Information Dmitry Shaporenkov
Email: dsha@acm.org
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.113 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)