Methods and systems for eliminating duplicate events

• US 10,180,980 B2
• Filed: 02/23/2015
• Issued: 01/15/2019
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Khan, Omar Habib, Lawrence, Stephen R.
• Primary Examiner(s): Sough, S.
• Assistant Examiner(s): Hoang, Phuong N
• Application Number:
  US14/629,399
• Publication Number:
  US 20150169741A1
• Time in Patent Office: 1,422 Days
• Field of Search: None
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems, methods, and computer-readable media are disclosed for identifying duplicate events. In one implementation, a computer-implemented method is provided that includes receiving an event based on a user interaction with a client device, and determining content and a location for the event. The method further includes calculating a duplicate value for the event using the content and the location of the even, and determining a degree of similarity by comparing the duplicate value to a table of stored duplicate values. In addition, the method includes identifying the event as a duplicate of a stored event when the degree of similarity exceeds a predetermined threshold level of similarity, and indexing the event on the client device depending on the determination of whether or not the event is a duplicate of the stored event.

Claims

1. A computer-implemented system, comprising:

a non-transitory computer-readable storage medium that stores program code; and

at least one processor that executes the program code to perform operations comprising;

receiving a user interaction of activity with a client device;

determining content of the user interaction and a storage location of an article with which the user interaction occurred;

calculating a duplicate value of the user interaction using the content of the user interaction and the storage location of the article with which the user interaction occurred;

determining, for each of a plurality of previous user interactions, a degree of similarity between the user interaction and the previous user interaction by comparing the duplicate value to a table of stored duplicate values for the previous user interactions, each stored duplicate value being calculated using content of a respective previous user interaction and a respective storage location of an article with which the respective previous user interaction occurred;

determining that the user interaction is not a duplicate of any of the previous user interactions when each degree of similarity between the duplicate value and each stored duplicate value does not exceed a predetermined threshold level of similarity; and

indexing the user interaction on the client device in response to determining that the user interaction is not a duplicate of any of the previous user interactions.

2. The computer-implemented system of claim 1, wherein the duplicate value is an output of a cryptographic hash function.

3. The computer-implemented system of claim 2, wherein determining a degree of similarity by comparing the duplicate value to a table of stored duplicate values further comprises:

determining whether the output of the cryptographic hash function is identical to a stored duplicate value in the table of stored duplicate values.

4. The computer-implemented system of claim 1, wherein the content of the user interaction is the title of the user interaction.

5. The computer-implemented system of claim 1, wherein the duplicate value is calculated using less than all of the content of the user interaction.

6. The computer-implemented system of claim 1, wherein the user interaction activity comprises a user interaction with at least one of an application or an article on the client device.

7. The computer-implemented system of claim 1, wherein the operations comprise:

determining, for each previous user interaction, a second degree of similarity between a second user interaction and the previous user interaction, by comparing a second duplicate value for a second user interaction to the table of stored duplicate values;

determining that the second user interaction is a duplicate of one of the previous user interactions when the second degree of similarity between the second duplicate value and a duplicate value for the one previous user interaction exceeds the predetermined threshold level of similarity; and

determining to not index the second user interaction on the client device in response to determining that the second user interaction is a duplicate of the one previous user interaction.

8. A computer-implemented method for identifying duplicate user interactions, the method comprising the following operations performed by one or more processors:

receiving a user interaction of activity with a client device;

determining content of the user interaction and a storage location of an article with which the user interaction occurred;

calculating a duplicate value of the user interaction using the content of the user interaction and the storage location of the article with which the user interaction occurred;

determining, for each of a plurality of previous user interactions, a degree of similarity between the user interaction and the previous user interaction by comparing the duplicate value to a table of stored duplicate values for the previous user interactions, each stored duplicate value being calculated using content of a respective previous user interaction and a respective storage location of an article with which the respective previous user interaction occurred;

determining that the user interaction is not a duplicate of any of the previous user interactions when each degree of similarity between the duplicate value and each stored duplicate value does not exceed a predetermined threshold level of similarity; and

indexing the user interaction on the client device in response to determining that the user interaction is not a duplicate of any of the previous user interactions.

9. The method of claim 8, wherein the duplicate value is an output of a cryptographic hash function.

10. The method of claim 9, wherein determining a degree of similarity by comparing the duplicate value to a table of stored duplicate values further comprises:

determining whether the output of the cryptographic hash function is identical to a stored duplicate value in the table of stored duplicate values.

11. The method of claim 8, wherein the content of the user interaction is the title of the user interaction.

12. The method of claim 8, wherein the duplicate value is calculated using less than all of the content of the user interaction.

13. The method of claim 8, further comprising:

determining, for each previous user interaction, a second degree of similarity between a second user interaction and the previous user interaction, by comparing a second duplicate value for a second user interaction to the table of stored duplicate values;

determining that the second user interaction is a duplicate of one of the previous user interactions when the second degree of similarity between the second duplicate value and a duplicate value for the one previous user interaction exceeds the predetermined threshold level of similarity; and

determining to not index the second user interaction on the client device in response to determining that the second user interaction is a duplicate of the one previous user interaction.

14. A non-transitory computer-readable medium storing instructions, that, when executed by a processor, cause the processor to perform operations comprising:

receiving a user interaction of activity with a client device;

determining content of the user interaction and a storage location of an article with which the user interaction occurred;

calculating a duplicate value of the user interaction using the content of the user interaction and the storage location of the article with which the user interaction occurred;

determining, for each of a plurality of previous user interactions, a degree of similarity between the user interaction and the previous user interaction by comparing the duplicate value to a table of stored duplicate values for the previous user interactions, each stored duplicate value being calculated using content of a respective previous user interaction and a respective storage location of an article with which the respective previous user interaction occurred;

determining that the user interaction is not a duplicate of any of the previous user interactions when each degree of similarity between the duplicate value and each stored duplicate value does not exceed a predetermined threshold level of similarity; and

indexing the user interaction on the client device in response to determining that the user interaction is not a duplicate of any of the previous user interactions.

15. The computer-readable medium of claim 14, wherein the duplicate value is an output of a cryptographic hash function.

16. The computer-readable medium of claim 15, wherein determining a degree of similarity by comparing the duplicate value to a table of stored duplicate values further comprises:

determining whether the output of the cryptographic hash function is identical to a stored duplicate value in the table of stored duplicate values.

17. The computer-readable medium of claim 14, wherein the content of the user interaction is the title of the user interaction.

18. The computer-readable medium of claim 14, wherein the duplicate value is calculated using less than all of the content of the user interaction.

19. The computer-readable medium of claim 14, wherein the operations comprise:

determining, for each previous user interaction, a second degree of similarity between a second user interaction and the previous user interaction, by comparing a second duplicate value for a second user interaction to the table of stored duplicate values;

determining that the second user interaction is a duplicate of one of the previous user interactions when the second degree of similarity between the second duplicate value and a duplicate value for the one previous user interaction exceeds the predetermined threshold level of similarity; and

determining to not index the second user interaction on the client device in response to determining that the second user interaction is a duplicate of the one previous user interaction.