Efficient algorithms  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
42706
Type K
Principal investigator Demetrovics, János
Title in Hungarian Hatékony algoritmusok
Title in English Efficient algorithms
Panel Mathematics and Computing Science
Department or equivalent HUN-REN Institute for Computer Science and Control
Participants Benczúr, András
Bodon, Ferenc
Fogaras, Dániel
Friedl, Katalin
Friedman, Anna Eszter
Ivanyos, Gábor
Lukács, András
Marx, Dániel
Pintér, Márta
Rónyai, Lajos
Starting date 2003-01-01
Closing date 2006-12-31
Funding (in million HUF) 15.913
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
A kutatás során csoportunk egy sor új eredményt ért el a számítástudomány több területén. Ezek a területek: algebrai és szimbolikus számítások, számításelmélet, kombinatorikus optimalizálás, adatbázis-elmélet, adatbányászat és internetes algoritmusok. Néhány fontosabb eredmény: -- véges ponthalmazokhoz rendelhető Gröbner-bázisok és kapcsolódó struktúrák leírása kombinatorikai szempontból érdekes esetekben, -- a kvantumszámítások néhány fontos modelljének az összehasonlítása, számító erejük tisztázása, kvantumalgoritmusok kidolgozása, -- az "Adatbázis-szerkezetek" c. akadémiai Nívódíjas monográfia elkészülte, -- komoly előrelépést értünk el több, az interneten való kereséssel kapcsolatos kérdésben: új, hatékony algoritmusokat javasoltunk a világháló lapjainak személyes preferenciákat figyelembe vevő rangsorolására; algoritmust dolgoztunk ki a web spam jelenség nagy megbízhatóságú, automatikus detektálására; létrehoztunk egy kísérleti keresőrendszert, -- új hatékony adatbányászati algoritmusok kidolgozása és ezek alkalmazása; az alkalmazások közül kiemelkedik a telekommunikációs ügyfelek viselkedésének modellezésével kapcsolatos vizsgálatunk, amely Barabási Albert László világhírű kutatócsoportjával közös munka, és amelyről a The New York Times is beszámolt.
Results in English
With the partial support of the present grant, we have achieved new results in several fields of computer science, including algebraic and symbolic computation, theoretical computer science, combinatorial optimization, database theory, data mining, algorithms for the internet. Some of the highlights are: -- a description of Gröbner bases and related structures attached to finite sets of of points, where the point sets have combinatorial significance, -- a comparison of some models of quantum computation from the perspective of computing power; development of new quantum algorithms, -- publication of the monograph "Database structures" (in Hungarian) which won the Quality Prize of the Akadémai Kiadó, -- significant advances in several directions connected to searching the internet: we proposed new, efficient methods for obtaining a personalized ranking of web pages; we proposed algorithms for the automatic and highly reliable detection of spam links in the web; we developed an experimental search engine, -- development and applications of new algorithms for several data mining tasks; among the applications the most important is a model for telecommunication customer behaviour, which has been elaborated in a joint project with the renowned group of Albert László Barabási, among others The York Times reported on some of our findings.
Full text http://real.mtak.hu/753/
Decision
Yes





 

List of publications

  
Baddeley, RW; Praeger, CE; Schneider, Csaba: Innately transitive subgroups of wreath products in product action, Transactions of the American Mathematical Society 358/4 1619-1641, 2006
D. Marx:: Eulerian disjoint paths problem in grid graphs is NP-complete, Discrete Applied Mathematics, 2004
D. Marx: Minimum sum multicoloring on the edges of trees., 1st Workshop on Approximation and Online Algorithms (WAOA), 2003, 2004
D. Marx: Parameterized graph separation problems, International Workshop on Parameterized and Exact Computation (IWPEC),, 2004
D. Marx: Parameterized coloring problems on chordal graphs, International Workshop on Parameterized and Exact Computation (IWPEC),, 2004
D. Marx: Parameterized complexity of constraint satisfaction problems, In Proceedings of 19th Annual IEEE Conference on Computational, 2004
Demetrovics J. with A. Molnár, B. Thalheim: Graphical Reasoning for Sets of Functional Dependencies, Springer –Verlag, Berlin Heidelberg, LNCS 3288(2004) 166-179, 2004
Demetrovics J. és Békéssy A.: Adatbázis-szerkezetek, Akadémiai Könyvkiadó, Budapest, 2005
Demetrovics J. és Sali A.: Relációs adatmodell tervezés, ELTE Eötvös Kiadó, 1. kötet. (2004) 503-536, 2004
BENCZÚR, A. A. - CSALOGÁNY, K. - FOGARAS, D.- FRIEDMAN, E.- RÁCZ, B.- SARLÓS, T.- UHER, M.- WINDHAGER, E: Magyar nyelvű tartalom a Világhálón, Információs Társadalom és Trendkutató Központ, 2004
DEMETROVICS, J.- MOLNÁR, A. – THALHEIM, B: Graphical and Spreadsheet Reasoning for Sets of Functional Dependencies, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität Kiel, egyetemi jegyzet, 2004
HEGEDŰS, G. - NAGY, A. - RÓNYAI, L: Gröbner beses for permutations and oriented trees, Ann. Univ. Sci. Budapest., Sectio Computatorica. 23: 137--148, 2004
FOGARAS, D. – RÁCZ, B: Towards Scaling Fully Personalized PageRank, WAW 2004 in conjunction with FOCS 2004. Published in LNCS Volume 3243/2004, Springer Verlag., 2004
FOGARAS, D. – RÁCZ, B: A Scalable Randomized Method to Compute Link-Based Similarity Rank on the Web Graph, ClustWeb in conjunction with EDBT 2004. Published in LNCS Volume 3268: 105-117, Springer Verlag, 2004
FOGARAS, D: Ranking the Pages of the World Wide Web, Periodica Polytechnica Ser. El. Eng. 48(1-2) 5-10, 2004
Benczúr, András; Bíró, István; Csalogány, Károly; Rácz, Balázs; Sarlós, Tamás: PageRank és azon túl: Hiperhivatkozások szerepe a keresésben, Magyar Tudomány 166/11, pp. 1325-1331, 2006
F. Bodon, Z. Hornák: Filtering False Alarms: an Approach Based on Episode Mining, Periodica Politechnica (megjelenés alatt), 2005
A. Lukács: Genarating random elements of Abelian groups, Random Structures and Algorithms 26 (4) 437-445, 2005
Janovitz-Freireich, I; Rónyai, Lajos; Szántó, Á: Approximate radical of ideals with clusters of roots, ISSAC MMVI. Proceedings of the 2006 international symposium on symbolic and algebraic com 1-59593-276-3, pp.146-153, 2006
M. Ferenczi, A. Pataricza, L. Rónyai (szerkesztők): Formal methods in computing, Akadémiai Kiadó, 2005
L. Rónyai, M. Pintér: Efficient algorithms, Formal Methods in Computing 1-54, Akadémiai Kiadó, 2005
G. Ivanyos, L. Rónyai: Algebra, Informatikai algoritmusok II. 18 fej. 838-892, 2005
K. Friedl, G. Ivanyos, M. Sántha: Efficient testing of groups, Proc. 37th Annual ACM Symp. on Theory of Computing, 157-166, 2005
K. Friedl, G. Ivanyos, M. Sántha, Y.F. Verhoeven: On the black-box complexity of Sperner's Lemma, Proc. 15th International Symp on Fundaments of Computation Theory, Springer LNCS 3623 , 245-257, 2005
G. Ivanyos, S. Massar, A.B. Nagy: Quantum computing on lattices using global two-qubit gates, Physical Review A. Vol. 72 (022339) 9 pages, 2005
J. Demetrovics, A. Sali: Lekérdezés-átírás relációs adatbázisokban, Informatikai algoritmusok II. ELTE Eötvös Kiadó, (30) 1436-1483, 2005
L. A. Végh, A.A. Benczúr: Primal-dual approach for directed vertex connectivity augmentation and generalizations, Proc. of 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA) 186-194, Vancouver, British Columbia, Canada, 2005
D. Fogaras, A. Lukács: Klaszterezés, Informatikai algoritmusok II. ELTE Eötvös Kiadó, (29) 1409-1435, 2005
F. Bodon: Gyakori elemhalmazok keresése, Informatikai algoritmusok II. (28) 1385-1404, ELTE Eötvös Kiadó, 2004
D. Fogaras, B. Rácz, K. Csalogány, T. Sarlós: Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds and Experiments, Internet Mathematics (2) No. 3. 341-366, 2005
A.A. Benczúr, K. Csalogány, T. Sarlós: On the Feasibility of Low-rank Approximation for Personalized PageRank, Proc. of the 14th International World Wide Web Conference 972-973, Chiba, Japan, 2005
A.A. Benczúr, K. Csalogány, A. Lukács, B. Rácz, Cs. I. Sidló, M. Uher, L. Végh: Architecture for mining massive web logs with experiments, Proc. of the HUBUSKA Open Workshop on Generic Issues of Knowledge Technologies, 2005
F. Bodon, L. Schmidt-Thieme: The Relation of Closed Itemset Mining, Complete Pruning Strategies and Item Ordering in APRIORI-based FIM algorithms, Proc. of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases 437-444, Porto, Portugal, 2005
F. Bodon: Trie-based APRIORI Implementation for Mining Frequent Itemsequences, Workshop on Open Source Data Mining, Chicago, USA, 2005
CS.I. Sidló, A. Lukács: Shaping SQL-Based Frequent Pattern Mining Algorithms, Proc. KDID 05 workshop in conjunction with ECML/PKDD, 2005
S. Ambrose, M. Neunhöffer, C.E. Praeger, Cs. Schneider: Generalized sifting in black-box groups, London Math. Soc. J. Comput. Math (8) 217-250, 2005
D. Fogaras, B. Rácz: Scaling Link-based Similarity Search, Proc. of the International World Wide Web Conference, 641-650, Chiba, Japan, 2005
A.A. Benczúr, K. Csalogány, T. Sarlós, M. Uher: SpamRank-Fully Automatic Link Spam Detection, Proc. of the 1st International Workshop on Adversarial Inf. Retrieval on the Web, Chiba, Japan, 2005
D. Marx:: List edge multicoloring in graphs with few cycles., Information Processing Letters, 89(2):85-90, 2004
Cohen, AM; Ivanyos, Gábor: Root filtration spaces from Lie algebras and abstract root groups, Journal of Algebra 300/2 pp.433-454, 2006
Felszeghy, B; Rónyai, Lajos: On the lexicographic standard monomials of zero dimensional ideals, Proceedings of the 10th Rhine workshop on computer algebra. Basel, 2006. pp. 95-105, 2006
Z. Dezső; E. Almaas; András Lukács; Balázs Rácz; I. Szakadát; A.-L. Barabási: Dynamics of Information Access on the Web, Phys. Rev. E 73/06 pp. 066132, 2006
Hegedűs, Gábor; Rónyai, Lajos: Standard monomials for partitions, Acta Mathematica Hungarica 111/3. pp.193-212, 2006
Schneider, Csaba: Small derived quotients in finite p-groups, Publicationes Mathematicae-Debrecen 69/3 pp. 373-378, 2006
Felszeghy, Bálint; Ráth, Balázs; Rónyai, Lajos: The lex game and some applications, Journal of Symbolic Computation 41, pp. 663-681, 2006
Friedl, K; Ivanyos, Gábor; Santha, M; Verhoeven, YF: Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes, Lecture Notes in Computer Science. 3998, pp. 380-391, 2006
Schönhofen, Péter; Benczúr, András: Exploiting extremely rare features in text categorization, Lecture Notes in Artificial Intelligence, ISBN: 978-3-540-45375-8, 4212, pp. 759-766, 2006
Team of the Informatics Laboratory: Detecting Nepotistic Links by Language Model Disagreement, Proceedings of WWW2006, poster section 939 - 940, 2006
Tamás Sarlós; András Benczúr; Balázs Rácz; Károly Csalogány; Fogaras Dániel: To Randomize or Not To Randomize: Space Optimal Summaries for Hyperlink Analysis, Proceedings of WWW2006 297-306, 2006
Dezső, Z; Almaas, E; Lukács, András; Rácz, Balázs; Szakadát, I; Barabási, AL: TDynamics of information access on the web, Physical Review E, 73, pp 066132-1-066132-6, 2006
Sarlós, Tamás: Improved approximation algorithms for large matrices via random projections, FOCS 2006. 47th annual IEEE symposium on foundations of computer science. Berkeley, 2006, pp. 143-152, 2006
Péter Schönhofen: Identifying Document Topics Using the Wikipedia Category Network, Web Intelligence, pp. 456-462, 2006
András Benczúr; Károly Csalogány; Tamás Sarlós: Similarity Search to Fight Web Spam, Airweb 2006 in conjunction with SIGIR 2006, 2006
Rácz, Balázs; Sidló, Csaba István; Lukács, András; Benczúr, András: Two-phase data warehouse optimized for data mining, VLDB 2006. First international workshop on business intelligence for the real time enterprise (BIRTE, 67-81, 2006
Demetrovics, János; Katona, GOH; Miklós, D; Thalheim, B: On the number of independent functional dependencies, Lecture Notes in Computer Science, 3861, pp. 83-91, 2006



Back »