Title

An evaluation between Bloom Filter join and PERF join in Distributed Query Processing

Date of Award

2008

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Morrissey, Joan (School of Computer Science)

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

Abstract

Nowadays, with the explosion of information and the telecommunication era's coming, more and more huge applications encourage decentralization of data while accessing data from different sites [HFB00]. The process of retrieving data from different sites called Distributed Query Processing. The objective of distributed query optimization is to find the most cost-effective of executing query across the network [OV99]. Semijoin [BC81] [BG+81] is known as an effective operator to eliminate the tuples of a relation which are not contributive to a query. 2-way semijoin [KR87] is an extended version of semijoin which not only performs forward reduction like traditional semijoin does, but also provides backward reduction always in cost-effective way. Bloom Filter[B70] and PERF [LR95] are 2 filter based techniques which use a bit vector to represent of the original join attributes projection during the data transmission. Compare with generating a bit array with hash function in bloom filter, Perf join is based on the tuples scan order to avoid losing information caused by hash collision. In the thesis, we will apply both bloom filter and pert on 2-way semijoin algorithms to reduce transmission cost of distributed queries. Performance of propose algorithms will compare against each others and IFS (Initial Feasible Solution) through amount of experiments. 'Keywords:' Distributed Query Processing, Semijoin, Bloom Filter, Perf Join.