Techniques for data-parallel searching for duplicate elements

Brenton Lessley; Kenneth Moreland; Matthew Larsen; Hank Childs

doi:10.1109/LDAV.2017.8231845

Techniques for data-parallel searching for duplicate elements

Brenton Lessley, Kenneth Moreland, Matthew Larsen, Hank Childs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

We study effective shared-memory, data-parallel techniques for searching for duplicate elements. We consider several data-parallel approaches, and how hash function, machine architecture, and data set can affect performance. We conclude that most choices of algorithm and hash function are problematic for general usage. However, we demonstrate that the choice of the Hash-Fight algorithm with the FNV1a hash function has consistently good performance over all configurations.

Original language	English
Title of host publication	2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-5
Number of pages	5
ISBN (Electronic)	9781538606179
DOIs	https://doi.org/10.1109/LDAV.2017.8231845
State	Published - Dec 19 2017
Externally published	Yes
Event	7th IEEE Symposium on Large Data Analysis and Visualization, LDAV 2017 - Phoenix, United States Duration: Oct 2 2017 → …

Publication series

Name	2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017
Volume	2017-December

Conference

Conference	7th IEEE Symposium on Large Data Analysis and Visualization, LDAV 2017
Country/Territory	United States
City	Phoenix
Period	10/2/17 → …

Access to Document

10.1109/LDAV.2017.8231845

Cite this

Lessley, B., Moreland, K., Larsen, M., & Childs, H. (2017). Techniques for data-parallel searching for duplicate elements. In 2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017 (pp. 1-5). (2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017; Vol. 2017-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/LDAV.2017.8231845

@inproceedings{2bc54537b1884dac89bb68d8a70a00d0,

title = "Techniques for data-parallel searching for duplicate elements",

abstract = "We study effective shared-memory, data-parallel techniques for searching for duplicate elements. We consider several data-parallel approaches, and how hash function, machine architecture, and data set can affect performance. We conclude that most choices of algorithm and hash function are problematic for general usage. However, we demonstrate that the choice of the Hash-Fight algorithm with the FNV1a hash function has consistently good performance over all configurations.",

author = "Brenton Lessley and Kenneth Moreland and Matthew Larsen and Hank Childs",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 7th IEEE Symposium on Large Data Analysis and Visualization, LDAV 2017 ; Conference date: 02-10-2017",

year = "2017",

month = dec,

day = "19",

doi = "10.1109/LDAV.2017.8231845",

language = "English",

series = "2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1--5",

booktitle = "2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017",

}

Lessley, B, Moreland, K, Larsen, M & Childs, H 2017, Techniques for data-parallel searching for duplicate elements. in 2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017. 2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017, vol. 2017-December, Institute of Electrical and Electronics Engineers Inc., pp. 1-5, 7th IEEE Symposium on Large Data Analysis and Visualization, LDAV 2017, Phoenix, United States, 10/2/17. https://doi.org/10.1109/LDAV.2017.8231845

Techniques for data-parallel searching for duplicate elements. / Lessley, Brenton; Moreland, Kenneth; Larsen, Matthew et al.
2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1-5 (2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017; Vol. 2017-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Techniques for data-parallel searching for duplicate elements

AU - Lessley, Brenton

AU - Moreland, Kenneth

AU - Larsen, Matthew

AU - Childs, Hank

PY - 2017/12/19

Y1 - 2017/12/19

N2 - We study effective shared-memory, data-parallel techniques for searching for duplicate elements. We consider several data-parallel approaches, and how hash function, machine architecture, and data set can affect performance. We conclude that most choices of algorithm and hash function are problematic for general usage. However, we demonstrate that the choice of the Hash-Fight algorithm with the FNV1a hash function has consistently good performance over all configurations.

AB - We study effective shared-memory, data-parallel techniques for searching for duplicate elements. We consider several data-parallel approaches, and how hash function, machine architecture, and data set can affect performance. We conclude that most choices of algorithm and hash function are problematic for general usage. However, we demonstrate that the choice of the Hash-Fight algorithm with the FNV1a hash function has consistently good performance over all configurations.

UR - http://www.scopus.com/inward/record.url?scp=85048417773&partnerID=8YFLogxK

U2 - 10.1109/LDAV.2017.8231845

DO - 10.1109/LDAV.2017.8231845

M3 - Conference contribution

AN - SCOPUS:85048417773

T3 - 2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017

SP - 1

EP - 5

BT - 2017 IEEE 7th Symposium on Large Data Analysis and Visualization, LDAV 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 7th IEEE Symposium on Large Data Analysis and Visualization, LDAV 2017

Y2 - 2 October 2017

ER -

Techniques for data-parallel searching for duplicate elements

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this