Patent · US Active

Dictionary-based order-preserving string compression for main memory column stores

US7868789B1 · kind B1 · utility

35Cited by

3References

20Claims

0Family size

Assignee

SAP AG · DE

Inventors

Carsten Binnig · Elztal, DE
Franz Faerber · Walldorf, DE
Stefan Hildenbrand · Altdorf, CH

Key dates

Filing date	Jun 28, 2009
Grant date	Jan 11, 2011
Priority date	—
Expiry date	Jun 28, 2029

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/24561
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

Methods and systems are described that involve usage of dictionaries for compressing a large set of variable-length string values with fixed-length integer keys in column stores. The dictionary supports updates (e.g., inserts of new string values) without changing codes for existing values. Furthermore, a shared-leaves approach is described for indexing such a dictionary that compresses the dictionary itself while offering access paths for encoding and decoding.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.