Triada, Ltd.

Joseph M Bugajski

James T Russo

Tao Zhang

K R Raghavan

By placing a low cardinality node or a leaf in a lower level, and a high cardinality node or a leaf at a higher level, an optimal memory structure is automatically generated which yields the best compression within N-gram technology. After making an initial list of parallel streams or fields, the streams are ordered in accordance with increasing cardinality. Adjacent streams (fields), or nodes, are paired, and the children of the resulting node are eliminated from the list, while a new parent node is added to the list. The resulting new list is re-arranged from right to left as a function of increasing cardinality, and the pairing steps are repeated until a single root node is remains for the final memory structure.

Method of optimizing an N-gram memory structure

A method of data compression includes means to accelerate a direct query thereof. Input data are transformed into a multilevel n-ary tree structure wherein each leaf node corresponds to the creation of a memory storing unique occurrences of a particular data body, and each non-leaf node corresponds to a memory storing unique occurrences associated with its child nodes, whether leaf or non-leaf types. To accelerate a determination as to the solution of a query of the data, one or more pointers are further stored at each memory level, the pointers at least including those used to identify the parent of each child node and the children of each parent. In the preferred embodiment additional pointers are further stored in conjunction with each non-leaf node, these being used to identify other locations corresponding to unique occurrences derived through the same child nodes.

Method of storing compressed data for accelerated interrogation

The compression system includes a series of pipelined data processors. Each processor has an associated memory. The body of digital data is applied serially to the first processor in the chain. The first processor analyzes pairs of data elements in its incoming signal to detect the occurrence of previously non-occurring sequences and stores those sequences in its associated memory. The output signal from the processor identifies the storage position in its associated memory of each pair of data elements in its input, whether or not those sequences have previously occurred in the data stream. Subsequent processors work with storage location signals only. Each processor provides a single output location signal for each pair of signals in its input. Each processor also determines the number of times that each incoming sequences has occurred and stores that number in association with each stored pair. A hashing table created by each processor and stored in its associated memory is used to segregate the stored pairs into groups having common lower significant figures to simplify the task of determining whether a pair of elements in the input has previously been stored. Pointers stored with each unique pair link the pairs in each hashed sequence in the order of their frequency of occurrence in the incoming data stream so that the incoming elements may be compared with the previously stored elements in the order of probability of occurrence of each pair in the data stream.

Data compression with pipeline processor having separate memories

The compression system includes a series of piplined data processors. Each processor has an associated memory. The body of digital data is applied serially to the first processor in the chain. The first processor analyzes pairs of data elements in its incoming signal to detect the occurrence of previously non-occurring sequences and stores those sequences in its associated memory. The output signal from the processor identifies the storage position in its associated memory of each pair of data elements in its input, whether or not those sequences have previously occurred in the data stream. Subsequent processors work with storage location signals only. Each processor provides a single output location signal for each pair of signals in its input. Each processor also determines the number of times that each incoming sequence has occurred and stores that number in association with each stored pair. A hashing table created by each processor and stored in its associated memory is used to segregate the stored pairs into groups having common lower significant figures to simplify the task of determining whether a pair of elements in the input has previously been stored. Pointers stored with each unique pair link the pairs in each hashed sequence in the order of their frequency of occurrence in the incoming data stream so that the incoming elements may be compared with the previously stored elements in the order of probability of occurrence of each pair in the data stream.

Growing community of inventors

Ypsilanti, MI, United States of America

Joseph M Bugajski