On mapping the sorted-set intersection problem onto a graphics processing unit

Syun Sheng Jhan; Liang Tsung Huang; Lien Fu Lai; Kai Cheng Wei; Tsung Yu Wei; Chao Chin Wu

doi:10.1007/978-1-4614-6747-2_19

On mapping the sorted-set intersection problem onto a graphics processing unit

Syun Sheng Jhan, Liang Tsung Huang, Lien Fu Lai, Kai Cheng Wei, Tsung Yu Wei, Chao Chin Wu

Department of Computer Science and Information Engineering

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

Abstract

The sorted-set intersection problem is important because it plays a key role in many algorithms. Instead of processing multiple short sorted-set intersections concurrently in previous work, this work focuses on how to efficiently find the intersection from two long sorted sets using emerging general-purpose graphics processing units (GPUs). We have implemented and evaluated four different algorithms to solve the set intersection problem. According to the experimental results, we identify which algorithm is the best choice based on the problem size.

Original language	English
Title of host publication	Intelligent Technologies and Engineering Systems
Pages	153-159
Number of pages	7
DOIs	https://doi.org/10.1007/978-1-4614-6747-2_19
Publication status	Published - 2013 Aug 8
Event	2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012 - Changhua, Taiwan Duration: 2012 Dec 13 → 2012 Dec 15

Publication series

Name	Lecture Notes in Electrical Engineering
Volume	234 LNEE
ISSN (Print)	1876-1100
ISSN (Electronic)	1876-1119

Other

Other	2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012
Country	Taiwan
City	Changhua
Period	12-12-13 → 12-12-15

Fingerprint

All Science Journal Classification (ASJC) codes

Industrial and Manufacturing Engineering

Cite this

Jhan, S. S., Huang, L. T., Lai, L. F., Wei, K. C., Wei, T. Y., & Wu, C. C. (2013). On mapping the sorted-set intersection problem onto a graphics processing unit. In Intelligent Technologies and Engineering Systems (pp. 153-159). (Lecture Notes in Electrical Engineering; Vol. 234 LNEE). https://doi.org/10.1007/978-1-4614-6747-2_19

@inproceedings{75e956be627344899750f545a8036384,

title = "On mapping the sorted-set intersection problem onto a graphics processing unit",

abstract = "The sorted-set intersection problem is important because it plays a key role in many algorithms. Instead of processing multiple short sorted-set intersections concurrently in previous work, this work focuses on how to efficiently find the intersection from two long sorted sets using emerging general-purpose graphics processing units (GPUs). We have implemented and evaluated four different algorithms to solve the set intersection problem. According to the experimental results, we identify which algorithm is the best choice based on the problem size.",

author = "Jhan, {Syun Sheng} and Huang, {Liang Tsung} and Lai, {Lien Fu} and Wei, {Kai Cheng} and Wei, {Tsung Yu} and Wu, {Chao Chin}",

year = "2013",

month = "8",

day = "8",

doi = "10.1007/978-1-4614-6747-2_19",

language = "English",

isbn = "9781461467465",

series = "Lecture Notes in Electrical Engineering",

pages = "153--159",

booktitle = "Intelligent Technologies and Engineering Systems",

note = "2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012 ; Conference date: 13-12-2012 Through 15-12-2012",

}

Jhan, SS, Huang, LT, Lai, LF , Wei, KC, Wei, TY & Wu, CC 2013, On mapping the sorted-set intersection problem onto a graphics processing unit. in Intelligent Technologies and Engineering Systems. Lecture Notes in Electrical Engineering, vol. 234 LNEE, pp. 153-159, 2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012, Changhua, Taiwan, 12-12-13. https://doi.org/10.1007/978-1-4614-6747-2_19

On mapping the sorted-set intersection problem onto a graphics processing unit. / Jhan, Syun Sheng; Huang, Liang Tsung; Lai, Lien Fu ; Wei, Kai Cheng; Wei, Tsung Yu; Wu, Chao Chin.

Intelligent Technologies and Engineering Systems. 2013. p. 153-159 (Lecture Notes in Electrical Engineering; Vol. 234 LNEE).

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

TY - GEN

T1 - On mapping the sorted-set intersection problem onto a graphics processing unit

AU - Jhan, Syun Sheng

AU - Huang, Liang Tsung

AU - Lai, Lien Fu

AU - Wei, Kai Cheng

AU - Wei, Tsung Yu

AU - Wu, Chao Chin

PY - 2013/8/8

Y1 - 2013/8/8

N2 - The sorted-set intersection problem is important because it plays a key role in many algorithms. Instead of processing multiple short sorted-set intersections concurrently in previous work, this work focuses on how to efficiently find the intersection from two long sorted sets using emerging general-purpose graphics processing units (GPUs). We have implemented and evaluated four different algorithms to solve the set intersection problem. According to the experimental results, we identify which algorithm is the best choice based on the problem size.

AB - The sorted-set intersection problem is important because it plays a key role in many algorithms. Instead of processing multiple short sorted-set intersections concurrently in previous work, this work focuses on how to efficiently find the intersection from two long sorted sets using emerging general-purpose graphics processing units (GPUs). We have implemented and evaluated four different algorithms to solve the set intersection problem. According to the experimental results, we identify which algorithm is the best choice based on the problem size.

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

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

U2 - 10.1007/978-1-4614-6747-2_19

DO - 10.1007/978-1-4614-6747-2_19

M3 - Conference contribution

AN - SCOPUS:84881034838

SN - 9781461467465

T3 - Lecture Notes in Electrical Engineering

SP - 153

EP - 159

BT - Intelligent Technologies and Engineering Systems

T2 - 2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012

Y2 - 13 December 2012 through 15 December 2012

ER -

Access to Document

10.1007/978-1-4614-6747-2_19