Distributed batch matching of videos based on recency of occurrence of events associated with the videos

• US 9,690,629 B1
• Filed: 11/02/2015
• Issued: 06/27/2017
• Est. Priority Date: 11/15/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gwosdek, Pascal, Liao, Tawei, Paschen, Kathrin
• Primary Examiner(s): Ghaffari, Abu
• Application Number:
  US14/930,137
• Time in Patent Office: 603 Days
• Field of Search: None
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/487 using geographical or spatial information, e.g. location
• CPC Class Codes: G06F 16/60 of audio data
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/7867 using information manually generated, e.g. tags, keywords, comments, title and artist information, manually generated time, location and usage information, user ratings
• CPC Class Codes: G06F 7/38 Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
• CPC Class Codes: G06F 7/76 Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Distribution of various processing tasks is performed for a plurality of comparison objects, such as videos and/or other media content in a matching system. The plurality of comparison objects can include at least one feature that is compared to at least one feature of a plurality of reference objects to determine whether a match occurs in the comparison. Task descriptions corresponding to the processing tasks are distributed with the different processing tasks to a task pool. Matching components select at least one task from the task pool based on the task descriptions.

Claims

1. A system comprising:

a computer processor; and

a non-transitory computer-readable storage medium that stores components executable by the computer processor, the components comprising;

a partitioning component that generates a plurality of distinct processing tasks, the plurality of distinct processing tasks describing a plurality of comparison objects for comparison with a plurality of reference objects, each of the plurality of reference objects associated with a copyrighted live event recorded in the reference object;

a distribution component that respectively distributes the plurality of distinct processing tasks to a task pool, and the distribution component assigning a prioritized scheduling score to each distinct processing task, the prioritized scheduling score for each distinct processing task based on a recency of occurrence of the copyrighted live events recorded in the plurality of reference objects that are associated with the distinct processing task, each distinct processing task associated with a corresponding task description that includes location data for a comparison object and at least a portion of the plurality of reference objects that are associated with the distinct processing task, and configuration settings and task identifiers related to the comparison object and the portion of the plurality of reference objects;

a plurality of matching components that each schedule when to perform a task from the plurality of distinct processing tasks included in the task pool based on the task descriptions and the prioritized scheduling score associated with each distinct processing task, and the plurality of matching components each performing a scheduled task by comparing a comparison object and at least the portion of the plurality of reference objects that are associated with the scheduled task based on the schedule.

2. The system of claim 1, wherein the plurality of matching components decouple and couple to the task pool independently from one another at any given time.

3. The system of claim 1, wherein at least one matching component continuously polls the task pool for unclaimed processing tasks from the distinct processing tasks.

4. The system of claim 1, wherein

the partitioning component generates the plurality of distinct processing tasks by dividing a match space of the plurality of comparison objects and the plurality of reference objects according a set of parameters, and partitions sections of the match space into one or more subsets to generate the different processing tasks.

5. The system of claim 4, wherein the set of parameters for at least one of the plurality of comparison objects or the plurality of reference objects include at least one of a duration from reception of a comparison object at the system, a same length of a comparison object and a reference object, a geographic region of origination, a subject category, a media content characteristic, a copyright identified, a popularity measure, or threshold number for a subset.

6. The system of claim 1, wherein the computer executable components further comprise:

a snapshot component that maintains the plurality of comparison objects static while changing a reference object of the plurality of reference objects that correspond to the different processing tasks, or maintains the plurality of reference objects static while changing comparison objects of the plurality of comparison objects that correspond to the different processing tasks.

7. The system of claim 6, wherein the task descriptions include location data for cached information on the distribution component having configuration settings and task identifiers related to the plurality of comparison objects or the plurality of reference objects.

8. The system of claim 7, wherein the computer executable components further comprise:

a similarity component that determines a similarity between the cached information of the different processing tasks and an additional task from the task pool based on a similarity function and communicates to the snapshot component which objects to maintain as static and which objects to change for the different processing tasks based on the determined similarity for reducing redundant copies being made of the cached information.

9. The system of claim 1, wherein the computer executable components further comprise:

a timer component that tracks a length of time that a matching component takes to generate the comparison for a processing task, wherein the distribution component monitors a state of match of the different processing tasks that are distributed to the task pool and selected by the plurality of matching components, and further re-distributes the selected processing task to a different matching component in response to the amount of time satisfying a threshold function.

10. The system of claim 1, wherein a first task having a prioritized schedule score that is indicative of the first task being associated with a recent copyrighted live event is scheduled for comparison sooner than a second tasking having a prioritized schedule score that is indicative of the second task being associated with a copyrighted live event that is less recent than the copyrighted live event associated with the first task.

11. A computer-implemented method, comprising:

generating a plurality of distinct processing tasks, the plurality of distinct processing tasks describing a plurality of comparison objects for comparison with a plurality of reference objects, each of the plurality of reference objects associated with a copyrighted live event recorded in the reference object;

distributing the plurality of distinct processing tasks to a task pool, each distinct processing task associated with a corresponding task description that includes location data for a comparison object and at least a portion of the plurality of reference objects that are associated with the distinct processing task, and configuration settings and task identifiers related to the comparison object and the portion of the plurality of reference objects;

assigning a prioritized scheduling score to each distinct processing task based on a recency of occurrence of the copyrighted live events recorded in the plurality of reference objects that are associated with the distinct processing task;

scheduling, for each of a plurality of matching components, when to perform a task from the plurality of distinct processing tasks included in the task pool based on the task descriptions and the prioritized scheduling score associated with each distinct processing task; and

using each of the plurality of matching components to perform a scheduled task by comparing a comparison object and at least the portion of the plurality of reference objects that are associated with the scheduled task based on the schedule.

12. The computer-implemented method of claim 11, comprising:

generating a subset of a match space of the plurality of comparison objects and the plurality of reference objects according a set of parameters; and

partitioning sections of the one or more subsets to be distributed as the different processing tasks.

15. The computer-implemented method of claim 11, comprising:

monitoring a state of the different processing tasks that are distributed to the task pool and selected by the plurality of matching components to process; and

re-distributing the selected at least one processing task from at least one matching component of the plurality of matching components to a different matching component in response to the state of the at least one processing task being idle for a predetermined amount of time.

16. The method of claim 11, further comprising:

processing the different processing tasks of the at last one matching component while using shared cached information.

13. The computer-implemented method of 11, comprising:

maintaining the plurality of comparison objects static while changing a reference object of the plurality of reference objects that correspond to the different processing tasks;

or

maintaining the plurality of reference objects static while changing comparison objects of the plurality of comparison objects that correspond to the different processing tasks.

14. The computer-implemented method of claim 13, comprising:

determining a similarity between a cached information of the different processing tasks and an additional task based on a similarity function; and

determining whether to maintain the plurality of reference objects or the plurality of comparison objects static and changing the plurality of comparison objects or the plurality of reference objects respectively for the different processing tasks based on the determined similarity to reduce redundant copies being made of the cached information.

17. A non-transitory computer-readable storage medium storing executable code, the code when executed by a computer processor causes the computer processor to perform steps comprising:

generating a plurality of distinct processing tasks, the plurality of distinct processing tasks describing a plurality of comparison objects for comparison with a plurality of reference objects, each of the plurality of reference objects associated with a copyrighted live event recorded in the reference object;

distributing the plurality of distinct processing tasks to a task pool, each distinct processing task associated with a corresponding task description that includes location data for a comparison object and at least a portion of the plurality of reference objects that are associated with the distinct processing task, and configuration settings and task identifiers related to the comparison object and the portion of the plurality of reference objects;

assigning a prioritized scheduling score to each distinct processing task based on a recency of occurrence of the copyrighted live events recorded in the plurality of reference objects that are associated with the distinct processing task;

scheduling, for each of a plurality of matching components, when to perform a task from the plurality of distinct processing tasks included in the task pool based on the task descriptions and the prioritized scheduling score associated with each distinct processing task; and

using each of the plurality of matching components to perform a scheduled task by comparing a comparison object and at least the portion of the plurality of reference objects that are associated with the scheduled task based on the schedule.

18. The non-transitory computer-readable storage medium of claim 17, wherein generating the plurality of distinct processing tasks comprises:

generating a subset of a match space of the plurality of comparison objects and the plurality of reference objects according a set of parameters; and

partitioning sections of the one or more subsets to be distributed as the different processing tasks.

19. The non-transitory computer-readable storage medium of 17, wherein the code when executed by the computer processor causes the computer processor to perform further steps comprising:

maintaining the plurality of comparison objects static while changing a reference object of the plurality of reference objects that correspond to the different processing tasks;

or

maintaining the plurality of reference objects static while changing comparison objects of the plurality of comparison objects that correspond to the different processing tasks.

20. The non-transitory computer-readable storage medium of claim 19, wherein the code when executed by the computer processor causes the computer processor to perform further steps comprising:

determining a similarity between a cached information of the different processing tasks and an additional task based on a similarity function; and

determining whether to maintain the plurality of reference objects or the plurality of comparison objects static and changing the plurality of comparison objects or the plurality of reference objects respectively for the different processing tasks based on the determined similarity to reduce redundant copies being made of the cached information.