Information Technology (Council of Physical Sciences)
100 %
Panel
Informatics and Electrical Engineering
Department or equivalent
HUN-REN Institute for Computer Science and Control
Starting date
2006-02-01
Closing date
2009-01-31
Funding (in million HUF)
3.449
FTE (full time equivalent)
1.28
state
closed project
Summary in Hungarian
Az utóbbi évek technológiai fejlődése új kihívásokat teremtett az adattömörítés terén. Új tömörítési eljárásokra van szükség a hálózati kommunikáció terén, ahol a tömörített adatot több felhasználónak kell eljuttatni, akik különböző kapacitású csatornákon keresztül kapcsolódnak egymáshoz. A veszteséges csomagkapcsolt hálózatokban az előforduló csomagvesztések a hagyományos tömörítési algoritmusok komoly teljesítménycsökkenését eredményezhetik. A kommunikáció során egyre nagyobb teret kapnak a kis késleltetést igénylő alkalmazások, illetve ezzel párhuzamosan - különösen a mobil eszközök elterjedésével - egyre nagyobb az igény a kis számításigényű kódoló és dekódoló eljárások széleskörű elterjedésére. A kutatás során a modern adattömörítés elméleti és gyakorlati problémáit szeretném vizsgálni, elsősorban a veszteséges hálózati tömörítési eljárásokra illetve kis késleltetésű szekvenciális tömörítési eljárásokra koncentrálva. Emellett kiemelten szeretnék foglalkozni a kódolási eljárások általános komplexitási kérdéseivel mind a veszteséges, mind a veszteségmentes tömörítés terén.
Summary
Advances in communications technologies create new challanges in data compression. Novel compression methods are needed in network communications, when compressed data is to be transmitted to several users who are connected via channels of different capacity. In lossy packet networks, data compression algorithms might suffer a substential loss in performance if packets are lost. Also, applications requirig small delay are increasingly popular, and, in parallel – together with the spread of mobil equipments – low complexity encoding and decoding algorithms are needed. In this research I propose to study practical and theoretical issues in modern data compression, with emphasis on lossy network source coding and a limited-delay sequential compression. Beside, I would like to concentrate on the study of general complexity issues in both lossless and lossy data compression.
Final report
Results in Hungarian
Univerzális, kis késleltetésű kódokat terveztünk individuális sorozatok veszteséges tömörítésére, melyek ugyanolyan jó teljesítményt nyújtanak, mint a sorozathoz illesztett legjobb időben változó kód egy referenciaosztályból, mely az alkalmazott kódolási eljárást időről időre változtathatja. Hatékony, kis komplexitású implementációt készítettünk arra az esetre, amikor az alap-referenciaosztály a hagyományos vagy bizonyos hálózati skalárkvantálók osztálya.
Új útvonalválasztási módszereket dolgoztunk ki kommunikációs hálózatokra, melyek aszimptotikusan ugyanolyan jó QoS (csomagvesztési arány, késleltetés) eredményt adnak, mint a változó hálózati környezethez (utólag) illesztett legjobb út. Kiemelendő, hogy a módszer teljesítménye és komplexitása időben optimális konvergenciasebesség mellett a hálózat méretével (és nem az utak számával) skálázik.
Kísérletek szerint az elterjedt standard bájt-alapú tömörítő algoritmusok rosszul teljesítenek, ha a forrás nem bájt-alapú, ugyanakkor a bit-alapú módszerek jól működnek bájt-alapú forrásokra is (továbbá komplexitásuk - az alkalmazott kisebb ábécé miatt - gyakran lényegesen kisebb). Ezt a megfigyelést elméletileg is igazoltuk, megvizsgálva, hogy hogyan közelíthetőek blokk-Markov-források magasabb rendű szimbólum-alapú Markov-modellek segítségével.
Megoldottuk a ládapakolási probléma egy szekvenciális, on-line változatát, mely alkalmazható bizonyos, kevés erőforrással rendelkező szenzorok hatékony adásütemezésére.
Results in English
We designed limited-delay data compression methods that perform asymptotically as well as the best time-varying code from a reference family (matched to the source sequence in hindsight) that can change the employed base code several times. We provided efficient, low-complexity solutions for the cases when the base reference class is the set of traditional or certain network scalar quantizers.
We developed routing algorithms for communication networks that can provide asymptotically as good QoS parameters (such as packet loss ratio or delay) as the best fixed path in the network matched to the varying conditions in hindsight. The performance and complexity of the developed methods scale with the size of the network (instead of with the number of paths) even when the rate of convergence (in time) is optimal.
Experiments indicate that data for which bytes are not the natural choice of symbols compress poorly using standard byte-based implementations of lossless data compression algorithms, while algorithms working on a bit level perform reasonably on byte-based data (in addition to having computational advantages resulting from operating on a small alphabet). We explained this phenomenon by analyzing how block Markov sources can be approximated with symbol-based higher order Markov sources.
We provided a solution to a sequential on-line version of the bin packing problem, which can be applied to schedule transmissions for certain sensors with limited resources.
Nagy DA, György A, Linder T: Symbol-Based Modeling and Coding of Block Markov Sources, IEEE Transactions on Information Theory, 52: 5570-5578, 2006
György A, Linder T, Lugosi G: Tracking the best quantizer, IEEE Transactions on Information Theory, vol. 54(4):1604-1625, 2008
György A, Linder T, Ottucsák Gy: The Shortest Path Problem Under Partial Monitoring, Proceedings of the 19th Annual Conference on Learning Theory, COLT 2006, LNAI 4005, pp. 468-482, 2006
György A, Linder T, Lugosi G: The Shortest Path Problem in the Bandit Setting, Proceedings of the 2006 IEEE Information Theory Workshop, pp. 87-91, Punta del Este, Uruguay, 2006
György A, Linder T, Lugosi G, Ottucsák Gy: The On-line Shortest Path Problem under Partial Monitoring, Journal of Machine Learning Research, 8:2369-2403, 2007
György A, Lugosi G, Ottucsák Gy: On-line sequential bin packing, Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008), pp. 447-454. (Helsinki, Finland, July 9-12), 2008, 2008
György A, Lugosi G, Ottucsák Gy: On-line sequential bin packing, Journal of Machine Learning Research, beküldve, 2009
György A, Linder T, Lugosi G: Efficient tracking of the best of many experts, Information and Communication Conference (Budapest, August 25-28), pp. 3-4, 2008
