System and method for informational reduction
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11031959-B1
Publication Date
2021-06-08
Expiration Date
Abstract
Information reduction in data processing environments includes at least one of: one or more Error Correcting Codes that decode n-vectors into k-vectors and utilize said decoding to information-reduce data from a higher dimensional space into a lower dimensional space. The information reduction further provides for a hierarchy of information reduction allowing a variety of information reductions. Transformations are provided to utilize available data space, and data may be transformed using several techniques including windowing functions, filters in the time and frequency domains, or any numeric processing on the data.
Core Innovation
The invention provides an information-reduction framework that performs dimensional reduction from n-dimensional n-vectors to k-dimensional k-vectors with n>k using error correcting code ECC(n,k) decoding. Noisy or received n-vectors are treated as inputs that are mapped to similar inputs within an error-correction capability of the ECC, thereby generating a reduced representation k-vector from each n-vector.
The framework specifies use of minimum distance d and finite fields GF(q) for constructing and operating ECC(n,k). It discusses error-correcting codes over finite fields and references the Singleton bound and Maximum Separable (MDS) code concepts, including Reed-Solomon, BCH, Hamming, Golay, and convolutional codes, as well as hierarchical multi-tier ECC layering.
The reduced representations produced by ECC-decoding dimensional reduction are applied to hashing and locally sensitive hashing (LSH), where ECC-decoding supports neighbor identification for nearest-neighbor and proximity search. The document also describes applying these reduced representations to biometrics and related searches, including fingerprint recognition, voiceprints, and spoken passwords, as well as preprocessing transforms applied to n-vectors and system deployment using commodity operating systems with kernel modules/plugins/interception layers and dataflow pipelines.
Claims Coverage
The independent claims cover a CPU-based system that stores ECC(n,k) and decodes length-n n-vectors into length-k k-vectors for information reduction, with n>k. Across the dependent claims summarized in the provided claim set, the claims add constraints on ECC type, minimum distance d, finite-field vector domains, software/OS implementation, and preprocessing contexts.
ECC-based dimensional reduction from n-vectors to k-vectors
The system stores one or more Error Correcting Code ECC(n,k) of length n and dimension k, where n>k, and vectors of length n (n-vector); and a CPU decodes the n-vector using the ECC(n,k) to generate a k-vector and stores the k-vector.
ECC with minimum distance d
The system specifies that the ECC(n,k) is an error correcting code with a minimum distance d.
ECC selection among Reed-Solomon, BCH, Golay, Hamming, and convolution
The system specifies that the ECC(n,k) is selected from Reed-Solomon, BCH, Golay, Hamming, convolution, or other length-n, dimension-k error correcting codes.
Vector domain over a finite field F
The system specifies that the finite field F used in the system has a number of elements that is a power of 2, and that n-vectors and k-vectors consist of elements from a finite field F.
Pre-processing transforms for recognition/biometric use
The system transforms each n-vector as pre-processing before performing information reduction for one or more of speech recognition, voiceprints, optical character recognition, or other biometrics.
Decoding over multiple encoded instances ECC_i for i=1..m
The system stores error correcting code ECC_i of length n_i and dimension k_i configured as n_i-vectors and k_i-vectors, where i=1..m, m>=1, and n_i>k_i; and the CPU decodes each n_i-vector using ECC_i to generate the corresponding k_i-vector and stores the k_i-vector.
Host operating system selection
The system is specified to use a host operating system selected from Linux, UNIX, Solaris, HP/UX, Android, iOS, MacOS, or Microsoft Windows.
ECC_i implemented using software components
The system is defined so that each ECC_i is implemented using one or more software components, such as applications, processes/threads, device drivers, kernel modules/extensions, plug-ins, or other software implementations.
Overall, the claim coverage centers on using ECC(n,k) decoding to generate reduced k-vectors from n-vectors with n>k, with added constraints on ECC properties and on system contexts including multi-instance ECC_i, host operating system selection, software-component implementation, and pre-processing for recognition and biometrics.
Stated Advantages
Reduces dimensionality from n-dimensional n-vectors to k-dimensional k-vectors using ECC-decoding.
Enables mapping noisy or received n-vectors to similar inputs within the ECC’s error-correction capability.
Supports hashing and locally sensitive hashing (LSH) through ECC-decoding based reduced representations.
Enables nearest-neighbor and proximity search via ECC-decoding as neighbor identification.
Applicable to biometrics including fingerprint recognition, voiceprints, and spoken passwords.
Documented Applications
Hashing and locally sensitive hashing (LSH) using ECC-decoding based reduced representations.
Nearest-neighbor search and proximity search using ECC-decoding as neighbor identification.
Biometric applications including fingerprint recognition, voiceprints, and spoken passwords.
Speech recognition, optical character recognition, and other biometrics using pre-processing transforms on n-vectors.
System deployment using commodity operating systems with kernel modules, plug-ins, interception layers, and dataflow pipelines.
Interested in licensing this patent?