Bitmap filter: Speeding up exact set similarity joins with bitwise operations

作者：

Highlights：

• A novel low overhead filter (Bitmap Filter) for the exact set similarity join.

• We improved four state-of-the-art algorithms in up to 4.50× (1.35× on average).

• Bitmap Filter can be used in candidate generation or verification stages.

• Bitmap Filter was also implemented in GPUs, presenting speedups of up to 577×.

摘要

•A novel low overhead filter (Bitmap Filter) for the exact set similarity join.•We improved four state-of-the-art algorithms in up to 4.50× (1.35× on average).•Bitmap Filter can be used in candidate generation or verification stages.•Bitmap Filter was also implemented in GPUs, presenting speedups of up to 577×.

论文关键词：Set similarity join,Query processing,Data mining

论文评审过程：Received 9 February 2018, Revised 17 May 2019, Accepted 1 October 2019, Available online 11 October 2019, Version of Record 22 October 2019.

论文官网地址：https://doi.org/10.1016/j.is.2019.101449