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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
Title of host publicationIntelligent Technologies and Engineering Systems
Pages153-159
Number of pages7
DOIs
Publication statusPublished - 2013 Aug 8
Event2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012 - Changhua, Taiwan
Duration: 2012 Dec 132012 Dec 15

Publication series

NameLecture Notes in Electrical Engineering
Volume234 LNEE
ISSN (Print)1876-1100
ISSN (Electronic)1876-1119

Other

Other2012 1st International Conference on Intelligent Technologies and Engineering Systems, ICITES 2012
CountryTaiwan
CityChanghua
Period12-12-1312-12-15

Fingerprint

Graphics processing unit
Processing

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
Jhan, Syun Sheng ; Huang, Liang Tsung ; Lai, Lien Fu ; Wei, Kai Cheng ; Wei, Tsung Yu ; Wu, Chao Chin. / On mapping the sorted-set intersection problem onto a graphics processing unit. Intelligent Technologies and Engineering Systems. 2013. pp. 153-159 (Lecture Notes in Electrical Engineering).
@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",

}

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 proceedingConference 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

ER -

Jhan SS, Huang LT, Lai LF, Wei KC, Wei TY, Wu CC. On mapping the sorted-set intersection problem onto a graphics processing unit. In Intelligent Technologies and Engineering Systems. 2013. p. 153-159. (Lecture Notes in Electrical Engineering). https://doi.org/10.1007/978-1-4614-6747-2_19