APPARATUS AND METHOD FOR FILTERING DUPLICATE DATA IN RESTRICTED RESOURCE ENVIRONMENT

• US 20130110794A1
• Filed: 04/30/2012
• Published: 05/02/2013
• Est. Priority Date: 11/02/2011
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Chun-Hee
• Application Number:
  US13/460,240
• Publication Number:
  US 20130110794A1
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

An apparatus and method for stably filtering duplicate data in various resource-restricted environments such as a mobile device and medical equipment are provided. The apparatus includes a cell array unit configured to comprise one or more cells; a duplication check unit configured to check whether input data is duplicate and set a value of a cell that matches the input data; and a duplication probability calculation unit configured to, in response to the input data being determined as duplicate data by the duplication check unit, calculate a probability of duplication of the input data using the set value of the cell. Data which may be duplicate data among a large amount of input data is not arbitrarily deleted, but is provided to an application along with a probability of duplication of the data. Accordingly, a false positive error that occurs in Bloom filter is prevented, and thereby system stability can be improved.

Claims

1. An apparatus to filter duplicate data in a resource-restricted environment, the apparatus comprising:

a cell array unit configured to comprise one or more cells;

a duplication check unit configured to check whether input data is duplicative, and set a value of a cell of the one or more cells that matches the input data; and

a duplication probability calculation unit configured to, in response to the input data being determined as duplicate data by the duplication check unit, calculate a probability of duplication of the input data using the set value of the cell.

2. The apparatus of claim 1, wherein the cell includes a bit cell for setting a bit value and a count cell for setting a count value.

3. The apparatus of claim 2, wherein:

the cell array unit further comprises one or more hash functions; and

the duplication check unit computes a hash address associated with the input data using one of the hash functions, sets the bit value of the bit cell that matches the computed hash address, and increases the count value of the count cell that matches the computed hash address.

4. The apparatus of claim 3, wherein the duplication check unit checks the bit value of the bit cell that matches the computed hash address, and determines whether the input data is duplicate data based on the checked bit value.

5. The apparatus of claim 3, wherein the duplication probability calculation unit calculates the probability of duplication of the input data using the count value of the count cell that matches the computed hash address.

6. The apparatus of claim 3, wherein the duplication check unit sets the bit value to “

1”

, and increases the count value by 1.

7. The apparatus of claim 3, wherein the duplication probability calculation unit checks whether a predetermined threshold is present, and in response to the predetermined threshold being present, the duplication probability calculation unit skips the calculating of the probability of duplication of the input data determined as duplicate data.

8. The apparatus of claim 7, wherein the duplication probability calculation unit checks whether the count value is greater than the predetermined threshold, and in response to the count value being greater than the predetermined threshold, the duplication probability calculation unit determines the input data as duplicate data and deletes the input data.

9. The apparatus of claim 1, wherein:

the duplication check unit transmits the input data determined as duplicate data to an application; and

the duplication probability calculation unit transmits the probability of duplication of the input data to the application.

10. A method of filtering duplicate data in a resource-restricted environment, the method comprising:

checking whether input data is duplicative;

setting a value of a cell that matches the input data; and

in response to the input data being determined as duplicate data, calculating a probability of duplication of the input data using the set value of the cell.

11. The method of claim 10, wherein the cell includes a bit cell for setting a bit value and a count cell for setting a count value.

12. The method of claim 11, wherein the checking of whether the input data is duplicative comprises:

computing one or more hash addresses associated with the input data using one or more hash functions;

checking the bit value of the bit cell that matches the computed hash addresses; and

determining whether the input data is duplicated based on the check bit value.

13. The method of claim 12, wherein the setting of the value of the cell comprises:

setting the bit value of the bit cell that matches each of the computed hash addresses; and

increasing the count value of the count cell that matches the computed hash addresses.

14. The method of claim 13, wherein the calculating of the probability of duplication comprises calculating the probability of duplication of the input data using the count value of the count cell that matches the computed hash addresses.

15. The method of claim 13, wherein the bit value is set to “

1”

, and the count value is increased by 1.

16. The method of claim 13, further comprising:

checking whether a predetermined threshold is present; and

in response to the predetermined threshold being present, skipping the calculating of the probability of duplication of the input data determined as duplicate data.

17. The method of claim 16, further comprising:

checking whether the count value is greater than the predetermined threshold; and

in response to the count value being greater than the predetermined threshold, determining the input data as duplicate data and deleting the input data.

18. The method of claim 10, further comprising transmitting the input data determined as duplicate data and the probability of duplication of the input data to an application.

19. An apparatus comprising:

a processor configured to

increment at least one count value based on input data,

determine whether the input data is probable duplicate data, and

determine a probability of duplication of the input data based on the at least one count value in response to the input data being determined to be probable duplicate data.

20. The apparatus of claim 19, wherein the processor is further configured to transmit the input data determined to be probable duplicate data and the determined probability of duplication of the input data to an application.