Method of similarity testing by syndromes and apparatus therefore

Patent metadata

Field	Value
Publication number	US-2017149451-A1
Application number	US-201514949458-A
Country	US
Kind code	A1
Filing date	Nov 23, 2015
Priority date	Nov 23, 2015
Publication date	May 25, 2017
Grant date	—

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.

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.

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.

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

• H03M13/19

  Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes · CPC title

• H03M13/611

  Specific encoding aspects, e.g. encoding by means of decoding · CPC title

• H03M13/1525 Primary

  Determination and particular use of error location polynomials · CPC title

• H04L51/212

  using filtering or selective blocking · CPC title

• H03M13/1575 Primary

  Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance · CPC title