Sparse linear algebra in column-oriented in-memory database

US10067909B2 · kind B2 · utility

Assignee

• SAP SE · DE

Inventors

• David Kernert · Heidelberg, DE
• Frank Koehler · Heidelberg, DE
• Wolfgang Lehner · Dresden, DE

Key dates

• Filing date: Jun 25, 2014
• Grant date: Sep 4, 2018
• Expiry date: Jan 16, 2035

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/221
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

Embodiments relate to storing sparse matrices in an in-memory column-oriented database system. Specifically, recent hardware shifts of primary storage from disc into memory, allow execution of linear algebra queries directly in the database engine. Dynamic matrix manipulation operations (like online insertion or deletion of elements) are not covered by most linear algebra frameworks. Therefore a hybrid architecture comprises a read-optimized main structure, and a write-optimized delta structure. The resulting system layout derived from the Compressed Sparse Row (CSR) representation, integrates well with a columnar database design. Moreover, the resulting architecture is amenable to a wide range of non-numerical use cases when dictionary encoding is used. Performance in specific examples is evaluated for dynamic sparse matrix workloads, by applying work flows of nuclear science and network graphs. Embodiments allow performing linear algebra operations on large, sparse matrices commonly associated with scientific computations and analytical business applications.