Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Soft Computing
Erschienen in: Soft Computing 22/2018

30.01.2018 | Foundations

Efficient parallel algorithm for computing rough set approximation on GPU

verfasst von: Si-Yuan Jing, Gong-Liang Li, Kai Zeng, Wei Pan, Cai-Ming Liu

Erschienen in: Soft Computing | Ausgabe 22/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Computation of rough set approximation (RSA) is a critical step for attribute reduction and knowledge acquisition in rough set theory. Continuously improving computation efficiency of RSA is very meaningful, because it can enhance user experience of existing applications. Furthermore, it is helpful to apply rough sets to some fields with high performance requirement. Graphics processing unit (GPU) has gained a lot of attention from scientific communities for its applicability in high-performance computing. Different from existing works, this paper tries to apply GPU to accelerate a state-of-the-art serial algorithm of RSA computation, which is based on radix sorting. Three key steps of the serial algorithm are parallel designed, including object sorting, computation of equivalence classes, and computation of RSA. The experimental results show that the parallel method can accelerate the computation process efficiently.
Vorheriger Artikel Stratified L-prefilter convergence structures in stratified L-topological spaces
Nächster Artikel A belief rule-based expert system to assess suspicion of acute coronary syndrome (ACS) under uncertainty

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
Balamash AS, Pedrycz W, -Hmouz RA et al (2017) Granular classifiers and their design through refinement of information granules. Soft Comput 21(10):2745–2759CrossRef
Chen HM, Li TR, Ruan D et al (2013) A rough-set-based incremental approach for updating approximations under dynamic maintenance environments. IEEE Trans Knowl Data Eng 25(2):274–284CrossRef
Cheng Y (2011) The incremental method for fast computing the rough fuzzy approximations. Data Knowl Eng 70(1):84–100CrossRef
David K, Hwu WM (2010) Programming massively parallel processors: a hand-on approach. Morgan Kaufmann Publishers Inc., San Francisco
Dean J, Ghemawat S (2008) Mapreduce: simplified data processing on large clusters. Commun ACM 51(1):107–113CrossRef
Deng DY, Yan DX, Wang JY (2010) Parallel reducts based on attribute significance. In: Yu J, Greco S, Lingras P et al (eds) Rough Set and Knowledge Technology, vol 6401. Lecture Notes in Computer Science. Springer, Berlin, pp 336–343CrossRef
Fan A, Zhao H, Zhu W (2016) Test-cost-sensitive attribute reduction on heterogeneous data for adaptive neighborhood model. Soft Comput 20(12):4813–4824CrossRef
Harris M, Sengupta S, Owens JD (2007) Parallel prefix sum (scan) with CUDA. In: Nguyen H (ed) GPU gems 3. Addison Wesley, Reading
Hu QH, Xie ZX, Yu DR (2007) Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation. Pattern Recognit 40(22):3509–3521CrossRef
Hu QH, Yu DR, Liu JF et al (2008) Neighborhood rough set based heterogeneous feature subset selection. Inf Sci 178(18):3577–3594MathSciNetCrossRef
Jensen R, Shen Q (2004) Fuzzy-rough attribute reduction with application to web categorization. Fuzzy Sets Syst 131(3):469–485MathSciNetCrossRef
Jing SY (2014) A hybrid genetic algorithm for feature subset selection in rough set theory. Soft Comput 18(7):1373–1382CrossRef
Jing SY, Ali S, She K et al (2013) State-of-the-art research study for green cloud computing. J Supercomput 65(1):445–468CrossRef
Li TR, Ruan D, Wets G et al (2007) A rough sets based characteristic relation approach for dynamic attribute generalization in data mining. Knowl Based Syst 20(5):485–494CrossRef
Li SY, Li TR, Zhang ZX et al (2015) Parallel computing of approximations in dominance-based rough sets approach. Knowl Based Syst 87:202–211CrossRef
Liang JY, Qian YH (2008) Information granules and entropy theory in information systems. Sci China Ser F Inf Sci 51(10):1427–1444MathSciNetCrossRef
Liang JY, Wang F, Dang CY et al (2012) An efficient rough feature selection algorithm with a multi-granulation view. Int J Approx Reason 53:912–926MathSciNetCrossRef
Lindholm E, Nickolls J, Oberman S (2008) Nvidia tesla: a unified graphics and computing architecture. IEEE Micro 28(2):39–55CrossRef
Min F, He HP, Qian YH et al (2011) Test-cost-sensitive attribute reduction. Inf Sci 181(22):4928–4942CrossRef
Pawlak Z (1991) Rough sets, theoretical aspects of reasoning about data. Kluwer Academic Publishers, DordrechtMATH
Pedrycz W (2001) Granular computing: an introduction. In: IFSA world congress & NAFIPS international conference
Pedrycz W, Al-Hmouz R, Balamash AS et al (2017) Modeling with linguistic entities and linguistic descriptors: a perspective of granular computing. Soft Comput 21(7):1833–1845CrossRef
Qian YH, Liang JY, Dang CY (2010a) Incomplete multigranulation rough set. IEEE Trans Syst Man Cybern Part A 40(2):420–431CrossRef
Qian YH, Liang JY, Pedrycz W et al (2010b) Positive approximation: an accelerator for attribute reduction in rough set theory. Artif Intell 174(9–10):597–618MathSciNetCrossRef
Qian J, Miao DQ, Zhang ZH (2011) Knowledge reduction algorithms in cloud computing. Chin J Comput 34(12):2332–2342CrossRef
Qian J, Miao DQ, Zhang ZH et al (2014) Parallel attribute reduction algorithms using MapReduce. Inf Sci 279:671–690MathSciNetCrossRef
Ryoo S, Rodrigues CI, Baghsorkhi SS et al (2008) Optimization principles and application performance evaluation of a multi-threaded GPU using CUDA. In: Proceedings of the PPoPP’08, pp 73–82
Satish N, Harris M, Garland M (2009) Designing efficient sorting algorithms for manycore GPUs. In: Proceedings of the IPDPS’09, pp 1–10
Susmaga R (2004) Tree-like parallelization of reduct and construct computation. In: Tsumoto S et al (eds) RSCTC 2004, LNAI 3066, Springer, Berlin, pp 455–464CrossRef
Tay FEH, Shen L (2002) Economic and financial prediction using rough sets model. Eur J Oper Res 141(3):641–659CrossRef
Tsumoto S (2004) Mining diagnostic rules from clinical databases using rough sets and medical diagnostic model. Inf Sci 162(2):65–80MathSciNetCrossRef
Wang GY, Yu H, Yang DC (2002) Decision table reduction based on conditional information entropy. Chin J Comput 25(7):759–766MathSciNet
Xu ZY, Liu ZP, Yang BR et al (2006) A quick attribute reduction algorithm with complexity of max(\(O|C, U|, O|C|^{2}|U/C|\)). Chi J Comput 29(3):391–399
Yu J, Yang Y (2016) Minimal attribute reduction with rough set based on compactness discernibility information tree. Soft Computing 20(6):2233–2243CrossRef
Zeng K (2016) Preference mining using neighborhood rough set model on two universes. Comput Intell Neurosci (Public online)
Zhang JB, Li TR, Ruan D et al (2012) A parallel method for computing rough set approximations. Inf Sci 194:209–223CrossRef
Zhang JB, Wong JS, Pan Y et al (2015) A parallel matrix-based method for computing approximations in incomplete information systems. IEEE Trans Knowl Data Eng 27(2):326–339CrossRef
Zhang JB, Zhu Y, Li TR et al (2016) Efficient parallel Boolean matrix based algorithms for computing composite rough set approximations. Inf Sci 329:287–302CrossRef
Zhu XZh, Zhu W, Fan XN (2017) Rough set methods in feature selection via submodular function. Soft Comput 21(13):3699–3711CrossRef
Metadaten
Titel
Efficient parallel algorithm for computing rough set approximation on GPU
verfasst von
Si-Yuan Jing
Gong-Liang Li
Kai Zeng
Wei Pan
Cai-Ming Liu
Publikationsdatum
30.01.2018
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 22/2018
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-018-3050-z

Weitere Artikel der Ausgabe 22/2018

Soft Computing 22/2018 Zur Ausgabe

Focus

A scientific decision-making framework for supplier outsourcing using hesitant fuzzy information

Focus

A hybrid genetic algorithm and DEA approach for multi-criteria fixed cost allocation

Editorial

Multi-Criteria Decision-Making: advances in theory and applications—an introduction to the special issue

Focus

Acceptably consistent incomplete interval-valued intuitionistic multiplicative preference relations

Focus

Beyond precision: accelerated life testing for fuzzy life time data

Foundations

Stratified L-prefilter convergence structures in stratified L-topological spaces