Dansker løser 33 år gammelt datakomprimeringsproblem
Kilde: 
14 november 2017

Danske Kasper Green Larsen fra Aarhus Universitet og hans amerikanske makker, Jelani Nelson, fra Harvard har vakt international opsigt, efter de har fundet løsningen på et 33 år gammelt datakomprimeringsproblem. Det skriver Ingeniøren.

Big data er blevet til big business, og flere og flere virksomheder får øjnene op for det digitale guld. Problemet er bare, at data fylder.

Derfor skal de store mængder data komprimeres, og det skal ske på en måde, der bevarer egenskaberne fra den rå data, så man stadig kan søge hurtigt og effektivt i det komprimerede datasæt.

En smart måde er at omsætte data til vektorer - det vil sige objekter med længde og retning - i flere dimensioner. Her opstår til gengæld et nyt problem: Nemlig en uhåndterbar mængde af dimensioner.
For eksempel kan det resultere i en vektor med flere millioner dimensioner, når man skal analysere indholdet af en simpel e-mail med 1.000 ord.

Den nye udfordring er altså at reducere antallet af dimensioner i det komprimerede datasæt til en overskuelig og håndterbar mængde.

En udbredt metode er ved hjælp af det såkaldte Johnson-Lindenstrauss lemma fra 1984, der bliver brugt i alt fra spamfiltre til biologi. Sætningen siger kort sagt, at det er muligt at reducere antallet af dimensioner, hvis man tillader at ændre på afstanden mellem vektorerne.

Her kommer det dansk-amerikanske makkerpar ind i billedet. De har nemlig bevist, at det 33 år gamle lemma ikke bare er en god, men den optimale metode til at reducere antallet af dimensioner i data.

Samtidig har de opdaget, hvor meget man kan reducere dimensionerne uden at forvrænge geometrien for meget:

»Vi har nu en fuld matematisk forståelse af, hvor meget højdimensionel data kan komprimeres. Udover at dataloger ikke mere skal bruge tid på at forske i metoder til at komprimere data, betyder det også, at vi kan sætte alle kræfter ind på at gøre komprimeringsprocessen hurtigere. Datamængderne bliver kun større i fremtiden, så hurtigere algoritmer er essentielle« siger Kasper Green Larsen til Ingeniøren.

mdm

Ovenstående er udvalgt og resumeret af Videnskab.dk, men redaktionen har ikke udført selvstændig research. Gå til den oprindelige kilde for flere detaljer.