System and method for informational reduction

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.

Claims

1. A system, comprising: one or more memory locations configured to store 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 one or more Central Processing Unit (CPU) operatively connected to said one or more memory locations and configured to decode said n-vector using said ECC(n,k) to generate a k-vector and store said k-vector in the one or more memory locations.

2. The system according to claim 1, wherein said CPU execute said one or more ECC(n,k) on a host with a host operating system that is one of Linux, UNIX, Solaris, HP/UX, Android, iOS, MacOS, or Microsoft Windows.

3. The system according to claim 1, wherein one or more pairs of (n-vector, k-vector) are stored in one of said second memory locations, and wherein a pair's k-vector is an information-reduced representation of the pair's n-vector.

4. The system according to claim 1, wherein said ECC(n,k) reduces the n-dimensional n-vector to a k-dimensional k-vector, and said ECC(n,k) is one or more of a linear error correcting code and a Maximum Separable (MDS) error correcting code.

5. The system according to claim 1, wherein said ECC(n,k) is an error correcting code with a minimum distance d.

6. The system according to claim 1, wherein said ECC(n,k) is one of a Reed-Solomon (RS) error code, a Bose, Ray-Chaudhuri, Hocquenghem (BCH) error correcting code, Golay error correction code, Hamming error correcting code, convolution code, other error correcting code of length n with dimension k.

7. The system according to claim 1, wherein said n-vectors and said k-vectors are comprised of elements from a finite field F.

8. The system according to claim 7, wherein said finite field F has a number of elements that is a power of 2.

9. The system according to claim 1, wherein said ECC is implemented as one or more of an application, one or more processes and threads, a device driver, a kernel module, a kernel extension, a plug-in, or other software implementation.

10. The system according to claim 1, wherein each n-vector is transformed prior to information reduction using a windowing function.

11. The system according to claim 10, where said windowing function is one of rectangular, triangular, Parzen, Welch, Hamming and Generalized Hamming, Hann, or other Windowing function.

12. The system according to claim 1, wherein each n-vector is transformed prior to information reduction using an inverse Fisher transform.

13. The system according to claim 1, wherein each n-vector is transformed prior to information reduction as pre-processing for one or more of speech recognition, voiceprints, optical character recognition, or other biometrics.

14. The system according to claim 1, wherein each n-vector is transformed prior to information reduction as pre-processing for a search application, or other alphanumeric processing application.

15. A system, comprising: one or more memory locations configured to store one or more Error Correcting Code ECC.sub.i of length n.sub.i and dimension k.sub.i configured as n.sub.i-vectors and k.sub.i-vectors, where i=1 . . . m, m>=1, and n.sub.i>k.sub.i; and one or more Central Processing Unit (CPU) operatively connected to said one or more memory locations and configured to decode said n-vector using said ECC(n,k) to generate a k.sub.i-vector and stores said k.sub.i-vector in the one or more memory locations.

16. The system according to claim 15, wherein said host operating system is one of Linux, UNIX, Solaris, HP/UX, Android, iOS, MacOS, or Microsoft Windows.

17. The system according to claim 15, wherein each said ECC.sub.i is one or more of linear error correcting code, Convolution error correcting code, and a Maximum Separable (MDS) error correcting code.

18. The system according to claim 15, wherein each said ECC.sub.i is one of a Reed-Solomon (RS) error code, a Bose, Ray-Chaudhuri, Hocquenghem (BCH) error correcting code, Golay error correction code, Hamming error correcting code, and other error correcting code of length n.sub.i with dimension k.sub.i.

19. The system according to claim 15, wherein each said n.sub.i-vectors and said k.sub.i-vector are comprised of elements from a finite field F.

20. The system according to claim 15, wherein each said ECC.sub.i is implemented as one or more of an application, one or more processes and threads, a device driver, a kernel module, a kernel extension, a plug-in, or other software implementation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The application will be more fully understood by reference to the following drawings which are for illustrative purposes only:

(2) FIG. 1 is a block diagram of the core system architecture

(3) FIG. 2 is a block diagram illustrating information reduction and an encoding and decoding pipeline.

(4) FIG. 3 is a block diagram illustrating code words in an error correcting code.

(5) FIG. 4 is a block diagram illustrating multiple error correcting codes over the same code words

(6) FIG. 5 is a block diagram illustrating dimensional reduction and pre-computation.

(7) FIG. 6 is a block diagram illustrating identifying similar fingerprints.

(8) FIG. 7 is a block diagram illustrating hierarchical dimensional reduction.

(9) FIG. 8 is a block diagram illustrating transformations.

(10) FIG. 9 is a block diagram illustrating sensor readings and normalization.

(11) FIG. 10 is a block diagram illustrating various data flows.

(12) FIG. 11 is a block diagram illustrating various configurations.

DETAILED DESCRIPTION OF THE APPLICATION

(13) Referring more specifically to the drawings, for illustrative purposes the present application will be disclosed in relation to FIG. 1 through FIG. 11. It will be appreciated that the system and apparatus of the application may vary as to configuration and as to details of the constituent components, and that the method may vary as to the specific steps and sequence, without departing from the basic concepts as disclosed herein.

0. INTRODUCTION

(14) The context in which this application is disclosed is an application running on one computer. Without affecting the general case of multiple applications, the following disclosures often depict and describe just one application. Multiple primary applications are handled in a similar manner.

(15) Likewise, the disclosures generally describe applications with one or two processes; any number of processes is handled in a similar manner. Finally, the disclosures generally describe one or two threads per process; any number of threads is handled in a similar manner

1. OVERVIEW

(16) FIG. 1 illustrates by way of example embodiment 10 the overall structure of the present application. The following brief overview illustrates the high-level relationship between the various components; further details on the inner workings and interdependencies are provided in the following sections. FIG. 1 Illustrates by way of example embodiment 10 a host 12 with an application 16 loaded into system memory 14. The application 16 is comprised of two processes; process A 18 and process B 20. Each of the two processes has two running threads. Process A contains thread T0 22 and thread T1 24, while process B contains thread T3 26 and thread T4 28. As part of loading the application 16 an interception layer (IL) 23, 29 is pre-loaded into the address space of each process. Interception Layer 23 for process A is preloaded into process A's address space and Interception Layer 29 is preloaded into process B's address space. The system libraries and system services 36 are generally interposed between the application 16 and operating system 38. Alongside with the operating system 38 are the loadable kernel modules 30.

(17) System resources, such as CPUs 46, I/O devices 44, Network interfaces 42 and storage 40 are accessed using the operating system 38 and the loadable kernel modules 30. Storage may include hard drives, flash drives, or other non-transitory storage devices. Devices accessing remote resources use some form of transport network 48. By way of example, system networking 42 may use TCP/IP over Ethernet transport, Storage 40 may use Fibre Channel or Ethernet transport, and I/O 44 may use USB.

(18) One or more external devices 45 may be connected to the host 12 either via the network 48 or a connection though I/O 44, or through other interfaces.

(19) FIG. 1 illustrates the system libraries 36 as separate from the application 16 and the individual processes process A 18 and process B 20. The system libraries are generally shared libraries. For clarity of presentation, the system libraries are depicted outside the address space of the individual processes, even though some library state and code is present within the address space of the individual application processes.

(20) In an alternate embodiment the functionality of the kernel module 30 is built into, i.e. compiled into, the kernel. This eliminates the need to load the kernel module, at the expense of being custom kernel. The preferred embodiment disclosed herein provides services as kernel modules, but it is obvious to anyone with ordinary skills in the art the kernel module functionality could be compiled into the kernel as disclosed for the alternate embodiment.

(21) FIG. 1 illustrates the application with an Interception Layer IL 23, 29 for each process. In a preferred embodiment using interception, the interception Layer is present. In a preferred embodiment not using interception, the interception Layer is absent, or configured to not perform any interceptions.

(22) 1. Information Reduction Overview

(23) FIG. 2. Illustrates by way of example embodiment 200 various high-level aspects of information reduction as taught by the present application.

(24) Source data 202 is reduced 204 to provide the Information Reduced data (IR Data) 206.

(25) In comparison, the typical Error Correction Code pipeline (ECC) teaches a partially similar-looking setup with Source data 210 being encoded 214 and transmitted over a noisy channel 216. At the receiving end, the received message is decoded 218 for an estimated source message 220. In the following teachings the focus is on linear codes; however the application applies to both linear and non-linear codes.

(26) For clarity, we designate a vector x in underlined bold, a scalar in normal font (e.g. x or x.sub.1), and a matrix M in upper case underlined bold.

(27) Referring to FIG. 2 again, x=(x.sub.1, . . . x.sub.k) 230 designates the source data 210 as a vector of dimension (i.e. length) k. Encoding 114 produces a code-word 232 c=(c.sub.1, . . . c.sub.n) as a vector of dimension (i.e. length) n, where n>k. The encoding step essentially adds (n−k) dimensions of redundant information. After being transmitted through the Channel 216, y=(y.sub.1, . . . y.sub.n) 234 is received with any channel errors e 233 introduced, and decoded 218 into an estimate for x 236 ex=(ex.sub.1, . . . ex.sub.k). Generally the channel is expected to introduce errors, so the received y may be considered to be the code word c with additional errors e introduced; written as y=c+e.

(28) This mathematical description of a typical error correction pipeline provides a consistent description of encoding and decoding and readily supports a large variety of ECCs. Please see Huffman & Pless Chapter I for an introduction. The encoding of the source vector x of dimension k to a code word c of dimension n may thus be viewed as adding (n−k) extra dimensions of redundant information, where the redundant information is constructed in such a way that it can assist in identifying any errors introduced in the channel. The individual elements of the vectors x, c, e, and y are considered elements of a finite field F.sub.q. Finite Fields are taught in Huffman & Pless Chapter 3 and will only be described as necessary to teach the present application. By way of example, if q=256 one may consider F.sub.256 as describing “bytes” of data, even though that only is accurate as far as size and some operations go. To simplify notation a finite field F.sub.q is also written as GF(q) “Galois Field” in honor of Galois, who formalized the mathematics of finite fields. Similarly, q=2 may be thought of as representing “bits”.

(29) A linear error correction code is called an [n,k] linear code or an [n,k,d] linear code, where d designates the minimum distance (please see next section). The encoding (FIG. 2 214) may be viewed as a matrix multiply by a Generator Matrix (G)
c=x*g

(30) where c is the code word of length (dimension) n, x is the source data of length (dimension) k, and G is a Generator matrix of dimension k×n. The Generator Matrix may be written in standard form by recognizing that the first k×k columns may be written as the identity matrix I.sub.k with the rest of G comprising the redundancy generating columns (P.sub.k):
G=[I.sub.k|P.sub.k]

(31) Similarly, certain aspects of decoding can be viewed as a Matrix multiply of the received code word y by a Parity Check Matrix (H)
H=[−P.sup.T|I.sub.n-K]

(32) Where H denotes the parity check matrix, and P.sup.T the transpose of P (the Parity check components of the standardized Generator H matrix).

(33) By calculating a syndrome s
s=H*y.sup.T

(34) Code words are identified by satisfying s=0, i.e. by having a zero syndrome.

(35) 1.1 Minimum Distance

(36) An important aspect of an error correcting code is the minimum distance. The minimum distance between two vectors d(x,y), or d.sub.min or d when the context is clear, is defined as the number of coordinates in which the two vectors differ.

(37) The minimum distance, is a measure of the error-correcting ability of a particular code. The minimum distance is not always known, but in view of the construction above, the Singleton bound states:
d<=n−k+1
This upper bound indicates the maximum separation achieved by adding redundancy, i.e. by adding (n−k) dimensions of redundancy as described above. The minimum distance is important for the following reasons (see Huffman & Pless) An error correcting code can detect (d−1) errors An error correcting code can correct (d−1)/2 errors

(38) FIG. 3 illustrates this in two dimensions by way of an example embodiment 300 with four code words 311, 321, 331, 341 arranged such that the minimum distance between two code words is “d” 310, 320, 330, 340. The minimum distance is indicated for each code word 312, 322, 332, 342 as a radial line of length d/2. While FIG. 3 illustrates the minimum distance in two dimensions the illustration readily extends to any number of dimensions.

(39) For a given [n,k] the larger the minimum distance, the better error correcting ability the code has. It is therefore generally of interest to find ECCs with the highest possible minimum distance for a given [n,k]. However, in practice the computational complexity of an [n,k,d] ECC is also an important factor, and it is common to choose a an [n,k,d] ECC that is not optimal if its computationally efficient.

(40) ECCs that meet the Singleton bound are called maximum distance separable codes (MDS codes).

2.0 Informational Reduction and Error Correction

(41) Looking at the ECC description in section 1 from a different perspective it can be viewed as:

(42) 1. a k-dimensional data space (“source”) is transformed (“encoded”) by adding redundant information by an [n,k,d] ECC and thereby embedded into an n-dimension space

(43) 2. the n-dimensional representation is transmitted over a noisy channel

(44) 3. the n-dimensional received data is transformed back (“decoded) into a k-dimensional representation within the limits of the [n,k,d] ECC.

(45) Assuming that no errors have been introduced during transmission, Step 3 essentially takes a higher-dimensional representation of a code word and reduces the representation from n to k dimensions subject to the limitations of the [n,k,d] ECC.

(46) Similarly, the decoding process from step 3 may be applied to any n-dimensional vector, and within the limits of an [n,k,d] ECC produce a k-dimensional representation.

(47) FIG. 4 illustrates this in two dimensions by way of an example embodiment 400. n-dimensional encoded code words 410, 411, 412 are indicated in a lattice as black filled circles. Two different ECC with different minimum distances are illustrated: an ECC 420 with the ability to correct 1 error (d.sub.min=3), and an ECC 422 with the ability to correct 2 errors (d.sub.min=5).

(48) By choosing ECCs with a larger minimum distances, more error may be corrected, or using different language, more received words y may be viewed as corresponding to one source word. Within the limits of the Singleton bound, the decoding process of an ECC may thus be used to reduce the informational content from n dimensions down to k dimensions.

(49) 2.1 Example ECCs

(50) A well-known class of error correcting codes is the Reed-Solomon (RS) class of codes. Please see Huffman and Pless for an introduction. Reed-Solomon codes are widely used for error correction in data storage systems including compact disks, data transmission, and satellite communication.

(51) Reed-Solomon codes are [n,k,n−k+1] linear block codes and are thus optimal in the sense that they meet the Singleton bound (they are MDS). RS codes generally have a symbol length (n) of size of the Field over which it's defined. In practice, a field that's a power of 2 is often used, such as GF(256)=GF(2.sup.8), as it naturally corresponds to a bits and bytes of information.

(52) Example RS codes over F.sub.256 are: RS(255,251,5), RS(255,239,17), and RS(255,223) with the ability to correct 2, 8 and 16 errors over GF(256) respectively.

(53) Reed Solomon codes are part of the bigger class of cyclic BCH codes (Bose, Ray-Chaudhuri, Hocquenghem). Many other classes of ECCs exist, and the use of RS codes is purely for illustrative purposes. RS codes are, however, good in practice as efficient decoding and encoding algorithms exists. Other classes of Error Correcting codes include Hamming Codes, Golay codes, codes from Algebraic Geometry, Convolutional codes, and repetition codes. There are also many well-known techniques to generate new codes by puncturing, extending, shortening or otherwise combining or changing existing codes.

3.0 DIMENSIONAL REDUCTION

(54) By way of example: If a user intended to search for “linear” but instead typed “lenear” it would be ideal of the search engine automatically could adapt to the spelling error. In the context of the teachings above, it may be observed that the minimum distance between “linear” and “lenear” is 1 (one), as the two words differ in exactly one position. Using an error correcting code with minimum distance 3 or higher, the decoding step (118 on FIG. 1) produces the same re-sourced vector (ex)(236 on FIG. 2) for both “linear” and “lenear”.

(55) An [n,k,d] ECC over GF(q) has q.sup.k different source words including the zero source word. This means that all source words are “known” ahead of time, which facilitates pre-calculating static operations.

(56) FIG. 5 illustrates this by way of an example embodiment 500. In the context of an [n,k,d] ECC, first all source words are generated 502. Generating all source words is comprised of creating 504 all possible k-vectors 510 over GF(q). This is followed by generating the results 506 for all source words. This is comprised of 508, for each source word x performing the associated operation and storing the result R(x) 512. By way of example, and not limitation, if the operation is a database lookup, each source word x is looked up, and R(x) corresponds to the result produced by the data base lookup. If, by way of another example, the operation is a calculation based on the source word, the result is said calculation performed on the source word.

(57) With pre-computed results 512 for all source words, processing of a code word proceeds as follows: Referring to the illustrative embodiment in FIG. 5, a code word 520 is first decoded 522 by the ECC and a corresponding source word 524 calculated. Using the results previously calculated, when needing to perform the operation on a code word 520, the source word produced 524 by the ECC 522 is used 526 to look up 528 the source word and identify the associated result 512, which is returned 530 as the result 532 of the operation. In an alternate embodiment, the Source 510 and Result 512 are not pre-calculated, but instead calculated as needed in the “look up” step 526 and Result 532.

(58) FIG. 5 and the associated teachings thus illustrate a technique whereby results of source words are pre-calculated and prepared for further reference. In applications where results from the same code/source words are accessed repeatedly, it may be advantageous to pre-computing as illustrated.

(59) FIG. 5 also illustrates a much more powerful technique. FIG. 5 and the associated teachings, illustrate the reduction of a problem in a higher-dimensional space, i.e. the code words 520 in n dimensions, to an equivalent problem in a lower k-dimensional space, i.e. source words in k dimensions, by using an [n,k,d] ECC to reduce the code words to source words within the context of a particular ECC and a noise-less channel.

(60) 3.1 Hashing as Dimensional Reduction

(61) Hash functions are used in a variety of situations, as previously summarized. One such application is to identify and group similar or identical words in e.g. a text or a directory. This type of hash function is at times called “Locally Sensitive Hashing” (LSH). So whereas a typical hash function is designed to generate different hash-values even for source data that is similar, LSH is designed to generate the same hash value for source data that is similar. Other applications of LSH are finger print recognition, and voice print recognition where the intent is to recognize that slightly different prints likely correspond to the same person.

(62) FIG. 6 illustrates an example embodiment 600 of the present application used to identify similar fingerprints. A fingerprint scanner 610 is comprised of a sensor 612 over which a user places her finger 614. The scanner generates a digital representation of the fingerprint 618. Naturally, each fingerprint scan will produce slightly different digital representations 618, as small variations in skin, such as a small scratch or dirt, generates slightly different fingerprint scans. The binary representation 618 is processed through an [n,k,d] ECC reducing the information content from n GF(q) elements to k elements. The source code words 622 naturally corresponds code words that are similar according to the ECC. The source words are thus the LSH hash values as generated by the present application. The LSH hash value 622 is then sent for process 624 having identified code words corresponding to identical source words, i.e. LSH hashes, within the limits of the [n,k,d] ECC.

(63) It is obvious to someone with ordinary skills in the art, that the example embodiment 600 illustrated on FIG. 6 naturally extends to voice prints, spoken passwords, or any other biometric measurement that generates a binary representation, and where small variations in biometric input may produce small variations in corresponding digital representations, and where those variations should be identified as belonging to the same person.

(64) Similarly, It is obvious to someone with ordinary skills in the art, that the example embodiment 600 illustrated on FIG. 6 also extends to any type of digital representation of an object, where small variations in the object, or the sampling of a particular object property, leads to small variations in the digital representation. Those variations may be identified and accounted for using the teachings of the present application.

(65) 3.2 Hierarchical Layering

(66) FIG. 7 illustrates by way of example embodiment 700 a hierarchical layering of several ECCs. Four encoded words 702, 704, 706, 708 are grouped by a first ECC 710 into a new code word. Code words by this first-tier ECC 710, 712, 714, 716 are group by a second-tier ECC 720. Similarly second-tier code words 720, 722, 724, 726 are grouped by a third-tier ECC. It is obvious to someone with ordinary skills in the art that this process may continue for as long as there are encoded code words to combine. The present application thus naturally extends to a hierarchical architecture where each layers of encoding and decoding identify larger and parts of the code word space.

(67) In continuation of the example embodiment illustrated on FIG. 6, it is thus reasonable to additionally add one or more tiers of ECC to identify increasing different fingerprints. By way of example, and not limitation, the first-tier ECC may correspond to identifying similar fingerprints when the finger is scanned in the same orientation. The second-tier ECC may correspond to identifying finger prints when the finger 614 is scanned held at a different angle over the scanner 612. Further tiers of ECC may be added if additional identification is possible based on e.g. different fingers, prints taken at different times allowing e.g. a scratch to be included, or other metric.

(68) Alternatively, an [n,k,d] ECC with a larger minimum distance me be used to identify a larger group of code words. While this is a well-known, and in one sense the standard approach, it requires the entire information reduction to occur in one step. There are multiple advantages to using multiple hierarchical ECCs as it allows the decoding process to stop sooner, and thus preserve more of the original information before identification is made. The tiered approach allows custom designed ECCs to be deployed at each level, and thus, by way of example, use a first ECC for fingerprint identification, a second ECC to detect rotated fingerprints, and a third ECC to detect dirty fingers.
3.3 Applications to Search

(69) A proximity search, also known as a “Nearest Neighbor Search (NSS)” is a common problem in optimization, data mining, and other data processing applications. Example use of NSS include identifying similar words, determining which residences belong to a particular post office, identifying words or speaker in speech recognition, determining that photos are similar, classification in machine learning and other machine learning algorithms.

(70) In many of the modern NSS algorithm a measure, also called a metric, of “closeness” is given, and the NSS objective is stated as a minimization problem: Given a set S of points and a measure of distance between the points in S, determine for each point p∈S the closest point q∈S. The point q would be the “nearest neighbor” to the point p.

(71) The Nearest Neighbor Search naturally maps to the previous teachings regarding information reduction. In the context of an [n,k,d] ECC, the NSS may be restated as follows: The set of points correspond to the code words of length n, and the metric for closeness is provided by the minimum distance. The “search” is then not actually performed as a search, but rather as an ECC decoding step identifying code words (i.e. the neighbors) within (d.sub.min−1)/2 error correcting capability of the [n,k,d] ECC. Please refer to section 1.1 for the error correcting capability of an [n,k,d] ECC and FIG. 3 for an illustration.

4.0 PREPROCESSING, MAPPINGS, AND TRANSFORMATIONS

(72) By way of example consider a sensor such as a digital thermometer: The thermometer measures temperature and reports the temperature as one-byte measurements. One mapping of the temperature in degree Celsius would be from −128 degrees to 127 degrees using the commonly accepted mapping for a signed byte.

(73) However, if it's known that the thermometer is intended to measure indoor temperature, it may be reasonable to assume that the temperature realistically should be expected to be between 15 degrees and 35 Celsius. It is thus possible to improve the precision by scaling the measured range from 15 to 35 so that e.g. a value of 0 (zero) corresponds to 15 degrees, and a reported value of 255 corresponds to 35. With the thermometer configured properly, the conversion then:
temp=sensor_reading*(35−15)/255+15

(74) FIG. 8 illustrates by way of example embodiment 800, the example in a general context. If the full address space of the code words 810 is larger than actually observed code words 812, it may be beneficial to transform 812 the code words into similar address space 820 where the transformed code words 822 use the full address space or at least use more of it. This allows higher precision in conversions and calculations, and thus generally allows an ECC to correct more errors as the transformed code words use more of the available bits of precision.

(75) A variety of well-known techniques exists for scaling and transformation of ranges. By way of example, and not limitation, the following teachings provide a few illustrative teachings and should be viewed as a few of many ways in which data may be scaled to better utilize available precision.

(76) 4.1 Moving Window/Relative Window

(77) A commonly used technique, often called a “moving window”, is illustrated by example embodiment on FIG. 9 900. A Sensor reading 900 is collected over time 950. The sensor range is known to be between a minimum value (Sensor MIN) 922 and a maximum value (Sensor MAX) 920. The sensor is recorded 940 between time t0 952 and t1 1954 and the observed sensor range is from a minimum value of R0 932 to a maximum value of R1 930. The sensor reading over the time interval t0−t1 may be transformed into the range of 0 to 1 (trans_01) as follows:
trans_01=(sensor−R0)/(R1−R0)

(78) If the output range was known to be, by way of example and not limitation, 16 bits, the full range could be used by multiplying the transformed value (trans_01) by 2.sup.16.

(79) The technique of “Windowing” is well known to someone with ordinary skills and generally considered one of the tools used in signal processing. Typically, Windowing is used to isolate, eliminate or enhance certain characteristics of a signal for a particular time frame. Wikipedia lists (https://en.wikipedia.org/wiki/Window_function) some of the better-known Windowing functions including rectangular, triangular, Parzen, Welch, Hamming and Generalized Hamming, Hann, and many others.

(80) In the examples given above, Windowing was used to isolate specific sensor ranges and better utilize the available range and code word space. Other related uses include filtering noise, shaping spectrum, and adjusting amplification (gain) or reduction (loss).

(81) 4.2 Fisher and Inverse Fisher Transforms

(82) It may be desirable to convert a set of observations, into a set of observations that approximate a Normal distribution, a.k.a. Gaussian distribution. The mathematical properties of Normal Distributions are well understood, are generally simple, and are thus often used.

(83) The Fisher transform (https://en.wikipedia.org/wiki/Fisher_transformation) is an approximate variance-stabilizing transformation, with essentially means that for many data sets the transformed data has properties approximating a normal distribution.

(84) The Fisher transform y of x is given by, where In is the natural logarithm
y=0.5*ln((1+x)/(1−x))

(85) This conversely means that the inverse transform (“Inverse Fisher”), i.e. solving for x, is
x=(e.sup.2y−1)/(e.sup.2y+1)

(86) The Inverse Fisher has as the characteristics that the values, i.e. x, is bounded by −1 and 1. In many situations it is thus a very effective way to normalize a data set, and ensure that all values are contained between −1 and 1.

(87) Referring to the example embodiment 900 again for illustration: instead of having to empirically determine the minimum (sensorMIN 922) and maximum (sensorMAX 920) values of the data stream, the sensor data is first transformed with an Inverse Fisher and it is then known that sensorMIN=−1 and sensorMAX=1. For mapping to the range [0;1] please see below.

(88) Generally, pre-processing by the Inverse Fisher transforms reduces the need to know the absolute limits of any sensor measurement and normalize the calculations it the range of −1 to 1.

(89) At times, it may be more convenient to assume an unsigned range of 0 to 1 (InvFisher.sub.01). Transformation for the standard [−1;1] Inverse Fisher (InvFisher) is easily performed by the following linear transformation
InvFisher.sub.01=½*InvFisher+½

(90) The InvFisher.sub.01 thus naturally maps to unsigned variables, whereas InvFisher naturally maps to signed variables.

(91) 4.3 Alpha Mappings

(92) Assigning numerical values to letters similarly require pre-processing. For instance, referring to ASCII (American Standard Code for Information Interchange):

(93) TABLE-US-00001 Character ASCII Value/Decimal ASCII in Hex ASCII in Binary ‘A’ 65 0x41 0100 0001 ‘B’ 66 0x42 0100 0010 ‘a’ 97 0x61 0110 0001

(94) In the context of comparing letters, there is thus a difference of “1” between A (65) and B (66) when viewed as decimal numbers, whereas there is a difference of “32” between A (65) and ‘a’ (97). As this demonstrates simply using the ASCII values as textural representations of letters seems to indicate that the “distance” between A and B is substantially less than the “distance” between “a” and “A”.

(95) Looking at the character values in binary, it is worth observing that only one bit is different between ‘A’ and ‘a’ (corresponding to the different of 32=2.sup.5). This, however, is not always easy to exploit as the “one bit difference” only naturally maps to upper and lower case for letters.

(96) Restating the textural comparisons in the contact of the present application: If the minimum distance is defined as the difference in decimal ASCII value, the difference between ‘A’ and ‘a’ is 32. If the minimum distance is defined as the number of bit-difference between ‘A’ and ‘a’, the minimum distance is 1.

(97) The Unicode Standard specifies a consistent encoding, representation, and handling of text as expressed in most of the world's writing system. Unicode uses between 1 byte and 4 bytes to represent characters and thus present similar mapping challenges as presented above.

(98) Ways to address the alphabetic mappings are typically language specific, and may involves pre-processing that maps all lower-case to upper-case, maps e.g. “l” to “lower-case L” (and vice versa), and ways to account for common typographical errors, typos, and abbreviations.

(99) 4.4 General Mappings

(100) The above illustrative example embodiments are intended to demonstrate example embodiments of the general concept. It will be appreciated by someone with ordinary skills in the art that preprocessing, mappings, and transformations may take any form, not just the examples given.

(101) By way of example, and not limitation, digital filters may be used to transform data. Digital filters may include transformations that operate in the time domain and transformations that operate in the frequency domain. By way of further example, transformations may include spectral transformation such as Fourier and Hilbert, filter banks, convolutions filters, and essentially any numeric processing of the data stream.

(102) In general, any numeric processing of the data stream may be viewed as a transformation and utilized as such in the context of the present Application.

5.0 DATAFLOW

(103) FIG. 10 illustrate by way of example embodiment 1000, an infrastructure incorporating elements of the teachings of the previous sections.

(104) By way of a first example, a fingerprint reader 1010 generates fingerprint data 1012 (“raw data”). The finger print data is transformed 1014 into the space of the ECC. The ECC 1016 for the fingerprint reader is run and the decoded data indicates provides a code-word estimate for the finger print scan. The code-word is provided to the software (“Device SW”) 1018, which is the intended user of the finger print 1010 data. By way of example, one such device software may be an application to unlock a smart phone.

(105) Similarly, a user types on a keyboard 1020, and the raw keyboard data 1022 is transformed 1024 into the space of the ECC. The ECC 1026 for the keyboard is run and the decoded data provides a code-word estimate for the keyboard data. The code-word is provided to the device software 1028 using the keyboard 1020 data. By way of example, one such device software may be an application to search the internet.

(106) It will be appreciated by someone with ordinary skills in the art, that the previous two examples are illustrative of a general approach, where a device 1030 generates raw data 1032, which is then transformed 1034 into the space of an ECC. The ECC creates an estimated code-word, which is used by device software 1038 for the device 1030.

(107) 5.1 Data Flow for Applications

(108) The same general data flow may be used if an application instead of a device creates the initial raw data. By way of example, an application 1040 generates raw data 1042, which is transformed 1044 into the space of the ECC. The ECC 1046 decodes the data and provide an estimated code-word for further processing by a processing application 1048.

(109) By way of example, the Input Generation Application 1040 may be a web browser where the user types in a search term. The search term is the raw data 1042 which is transformed 1044 possibly using alpha mappings as previously taught. The ECC 1046 estimates a code-word for the search term and delivers the code-word to the search engine 1048 for further processing. The transformation 1044 may be provided using a plugin, and the ECC 1046 may be provided using a plugin. Using plugins allows the present application to be incorporate into existing applications, including web browsers, without requiring any customization of said existing applications.

(110) 5.2 Implementation Considerations

(111) The previous disclosures used the terminology “Device Software” (1018, 1028, and 1038). It is appreciated by someone with ordinary skills, that the designation “Device SW” may include programs, processes, threads, device drivers, kernel drivers, kernel modules, plugins, mobile apps, and other designations for software executing on a processor.

(112) By way of example, a device 1030 may have an associated device driver, and the raw data 1032 is delivered through a device driver. Similarly, a device 1030 may have an associated kernel module or kernel extension, and the raw data 1032 is delivered via said kernel module. In another embodiment a system library or other library is used to interface to the device 1030 and the raw data 1032 is provided via a library.

(113) Alternatively, the device 1030 may be accessed using an application, and the raw data 1032 is delivered using an application level interface. By way of example, access to the raw data 1032 may be achieved through interception at the application layer, system layer, library layer, or kernel layer. The interception may use an Application Programming Interface (API) provided by the operating system, or an API provided by the application.

(114) The Transform 1034 and ECC 1036 may similarly be accessed using one or more APIs, plugins, or programming interfaces and may be agnostic to the implementation of the Device and its operation. The Transform 1034 and ECC 1036 may be implemented using as one of application, one or more processes and threads, a device driver, a kernel module, a kernel extension, a plug-in, or other software implementation.

(115) Similarly, for an Input Generation Application 1040 interception may be provided using an API provided by the Operating System, the Application, a library, via a plugin, or any other interface provided. The Transform 1044 and ECC 1046 may similarly be provided via API or plugin and may thus be agnostic to the implementation of the Input Generation Application 1040.

(116) It is thus readily obvious to someone with ordinary skills in the art that the present application may interoperate with existing software using one or more of interception, plugins, or other interfaces.

6.0 APPLICATIONS IN BIG DATA AND MACHINE LEARNING

(117) Machine Learning is field of computer science related to pattern recognition and computational learning. Machine Learning is an umbrella designation of a variety of computation techniques often involving evolving adaptive techniques. Machine Learning has been applied to speech recognition, voice recognition, biometrics recognition, optical character recognition (OCR), Computer Vision, and Search to name a few.

(118) Several classes of machine learning contain elements of finding similar data objects and identifying them. For instance, OCR attempts to recognize text in images and should ideally recognize the letters independent of the font used.

(119) Similarly, voice recognition may be used for spoken passwords and the Machine learning system way wish to identify similar voiceprints with one person. Similarly for spoken control, where small variances in ambient noise or speaker intonation, should be acceptable.

(120) In Search, it may be desirable to identify common spellings and misspellings and thus provide the same search results in view of minor typos.

(121) It is thus readily apparent to someone with ordinary skills in the art that the teachings of the present application applies broadly to Machine Learning, and may be used in one or more of the algorithms of Machine Learning.

7.0 APPLICATION TO HOSTED APPLICATIONS AND STREAMING APPLICATIONS

(122) Application Hosting and Application Streaming may be components of many “Cloud” products: Applications and services are streamed or hosted to clients and a client uses a web browser or a streaming infrastructure to access said hosted or streaming services. The present application may be advantageously used in the context of hosted applications to reduce duplication of data, duplication of processing, and other activities which may be identified being essentially different instances of the same base activity.

8.0 FAULT DETECTION

(123) The present application may advantageously be used in Fault Detection and Application Agnostic Fault Detection. As taught in Ser. Nos. 13/017,340 and 13/017,717, the disclosures of which were included in their entirety by reference, one of the bigger challenges in fault detection is elimination of duplicate or redundant fault detection events. The information reduction teachings of the present application may be used to consolidate, i.e. identify, a variety of fault events with common root causes.

9.0. APPLICATIONS FOR MOBILE AND EMBEDDED DEVICES

(124) The present application is directly applicable to mobile and embedded devices. Common limitation of a typical mobile device is less memory, less processing power, limited network bandwidth, limited Input/Output (I/O), and battery operation when compared to a desktop or server system. It is thus desirable to pre-process as much information as possible before engaging the CPU and network in a computationally expensive operation. Error Correction Codes are well understood and computationally efficient. Modern multi-media integrated circuits (ICs) may contain functionality to accelerate ECC calculations as ECCs are widely used in storage and data communication systems.

(125) It is thus readily apparently to someone with ordinary skills in the art, that the present application advantageously may be used in mobile and embedded systems to pre-process information, identify similarities, and thus enable a more efficient use of the CPU, memory, network, and I/O.

10. DEPLOYMENT SCENARIOS

(126) FIG. 11 illustrates by way of example embodiment 1100 a variety of ways the application can be configured to operate.

(127) In one embodiment, the application is configured with a central file server 1102 and one or more servers 1104. The servers 1104 and storage 1102 are connected to a local area network (LAN) 1103 and the network is connected to the internet 1116 for external access. In one embodiment Wi-Fi 1106 is provided for Wi-Fi access to the LAN. In another embodiment a personal computer, laptop, Chromebook, or other similar device 1114 is connected to the network 1103 using one or more of network 1103 or Wi-Fi 1106. In another embodiment a cellular wireless or public Wi-Fi 1108 is supported and connected via the internet 1116 to the LAN 1103. In yet another embodiment a cellular phone 1110, tablet 1112 or other mobile device is connected to using one of Wi-Fi 1106 or cellular or public Wi-Fi 1108. In another embodiment a personal computer, Chromebook, laptop, or other similar device 1116 is connected to the internet 1116.

(128) Finally, the present application works universally independent of device type, network type, and operating system. The illustrated example embodiments should not be construed as limiting the scope of the application but as merely providing illustrations of some of the exemplary embodiments.

11. CONCLUSION

(129) In the embodiments described herein, an example programming environment, systems and configurations were disclosed for which one or more embodiments according to the application were taught. It should be appreciated that the present application can be implemented by one of ordinary skill in the art using different program organizations and structures, different data structures, different configurations, different systems, and of course any desired naming conventions without departing from the teachings herein. In addition, the application can be ported, or otherwise configured for, use across a wide-range of operating system environments.

(130) Although the description above contains many details, these should not be construed as limiting the scope of the application but as merely providing illustrations of some of the exemplary embodiments of this application. Therefore, it will be appreciated that the scope of the present application fully encompasses other embodiments which may become obvious to those skilled in the art, and that the scope of the present application is accordingly to be limited by nothing other than the appended claims, in which reference to an element in the singular is not intended to mean “one and only one” unless explicitly so stated, but rather “one or more.” All structural and functional equivalents to the elements of the above-described preferred embodiment that are known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the present claims. Moreover, it is not necessary for a device or method to address each and every problem sought to be solved by the present application, for it to be encompassed by the present claims. Furthermore, no element, component, or method step in the present disclosure is intended to be dedicated to the public regardless of whether the element, component, or method step is explicitly recited in the claims. No claim element herein is to be construed under the provisions of 35 U.S.C. 112, sixth paragraph, unless the element is expressly recited using the phrase “means for.”