US 7,734,652 B2 · Non-negative matrix factorization from the data in the multi-dimensional data table using the specification and to store metadata representing the built relational database management system

Abstract

An implementation of NMF functionality integrated into a relational database management system provides the capability to apply NMF to relational datasets and to sparse datasets. A database management system comprises a multi-dimensional data table operable to store data and a processing unit operable to perform non-negative matrix factorization on data stored in the multi-dimensional data table and to generate a plurality of data tables, each data table being smaller than the multi-dimensional data table and having reduced dimensionality relative to the multi-dimensional data table. The multi-dimensional data table may be a relational data table.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims21

Dependent claims

A database management system comprising:

a processor to execute computer program instructions and process data;
a memory to store the computer program instructions executable by the processor and a multi-dimensional data table to store data;
and
computer program instructions stored in the memory and executable to generate a plurality of data tables from the data stored in the multi-dimensional data table using non-negative matrix factorization, wherein each one of the plurality of data tables is an approximate factor of the multi-dimensional data table;
wherein the computer program instructions are further executable to implement:
a server application programming interface to provide an interface to client software to construct a specification for a relational database model including non-negative matrix factorization model as the result of a build task performed by a build unit;
the build unit to build the relational database model including non-negative matrix factorization from the data in the multi-dimensional data table using the specification and to store metadata representing the built relational database model including non-negative matrix factorization in a database;
and
an apply unit to apply the relational database model including non-negative matrix factorization stored in the database to the data in the multi-dimensional data table, wherein at least one of the build unit and the apply unit is operable to un-nest nested table columns in the multi-dimensional data table and to explode categorical attributes in the multi-dimensional data table into a series of binary attributes.

6 more elements

A computer program product for operating a database management system comprising a processor to execute computer program instructions and process data, and a memory to store the computer program instructions executable by the processor, the computer program product comprising a computer readable recordable-type storage medium, and computer program instructions, recorded on the computer readable recordable-type storage medium, executable by a processor, for performing the steps of:

storing data in a multi-dimensional data table;
and
generating a plurality of data tables from the data stored in the multi-dimensional data table using non-negative matrix factorization, wherein each one of the plurality of data tables is an approximate factor of the multi-dimensional data table;
providing a server application programming interface to provide an interface to client software to construct a specification for a relational database model including non-negative matrix factorization as the result of a build task;
performing a build task to build the relational database model including non-negative matrix factorization from the data in the multi-dimensional data table using the specification and to store metadata representing the built relational database model including non-negative matrix factorization in a database;
and
performing an apply task to apply the relational database model including non-negative matrix factorization stored in the database to the data in the multi-dimensional data table, wherein at least one of the building step and the applying step comprises:
un-nesting nested table columns in the multi-dimensional data table;
and
exploding categorical attributes in the multi-dimensional data table into a series of binary attributes.

7 more elements

Dependencies are inferred from the claim text.

Description3,892 words

Summary848 words

#1. Field of the Invention

#The present invention relates to providing an implementation of Non-negative Matrix Factorization functionality integrated into a relational database management system

#2. Description of the Related Art

Brief description of the drawings6 figures

#Further features and advantages of the invention can be ascertained from the following detailed description that is provided in connection with the drawings described below:

#FIG. 1 illustrates an example of the application of NMF to a dataset.

#FIG. 2 is an exemplary flow diagram of a process of iteratively generating the factorization matrices W and H.

Detailed description2,926 words

#The present invention provides an implementation of NMF functionality integrated into a relational database management system (RDBMS). This provides the capability to apply NMF to relational datasets, to sparse datasets, and categorical attributes.

#Given an N (rows)×M (columns) two-dimensional (2D) dataset V and k<N, M, NMF computes an approximation of the original data V as V˜V′=W×H, where W is N by k, and H is k by M. Starting from random initial conditions, W and H are iteratively updated until convergence to a local minimum is achieved, monitored by the minimization of the Euclidean cost function. Alternatively, a divergence cost function can be used. V must have positive entries, and so do W and H by construction. Even though localization is not an explicit property of the algorithm, NMF appears to produce quite localized and sparse features that facilitate the interpretation of results and the transparency of the model. For example, when NMF is applied to a dataset of facial images, the extracted features are facial parts: eyes, noses etc. When the dataset is a document/keyword matrix then NMF extracts “semantic” features.

#An example of the application of NMF to a dataset is shown in FIG. 1. Dataset V 102 is a 2D dataset having dimensions x and y. V 102 has n entries in the x dimension and m entries in the y dimension. Encoding coefficients W 104 is 2D and has dimensions x and u, with n entries in the x dimension and k entries in the u dimension. Basis model H 106 is 2D and has dimensions v and y, with k entries in the v dimension and m entries in the y direction. NMF constructs approximate factorizations of the input data matrix V [N×M] as V˜V′=WH where W and H are two smaller matrices. V must have positive entries, and so do W and H by construction (V, W, and H>0). Starting from non-negative initial conditions of W and H, iterations of the multiplicative update rules converge to a local maximum of the objective function. The dimensions of W and H are N×K and K×M respectively. In general K<<NM, or (N+M) K<NM so that W and H are a “compressed” representation of V. This method uses only additive contributions and therefore avoids cancellations. In particular, decomposition is performed by additive mixture of positive components:

Facts

Application

10/927,083Filed 27 Aug 2004 · us provisional application

Priority

29 Aug 2003

Published

US 2005/0246354 A13 Nov 2005

Granted

8 Jun 2010

Term ends

26 Dec 2027

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 1,216 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification3 codes

G06F 16/283
Databases characterised by their database models, e.g. relational or object models: multi-dimensional databases or data warehouses, e.g. MOLAP or…
G06F 16/2465
Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries: query processing support for facilitating data mining…
G06F
Computing and data processing

Timeline

29 Aug 2003Priority claimedParent application 60/498,700
27 Aug 2004Application filedUS 10/927,083
7 Feb 2005Assigned to Oracle International Corporationassignment of assignor's interest
3 Nov 2005PublishedUS 2005/0246354 A1
8 Jun 2010GrantedUS 7,734,652 B2
12 Oct 2026TodayWithin its term
26 Dec 2027Term endsEstimated, includes 1,216 days of adjustment

Non-negative matrix factorization from the data in the multi-dimensional data table using the specification and to store metadata representing the built relational database management system

Life of this patent

Non-negative matrix factorization from the data in the multi-dimensional data table using the specification and to store metadata representing the built relational database management system

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims21

Description3,892 words

Drawings

Classification3 codes

Life of this patent

Description3,892 words