• Optimizacija grafov in ogromno podatkov
Naročnik: Javna agencija za raziskovalno dejavnost Republike Slovenije ( N2-0053 )
Tip projekta: Raziskovalni projekti ARRS
Trajanje projekta: 2016 - 2019
  • Opis

Osnovni cilj projekta je prepoznati probleme s področja obdelave velike količine podatkov (angl Big Data) v smislu modelov za predstavitev in obdelavo grafov, dokazovanje izrekov (kromatično število, neodvisnostno število itd.), načrtovanje učinkovitih vzporednih algoritmov na grafih za reševanje tovrstnih modelov in izvedba, ki bo tekla na superračunalnikih naslednje generacije (angl. exascale computing).

Projekt bo sestavljen tako iz temeljnih raziskav kot iz aplikativnega dela, ki se bodo med seboj prepletali in dopolnjevali: aplikativni del rešuje aktualne praktične probleme, ki so praviloma enostavnejši od posplošenega problema, medtem ko temeljne raziskave iščejo izreke, ki so lahko kasneje uporabljeni za učinkovito izvedbo vzporednih algoritmov. Temeljne raziskave bodo opravljali predvsem sodelujoči iz Rényijevega Inštituta, medtem ko bo načrtovanje algoritmov pri aplikativnem delu namenjena sodelujočim iz Szegeda, Pécsi in Ljubljane. Glavno gonilo projekta bo sodelovanje in izmenjava idej med področji.

Osnovna težava pri reševanju problemov, povezanih z velikimi podatki, so računsko zahtevni, neobvladljivi problemi (NP-težki in NP-polni). Kljub temu da ni mogoče poiskati optimalne rešitve ali pa je možno izračunati optimalno rešitev le pod posebnimi pogoji, si želimo te probleme vseeno rešiti. Rešujemo jih deloma z dokazovanjem izrekov in deloma s snovanjem algoritmov, ki dajejo zadovoljive rezultate.

Pričakovani rezultati raziskav bodo pomembni na dveh področjih: Po eni strani pričakujemo pomemben doprinos k teoriji grafov in v splošnem k področju diskretne matematike. Po drugi (pogosto pomembnejši) strani bodo razviti algoritmi in metode lahko neposredno uporabljeni v praksi.
Osnovni cilj projekta je prepoznati probleme s področja obdelave velike količine podatkov (angl Big Data) v smislu modelov za predstavitev in obdelavo grafov, dokazovanje izrekov (kromatično število, neodvisnostno število itd.), načrtovanje učinkovitih vzporednih algoritmov na grafih za reševanje tovrstnih modelov in izvedba, ki bo tekla na superračunalnikih naslednje generacije (angl. exascale computing).

 

Letni obseg

0,63 FTE

 

Sodelujoče raziskovalne organizacije

Sestava projektne skupine

 

Faze projekta

Ker je bilaterala, projekt nima faz.

 

 

Bibliografske reference projekta

  • BRODNIK Andrej. Polypeptide origami. V: Abstracts, SWORDS 2017 - Szeged workshop on discrete structures, 23. 11. 2017 - 24. 11. 2017, Szeged, Hungary. Szeged: [University of Szeged]. 2017, 1 str. http://www.domlab.hu/swords2017/abstracts.html.
  • BRODNIK, Andrej, JOVIČIĆ, Vladan, PALANGETIĆ, Marko, SILADI, Daniel. Construction of Orthogonal CC-Set. V: BRODNIK, Andrej (ur.). Middle-European Conference on Applied Theoretical Computer Science (MATCOS 2016) : zbornik 19. mednarodne multikonference Informacijska družba - IS 2016, 12.-13. oktober 2016, [Ljubljana, Slovenija] = proceedings of the 19th International Multiconference Information Society - IS 2016, 12.-13 October 2016, Ljubljana, Slovenia : zvezek H = volume H. Ljubljana: Institut Jožef Stefan. 2016, str. 36-39. http://library.ijs.si/Stacks/Proceedings/InformationSociety/2016/IS2016_Volume_H%20-%20MATCOS.pdf.
  • BRODNIK, Andrej, GRGUROVIČ, Marko. Solving all-pairs shortest path by single-source computations : theory and practice. Discrete applied mathematics, ISSN 0166-218X. [Print ed.], 2017, vol. 231, str. 119-130. https://doi.org/10.1016/j.dam.2017.03.008, doi: 10.1016/j.dam.2017.03.008. [COBISS.SI-ID 1540083908], [JCR, SNIP, WoS do 31. 1. 2018: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 31. 1. 2018: št. citatov (TC): 0, čistih citatov (CI): 0]
  • ČIBEJ, Uroš, MIHELIČ, Jurij. Adaptation and evaluation of the simplex algorithm for a data-flow architecture. V: HURSON, A. R. (ur.), MILUTINOVIĆ, Veljko (ur.). Advances in computers, (Advances in computers, ISSN 0065-2458, vol. 106). 1st ed. Cambridge (MA) [etc.]: Academic Press, an imprint of Elsevier. cop. 2017, str. 63-105, ilustr. http://www.sciencedirect.com/science/article/pii/S0065245817300153, doi: 10.1016/bs.adcom.2017.04.003. [COBISS.SI-ID 1537626051], [JCR, SNIP, WoS do 17. 11. 2017: št. citatov (TC): 0, čistih citatov (CI): 0, Scopus do 3. 11. 2017: št. citatov (TC): 0, čistih citatov (CI): 0]
  • DEPOLLI, Matjaž, KONC, Janez, SZABÓ, Sándor, ZAVALNIJ, Bogdan. Usage of hereditary colorings of product graphs in clique search programs. V: BRODNIK, Andrej (ur.). Middle-European Conference on Applied Theoretical Computer Science (MATCOS 2016) : zbornik 19. mednarodne multikonference Informacijska družba - IS 2016, 12.-13. oktober 2016, [Ljubljana, Slovenija] = proceedings of the 19th International Multiconference Information Society - IS 2016, 12.-13 October 2016, Ljubljana, Slovenia : zvezek H = volume H. Ljubljana: Institut Jožef Stefan. 2016, str. 40-43. http://library.ijs.si/Stacks/Proceedings/InformationSociety/2016/IS2016_Volume_H%20-%20MATCOS.pdf. [COBISS.SI-ID 29895975]
  • DOBRAVEC, Tomaž. ALGator - an automatic algorithm evaluation system. V: BRODNIK, Andrej (ur.). Middle-European Conference on Applied Theoretical Computer Science (MATCOS 2016) : zbornik 19. mednarodne multikonference Informacijska družba - IS 2016, 12.-13. oktober 2016, [Ljubljana, Slovenija] = proceedings of the 19th International Multiconference Information Society - IS 2016, 12.-13 October 2016, Ljubljana, Slovenia : zvezek H = volume H. Ljubljana: Institut Jožef Stefan. 2016, str. 28-31, ilustr. http://library.ijs.si/Stacks/Proceedings/InformationSociety/2016/IS2016_Volume_H%20-%20MATCOS.pdf. [COBISS.SI-ID 1537311939]
  • DOBRAVEC, Tomaž, BULIĆ, Patricio. Comparing CPU and GPU implementations of a simple matrix multiplication algorithm. International journal of computer and electrical engineering, ISSN 1793-8163, Dec. 2017, vol. 9, no. 2, str. 430-438, ilustr. http://www.ijcee.org/index.php?m=content&c=index&a=show&catid=89&id=1091, doi: 10.17706/ijcee.2017.9.2.430-438. [COBISS.SI-ID 1537552067]
  • MIHELIČ, Jurij, ČIBEJ, Uroš. Experimental algorithmics for the dataflow architecture : guidelines and issues. The IPSI BGD Transactions on Advanced Research, ISSN 1820-4511, Jul. 2017, vol. 13, no. 1, str. 1-8, ilustr. http://tar.ipsitransactions.org/. [COBISS.SI-ID 1537327555]

 

 

Financerji