Distributed batch matching of videos with dynamic resource allocation based on global score and prioritized scheduling score in a heterogeneous computing environment

• US 9,207,964 B1
• Filed: 12/17/2012
• Issued: 12/08/2015
• Est. Priority Date: 11/15/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Liao, Tawei, Gwosdek, Pascal, Paschen, Kathrin
• Primary Examiner(s): Al Kawsar, Abdullah
• Assistant Examiner(s): Ghaffari, Abu
• Application Number:
  US13/717,233
• Time in Patent Office: 1,086 Days
• Field of Search: 718/100, 718/102, 718/103, 704/9, 705/7.13
• US Class Current: 1/1
• 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 memory that stores computer executable components;

a processor that executes the following computer executable components stored in the memory;

a distribution component configured to;

distribute distinct processing tasks, associated with a match space for a pairwise comparison of a plurality of comparison objects and a plurality of reference objects, to a task pool, wherein respective processing tasks comprise task descriptions related to a subset of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by a processing task, wherein the match space comprises the plurality of comparison objects and the plurality of reference objects; and

places one or more processing tasks in respective one or more local cache snapshots associated with matching components of a plurality of matching components that perform the processing tasks from the task pool based on the task descriptions, where the distribution component places the one or more processing tasks based upon respective global scores for pairwise combinations of local cache snapshots and task descriptions, wherein the respective global scores are indicative of amounts of previously cached data of comparison objects and references objects in the local cache snapshots associated with previous pairwise comparisons of comparison objects and references objects by the matching components that correspond to comparison objects and references objects of the respective subsets of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by the processing tasks associated the task descriptions; and

wherein the plurality of matching components respectively select the processing tasks from the task pool based on respective prioritized scheduling scores associated with the distinct processing tasks, and a prioritized scheduling score is assigned based at least upon how recently copyrighted live events recorded in reference objects associated with the processing task occurred.

2. The system of claim 1, wherein the respective task descriptions include location data for information, configuration settings and task identifiers related to the subset of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by the processing task.

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

4. 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.

5. The system of claim 1, further comprising a partitioning component that divides the match space into the subsets of the plurality of comparison objects and the plurality of reference objects according a set of parameters.

6. The system of claim 5, wherein the set of parameters include at least one of duration since reception of at least one of a comparison object or a reference object, duration of at least one of the comparison object or the reference object, geographic regions of origination of at least one of the comparison object or the reference object, subject category of at least one of the comparison object or the reference object, media content characteristic of at least one of the comparison object or the reference object, a copyright identified for at least one reference object, a popularity measure of at least one comparison object, or a threshold number of at least one of comparison objects or reference objects to include in a subset.

7. The system of claim 1, further comprising 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 distinct processing tasks, or maintains the plurality of reference objects static while changing comparison objects of the plurality of comparison objects that correspond to the distinct processing tasks.

8. The system of claim 1, wherein the distribution component monitors a state of the processing tasks in a local cache snapshot associated with a matching component, and moves the processing task to a local snapshot associated with another matching component in response to the processing task not being completed within an amount of time satisfying a threshold function.

9. A method, comprising:

distributing, by a system including a processor, distinct processing tasks, associated with a match space for a pairwise comparison of a plurality of comparison objects and a plurality of reference objects, to a task pool, wherein respective processing tasks comprise task descriptions related to a subset of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by a processing task, wherein the match space comprises the plurality of comparison objects and the plurality of reference objects;

determining, by the system, respective global scores for pairwise combinations of local cache snapshots associated with matching components of a plurality of matching components and task descriptions, wherein the respective global scores are indicative of amounts of previously cached data of comparison objects and references objects in the local cache snapshots associated with previous pairwise comparisons of comparison objects and references objects by the matching components that correspond to comparison objects and references objects of the respective subsets of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by the processing tasks associated the task descriptions, wherein matching components of the plurality of matching components perform the processing tasks from the task pool based on the task descriptions;

placing, by the system, one or more processing tasks in respective one or more local cache snapshots associated with the matching components of the plurality of matching components based upon the global scores; and

wherein the plurality of matching components respectively select the processing tasks from the task pool based on respective prioritized scheduling scores associated with the distinct processing tasks, and a prioritized scheduling score is assigned based at least upon how recently copyrighted live events recorded in reference objects associated with the processing task occurred.

10. The method of claim 9, comprising:

generating, by the system, the subsets of the plurality of comparison objects and the plurality of reference objects according a set of parameters.

11. The method of claim 9, further comprising:

maintaining, by the system, the plurality of comparison objects static while changing a reference object of the plurality of reference objects that correspond to the distinct processing tasks;

or

maintaining, by the system, the plurality of reference objects static while changing comparison objects of the plurality of comparison objects that correspond to the distinct processing tasks.

12. The method of claim 9, wherein the prioritized scheduling score is assigned further based at least upon view counts associated with at least one of comparison objects or reference objects.

13. A non-transitory computer-readable medium having instructions stored thereon that, in response to execution, cause a system including a processor to perform operations comprising:

distributing distinct processing tasks, associated with a match space for a pairwise comparison of a plurality of comparison objects and a plurality of reference objects, to a task pool, wherein respective processing tasks comprise task descriptions related to a subset of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by a processing task, wherein the match space comprises the plurality of comparison objects and the plurality of reference objects;

determining respective global scores for pairwise combinations of local cache snapshots associated with matching components of a plurality of matching components and task descriptions, wherein the respective global scores are indicative of amounts of previously cached data of comparison objects and references objects in the local cache snapshots associated with previous pairwise comparisons of comparison objects and references objects by the matching components that correspond to comparison objects and references objects of the respective subsets of the plurality of comparison objects and the plurality of reference objects for which the pairwise comparison will be performed by the processing tasks associated the task descriptions, wherein the matching components of the plurality of matching components perform the processing tasks from the task pool based on the task descriptions;

placing one or more processing tasks in respective one or more local cache snapshots associated with the matching components of the plurality of matching components based upon the global scores; and

wherein the plurality of matching components respectively select the processing tasks from the task pool based on respective prioritized scheduling scores associated with the distinct processing tasks, and a prioritized scheduling score is assigned based at least upon how recently copyrighted live events recorded in reference objects associated with the processing task occurred.

14. The non-transitory computer-readable medium of claim 13, where the prioritized scheduling score is assigned further based at least upon view counts associated with at least one of comparison objects or reference objects.