Method of similarity testing by syndromes and apparatus therefore

Patent metadata

Field	Value
Publication number	US-9690512-B2
Application number	US-201514949458-A
Country	US
Kind code	B2
Filing date	Nov 23, 2015
Priority date	Nov 23, 2015
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

A method, executed by a processor, for determining similarity between messages includes calculating a syndrome of each of first and second messages with respect to a linear code. A difference between the syndromes of the first and second messages is calculated, and a vector that minimizes a metric in a coset defined by the syndrome difference is identified. A compact representation of the second message that is based upon the first message is generated when a metric of the identified vector is less than or equal to a predetermined threshold. The compact representation of the second message is stored in a location of a memory device assigned for storing the second message, when the metric of the identified vector is less than or equal to the predetermined threshold.

First claim

What is claimed is:

1. A method, executed by a processor, for determining similarity between messages, the method comprising:
calculating a syndrome of each of first and second messages with respect to a linear code;
calculating a difference between the syndromes of the first and second messages;
identifying a vector that minimizes a metric in a coset defined by the syndrome difference;
generating a compact representation of the second message that is based upon the first message, when a metric of the identified vector is less than or equal to a predetermined threshold; and
storing in a location of a memory device assigned for storing the second message, when the metric of the identified vector is less than or equal to the predetermined threshold, the compact representation of the second message, thereby reducing used space in the memory device.

2. The method of claim 1 , wherein the compact representation of the second message comprises a pointer to a storage location of the first message within the memory device.

3. The method of claim 2 , wherein the compact representation of the second message further comprises information identifying a difference between the first and second messages.

4. The method of claim 3 , wherein the information identifying the difference between the first and second messages is a set of indices identifying locations in which the second message differs from the first message.

5. The method of claim 3 , wherein the information identifying the difference between the first and second messages is compressed by a compression algorithm prior to being stored in the memory location assigned for storing the second message.

6. The method of claim 1 , wherein the metric in the coset defined by the syndrome difference is a Hamming weight.

7. The method of claim 1 , wherein the metric in the coset defined by the syndrome difference is a burst length.

8. The method of claim 1 , wherein the code is a Reed-Solomon code.

9. The method of claim 1 , wherein the code is a Bose-Chaudhuri-Hocquenghem (BCH) code or Reed-Muller code.

10. An apparatus for executing de-duplication of similar messages, the apparatus comprising:
a memory that stores messages, including a first message; and
a memory controller that:
calculates a syndrome of each of the first message and a second message with respect to a linear code;
calculates a difference between the syndromes of the first and second messages;
identifies a vector that minimizes a metric in a coset defined by the syndrome difference; and
stores in a location of the memory assigned for storing the second message, when the metric of the identified vector is less than or equal to a predetermined threshold, a compact representation of the second message that is based upon the first message, thereby reducing used space in the memory.

11. The apparatus of claim 10 , wherein the compact representation of the second message comprises a pointer to a storage location of the first message within the memory.

12. The apparatus of claim 10 , wherein the compact representation of the second message comprises information identifying a difference between the first and second messages.

13. The apparatus of claim 12 , wherein the information identifying the difference between the first and second messages is a set of indices identifying locations in which the second message differs from the first message.

14. The apparatus of claim 12 , wherein the information identifying the difference between the first and second messages is compressed by a compression algorithm prior to being stored in the memory location assigned for storing the second message.

15. The apparatus of claim 10 , wherein the metric in the coset defined by the syndrome difference is a Hamming weight.

16. The apparatus of claim 10 , wherein the metric in the coset defined by the syndrome difference is a burst length.

17. The apparatus of claim 10 , wherein the code is a Reed-Solomon code.

18. The apparatus of claim 10 , wherein the code is a Bose-Chaudhuri-Hocquenghem (BCH) code or Reed-Muller code.

19. A method, executed by a processor, for determining similarity between messages, each of the messages having N sub-components, the method comprising:
a) calculating, for each value of 1≦j≦N, a syndrome of each of a j th sub-component of a k th first message and a j th sub-component of a second message with respect to a linear code, wherein N is an integer greater than one, j is an integer, and k is an integer greater than zero;
b) calculating, for each value of 1≦j≦N, a j th difference between the syndromes of the j th sub-component of the k th first message and the j th sub-component of the second message;
c) identifying, for each value of 1≦j≦N, a j th vector that minimizes a metric in a coset defined by the j th syndrome difference for the k th first message;
d) identifying, for each value of 1≦j≦N, the j th sub-component of the k th first message and the j th sub-component of the second message as being similar when a metric of the j th vector is less than or equal to a first predetermined threshold;
e) identifying the k th first message and the second message as being similar when the number of sub-components identified as being similar between the k th first message and the second message exceeds a second predetermined threshold;
f) generating a compact representation of the second message that is based upon the k th first message, when the k th first message and second message are identified as being similar and satisfy a predetermined degree of similarity; and
g) storing in a location of a memory assigned for storing the second message, when the k th first message and second message are identified as being similar and satisfy the predetermined degree of similarity, the compact representation of the second message, thereby reducing used space in the memory.

20. The method of claim 19 , further comprising:
performing operations (a) through (e) for each of k>1 first messages, wherein
the k th first message and the second message satisfy the predetermined degree of similarity when the k th first message is no less similar to the second message than any of the other k−1 first messages.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Shany Yaron
• Dor Avner
• Erez Elona
• Kong Jun Jin

Classifications

• G06F11/1453

  using de-duplication of the data · CPC title

• H03M13/1525

  Determination and particular use of error location polynomials · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F17/30156

  Physics · mapped topic