A method for decoding encoded structured data from a bit-stream comprising a plurality of encoded data units having the steps of, obtaining unit information comprising positions of the encoded data units within the bit-stream, retrieving the encoded data units from the bit-stream based on the unit information, creating decoding tasks for decoding the retrieved encoded data units, assigning the created decoding tasks to cores of a multi-core decoder, based on estimated decoding costs of the encoded data units, running the tasks on their assigned cores to decode the encoded data units in parallel is disclosed. It is applied to the decoding of XML documents in the EXI format.