Algorithms for Big Data Analytics  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
105645
Type NK
Principal investigator Rónyai, Lajos
Title in Hungarian Nagyléptékű adatok algoritmikus analízise
Title in English Algorithms for Big Data Analytics
Keywords in Hungarian algoritmusok, bonyolultság, elosztott architektúrák, adatbányászat
Keywords in English algorithms, complexity, distributed architectures, data mining
Discipline
Computing Science (Council of Physical Sciences)70 %
Mathematics (Council of Physical Sciences)30 %
Ortelius classification: Algorithms
Panel Mathematics and Computing Science
Department or equivalent Computer and Automation Research Institute HAS
Participants Benczúr, András
Bernáth, Attila
Csaba, Ákos
Daróczy, Bálint
Demetrovics, János
Dudás, László
Fehér, Judit
Fekete, Zsolt
Geszler, Döme
Ivanyos, Gábor
Kiss, Viktor
Kocsis, Levente
Kós, Géza
Marx, Dániel
Molnár, András
Pap, Júlia
Petrás, István
Sidló, Csaba István
Szabó, Adrienn
Szőnyi, Tamás
Szőnyi, Tamás
Starting date 2012-09-01
Closing date 2016-08-31
Funding (in million HUF) 69.728
FTE (full time equivalent) 26.77
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

Az üzleti intelligencia, e-tudomány és a Web elemzés mind extrém nagy adatelemzési problémákat rejt. Célunk, hogy mély elméleti alapokra építve hatékony, a kialakulóban levő elosztott infrastruktúrákat kiaknázó megoldásokat keressünk.

Új alapkutatási eredményeket kívánunk elérni a következő területeken:
- Web adatok, közösségi média vizsgálata;
- Tartalom alapú képkeresés és klasszifikáció;
- Hatékony elosztott adattárházak;
- Nagy közlekedési és mobilitási adatok feldolgozása.

Célunk a meglevő technológiákon túllépve új, az elosztott és a sokmagos technológiákat kombináló algoritmikus keretek kutatása, és az alkalmazási területeken áttörést elérő interdiszciplináris eredmények elérése. A kapcsolódó területek: adatbázisok elmélete, algoritmusok és bonyolultság, keresőtechnológiák, adatbányászat és gépi tanulás.

Kutatásunk a közelítési és futási idő becsléseken alapuló elméleti és az alkalmazások igényeit megvalósító, heurisztikus módszerek keveréke, kiegészítve a valós adatokon történő kísérletezéssel és méréssel.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

Az "extrém nagy" vagy "óriás" adat fogalma arra utal, amikor a gyűjtés, tárolás,
kezelés és elemzés meghaladja a szokásos hardver és szoftver eszközök képességeit. A közösségi média vagy a telekommunikáció adatai gyakran több nagyságrenddel nagyobbak, mint a "nagy adatok" kora előttkeletkezett bármilyen adathalmaz. Miközben egy évtizeddel ezelőttig nem sok gyakorlati alkalmazás találta magát pár 10,000-nél több csúcsú gráfokkal, a közösségi kapcsolatok gráfjai legalább 3, de néha 5-6 nagyságrenddel is nagyobbak ennél. Ezeken a gráfokon a lineárisnál lassabb algoritmusok lényegében használhatatlanok. Ebben a helyzetben olyan, tipikusan közelítő és elosztott algoritmusokat keresünk elosztott architektúrákon, mint pl. a Hadoop vagy az S4. A jövőbeli alkalmazások szempontjából mindegyik esetben a skálázhatóság a kulcskérdés.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A föld lakosságának 60%-a, mintegy négymilliárd ember használ mobiltelefont. Ebből 12%-ot tesz ki az okostelefonok használata, amely évente 20%-kal növekszik. Összességében több, mint 30 milliárd elemből áll a közlekedés, jármű, ipar, szolgáltatások és kereskedelem szektoraiban elhelyezett szenzorhálózat, és ez a mennyiség évente 30%-kal növekszik. A mobil eszközökből és szenzorokból származó adatokra úgy tekinthetünk, mint egy nagy, a közösség interakcióit leíró médiumra. A szenzoradatok gyakran megjelennek a közösségi kapcsolatainkban, például amikor a Facebook, Foursquare vagy a Gowalla rögzíti a felhasználó okostelefonjának geo-koordinátáit.

További új jelenség, hogy az adatok nagyon nagy gyakorisággal keletkeznek és a statikus elemzésük reménytelen vállalkozás. Például a Twitter, Facebook üzeletek, vagy a mobilitási adatok nyaktörő sebességgel érkeznek és analízisük, tisztításuk, tárolásuk és kategorizálásuk csak azonnali, adaptív módszerekkel történhet. Ezen felül a közösségi kapcsolatok azonnali reakciót igényelnek, függetlenül a mögötte elhelyezkedő óriási adatmennyiségtől - mindaddig, amíg algoritmusaink képesek az információfolyammal megküzdve megfelelő válasz és reakcióidőt elérni.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média illetve az adófizetők tájékoztatása szempontjából különösen fontos az NKFI számára.

A közösségi média, online és mobil szolgáltatások, és a szenzorhálózatok robbanásszerű elterjedésével óriási adatmennyiségek gyűlnek össze, amelyeket továbbá nagyfokú heterogenitás és nagyon széles hatókör jellemez. Heterogenitás alatt azt értjük, hogy nagyon sokféle típusú adat: hely és idő koordináták, szenzor idősorok, emberi kommunikáció, fényképek, szöveges üzenetek, blogok, tweetek, Wiki tartalmak, hírek keletkeznek. Széles hatókör alatt pedig azt értjük, hogy manapság a földön lényegében minden emberi és természeti aktivitásról keletkezik valamilyen adat, amely aranybánya lehet az intelligens, megbízható döntéshozatal számára.

Hatalmas kihívást jelent az, hogy a meglevő óriási adatokból kivonjuk a tudást és ezt a hatékony döntéshozatal szolgálatába állítsuk. Részben az információs túltelítődés jelent gondot: gyakran éppen azért nem tudunk dönteni, mert már nem tudjuk átlátni a rendelkezésre álló adatok tömegét.

A hálózati számítások soha nem látott adatméreteket hoznak létre: a World Wide Web több Petabyte információt tartalmaz; a Google 1 Petabyte adatot mindössze 6 óra alatt képes rendezni; a Walmart áruházlánc termékadatbázisa 24 Terabyte, hogy csak pár példát említsünk. Miközben a hardver sebessége és kapacitása folyamatosan növekszik, a háttértárolók (diszkek) sebessége alig változott az elmúlt években. Éppen ezért célunk az óriási adatokból tudás kinyerésére alkalmas módszerek kutatása.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

Business intelligence, e-science and Web mining are rapidly growing sources of extreme large scale problems. We aim to design efficient methods for these problems based on deep theoretical foundations and relying on emerging means of distributed or many-core architectures.

We expect new basic research results in the following areas:
- Web data and social network analysis;
- Content based image retrieval;
- Efficiency of distributed data warehouses for log processing and entity resolution;
- Handling mass data of transport and mobility.

We pass beyond existing technologies in designing new frameworks, combining distributed and multicore technologies, and seeking new, breakthrough applications in an interdisciplinary research of
interrelated fields in Database Technologies, Theory of Algorithms, Search and Information Retrieval as well as
Data Mining and Machine Learning. Our research is a mixture of theoretical bounds for approximation error and running time, models and heuristics for solving practical problems, and measurements on real life data.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

The expressions "Large-Scale Data" or "Big Data" refer to datasets whose size is beyond the ability of typical software tools to capture, store, manage and analyze. Social network or telco data is typically various orders of magnitude larger than any similar data resource available before. For example, no practical application until a decade ago ever happened to consider graphs larger than ten thousand nodes; current social-network graphs are at least three (often five or six) orders of magnitude larger than this, making any super-linear algorithm essentially useless. This situation pushes towards new algorithms (typically, approximated and/or distributed ones) and new computational frameworks (e.g., Hadoop, S4). In all scenarios, however, scalability is crucial factor to enable any future technology to deal with these datasets.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

About 60% percent of the world's population are using mobile phones, more than 4 billion people, and 12% of them are smartphones, growing more than 20% a year. More than 30 million networked sensor nodes are now present in many important sectors as transportation, automotive, industrial, utilities and retail sectors. The number of sensors is increasing at a rate of 30% a year. Data coming from those mobile platforms and sensors can be themselves thought of as large social-interaction media; sometimes sensors data are reflected in proper social networks; as it happens, for example, when Facebook records the geo-location of a user posting contents from her smartphone; or people use applications as Foursquare or Gowalla.

A further peculiarity is that data are produced at a very high rate and continuously, making every purely static approach hopeless. Data (e.g., tweets on Twitter, posts on Facebook or mobility traces) arrive at a breakneck rate, and they should be analyzed, cleansed, stored, categorized immediately and in a highly adaptive manner. Moreover, interacting on a social network often requires immediate reaction: platforms like Twitter creates in the users expectations of immediate response; on the other hand, precisely the high-reactivity of social media makes them an ideal source of fresh news, but only as far as we are able to cope with the information flow they produce and to exhibit a short response/reaction time.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NKFI in order to inform decision-makers, media, and the taxpayers.

With the explosion of social-networking applications, the ubiquity of mobile devices and on-line services, and the rapid deployment of sensor-networking technologies, an enormous amount of data is being accumulated. Collected data is also characterized by very high heterogeneity and high coverage. By heterogeneity we refer to the multitude of available data types and data attributes, for example, spatiotemporal annotations, sensor measurement time series, personal communications, photos, text messages, blogs, tweets, wikis, news articles, and much more. By coverage we refer to the fact that data are nowadays collected for virtually every type of human and natural activity on the planet. As a result, the collected data form a goldmine from which knowledge can be extracted and distilled into intelligent and trustful decision-making mechanisms.

The task of extracting intelligence and incorporating the available data into effective decision-making mechanisms creates tremendous challenges. Part of the problem is information overload: the presence of too much information hampers the tasks of understanding some given issues and making effective decisions.

The explosion of networked computation produces data sizes unseen before: the World Wide Web contains Petabytes of information that Google sorts 1 petabyte of data in 6 hours; Walmart`s item information data occupies 24 Terabytes, just to name a few examples. While the hardware speed and the capacity constantly increases, the access speed to external storages (disks) has improved very little over the past years. For this reason, our main goal is to devise algorithms capable of extracting knowledge for very large data.





 

Final report

 
Results in Hungarian
45 SCI-folyóirat és 43 konferencia publikáció mellett egy könyv készült az optikai hálózatokról, egy pedig a parametrikus bonyolultságról. Igazoltuk Littlewood sejtését, amely szerint létezik hét, egymást páronként érintő azonos sugarú végtelen henger. A közelítő megoldásból számítógépes szimbolikus-numerikus módszerekkel tettük egzakttá. Determinisztikus polinomidejű algoritmusokat találtunk mátrixokból álló lineáris terek maximális rangú elemeinek keresésére érdekes speciális esetekben. Több olyan algoritmikus és matematikai módszert dolgoztunk ki, amely alkalmazható optikai hálózatok hibáinak a feltárása a normális működés helyreállítása során. Új, hatékony algoritmusokat találtunk véges testek feletti alacsony fokú diagonális egyenletekből álló rendszerek megoldására és jelentős előrelépést értünk el a függvénytestek feletti explicit izomorfizmus probléma vizsgálatában. Valós idejű prediktív módszerekkel jeleztük előre az emberek mozgását valós idejű közlekedési vizsgálatokban. Levezettük, hogy tetszőleges, megfelelő matematikai paraméterekkel rendelkező hasonlóságmérték és azon kombinációja esetében is képes a Fisher metrika automatikusan távolságot definiálni és akár több modalitású adatok relatív erősségét automatikusan skálázni. Új eredményeinket elosztott algoritmikus technológia alkalmazása tette lehetővé, amelynek segítségével a modellek valós időben kiértékelhetők, illetve új információkkal frissíthetők.
Results in English
In addition to 45 SCI journal and 43 conference publications, we wrote two books, one on optical networks and one on parametric complexity. Littlewood conjecture was proved that there are seven infinite circular disks of the same radius which pairwise touch each other. The approximate solution was turned exact by symbolic computational and numerical methods. We found deterministic polynomial algorithms for maximum rank matrix elements in linear spaces of matrices in interesting special cases. Several algorithmic and mathematical methods were developed for optical networks that can be used for error detection and error recovery. We found new, efficient algorithms to solve low degree digonal equations over finite fields. We made significant progress on the explicit isomorphism problem over function fields. We gave real-time predictive methods for the movement of people in real-time traffic applications. We have deduced that for arbitrary similarity measures (with suitable mathematical paramateres) and for their linear combinations the Fisher metric provides a very useful distance. In this distance the relative strength of multi-modal data is automatically scaled. We relied on distributed algorithmic technologies to evaluate our new models.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=105645
Decision
Yes





 

List of publications

 
Pálovics, R., Ayala-Gómez, F., Csikota, B., Daróczy, B., Kocsis, L., Spadacene, D., & Benczúr, A. A.: RecSys Challenge 2014: an ensemble of binary classifiers and matrix factorization, Proc. 2014 Recommender Systems Challenge (p. 13). ACM. (2014, October), 2014
Róbert Pálovics, András A. Benczúr: Temporal influence over the Last.fm social network. Social Network Analysis and Mining., Springer. 2015, 5:4, 2015
Daroczy, B., Siklosi, D., Palovics, R., & Benczur, A. A.: Text Classification Kernels for Quality Prediction over the C3 Data Set, Proc. 24th WWW Companion (pp. 1441-1446). (2015, May), 2015
Pálovics, R., Benczúr, A. A., Kocsis, L., Kiss, T., & Frigó, E.: Exploiting temporal influence in online recommendation, Proc. 8th ACM Conference on Recommender systems (pp. 273-280). ACM. (2014, October), 2014
Daróczy, B., Vaderna, P., & Benczúr, A.: Machine Learning Based Session Drop Prediction, LTE Networks and its SON Aspects, 2015
M.Erdelyi, A.. Benczur. B. Daroczy, A. Garzo, T. Kiss, D. Siklosi: The classification power of Web features, Internet Mathematics, 10.3-4 (2014): 421-457., 2014
P. Borwein, T. Erdélyi, G. Kós: The multiplicity of the zero at 1 of polynomials with constrained coefficients, ACTA ARITHMETICA 159.4 (2013): 387-395., 2013
S. Z. Kiss, E. Rozgonyi, Cs. Sándor: Sets with almost coinciding representation functions, Bulletin of the Australian Math. Soc. 89.01 (2014): 97-111., 2013
S. Z. Kiss, E. Rozgonyi, Cs. Sandor: On additive complement of a finite set, Journal of Number Theory, 136 (2014): 195-203., 2014
Daróczy, B., Vaderna, P., & Benczúr, A.: Machine Learning Based Session Drop Prediction in LTE Networks and its SON Aspects., 2015 IEEE 81st Vehicular Technology Conference (VTC Spring). IEEE, 2015., 2015
É. Hosszu, S. Kiss, L. Rónyai, J. Tapolcai: On a Parity Based Group Testing Algorithm, Acta Cybernetica-Szeged, 22 (2015), 423-433., 2015
S. Kiss, Cs. Sándor: On the multiplicativity of the linear combination of additive representation functions, Ramanujan Journal 2016 1-15., 2016
G. Ivanyos, M. Karpinski, Y. Qiao and M. Santha: Generalized Wong sequences and their applications to Edmonds' problems., J. Comput. Syst. Sci. 81 (2015), 1373-1386., 2015
S. Bozóki, T.-L. Lee, L. Rónyai: Seven mutually touching infinite cylinders, Computational Geometry 48.2 (2015): 87-93, 2015
L. Csató, L. Rónyai: Incomplete pairwise comparison matrices and weighting methods, FUNDAMENTA INFORMATICAE 144:(3-4) pp. 309-320. (2016); DOI 10.3233/FI-2016-1337, 2016
P. L. Erdos, S. Kiss, I. Miklos, L. Soukup: Approximate Counting of Graphical Realizations, PloS ONE, 10(7), 2015., 2015
S. Kiss, Cs: Sándor: On the maximum values of the additive representation functions, International Journal of Number Theory, 12.04 (2016): 1055-1075., 2016
I Hegedűs, Á Berta, L Kocsis, AA Benczúr, M Jelasity: Robust Decentralized Low-Rank Matrix Decomposition, ACM Transactions on Intelligent Systems and Technology (TIST) 7 (4), 62 2016, 2016
D. Marx, M. Pilipczuk: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams, In Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), Lecture Notes in Computer Science Volume 9294, Springer, 865-877, 2015., 2015
D. Marx, T. Miltzow: Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems, Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), 52:1-52:16, 2016., 2016
R. Curticapean, D. Marx: Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus, Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 1650-1669, 2016., 2016
M. Bateni, E. Demaine, M. Hajiaghayi, D. Marx: A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), 570-583, 2016., 2016
S.A. Amiri, S. Kreutzer, D. Marx, R. Rabinovich: Routing with Congestion in Acyclic Digraphs, MFCS 2016: 7:1-7:11, 2016
D. Marx, V. Mitsou: Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth, ICALP 2016: 28:1-28:15, 2016
A.E. Feldmann, D. Marx: The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, ICALP 2016: 27:1-27:14, 2016
É. Bonnet, L. Egri, D. Marx: Fixed-Parameter Approximability of Boolean MinCSPs, ESA 2016: 18:1-18:18, 2016
S. Kratsch, D. Marx, M. Wahlström: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, Transactions on Computational Theory 8(1): 1 (2016), 2016
M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh, M. Wahlström: On Problems as Hard as CNF-SAT, ACM Trans. Algorithms 12(3): 41 (2016), 2016
Y. Cao, D. Marx: Chordal Editing is Fixed-Parameter Tractable, Algorithmica 75(1): 118-137 (2016), 2016
M. Grohe, D. Marx: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, SIAM Journal on Computing, 44(1):114-159, 2015
Y. Cao, D. Marx: Interval deletion is fixed-parameter tractable, ACM Transaction on Algorithms, 11(3):21, 2015., 2015
A. Pasic, J. Tapolcai, P. Babarczi, E. Bérczi-Kovács, Z. Király, and L. Rónyai: Survivable routing meets diversity coding, Proc. IFIP Networking Conference, Toulouse, France, 2015, pp. 1-9., 2015
J. Tapolcai, L. Rónyai, É. Hosszu, L. Gyimóthi, P-H. Ho, S. Subramaniam: Signaling Free Localization of Node Failures in All-Optical Networks, IEEE Transactions on Communications Volume: 64, Issue: 6, June 2016, 2527—2538 ; DOI 10.1109/TCOMM.2016.2545653, 2016
R Pálovics, P Szalai, J Pap, E Frigó, L Kocsis, AA Benczúr: Location-aware online learning for top-k recommendation, Pervasive and Mobile Computing (2016), 2016
Bálint Daróczy, Róbert Pálovics, Vilmos Wieszner, Richárd Farkas, András A. Benczúr: Predicting User-specific Temporal Retweet Count Based on Network and Content Information, INRA workshop, RecSys 2015, 2015
J. Tapolcai, P-H. Ho, P. Babarczi, L. Rónyai: Neighborhood Failure Localization in All-Optical Networks via Monitoring Trails, IEEE-ACM Transactions on Networking 23:(6) pp. 1719-1728. (2015) ; DOI: 10.1109/TNET.2014.2342222, 2015
Y. Cao, D. Marx: Interval deletion is fixed-parameter tractable, ACM Transaction on Algorithms, 11(3):21, 2015., 2015
T. Mészáros, L. Rónyai: Shattering-extremal set systems of VC dimension at most 2, The Electronic Journal of Combinatorics, Vol. 21/4, #P4.30, 2014
T. Mészáros, L. Rónyai: A note on Alon's combinatorial Nullstellensatz, Annales Univ. Sci. Budapest., Sect. Comp. Vol. 42, 249-260., 2014
A. Pasic, J. Tapolcai, P. Babarczi, E. Bérczi-Kovács, Z. Király, and L. Rónyai: Survivable routing meets diversity coding, Proccedings of the 2015 IFIP Networking Conference, Toulouse, France, pp. 1-9., 2015
G. Ivanyos, M. Karpinski, Y. Qiao and M. Santha: Generalized Wong sequences and their applications to Edmonds' problems, {\it J. Comput. Syst. Sci. 81 (2015), 1373-1386.}, 2015
A. M. Childs, G. Ivanyos: Quantum computation of discrete logarithms in semigroups, J. Math. Cryptology 8 (2014) 405-416., 2014
G. Ivanyos, M. Santha: On solving systems of diagonal polynomial equations over finite fields, Proc. FAW 2015, Springer LNCS, Vol. 9130 (2015), 125-137., 2015
P. L. Erdos, S. Kiss, I. Miklos, L. Soukup: Approximate Counting of Graphical Realizations, PloS ONE, 10(7), 2015
S. Kiss, Cs. Sándor and E. Rozgonyi: Groups, partitions and representation functions, Publicationes Math. Debrecen, 85 (2014), 425-433., 2014
S. Kiss, Cs: Sándor: On the maximum values of the additive representation functions, International Journal of Number Theory, to appear, 2015
M. Grohe, D. Marx: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, SIAM Journal on Computing, 44(1):114-159, 2015., 2015
Y. Cao, D. Marx: Interval deletion is fixed-parameter tractable, ACM Transaction on Algorithms, 11(3):21, 2015., 2015
L.A. Végh, D. Marx: Fixed-parameter algorithms for minimum cost edge-connectivity augmentation, ACM Transaction on Algorithms, 11(4):27, 2015., 2015
R. Chitnis, M. Cygan, M. Hajiaghayi, D. Marx: Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable, ACM Transaction on Algorithms, 11(4):28, 2015., 2015
D. Marx, P. Wollan: An exact characterization of tractable demand patterns for maximum disjoint path problems, In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 642-661,2015., 2015
B.M.P. Jansen, D.Marx: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels, Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 616-629, 2015., 2015
Dániel Marx, Paul Wollan: Immersions in Highly Edge Connected Graphs., SIAM J. Discrete Math. 28(1): 503-520 (2014), 2014
Martin Grohe, Dániel Marx: Constraint Solving via Fractional Edge Covers., ACM Transactions on Algorithms 11(1): 4 (2014), 2014
Dániel Marx, Anastasios Sidiropoulos: The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for -dimensional geometric problems., Symposium on Computational Geometry 2014: 67, 2014
Sylvain Guillemot, Dániel Marx: Finding small patterns in permutations in linear time., SODA 2014: 82-101, 2014
Yixin Cao, Dániel Marx: Interval Deletion is Fixed-Parameter Tractable., SODA 2014: 122-141, 2014
Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx: Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), SODA 2014: 1782-1801, 2014
Philip N. Klein, Dániel Marx: A subexponential parameterized algorithm for Subset TSP on planar graphs., SODA 2014: 1812-1830, 2014
Yixin Cao, Dániel Marx: Chordal Editing is Fixed-Parameter Tractable., STACS 2014: 214-225, 2014
Dániel Marx, Michal Pilipczuk: Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)., STACS 2014: 542-553, 2014
K.Sandor, Cs. Sandor, E. Rozgonyi: On Sidon sets which are asymptotic bases of order 4, Functiones et Approximatio Commentarii Mathematici, to appear., 2014
Sandor Kiss, Istvan Miklos and Eric Tannier: On sampling SCJ rearrangement scenarios, Theoretical Computer Science, to appear., 2014
Miklos Erdelyi, Andras A. Benczur. Balint Daroczy, Andras Garzo, Tamas Kiss, David Siklosi: The classification power of Web features., INTERNET MATHEMATICS Volume 10, Issue 3-4, Paper 10.1080/15427951.2013.850456. 31 p. (2014)., 2014
Bálint Daróczy, András A. Benczúr, Lajos Rónyai: Fisher kernels for image descriptors: a theoretical overview and experimental results, Annales Univ. Sci. Budapest., Sectio Computatorica special issue dedicated to Professors Zoltán Daróczy and Imre Kátai on the occasion of their 75th birthday, 2013, 2013
Julianna Göbölös-Szabó, András Benczúr: Temporal Wikipedia search by edits and linkage., SIGIR 2013 Workshop on Time-aware Information Access, 28 July – 1 August 2013, Dublin, Ireland, 2013
Andras Garzo, Andras A. Benczur, Csaba Istvan Sidlo, Daniel Tahara, Erik Francis Wyatt: Real-time streaming mobility analytics, IEEE Big Data 2013, 2013
Andrei A. Bulatov, Dániel Marx: Constraint Satisfaction Parameterized by Solution Size., SIAM J. Comput. 43(2): 573-616 (2014), 2014
M.Erdelyi, A.. Benczur. B. Daroczy, A. Garzo, T. Kiss, D. Siklosi: The classification power of Web features, Internet Mathematics, közlésre elfogadva., 2013
A. Garzo, I. Petras, Cs. I. Sidlo, A. A. Benczur.: Real-time streaming mobility analytics., NetMob 2013 - Third conference on the Analysis of Mobile Phone Datasets. May 1-3, 2013, MIT, Boston, USA, 2013
R. Pálovics, A. Benczúr.: Temporal influence over the Last.fm social network, The 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining ASONAM 2013 Niagara Falls, Canada, August 25-28, 2013, 2013
A. Garzó, B. Daróczy, T. Kiss, D. Siklósi, A. A. Benczúr.: Cross-lingual web spam classification., The 3rd Joint WICOW/AIRWeb Workshop on Web Quality Rio de Janeiro, Brasil. May 13, 2013. Proceedigs of the 22nd international conference on World Wide Web companion, 2013
L. Dudás, Zs. Fekete, J. Göbölös-Szabó, A. Radnai, A. Salánki, A. Szabó, G. Szűcs: OWLAP - using OLAP approach in anomaly detection (Award: Good Support for the Data Preparation, Analysis, and Presentation Process), IEEE Conference on Visual Analytics Science and Technology 2012 October 14 - 19, Seattle, WA, USA, 2012
B. Daróczy, D. Siklósi and A.A. Benczúr: SZTAKI @ ImageCLEF 2012 Photo Annotation, In Working Notes of the ImageCLEF 2011 Workshop at CLEF 2012 Conference, Rome, Italy, 2012
J. Göbölös-Szabó, A. Benczúr: Temporal Wikipedia search by edits and linkage, SIGIR 2013 Workshop on Time-aware Information Access, 28 July – 1 August 2013, Dublin, Ireland, 2013
T. Mészáros, L. Rónyai: Shattering-Extremal Set Systems of Small, VC-Dimension, ISRN Combinatorics, vol. 2013, Article ID 126214, 8 pages,, 2013
G. Ivanyos, Á. Lelkes, L. Rónyai: Improved algorithms for splitting full matrix algebras, JP Journal of Algebra, Number Theory and Applications Volume 28, Number 2, 2013, Pages 141-156., 2013
É. Hosszú, J. Tapolcai, L. Rónyai, P. Babarczi, P. Soproni, P-H. Ho: Fast failure Localization in all-optical networks with length-constrained monitoring trails, In: Proc. of the Workshop on Reliable Networks Design and Modeling (RNDM), St. Petersburg, Russia, 2012, pp. 677-683., 2012
J. Tapolcai, Pin-Han Ho, P. Babarczi, L. Rónyai: On Signaling-Free Failure Dependent Restoration in All-Optical Mesh Networks, IEEE/ACM Transactions on Networking, 2013. (accepted), 2013
J. Tapolcai, Pin-Han Ho, P. Babarczi, L. Rónyai: On Achieving All-Optical Failure Restoration via Monitoring, In Proc. IEEE INFOCOM Mini-Symposium, Turin, Italy, 2013., 2013
J. Tapolcai, L. Rónyai, Pin-Han Ho: Link Fault Localization using Bi-directional M-Trails in All-Optical Mesh Networks, IEEE Transactions on Communications, 2012. (accepted), 2013
S. Bozóki, T.-L. Lee, L. Rónyai: Seven mutually touching infinite cylinders, submitted to Computational Geometry. pp. 1-13., 2013
B. Daróczy, A. A. Benczúr, L. Rónyai: Fisher kernels for image descriptors: a theoretical overview and experimental results, Annales Univ. Sci. Budapest., Sect. Comp. 40 (2013) (accepted) pp. 1-15., 2013
T. Decker, G. Ivanyos, M. Santha, P. Wocjan: Hidden Symmetry Subgroup Problems, pp. 1-21. SIAM Journal on Computing, to appear, 2013
K. Friedl, G. Ivanyos, F. Magniez, M. Santha and P. Sen: Hidden translation and translating coset in quantum computing, Submitted to SIAM J. Comput. pp. 1-22, 2013
G. Ivanyos, H. Klauck, T. Lee, M. Santha and R. de Wolf: New bounds on the classical and quantum communication complexity of some graph properties, Proc. FSTTCS 12 (Leibniz International Proceedings in Informatics Vol. 18), 148-159. (Open access.), 2012
S. Guillemot, D. Marx: A faster FPT algorithm for Bipartite Contraction, Information Processing Letters, To appear, 2013
D. Marx, I. Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset, SIAM Journal on Computing, To appear, 2013
G. Kós: Representing the GCD as linear combination in non-PID rings, ACTA MATHEMATICA HUNGARICA 140:(3) pp. 243-247. (2013), 2013
P. Borwein, T. Erdélyi, G. Kós: The multiplicity of the zero at 1 of polynomials with constrained coefficients, Accepted by ACTA ARITHMETICA in 2013, 2013
S. Z. Kiss, E. Rozgonyi, Cs. Sándor: Sets with almost coinciding representation functions, Bulletin of the Australian Math. Soc. pp. 1-14. (elfogadva), 2013
S. Z. Kiss, E. Rozgonyi, Cs. Sandor: On additive complement of a finite set, Journal of Number Theory, pp. 1-9. (elfogadva), 2013
L. Kocsis, A. György, A. N. Bán: BoostingTree: Parallel Selection of Weak Learners in Boosting, with Application to Ranking, Machine Learning, 2013 DOI: 10.1007/s10994-013-5364-5, 2013
Péter Babarczi, János Tapolcai, Lajos Rónyai, and Muriel Médard: Resilient Flow Decomposition of Unicast Connections with Network Coding, Proceedings of the 2014 IEEE International Symposium on Information Theory (ISIT), pp. 116--120., 2014
J. Tapolcai, Pin-Han Ho, P. Babarczi, L. Rónyai: On Achieving All-Optical Failure Restoration via Monitoring, In Proc. IEEE INFOCOM Mini-Symposium, Turin, Italy, 2013, 380--384., 2013
J. Tapolcai, L. Rónyai, Pin-Han Ho: Link Fault Localization using Bi-directional M-Trails in All-Optical Mesh Networks, IEEE Transactions on Communications, 61 (2013), 291--300., 2013
S. Bozóki, T.-L. Lee, L. Rónyai: Seven mutually touching infinite cylinders, Computational Geometry: Theory and Applications, 48(2015), pp. 87-–93., 2015
T. Decker, G. Ivanyos, M. Santha, P. Wocjan: Hidden Symmetry Subgroup Problems, SIAM Journal on Computing 42:5 (2013), 1987-2007., 2013
K. Friedl, G. Ivanyos, F. Magniez, M. Santha and P. Sen: Hidden translation and translating coset in quantum computing, SIAM Journal on Computing 43:1 (2014), 1-24., 2014
D. Marx, I. Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset, SIAM Journal on Computing, 43(2): 355-388 (2014), 2014
J. Tapolcai, Pin-Han Ho, P. Babarczi, L. Rónyai: Internet Optical Infrastructure - Issues on Monitoring and Failure Restoration, Springer, pp. 1-212, 2014. [ISBN 978-1-4614-7737-2], 2014
J. Tapolcai, L. Rónyai, É. Hosszu, Pin-Han Ho, S. Subramaniam: Signaling Free Localization of Node Failures in All-Optical Networks, IEEE INFOCOM, Toronto, Canada, pp. 1860-1868, 2014, 2014
J. Tapolcai, Pin-Han Ho, P. Babarczi, L. Rónyai: Neighborhood Failure Localization in All-Optical Networks via Monitoring Trails, IEEE/ACM Transactions on Networking, 2014. [accepted, 2014
A. Nagy, L. Rónyai: Finite semigroups whose semigroup algebra over a field has a trivial right annihilator, International Journal of Contemporary Mathematical Sciences, 9(2014) 25--36. (open access), 2014
G. Ivanyos, M. Karpinski, Y. Qiao and M. Santha: Generalized Wong sequences and their applications to Edmonds' problems, STACS 14 (Leibniz International Proceedings in Informatics Vol. 25 (2014), 397-408., 2014
M. Arora, G. Ivanyos, M. Karpinski and N. Saxena: Deterministic polynomial factoring and association schemes, LMS J. of Computation and Mathematics 17 (2014), 123-140., 2014
G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha and A. Sundaram: On the complexity of trial and error for constraint satisfaction problems, ICALP 2014, Springer LNCS Vol. 8572 (2014), 663-675., 2014
T. Decker, P. Hoyer, G. Ivanyos and M. Santha: Polynomial time quantum algorithms for certain bivariate hidden polynomial problems, Quantum Information and Computation 14 (2014) 790-806., 2014
T. Decker, G. Ivanyos, R. Kulkarni, Y. Qiao and M. Santha: An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group, MFCS 2014, Springer LNCS Vol. 8635 (2014), 226-238., 2014
S. Guillemot, D. Marx: A faster FPT algorithm for Bipartite Contraction, Information Processing Letters, 113(22-24): 906-912 (2013), 2013





 

Events of the project

 
2015-11-12 15:48:50
Résztvevők változása
2015-03-09 17:38:43
Résztvevők változása
2014-06-11 10:41:28
Résztvevők változása
2014-02-24 12:54:15
Résztvevők változása
2013-10-24 10:50:03
Résztvevők változása
2012-08-07 15:20:13
Résztvevők változása




Back »