Patent application EP20180485A (EP), filed 2020-06-17
Publication number: EP3754516A1
Title: ADVANCED DATABASE DECOMPRESSION
Abstract: A method, a system, and a computer program product for decompressing data. One or more compressed blocks in a set of stored compressed blocks responsive to a request to access data in the set of stored compressed blocks are identified. String prefixes inside the identified compressed blocks are decompressed using front coding. String suffixes inside the identified compressed blocks are decompressed using a re-pair decompression. Uncompressed data is generated.
IPC codes: G06F  16/    22            A I
Claims: number: 1
text: A computer-implemented method, comprising:
number: 2
text: The method according to claim 1, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks;
the one or more compressed blocks are generated from one or more front coded buckets of strings in a dictionary, the one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more compressed blocks.
number: 3
text: The method according to claim 2, wherein the symbol tree includes a plurality of nodes, wherein the plurality of nodes includes at least one of the following: a terminal character, a non-terminal character, and any combination thereof.
number: 4
text: The method according to claim 3, further comprising performing a plurality of re-pair decompressions in parallel.
number: 5
text: The method according to claim 3 or 4, wherein the number of terminal characters is limited to a predetermined number, wherein the number of iterative expansions of each symbols is determined based on the predetermined number.
number: 6
text: The method according to claim 4 or 5, wherein the re-pair decompression includes
initializing a stack position in a memory corresponding to each symbol in the symbol tree;
simultaneously loading, using vector instructions, each symbol in the symbol tree from storage into the memory;
combining loaded symbols into the uncompressed data by evaluating one or more predicates associated with the symbols; and
repeating, using the predetermined number, the simultaneously loading and the combining.
number: 7
text: The method according to any one of the preceding claims, wherein each block in the set of compressed blocks includes a sequence of bucket headers and compressed buckets, and/or
wherein the block size is at least one of the following: a fixed size and a variable size, and/or,
wherein the one or more compressed blocks are compressed using re-pair compression.
number: 8
text: A system comprising:
number: 9
text: The system according to claim 8, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks;
the one or more compressed blocks are generated from one or more front coded buckets of strings in a dictionary, the one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more compressed blocks.
number: 10
text: The system according to claim 9, wherein the symbol tree includes a plurality of nodes, wherein the plurality of nodes includes at least one of the following: a terminal character, a non-terminal character, and any combination thereof, and, optionally,
wherein the number of terminal characters is limited to a predetermined number, wherein the number of iterative expansions of each symbols is determined based on the predetermined number.
number: 11
text: The system according to any one of claims 8 to 10, wherein the operations further comprise performing a plurality of re-pair decompressions in parallel.
number: 12
text: The system according to claim 11, wherein the re-pair decompression includes
initializing a stack position in a memory corresponding to each symbol in the symbol tree;
simultaneously loading, using vector instructions, each symbol in the symbol tree from storage into the memory;
combining loaded symbols into the uncompressed data by evaluating one or more predicates associated with the symbols; and
repeating, using the predetermined number, the simultaneously loading and the combining.
number: 13
text: The system according to any one of claims 8 to 12, wherein each block in the set of compressed blocks includes a sequence of bucket headers and compressed buckets, and/or
wherein the block size is at least one of the following: a fixed size and a variable size, and/or
wherein the one or more compressed blocks are compressed using re-pair compression.
number: 14
text: A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
number: 15
text: The computer program product according to claim 14, wherein the re-pair decompression includes iteratively expanding each symbol in a symbol tree corresponding to the data stored in the identified compressed blocks;
the one or more compressed blocks are generated from one or more front coded buckets of strings in a dictionary, the one or more front-coded buckets are configured to be sampled to form one or more superblocks, wherein each one or more superblocks are configured to be compressed to generate a shared grammar for compression of the one or more compressed blocks.
Office action: search_report, dated 2020-12-23
Rejection reasons: novelty_epc_54
Prior art cited: ref_id: EP2889787A2
ref_type: patent
severity: background
ref_id: - BRISABOA NIEVES R ET AL: "Compressed String Dictionaries", 5 May 2011, BIG DATA ANALYTICS IN THE SOCIAL AND UBIQUITOUS CONTEXT : 5TH INTERNATIONAL WORKSHOP ON MODELING SOCIAL MEDIA, MSM 2014, 5TH INTERNATIONAL WORKSHOP ON MINING UBIQUITOUS AND SOCIAL ENVIRONMENTS, MUSE 2014 AND FIRST INTERNATIONAL WORKSHOP ON MACHINE LE, ISBN: 978-3-642-17318-9, XP047432531
ref_type: npl
severity: background
ref_id: - INGO M?LLER ET AL: "Adaptive String Dictionary Compression in In-Memory Column-Store Database Systems", 24 March 2014 (2014-03-24), XP055198200, Retrieved from the Internet <URL:http://openproceedings.org/EDBT/2014/paper_25.pdf> [retrieved on 20150624], DOI: 10.5441/002/edbt.2014.27
ref_type: npl
severity: background
ref_id: EP2889787
ref_type: patent
severity: novelty_destroying
ref_id: - BRISABOA NIEVES R ET AL, Compressed String Dictionaries, BIG DATA ANALYTICS IN THE SOCIAL AND UBIQUITOUS CONTEXT : 5TH INTERNATIONAL WORKSHOP ON MODELING SOCIAL MEDIA, MSM 2014, 5TH INTERNATIONAL WORKSHOP ON MINING UBIQUITOUS AND SOCIAL ENVIRONMENTS, MUSE 2014 AND FIRST INTERNATIONAL WORKSHOP ON MACHINE LE, (20110505), ISBN 978-3-642-17318-9, XP047432531 [X] 1,8,14 * the whole document * [A] 2-7,9-13,15
ref_type: npl
severity: novelty_destroying
ref_id: - Ingo M?ller ET AL, "Adaptive String Dictionary Compression in In-Memory Column-Store Database Systems", doi:10.5441/002/edbt.2014.27, (20140324), URL: http://openproceedings.org/EDBT/2014/paper_25.pdf, (20150624), XP055198200 [X] 1,8,14 * the whole document * [A] 2-7,9-13,15
ref_type: npl
severity: novelty_destroying
Final disposition: pending (2020-12-23)