Applied algorithms for large-scale problems  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
72845
Type NK
Principal investigator Demetrovics, János
Title in Hungarian Alkalmazott algoritmusok nagyméretű feladatokra
Title in English Applied algorithms for large-scale problems
Keywords in Hungarian algorithms
Keywords in English algorithms
Discipline
Information Technology (Council of Physical Sciences)60 %
Ortelius classification: Applied informatics
Computing Science (Council of Physical Sciences)20 %
Mathematics (Council of Physical Sciences)20 %
Ortelius classification: Combinatorial analysis
Panel Informatics and Electrical Engineering
Department or equivalent HUN-REN Institute for Computer Science and Control
Participants Benczúr, András
Bíró, István
Brendel, Mátyás
Daróczy, Bálint
Fekete, Zsolt
Ivanyos, Gábor
Iwatt, Róbert
Kurucz, Miklós
Lukács, András
Marx, Dániel
Neumark, Péter
Rácz, Simon
Rónyai, Lajos
Schneider, Csaba
Siklósi, Dávid
Szabó, Jácint
Starting date 2008-04-01
Closing date 2011-04-30
Funding (in million HUF) 30.633
FTE (full time equivalent) 9.23
state closed project
Summary in Hungarian
A világhálón fellelhető hatalmas információtömegben igen nehéz megtalálni azokat a weboldalakat, amelyek információigényünknek mind tartalmukban, mind minőségükben megfelelnek. A webkeresés módszereinek kutatása még távolról sem zárult le; a körülbelül tízmilliárd weboldalt tartalmazó gigantikus indexállományok begyűjtése és a felhasználó igényeihez legjobban illeszkedő információ kiszűrése számtalan technikai nehézséget rejt magában. Érdekünk, hogy a hazai kutatás-fejlesztés ne maradjon ki a világháló e fontos szegmenséből. A projekt megvalósulása esetén ezen túl az eredmények közvetlen oktatásban való megjelenését is biztosítja.
A feladat megvalósítása az alkalmazásokkal való közeli kapcsolat mellett komoly matematikai és algoritmuselméleti hátteret igényel, amellyel a pályázó egy oktatási és kutatóintézeteken, ipari projekteken átívelő csoport meghatározó tagjaként rendelkezik. A kutatás során építünk adatbáziselméleti, adatbányászati, algebrai, statisztikai és információ-visszakeresési kutatási tapasztalatainkra, valamint a 2006/07 akadémiai évben Yahoo! Faculty Research Grant adományozásával értékelt kutatásainkra.
A nemzetközi kutatásba való bekapcsolódás elengedhetetlen feltétele, hogy igen nagy méretű benchmark adathalmazokon dolgozzunk, így alapfeltétel a meglevő kapacitásaink bővítése minimálisan egyidejűleg 4, egyenként 8-8GB memória igényű feladat futtatásának biztosítására.
Summary
Data size explosion forms the main reason for the expanding interest in large scale algorithmic problems. We plan to conduct research with applications for social network mining, graph clustering, personalized and similarity search, recommendation and spam filtering, a set of interrelated fields in Database Technologies, Theory of Algorithms, High Performance Symbolic Computation, Search and Information Retrieval as well as to Data Mining and Machine Learning. Based on our ongoing research honored by a Yahoo! Faculty Research Grant for the theory of efficient algorithms based on data warehouse technologies, algebraic structures, low space summaries, we also propose and experimentally test algorithms that were previously considered computationally infeasible. 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. We build on the unique nature of our research group to cover the full chain from core research to industrial deployment, including experience in handling and processing exremely large scale industrial data.




 

Final report

  
Results in Hungarian
Alap és alkalmazott kutatást végeztünk a következő fő területeken: - Formális matematikai módszerek adatbányászatban és optimalizálásban; - Nagyméretű adatok elemzése és modellezése, hálózatokkal kapcsolatos üzleti intelligencia alkalmazásokban; - Felhasználó és tartalom összerendelése, keresés, ajánlás. A projekt résztvevői zárt láncban a teljes innovációs láncot lefedik az oktatástól (ELTE és BME algoritmusok, adatbányászat, Web információ-keresés előadások) az elméleti kutatásokon át az alkalmazásokig. A kutatáshoz kapcsolódó legfontosabb két ipari partnerünk a Magyar Telekom és az AEGON, amelyek számára egyedi kereső megoldásokat fejlesztettünk, naplóelemzési és ügyfél-elemzési feladatokat oldottunk meg. Európai kapcsolataink segítségével a jelen kutatási eredményekre épülő Digitális Könyvtárak és Biztonság témájú projektben veszünk részt. A kutatásunk nemzetközi elismertségét jelzi, hogy felkértek a legjelentősebb európai adatbányászati verseny, az ECML/PKDD Discovery Challenge szervezésére, illetve a legrangosabb World Wide Web konferencián Workshop Chair, a WSDM (Web Search and Data Mining) konferencián szenior, további kapcsolódó témájú konferencián és workshopon (ICALP, AIRWeb, ESA stb) programbizottági tagot adunk. Legfontosabb eredményeink: - Előrelépést a véges testek feletti polinomfelbontás algoritmusaiban; - Díjnyertes megoldás a KDD Cup 2009 feladaton; - Új Web Spam szűrő módszerek; - Tartalom alapú képkereső eljárások.
Results in English
Our results cover a wide range of areas of theory and application: -Formal mathematical methods in data mining and optimization; -Analysis and modeling very large scale data with applications in the areas of network related business intelligence; -User-content interaction, optimization. The project team covers full innovation chain from Education (Technical University and Eötvös University courses in algorithms, data mining, Web information retrieval), Pure, Applied Research and Innovation. Our industrial exploitation include the Hungarian Telecom Group and AEGON Hungary where we developed custom search engines and conducted log mining and business intelligence projects. Based on the reported results, we participated in several Digital Libraries and Security ICT projects. Our results are acknowledged by being the main organizer of the major European data mining contest, the ECML/PKDD Discovery Challenge 2010 and the invitation to serve as Workshop Chair at the highest prestige World Wide Web conference, senoir program committee member at the Web Search and Data Mining conferences, and PC member of other related conferences and workshops (ICALP, AIRWeb, ESA etc). Our most important research results include -Breakthrough algorithms in factorization of polynomials over finite fields; -Prize winner solution at KDD Cup 2009, in a telco classification task; -New methodologies in Web Spam filtering; -Content-based multimedia indexing methods.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=72845
Decision
Yes





 

List of publications

  
G. Ivanyos, M. Karpinski, L. Rónyai, N. Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures, Mathematics of Computation, to appear, 2011
Miklós Kurucz, Dávid Siklósi, István Bíró, Péter Csizsek, Zsolt Fekete, Róbert Iwatt, Tamás Kiss, Adrienn Szabó: KDD Cup 2009 @ Budapest, Journal on Machine Learning Research, 2009
J. Tapolcai, B. Wu, P-H. Ho, L. Rónyai: A novel approach for failure localization in all-optical mesh networks, IEEE/ACM transactions on Networking, 19, 275--285., 2011
G. Ivanyos, M. Karpinski, N. Saxena: Deterministic polynomial time algorithms for matrix completion problems,, SIAM Journal on Computing 39:8 , 3736-3751., 2010
B. Felszeghy, L Rónyai: Some meeting points of Gröbner bases and combinatorics, Special Semester on Gröbner Bases, Linz. Springer, 2009
Miklós Kurucz, András A. Benczúr: Geographically organized small communities and the hardness of clustering social Networks, Annals of Information Systems special issue on Social Network Analyis, 2010
S. Bozóki, J. Fülöp, L Rónyai: On optimal completions of incomplete pairwise comparison matrices, Eur. J. Op. Res., 2009
John Bamberg, Tim Penttila, and Csaba Schneider: Elation generalized quadrangles for which the number of lines on a point is the successor of a prime, J. Austral. Math. Soc. , Volume 85, Issue 03, December 2008, pp 289-303., 2008
A. Nagy, L Rónyai: Right (left) linearly independent finite semigroups, Publ. Math. Debrecen, 2009
Hendrik Van Maldeghem and Csaba Schneider: Primitive flag-transitive generalized hexagons and octagons., J. Combin. Theory Ser. A. 115(8), pages 1436-1455, 2008., 2008
Robert W. Baddeley, Cheryl E. Praeger, and Csaba Schneider: Intransitive Cartesian decompositions preserved by innately transitive permutation groups, Trans. Amer. Math. Soc. 360(2), pages 743-764, 2008
A.A. Benczur, K. Csalogany, M. Kurucz, A. Lukacs, L. Lukacs, D. Siklosi: Telephone Call Network Data Mining: A Survey with Experiments (Chapter 12), Handbook of Large-Scale Random Networks, Bolyai Society Mathematical Studies, Vol. 18. eds: B. Bollobás, R. Kozma, D. Miklós, Springer, 2008
András A. Benczúr and Michel X. Goemans: Deformable Polygon Representation and Near-Mincuts, M. Grötschel, Konrad-Zuse-Zentrum, Berlin, Germany; G. O. H. Katona, Hungarian Academy of Sciences, Budapest, Hungary, Eds: Building Bridges Between Mathematics and Compu, 2008
Gábor Ivanyos, Luc Sanselme and Miklos Santha: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups, Proc LATIN 2008: Theoretical Informatics, Lecture Notes in Computer Science Vol. 4957/2008, pp. 1611-3349, 2008
Gábor Ivanyos, Nitin Saxena, Marek Karpisnski: Schemes for deterministic polynomial factoring, Proc. ISSAC 2009, 2009
S. Rácz, B. Daróczy, A. Pereszlényi, D. Siklósi, A. Benczúr, M. Brendel: Increasing cluster recall of cross-modal image retrieval, Working Notes of the 2008 CLEF Workshop, Aarhus, Denmark, Sept. 2008, 2008
B. Daróczy, Zs. Fekete, M. Brendel: SZTAKI @ ImageCLEF 2008 Visual Concept Detection, Working Notes of the 2008 CLEF Workshop, Aarhus, Denmark, Sept. 2008, 2008
Bálint Daróczy Zsolt Fekete Mátyás Brendel Simon Rácz András Benczúr Dávid Siklósi Attila Pereszlényi: SZTAKI @ ImageCLEF 2008: visual feature analysis in segmented images, Peters, C., Giampiccol, D., Ferro, N., Petras, V., Gonzalo, J., Peñas, A., Deselaers, T., Mandl, T., Jones, G., Kurimo, M., eds.: Evaluating Systems for Multilingual and, 2009
A. A. Benczúr, D. Siklósi, I. Bíró, Zs. Fekete, M. Kurucz, A. Pereszlényi, S. Rácz, A. Szabó, and J. Szabó: Web Spam: a Survey with Vision for the Archivist, Proc. IWAW 2008, 2008
Miklós Kurucz, András A. Benczúr, Attila Pereszlényi: Large-Scale Principal Component Analysis on LiveJournal Friends Network, n proc Workshop on Social Network Mining and Analysis Held in conjunction with The 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 20, 2008
Péter Schönhofen: Annotating documents by Wikipedia concepts, Web Intelligence, 2008
Istvan Biro, Andras Benczur, Jacint Szabo and Ana Gabriela Maguitman: A Comparative Analysis of Latent Variable Models for Web Page Classification., In Proc LA-Web 2008, 2008
István Bíró, Jácint Szabó, András A. Benczúr: Latent Dirichlet Allocation in Web Spam Filtering, Proc. Airweb 2008 in conjunction with WWW 2008, 2008
Dávid Siklósi, András A. Benczúr, Zsolt Fekete, Miklós Kurucz, István Bíró, Attila Pereszlényi, Simon Rácz, Adrienn Szabó, Jácint Szabó: Web Spam Hunting @ Budapest, Proc. Airweb 2008 in conjunction with WWW 2008, 2008
Miklós Erdélyi, Dávid Siklósi, Julien Masanes, András A. Benczúr: Web Spam Filtering in Internet Archives, Proc. Airweb 2009 in conjunction with WWW 2009, 2009
András A. Benczúr, Miklós Erdélyi, Julien Masanes, Dávid Siklósi,: Web Spam Challenge Proposal for Filtering in Archives, Proc. Airweb 2009 in conjunction with WWW 2009, 2009
István Bíró, Dávid Siklósi, Jácint Szabó and András Benczúr: inked Latent Dirichlet Allocation in Web Spam Filtering, Proc. Airweb 2009 in conjunction with WWW 2009, 2009
Demetrovics, J., Molnár, A., Thalheim, B.: Reasoning methods for designing and surveying relationships described by sets of functional constraints., Serdica Journal of Computing, 2009
B. Felszeghy, G. Heged?s, L. Rónyai: Algebraic Properties of Modulo q Complete l-Wide Families, Combinatorics, Probability & Computing 18(2009), 309-333., 2009
B. Felszeghy, L. Rónyai: Some meeting points of Gröbner bases and combinatorics, Algorithmic Algebraic Combinatorics and Gröbner bases (M. Klin, G. A. Jones, A. Jurisic, M. Muzychuk, I. Ponomarenko editors), Springer, 2009
S. Bozóki, J. Fülöp, L. Rónyai: Incomplete Pairwise Comparison Matrices in Multi-Attribute Decision Making, Proceedings of The IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), 2009
B. Daróczy, Z. Fekete, M. Brendel, S. Rácz, A. A. Benczúr, D. Siklósi and A. Pereszlényi: SZTAKI @ ImageCLEF 2008: visual feature analysis in segmented images., ADVANCES IN MULTILINGUAL AND MULTIMODAL INFORMATION RETRIEVAL. 9th Workshop of the Cross-Language Ev, 2009
Cs. Sidló: Generic Entity Resolution in Relational Databases., Advances in Databases and Information Systems: 13th East European Conference, ADBIS 2009, 2009
Bálint Daróczy, István Petrás, András A. Benczúr, Zsolt Fekete, Dávid Nemeskey, Dávid Siklósi, Zsuzsa Weiner: . SZTAKI @ ImageCLEF 2009, 10th Workshop of the Cross-Language Evaluation Forum, CLEF 2009, 2009
Bálint Daróczy, Dávid Nemeskey, István Petrás, András A. Benczúr, Tamás Kiss: SZTAKI @ TRECVID 2009, In Proc. TRECVID 2009, 2009
Miklós Kurucz, László Lukács, Dávid Siklósi, András A. Benczúr, Károly Csalogány, András Lukács: Kapcsolatok és távolságok: a hazai vezetékes hívás-szokások elemzése., Magyar Tudomány, 2009/6, 2009
G. Ivanyos, L. Sanselme, M. Santha: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups, Algorithmica, to appear, 2011
J. Tapolcai, P-H. Ho, L. Rónyai: Optimal Solutions for Single Fault Localization in Two Dimensional Lattice Networks, Proc. IEEE INFOCOM Mini-Symposium, San Diego, CA, USA, 5 pages., 2010
S. Bozóki, J. Fülöp, L. Rónyai: On optimal completion of incomplete pairwise comparison matrices, Math. Comput. Modelling 52 , no. 1-2, 318-333., 2010
G. Hegedűs-L. Rónyai: Multivalued generalizations of the Frankl--Pach Theorem, Journal of Algebra and its Applications arXiv:1008.4660 , elfogadva, 2011
G. Kós, L. Rónyai: Alon's Nullstellensatz for multisets, Benyújtva: Combinatorica arXiv:1008.2901, 2011
M. Erdélyi, A. Garzó, and A. A. Benczúr: Web spam classification: a few features worth more, In Joint WICOW/AIRWeb Workshop on Web Quality (WebQuality 2011) In conjunction with the 20th International World Wide Web Conference Hyderabad, India. ACM Press 2011., 2011
M. Erdélyi, and A. A. Benczúr: Temporal Analysis for Web Spam Detection: An Overview In 1st International Temporal Web Analytics Workshop (TWAW), in conjunction with the 20th International World Wide Web Conference Hyderabad, India. CEUR Workshop Proceedings, 2011
Ádám Gyenge, Janne Sinkkonen, and András A. Benczúr: An efficient block model for clustering sparse graphs, In Proceedings of the Eighth Workshop on Mining and Learning with Graphs (MLG '10). ACM, New York, NY, USA, 62-69., 2010
Bálint Daróczy, István Petrás, András A. Benczúr, Dávid Nemeskey: SZTAKI @ ImageCLEF 2010, Conference on Multilingual and Multimodal Information Access Evaluation, 20-23 September 2010, Padua, 2010
Bálint Daróczy, István Petrás, András A. Benczúr, Zsolt Fekete, Dávid Nemeskey, Dávid Siklósi, Zsuzsa Weiner: SZTAKI @ ImageCLEF 2009. ADVANCES IN MULTILINGUAL AND MULTIMODAL INFORMATION RETRIEVAL, 10th Workshop of the Cross-Language Evaluation Forum, CLEF 2009, Revised Selected Papers. Springer LNCS, 2010
Bálint Daróczy, Daniele Falavigna, Roberto Gretter, Dávid Nemeskey, István Petrás, Róbert Pethes, András A. Benczúr: SZTAKI @ TRECVID 2010, In TRECVID 2010 Working Notes, 2010
András Garzó, Dávid Nemeskey, Róbert Pethes, Dávid Siklósi, András A. Benczúr: SZTAKI @ TREC 2010, in TREC 2010 Working Notes, 2010




 

Events of the project

  
2009-06-24 15:57:23
Résztvevők változása



Back »