Matching pattern combinations via fast array comparison

Patent metadata

Field	Value
Publication number	US-9998140-B2
Application number	US-201313867596-A
Country	US
Kind code	B2
Filing date	Apr 22, 2013
Priority date	Apr 22, 2013
Publication date	Jun 12, 2018
Grant date	Jun 12, 2018

Abstract

Methods and arrangements for providing a compressed representation of a number sequence. An input number sequence is received, as is a stored number sequence. The input number sequence is compared to the stored number sequence. The comparing includes determining a set of coefficients corresponding to the input number sequence, via solving at least one algebraic equation, the at least one algebraic equation comprising at least one of: an arithmetic equation, and an exponential equation. The comparing further includes applying at least one test to determine whether the set of coefficients identifies at least a portion of the stored number sequence as matching the entire input number sequence.

First claim

What is claimed is:

1. A method of providing a compressed representation of a number sequence, said method comprising:
utilizing a processor to execute computer code configured to perform the steps of:
receiving an input number sequence representing an atomic service having a predetermined duration, wherein the input number sequence comprises a plurality of elements, wherein a number of the plurality of elements corresponds to a number of units of time within the predetermined duration represented as an array;
determining a set of coefficients describing the input number sequence, via solving at least one algebraic equation, the at least one algebraic equation comprising at least one of: an arithmetic equation, and an exponential equation;
accessing a library of stored number sequences, the number sequences comprising at least one of: arithmetic number sequences, and exponential number sequences;
determining a representation of the stored number sequences;
ascertaining a match of the set of coefficients with respect to the representation of the stored number sequences, wherein the ascertaining a match is performed by partitioning the representation of the stored number sequences into equivalence sets by performing a linear transformation test, a constant multiple test, a constant multiple of a product test, and a constant multiple of sum test on the input number sequence to reduce a number of stored number sequences to be considered when ascertaining a match and increasing a speed for ascertaining a match;
the ascertaining a match comprising:
determining, by performing the linear transformation test, whether the input number sequence is at least one of: a linear transformation of at least one of the representation of the stored number sequences and a log-linear transformation of at least one of the representation of the stored number sequences by applying a linear or log-linear transformation to a random position of the stored number sequence and comparing the result of the linear or log-linear transformation to a corresponding position of the input number sequence, wherein a match comprises a representation of the stored number sequence passing the linear transformation test;
determining, by performing the constant multiple test, whether the input number sequence comprises a constant multiple of at least one of the representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple test;
determining, by performing the constant multiple of a product test, whether the input number sequence comprises a constant multiple of a product of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a product test;
determining, by performing the constant multiple of a sum test, whether the input number sequence comprises a constant multiple of a sum of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a sum test; and

iteratively performing the ascertaining a match for each of the representation of the stored number sequences until a match is found, the match representing a stored number sequence that corresponds to at least a portion of a specialized predictive cost model for the atomic service and providing the at least a portion of a specialized predictive cost model to a user; and
in the event a match is not found, adding the input number sequence to the library of stored number sequences.

2. The method according to claim 1 , wherein said ascertaining comprises mathematically comparing the set of coefficients to the representation of stored number sequences.

3. The method according to claim 2 , wherein said determining of a set of coefficients comprises determining a compressed representative sequence pattern for the input number sequence.

4. The method according to claim 1 , wherein said ascertaining comprises applying at least one test to determine whether the set of coefficients identifies at least a portion of a stored number sequence as matching the entire input number sequence.

5. The method according to claim 4 , wherein:
said accessing comprises accessing a first library; and
said method comprises, in response to a failed matching test with respect to the first library:
accessing a second library of stored number sequences; and
testing whether the input number sequence matches a representation of the stored number sequences of the second library.

6. The method according to claim 5 , wherein said testing comprises applying a linear equivalence test.

7. The method according to claim 5 , comprising adding the input number sequence to the second library in response to a failed matching test with respect to the second library.

8. The method according to claim 1 , wherein said determining of a set of coefficients comprises determining a set of coefficients with respect to at least one predetermined position in the input number sequence.

9. The method according to claim 8 , wherein:
the at least one predetermined position comprises at least one initial position; and
said using of the set of coefficients comprises applying at least one test to the at least one initial position.

10. The method according to claim 9 , wherein:
the at least one predetermined position comprises at least one random position different from the at least one initial position; and
said ascertaining comprises applying at least one test to the at least one random position.

11. The method according to claim 10 , wherein said ascertaining comprises applying at least one test to all remaining positions in the input sequence in response to a successful matching test with respect to the at least one random position.

12. The method according to claim 1 , wherein said ascertaining comprises at least one of:
testing whether at least one element of the input number sequence is a constant multiple of at least one of: an arithmetic pattern, and an exponential pattern;
testing whether at least one element of the input number sequence is a constant multiple of a product of an arithmetic pattern and an exponential pattern; and
testing whether at least one element of the input number sequence is a constant multiple of a sum of an arithmetic pattern and an exponential pattern.

13. The method according to claim 12 , wherein said ascertaining comprises all of:
said testing of whether at least one element of the input number sequence is a constant multiple of at least one of: an arithmetic pattern, and an exponential pattern;
said testing of whether at least one element of the input number sequence is a constant multiple of a product of an arithmetic pattern and an exponential pattern; and
said testing of whether at least one element of the input number sequence is a constant multiple of a sum of an arithmetic pattern and an exponential pattern.

14. The method according to claim 12 , wherein said ascertaining comprises, in sequence:
said testing of whether at least one element of the input number sequence is a constant multiple of at least one of: an arithmetic pattern, and an exponential pattern;
thereafter performing said testing of whether at least one element of the input number sequence is a constant multiple of a product of an arithmetic pattern and an exponential pattern; and
thereafter performing said testing of whether at least one element of the input number sequence is a constant multiple of a sum of an arithmetic pattern and an exponential pat

Assignees

• IBM

Inventors

• Lehman Tobin J
• Lichtsinn Mario H
• Strong Jr Hovey R

Classifications

• H03H7/30

  Time-delay networks {(analogue shift registers G11C27/04)} · CPC title

• H03M7/14 Primary

  Conversion to or from non-weighted codes · CPC title