Patent Description:
Because video programs are long and viewers have limited time, it is useful to have snippets of a program that show some of the highlights. To be useful, the snippets of a program must be shorter than the actual program, and preferably contain some of the most interesting scenes from the video program. However, identifying the interesting scenes can be time consuming and the results can vary depending on who is evaluating the video program. <CIT> relates to audio and/or video scene detection and retrieval.

Disclosed implementations address the above deficiencies and other problems associated with generating a video program extract. A first step in building an extract is to correlate user search queries to broadcast video programs. This can be done by correlating search terms, phrases, keywords, or concepts to corresponding terms, phrases, keywords, or concepts in the video program. As described below, one way to correlate these uses video program subtitles. Some implementations use voice recognition software to identify the words in the video, and correlate these to the search terms, phrases, keywords, or concepts. This correlation also identifies locations in the video program where the terms, phrases, keywords, or concepts occur.

In general, search queries asked during a TV program represent interesting aspects of the TV program. The video scenes that contain keywords, phrases, or conceptual entities corresponding to popular queries are generally representative of the whole program, and thus stitching together these scenes creates a useful video snippet.

In some implementations, the video extract is formed by finding the time in the video content that matches the search query terms (e.g., by matching subtitles), and extending the video scene to the boundaries (both backward and forward). In some implementations, long scenes are limited (e.g., not more than <NUM> seconds before and after each matched location in the video). In some implementations, video scene boundaries are identified by sudden changes in the audio or video signal. In some implementations, having identified matching terms, keywords, phrases, or conceptual entities, additional matches to other instances of the same terms, keywords, phrases, or concepts are also identified and included in the extract. For example, if the matching is done using subtitles, other locations throughout the content may be identified that include the same terms, keywords, phrases, or concepts.

In some implementations, all of the matched scenes are stitched together chronologically, but some implementations order the extracted snippets in other ways (e.g., placing particularly active or interesting scenes at the start or end of the extract). In some implementations, matching is based on aggregated user queries (e.g., using queries that were asked around the same time for a given video scene from multiple users), which form a spike above normal query levels. The snippets generated therefore reflect a general interest in the matched scenes.

In some implementations, the same matching process is applied to individual queries from a single user (or a small number of users, such as users from a small social network). This generates video snippets that are personalized. In some implementations, personal matching is achieved with different techniques (e.g., knowing that a given user who asked a given query is also watching a given content at a given timestamp).

Some implementations apply the same process more broadly to generate a video extract for more than a single program. For example, some implementations generate a video extract from a given day, to create a "summary of a day. " Such an extract may include video programs from all channels, or a subset of channels (e.g. just news channels, or just entertainment channels). In some implementations that create broader extracts, the individual scene portions may be more limited (e.g., <NUM> or <NUM> seconds before and after each matched location), or certain matched portions may be omitted (e.g., by requiring a higher threshold frequency of user queries).

Some implementations use search query spikes to identify terms, phrases, or concepts for matching. One can match queries submitted to a search engine against TV content that is or was broadcast to multiple viewers in the same time frame. Some implementations select query candidates by analyzing the frequency that queries are submitted. When there is a sudden increase in the query frequency for a given query (a query "spike"), there is a good likelihood that it corresponds to a specific event (e.g., a scene from a movie was just broadcast).

Some implementations match queries to broadcast content by means of matching keywords, phrases, or concepts in search queries to appropriate counterparts in television subtitles, co-occurring within some time window. For example, if the term "gobble stopper" is mentioned on some TV channel, and appears in subtitles, viewers might be interested in the definition of "gobble stopper" or want more details. Within a short time (e.g., a minute), some viewers start entering queries in a search engine. This creates an observable spike in the frequency of "gobble stopper" queries. Some implementations identify such a spike by comparing the average frequency of requests for the query (e.g., measured in query submissions per minute) with a current frequency for the same query (e.g., during the past hour, past <NUM> minutes, or past five minutes). Some implementations identify such a spike by comparing the maximum frequency of requests for the query over a recent moving time window (e.g., the most recent hour or half hour of query frequency data - excluding the most recent few minutes) with a current frequency for the same query. Some implementations identify such a spike by comparing a combination of the maximum frequency of requests and the average frequency of requests with a current frequency for the same query.

In addition to matching queries by keywords or phrases, some implementations match concepts, which are sometimes referred to as knowledge graph entities. This accounts for the situation where different people use different words or phrases to describe the same conceptual entity.

For each detected candidate spike (query or entity), some implementations check whether the words, keywords, phrases, or conceptual entities are correlated with data in subtitles of any monitored TV channel within the last few minutes (e.g., within the last five minutes or within the last <NUM> minutes). In some implementations, the check includes determining whether most of query words, keywords, phrases, or entities are present within the moving window of subtitles for a single television program. In some implementations, the order of the terms from each query is evaluated as well, with a preference for matching subtitles that appear in the same order. Alternatively, some implementations perform the matching in the opposite direction: checking whether parts of subtitles are present in a search query.

When there is a non-empty intersection between query elements and subtitle elements for a television program within a given moving time window, there is a potential match. In some implementations, the overlap is evaluated to compute a score, and when the score exceeds a threshold value, it is considered a match. Some implementations impose additional constraints for matching, such as the expected order of the terms.

Some implementations apply voice recognition algorithms directly to the TV content to generate a stream of words to match on rather than relying on subtitles. In some implementations, both subtitles and voice recognition are used.

Some implementations use Twitter® tweets™ instead of or in addition to user search queries to identify user interest in specific portions of a broadcast video program.

In accordance with some implementations, a method executes at a server system with one or more processors and memory. The memory stores one or more programs configured for execution by the one or more processors. The process identifies a plurality of search query spikes from search queries submitted by a plurality of users. In some implementations, each search query spike corresponds to a respective set of one or more search queries identified as equivalent, and the frequency for submitting queries from the respective set during a corresponding spike period exceeds the frequency for submitting queries from the respective set during an average span of time by a predefined threshold amount.

The process correlates a subset of the search query spikes to a broadcast video program. Each correlated search query spike corresponds to a respective location in the video program. In some implementations, correlating a search query spike to a broadcast video program includes matching search terms from the corresponding search queries to subtitles of the video program at a corresponding respective location in the video program. The process constructs a snippet of the video program by stitching together portions of the video program that contain the locations corresponding to the correlated search query spikes. In some implementations, the portions of the video program that contain the locations corresponding to the correlated search query spikes extend to video scene boundaries before and after each location. In some implementations, the process provides the constructed snippet to a user who submits a search query for information about the video program.

In accordance with some implementations, the process further includes constructing respective snippets for a plurality of respective broadcast video programs. Each respective snippet is based on correlating a respective plurality of the search query spikes to a respective video program, and the plurality of broadcast video programs were all broadcast during a predefined span of time. The process stitches together the snippets for the plurality of broadcast programs to form a single video summary for the predefined span of time. In some implementations, the predefined span of time is one day. The plurality of broadcast programs may be limited to a single channel (or subset of channels), limited to a specific genre (e.g., news), or may be specified by a user.

Thus methods and systems are provided that generate video program extracts that are shorter than the original programs but provide interesting scenes that are representative of the video programs.

For a better understanding of the aforementioned implementations of the invention as well as additional implementations thereof, reference should be made to the Description of Implementations below, in conjunction with the following drawings in which like reference numerals refer to corresponding parts throughout the figures.

Reference will now be made in detail to implementations, examples of which are illustrated in the accompanying drawings. In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one of ordinary skill in the art that the present invention may be practiced without these specific details.

<FIG> is a block diagram that illustrates the major components of some implementations. The various client devices <NUM> and servers <NUM> in server system <NUM> communicate over one or more networks <NUM> (such as the Internet). A client environment <NUM> includes a television <NUM>, which is typically connected to a set top box <NUM> (or a receiver / converter). The set top box <NUM> receives media content from a content provider <NUM>, such as a cable TV network, a satellite dish network, or broadcast over the airwaves. As illustrated in <FIG>, in some cases the media content is transmitted through the communication networks <NUM>.

In some instances, the client environment <NUM> also includes one or more client devices <NUM>, such as smart phones, tablet computers, laptop computers, or desktop computers. In the context here, the client device is typically in close proximity to the television <NUM>. In some instances, running on the client device is a client application <NUM>, which in some implementations is a "second screen application" that correlates with the programming displayed on the television <NUM>. In some implementations, the client application runs within a web browser <NUM>. Although only a single client environment <NUM> is illustrated in <FIG>, there are typically millions of client environments at any time. Different client environments <NUM> may use different media content providers <NUM>, and may use varying combinations of client devices <NUM> and boxes <NUM> that function as receivers, converters, or set top boxes. Although <FIG> illustrates a single set top box <NUM>, one of skill in the art would recognize that other environments could consist of a plurality of distinct electronic components, such as a separate receiver, a separate converter, and a separate set top box. Also, some or all of the functionality of the set top box <NUM> (or converter or receiver) may be integrated with the television <NUM>.

The server system <NUM> includes a plurality of servers <NUM>, and the servers <NUM> may be connected by an internal communication network of bus <NUM>. The server system <NUM> includes a query processing module <NUM>, which receives queries from users (e.g., from client devices <NUM>) and returns responsive query results. The queries are tracked in a search query log <NUM> in a database <NUM>.

In some implementations, the server system <NUM> also includes a television program determination module <NUM>, which determines what television programs viewers are watching. In some implementations, the television program determination module <NUM> receives notifications from a client application <NUM> running on a client device <NUM>, and the notification specifies the television program that is being presented on the associated television <NUM>. In some implementations, the television program determination module <NUM> receives notification from the set top box <NUM> (e.g., when the user at the client environment registers to have viewership tracked). In some implementations, the television program determination module receives an audio stream (from the client application <NUM> or the set top box) and determines the television program by analyzing the stream. In some implementations, the television program determination module <NUM> is part of the client application <NUM>, and the determined programs are communicated to the media supplement module <NUM>.

In some implementations, the server system includes a media supplement module <NUM>, which provides additional information about television programs to the client application <NUM>, such as search results corresponding to aspects of the viewed television programs. The operation of the media supplement module <NUM> is described in more detail throughout this disclosure, including with respect to <FIG>.

The server system includes one or more databases <NUM>. The data stored in the database <NUM> includes a search query log <NUM>, which tracks each search query submitted by a user. In some implementations, the search query log is stored in an aggregated format to reduce the size of storage. The database may include television program information <NUM>. The television program information <NUM> may include detailed information about each of the programs, including subtitles, as well as broadcast dates and times. Some of the information is described below with respect to <FIG>.

The server system also include an video extract module <NUM>, which uses submitted queries to identify interesting potions of video programs and generate extracts for the video programs using the identified interesting portions. This is described in more detail below with respect to <FIG>.

<FIG> is a block diagram illustrating a client device <NUM> that a user uses in a client environment <NUM>. A client device <NUM> typically includes one or more processing units (CPU's) <NUM> for executing modules, programs, or instructions stored in memory <NUM> and thereby performing processing operations; one or more network or other communications interfaces <NUM>; memory <NUM>; and one or more communication buses <NUM> for interconnecting these components. The communication buses <NUM> may include circuitry (sometimes called a chipset) that interconnects and controls communications between system components. A client device <NUM> includes a user interface <NUM> comprising a display device <NUM> and one or more input devices or mechanisms <NUM>. In some implementations, the input device/mechanism includes a keyboard and a mouse; in some implementations, the input device/mechanism includes a "soft" keyboard, which is displayed as needed on the display device <NUM>, enabling a user to "press keys" that appear on the display <NUM>.

In some implementations, the memory <NUM> includes high-speed random access memory, such as DRAM, SRAM, DDR RAM or other random access solid state memory devices. In some implementations, memory <NUM> includes non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices. In some implementations, the memory <NUM> includes one or more storage devices remotely located from the CPU(s) <NUM>. The memory <NUM>, or alternately the non-volatile memory device(s) within memory <NUM>, comprises a non-transitory computer readable storage medium. In some implementations, the memory <NUM>, or the computer readable storage medium of memory <NUM>, stores the following programs, modules, and data structures, or a subset thereof:.

Each of the above identified executable modules, applications, or sets of procedures may be stored in one or more of the previously mentioned memory devices and corresponds to a set of instructions for performing a function described above. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures, or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various implementations. In some implementations, the memory <NUM> may store a subset of the modules and data structures identified above. Furthermore, the memory <NUM> may store additional modules or data structures not described above.

Although <FIG> shows a client device <NUM>, <FIG> is intended more as a functional description of the various features that may be present rather than as a structural schematic of the implementations described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated.

<FIG> is a block diagram illustrating a server <NUM> that may be used in a server system <NUM>. A typical server system includes many individual servers <NUM>, which may be hundreds or thousands. A server <NUM> typically includes one or more processing units (CPU's) <NUM> for executing modules, programs, or instructions stored in the memory <NUM> and thereby performing processing operations; one or more network or other communications interfaces <NUM>; memory <NUM>; and one or more communication buses <NUM> for interconnecting these components. The communication buses <NUM> may include circuitry (sometimes called a chipset) that interconnects and controls communications between system components. In some implementations, a server <NUM> includes a user interface <NUM>, which may include a display device <NUM> and one or more input devices <NUM>, such as a keyboard and a mouse.

In some implementations, the memory <NUM> includes high-speed random access memory, such as DRAM, SRAM, DDR RAM or other random access solid state memory devices. In some implementations, the memory <NUM> includes non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices. In some implementations, the memory <NUM> includes one or more storage devices remotely located from the CPU(s) <NUM>. The memory <NUM>, or alternately the non-volatile memory device(s) within memory <NUM>, comprises a non-transitory computer readable storage medium. In some implementations, the memory <NUM>, or the computer readable storage medium of memory <NUM>, stores the following programs, modules, and data structures, or a subset thereof:.

Each of the above identified elements in <FIG> may be stored in one or more of the previously mentioned memory devices. Each executable program, module, or procedure corresponds to a set of instructions for performing a function described above. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various implementations. In some implementations, the memory <NUM> may store a subset of the modules and data structures identified above. Furthermore, the memory <NUM> may store additional modules or data structures not described above.

Although <FIG> illustrates a server <NUM>, <FIG> is intended more as functional illustration of the various features that may be present in a set of one or more servers rather than as a structural schematic of the implementations described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated. The actual number of servers used to implement these features, and how features are allocated among them, will vary from one implementation to another, and may depend in part on the amount of data traffic that the system must handle during peak usage periods as well as during average usage periods.

In some implementations, the database <NUM> stores video program data <NUM>. Each video program includes a program ID <NUM>, and various other information, which may be subdivided into separate data structures.

In some implementations, the video program data for each program includes a program profile <NUM>, which is described in more detail with respect to <FIG>. The profile includes the program ID <NUM>, which is a unique identifier for each video program. In some implementations, the profile <NUM> includes a program description <NUM>, which may comprise one or more paragraphs that describe the program. The profile <NUM> may include cast information <NUM>, which includes details about individual cast members or links to further information about the cast members (e.g., links to cast member web pages). For video programs that are part of a series, some implementations include series information <NUM> in the profile <NUM>. In some implementations, the profile <NUM> includes genre information <NUM>, which may include general information about the genre of the video program, and may provide links to additional information. In some implementations, the profile <NUM> includes related terms <NUM>, which may include key terms that describe the video program or may identify terms that enable a user to identify related content.

In some implementations, the video program data includes subtitle data <NUM>, as illustrated in <FIG>. In some instances, the subtitle information is publicly available beforehand, but in other instances, the subtitle information is dynamically extracted and stored as a video program is broadcast.

In some implementations, the subtitle data includes the program ID <NUM> and a subtitle list <NUM>, which is a sequential list of the subtitles that appear in the video program. For video programs that scroll the subtitles, portions of the subtitle text may scroll in and out of view during windows of time (e.g., showing line <NUM> and line <NUM> during a first period of time, showing line <NUM> and line <NUM> during a second period of time, showing line <NUM> and line <NUM> during a third period of time, and so on). To address this type of subtitle, some implementations allow overlapping text between successive subtitles. Some implementations store each distinct portion of text, and allow overlapping periods of time.

The subtitle list includes a sequence of subtitle text portions. Each portion is identified by a subtitle ID <NUM>. In some implementations, the subtitle ID is globally unique, but in other implementations, the subtitle ID is unique only within a give program ID <NUM>. The subtitle ID <NUM> may be a sequential number within each video program. Each subtitle portion includes data that specifies the location <NUM> within the program. In some implementations, this is specified as an offset (e.g., in seconds) from the beginning of the video program. In some implementations, the location information <NUM> also includes the length of time the subtitle is displayed or an ending time for the subtitle (e.g., the offset in seconds to the end of the period of time that the subtitle is displayed). Some implementations address commercial breaks in various ways. In some implementations, the locations <NUM> are specified only with respect to the media content itself, and adjust for commercial breaks dynamically based on the actual lengths of the commercial breaks. In some instances, if the lengths of the commercial breaks are predefined, the locations <NUM> can include the commercial breaks, effectively treating the commercials as part of the video program.

Each subtitle portion also includes the text <NUM> in the subtitle. In some implementations, the text is parsed into a sequence of words, and may eliminate punctuation. In some implementations, the language <NUM> of the subtitles is also stored. Some implementations store additional or different data, or store the data in alternative formats (e.g., tokenized).

In addition to the information about video program content or the subtitles, some implementations store information about when the video program has been or will be broadcast. Some implementations focus on video programs that are broadcast on a predefined schedule, and thus multiple viewers are viewing the same video program at the same time. Different techniques are applied to use video on demand (VOD) data, and may not use a broadcast data table <NUM>.

<FIG> illustrates a skeletal data structure for storing broadcast data <NUM>. Broadcast data <NUM> includes a program ID <NUM> and a broadcast list <NUM>, which identifies when the video program has or will be broadcast. In some implementations, each broadcast instance has a start time <NUM> and an end time <NUM>. In some implementations, each broadcast instance includes a start time <NUM> and a duration. In some implementations, each broadcast instance includes information <NUM> that specifies the channel, station, or other source of the broadcast. In some implementations, each broadcast instance includes information <NUM> that specifies the geographic location or region where the broadcast occurred. In some implementations, the information <NUM> is a broadcast area. In some implementations, each broadcast instance stores the time zone <NUM> of the broadcast.

As noted above, the database <NUM> may store a search query log <NUM>. In some implementations, each search query is assigned a unique query ID <NUM> (e.g., globally unique). In addition, the log stores various search query data <NUM>, as illustrated in <FIG>. Each query includes a set of query terms <NUM>, which may be parsed to eliminate punctuation. In some implementations, typographical errors are retained because they may match typographical errors that appear in video program subtitles.

The query data <NUM> typically includes a timestamp <NUM> that specifies when the query was issued. In some implementations, the timestamp <NUM> is based on the user time zone <NUM>, which is also stored. In other implementations, the timestamp <NUM> represents a server generated timestamp indicating when the query was received. Some server systems <NUM> include one or more servers <NUM> that accurately manage timestamps in order to guarantee both accuracy of the data as well as sequential consistency. In some implementations, a server timestamp <NUM> together with the user time zone <NUM> (as well as knowing the server time zone) allows the server system to accurately know when each query was submitting according to the user's local time, and does not rely on the user's client device <NUM>. In some implementations, the query data includes the user's IP address <NUM> and the user's geographic location <NUM>. The set of possible values for the user's geographic location <NUM> typically corresponds to the same set of values for the geographic location or region <NUM> used for video broadcasts.

In some implementations, the database <NUM> stores query groups <NUM>, which identify sets of queries that are considered equivalent. Some of the ways that queries may be grouped together are illustrated in <FIG>. Each query group has a query group ID <NUM>, which uniquely identifies the group. Associated with each group is an average query frequency <NUM>, which may be expressed in query instances per minute or query instances per hour. The average <NUM> may be computed over a period of time, such as week or a month. In some implementations, the average is computed over a shorter period of time (e.g., the last <NUM> hours) in order to keep the value relatively current. Because spikes are identified relative to the background average <NUM>, the average is kept up to date. For example, the background average <NUM> may fluctuate slowly over time, which does not constitute a spike.

In some implementations, a maximum query frequency <NUM> is computed and updated over a moving time window for each query group <NUM>. The time window is typically short and relatively recent (e.g., the most recent hour or half hour). Because the maximum query frequency is used to detect spikes, the time window generally excludes the most recent few minutes in order to avoid overlap with an actual current spike. In some implementations, a spike is identified for a group relative to just the maximum query frequency <NUM>. In other implementations, a spike is identified using both the average query frequency <NUM> and the maximum query frequency <NUM>. In implementations where a spike is identified relative to the maximum query frequency <NUM>, the spike is identified for a respective group when the current group query frequency exceeds the saved maximum query frequency by a substantial factor (e.g., twice the maximum query frequency). In some implementations where a spike is identified based on a combination of average query frequency <NUM> and maximum query frequency <NUM>, the spike is identified when the current query activity exceeds some numerical combination (such as linear combination) of the average and maximum query frequencies for that group. In some implementations, a spike is identified when the current query activity exceeds both the maximum query frequency and the average query frequency (e.g., by predefined factors). In some implementations, a spike is identified when the current query activity exceeds either the maximum query frequency or the average query frequency.

As illustrated in <FIG>, each query group <NUM> includes a set <NUM> of queries that are in the group. The set of queries <NUM> includes the query group ID <NUM>, and the query list <NUM>. Each query instance includes a set of query terms <NUM>, which may be stored in varying formats (e.g., the complete query as originally submitted, complete queries with punctuation removed, or a list of individual terms). In addition, some implementations include a set of query classifications <NUM>, which may be humanly meaningful or generated as part of a trained machine learning classifier.

The database <NUM> also stores spike information <NUM>. A spike is associated with a specific query group, which is identified by its query group ID <NUM>, and is associated in some cases with a specific video program identified by a program ID <NUM>.

<FIG> illustrates other spike data <NUM> that some implementations track for each spike. In some implementations, each spike has an associated start time <NUM> and an end time <NUM>, which are generally based on the server clock. In some implementations, the spike data <NUM> includes a timestamp when the spike reached a peak, which may be stored instead of the start time <NUM> and end time <NUM>. In some implementations, the spike data <NUM> includes a query instance count <NUM>, which indicates the number of distinct query instances during the spike. In some implementations, the spike data <NUM> includes a computed query frequency <NUM>. Note that query frequency = query instance count <NUM> / (end time <NUM> - start time <NUM>). While a spike is occurring, the data may be updated almost constantly. When a spike has been matched to subtitles of a video program, the spike data may include the program ID <NUM> of the corresponding video program, and a location <NUM> in the video program where the matched subtitles appeared. The location may be specified as an offset from the beginning of the program, or a timestamp indicating the broadcast time of the portion of the video program with the matching subtitles. When a timestamp is used to specify the location, implementations may use the timestamp when the subtitle portion started, when it ended, or the middle. In some implementations, the location information <NUM> specifies the interval of time rather than a single point (e.g., start and end or start and duration).

<FIG> illustrates visually the identification of a query spike and correlating the spike to a video program. In the upper half of <FIG> is a graph showing query frequency <NUM> versus time <NUM> for a specific query group 342A. The time period displayed is the time between <NUM>:<NUM> PM and <NUM>:<NUM> PM on a certain day. The curve <NUM> shows how the query frequency fluctuates, but stays near the background average <NUM> most of the time. However, we can see a spike <NUM> in query frequency between the start time <NUM> and the end time <NUM>. The increased query frequency during the spike includes all of the queries in the query group 342A. For implementations that identify spikes based on recent maximum query frequency <NUM> for a group, the recent maximum query frequency for the group is determined in a window <NUM> (defined between the dashed lines) of the query frequency data that precedes the current time.

Below the graph are the program lineups for four channels. Channel <NUM> is presenting program A <NUM>-<NUM> during this hour. Channel <NUM> is presenting program B <NUM>-<NUM> during the first half hour and program C <NUM>-<NUM> during the second half hour. Channel <NUM> is presenting program D <NUM>-<NUM> during the hour, and channel <NUM> is presenting program E <NUM>-<NUM> during the hour. The server system <NUM> collects video program terms (e.g., subtitle data <NUM> or terms identified by voice recognition software) for the five program <NUM>-<NUM>,. , <NUM>-<NUM> dynamically while they are broadcast.

Once the spike <NUM> is detected, the query terms are compared against the video program terms for a recent period of time prior to the beginning of the spike <NUM> (e.g., <NUM> minute, <NUM> minutes, or ten minutes). In this case, a match is detected with program D <NUM>-<NUM> at location <NUM>. In some cases, a match is detected by matching specific words or keywords in the video program terms. In other cases, the match is detected based on a sequence of words or a matching linguistic concept. In some implementations, the matching is performed by a classifier trained on data from previously stored video program terms and query groups. Some examples of matching are illustrated with respect to <FIG>.

As illustrated in this example, the spike is detected without regard to the specific users who submitted the queries. In some implementations, the users may be any people who submit queries to the query module <NUM>. In some implementations, the set of users is limited to those who have installed the client application <NUM> on a client device <NUM>. In this case, the queries tracked are based on the client application, and thus generally related to video programs. When queries are tracked for all users, the queries are not necessarily related to television, so there can be substantial overhead costs. In some implementations, spike results are generated only from queries from unique users. In some such implementations, unique users are determined by storing user query sets in server memory <NUM> and then discounting (i.e., not using in spike detection) duplicate queries from the same user.

<FIG> illustrates one way of matching that does not require literal matching of identical terms. Sometimes people express the same basic concept using different terms. In this example, the phrase "life on Mars" <NUM> expresses essentially the same concept as "Martian life" <NUM>, but the two phrases use different words and word order. If these two phrases were submitted as queries to the search query module <NUM>, some implementations would group them together in a single query group <NUM>. The same process of concept matching can be applied when matching query terms to video program terms from a video program. For example, if there is a spike in submissions of the "life on Mars" <NUM> query, and "Martian life" <NUM> appears in the video program terms of a broadcast video program, some implementations would correlate them.

<FIG> illustrates another way of matching query terms. In this case, a match is identified when two sets of terms have sequences of terms that are substantially the same. In some cases the sequences are exactly the same, but in other cases, there is some slight variation, as illustrated by these examples. For example, the sequences <NUM> and <NUM> differ only in that sequence <NUM> has added the term "river" at the end. They are substantially the same. The sequence <NUM> is also substantially the same as sequence <NUM> because the only difference is omitting the insignificant term "on. " Although the sequence <NUM> adds the two terms "Mary Poppins," some implementations would classify it as substantially the same as the first sequence <NUM> because it includes a significant sequence that is identical to sequence <NUM>. The final example <NUM> illustrates that some implementations also account for misspellings or typographical errors. Some people (e.g., Americans) might not know how to spell "Thames," but there is sufficient context in sequence <NUM> to consider it a match. Some implementations would group together all five of these sequences into a single group <NUM>, and measure query frequency based on the total aggregated queries submitted for all of them.

In addition to grouping together by various matching techniques as illustrated in <FIG>, some implementations group together queries using a clustering algorithm.

The examples in <FIG> are also applied to matching between submitted queries and video program terms (e.g., subtitle terms).

<FIG> illustrates a process of performed by the video extract module <NUM>. The video extract module <NUM> generates a video program extract based on submitted users queries. Whereas <FIG> above illustrated matching a single search query spike <NUM> to a location <NUM> in a video program <NUM>-<NUM>, <FIG> correlates multiple spikes for a single program <NUM>. In the upper part of <FIG>, are plots of query frequency <NUM> against time <NUM> for three distinct query groups 342A, 342B, and 342C. The graph 1342C corresponds to query group 342C, the graph 1342A corresponds to the query group 342A, and the graph 1342B corresponds to the query group 342B.

Note that the background or average query frequency for each of the query groups is different (the graphs 1342A, 1342B, and 1342C have different average heights above the x-axis). In this illustrated example, each of the graphed query groups has a spike (348A, 348B, and 348C) between <NUM>:<NUM> PM and <NUM>:<NUM> PM. The spike identification module <NUM> identifies (<NUM>) the spikes 348A, 348B, and 348C, as explained above with respect to <FIG>. Although illustrated here for search queries, the same methodology is applied to Twitter® tweets™ in some implementations.

Each spike <NUM> may be correlated (<NUM>) to a location <NUM> in a video program <NUM>, as described above with respect to <FIG>. Here, the spike 348A is correlated with the location 910A, the spike 348B is correlated with the location 910B, and the spike 348C is correlated with the location 910C.

Once the locations <NUM> in the video program <NUM> are identified, the process selects (<NUM>) video scene portions that include those locations. In particular, a snippet includes more than a single video frame at each location. Typically, implementations select a portion around each location to create a contiguous video portion that includes each location. In some implementations, the portion extends forwards and backwards to the nearest video scene boundaries. In some instances, extending all the way to the boundary would be too long, so the portion may be limited. For example, some implementations limit the portion to <NUM> seconds before and after each location. (And a portion can be smaller when there is a video scene boundary less than thirty seconds from the corresponding location. ) As illustrated in <FIG>, the portion corresponding to location 910A ranges from lower position <NUM> to upper position <NUM>. The locations 910A and 910B are roughly in the middle of the illustrated portions, but the location 910C is off center.

Finally, the video scene portions are stitched together (<NUM>) to form a video extract <NUM>. The extract <NUM> is smaller than the full video program <NUM>, but includes some content that has been identified as interesting to users. Once the extract <NUM> has been generated, it may be provided to users. For example, if the video program is a movie or TV episode, a user may view the extract <NUM> to decide whether to watch the whole program. If the video program is a news program, the extract alone may be sufficient to let the user know the highlights. In some implementations, when a video extract is created, the information about the locations <NUM> is stored, which enables quick links to video segments in the original video program. For example, if a user is interested in one of the news clips in the video extract, the user may be able to link to the original content and see the entire relevant segment.

<FIG> provide a flowchart of a process <NUM>, performed by a server system <NUM> for building (<NUM>) video program extracts. The extracts are sometimes referred to as snippets. The method is performed (<NUM>) at a server system with one or more processors and memory. The memory stores (<NUM>) programs configured for execution by the one or more processors.

The process identifies (<NUM>) a plurality of search query spikes from search queries submitted by a plurality of users. The spikes are typically during a specified span of time (e.g., between <NUM>:<NUM> PM and <NUM>:<NUM> PM in <FIG>). In some implementations, the search queries are from users running the client application <NUM>. In some implementations, the users are not necessarily using the client application <NUM>.

A spike represents a short term increase in the query frequency, and thus each spike has a limited duration (e.g., less than a predefined duration, such as five minutes). In some implementations, each search query spike <NUM> corresponds (<NUM>) to a respective set of one or more search queries that are identified as equivalent. Different people express the same basic query in different ways, so implementations generally group them together for more accurate reporting.

In some implementations, a first search query and a second search query are identified (<NUM>) as equivalent when an ordered sequence of search terms from the first search query is substantially identical to an ordered sequence of search terms from the second search query. This was illustrated above with respect to <FIG>. In some implementations, a first search query and a second search query are identified (<NUM>) as equivalent when a linguistic concept expressed using search terms from the first search query is substantially the same linguistic concept expressed using search terms from the second search query. This was illustrated above with respect to <FIG>.

A "spike" is more than a little bump in the query frequency. Here, a spike is identified when the frequency of submitting queries from a respective set during the spike period exceeds (<NUM>) the frequency of submitting queries from the set during an average span of time by a predefined threshold amount or percentage. For example, some implementations specify the threshold percentage as <NUM>% or <NUM>%. Some implementations use an even higher percentage in order to focus on significant spikes. Some implementations have an adaptive percentage based on the query group or other factors. For example, if the number of relevant spikes in the past half hour has been small, the required threshold percentage may be reduced in order to identify more spikes. In some implementations, the query frequency for a potential spike is compared to a maximum query frequency <NUM> during a recent span of time. This was described above with respect to <FIG>.

The search term matching module <NUM> then correlates (<NUM>) a subset of the search query spikes to a broadcast video program. Some implementations match (<NUM>) one or more terms from a set of search queries to one or more subtitle terms appearing in the video program at a particular location. The matching may involve matching specific words or keywords, phrase, or conceptual entities. Some examples are illustrated in <FIG>. Each correlated search query spike corresponds (<NUM>) to a respective location in the video program.

In some instances, the video program is (<NUM>) a televised television program. In some instances, the video program is streamed from the Internet, and may consist of media content other than a television program.

In some implementations, for each respective correlated search query spike, the time difference between the time of the search query spike and when the respective location in the video program was broadcast is (<NUM>) less than a predefined delay. This is consistent with the goal of identifying spikes that are triggered by specific media content. In some instances, the search term matching module <NUM> stitches together subtitles from two or more consecutive segments in order to match search queries.

In some implementations, matching one or more terms from a set of search queries to one or more subtitle terms appearing in the video program includes matching an ordered sequence of terms from a search query in the set to a substantially identical ordered sequence of subtitle terms. This was illustrated above with respect to <FIG>. In some implementations, matching one or more terms from a set of search queries to one or more subtitle terms appearing in the video program includes matching a linguistic concept expressed using terms from a search query in the set with substantially the same linguistic concept expressed using the subtitle terms. This was illustrated above with respect to <FIG>.

The process <NUM> constructs (<NUM>) a snippet of the video program by stitching together portions of the video program that contain the locations corresponding to the correlated search query spikes. This was illustrated above in <FIG>. In some instances, the portions of the video program are arranged (<NUM>) in order in the constructed snippet according to the order of the portions within the video program. This provides an extract that is "chronologically correct. " In some implementations, the portions are not necessarily stitched together in order, allowing some flexibility to group together related scenes, place significant portions are the beginning, or the end of the extract, or for other purposes.

In some implementations, the portions of the video program that contain the locations corresponding to the correlated search query spikes extend (<NUM>) to video scene boundaries before and after each location. This was illustrated above in <FIG>, selecting (<NUM>) a portion from lower position <NUM> to upper position <NUM> containing the location 910A. Typically the portions are chosen long enough for a viewer to understand each scene, but not so long that the extract takes too long to watch.

In some instances, when a user submits a search query for information about a video program, the server system <NUM> provides (<NUM>) the constructed snippet to the user.

In some implementations, snippets from multiple video programs are stitched together to form a video summary. The video summary typically represents a specific span of time, such as a day, a morning, or an evening, and may be limited in other ways, such as a specific channel, a group of channels, or a genre. In some implementations, a user may specify selection criteria and receive a personalized video summary based on those selection criteria.

In some implementations, a video summary is created by constructing (<NUM>) respective snippets for a plurality of respective broadcast video programs. Each respective snippet is based on (<NUM>) correlating a respective plurality of the search query spikes to the respective video program, as illustrated above with respect to <FIG>. The plurality of broadcast video programs were all broadcast (<NUM>) during a predefined span of time. The process <NUM> then stitches together (<NUM>) the snippets for the plurality of broadcast programs to form a single video summary for the predefined span of time (the summary may be limited by other criteria as well, as noted above).

The terminology used in the description of the invention herein is for the purpose of describing particular implementations only and is not intended to be limiting of the invention. As used in the description of the invention and the appended claims, the singular forms "a", "an" and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term "and/or" as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items.

Claim 1:
A method of building a video program extract (<NUM>), comprising:
at a server system with one or more processors and memory storing programs configured for execution by the one or more processors:
identifying one or more search query groups (<NUM>), wherein each search query group includes one or more search queries, submitted by a plurality of users within a predefined span of time, that were identified as equivalent;
identifying (<NUM>) a plurality of search query spikes (<NUM>) from the one or more search query groups, wherein each search query spike corresponds (<NUM>) to a respective search query group, and wherein a frequency for submitting queries from the respective search query group during a corresponding spike period exceeds a frequency (<NUM>) for submitting queries from the respective search query group during an average span of time by a predefined threshold amount;
correlating (<NUM>) a subset of the search query spikes to a video program broadcast during the predefined span of time, wherein each correlated search query spike corresponds to a respective location (<NUM>) in the video program, the subset comprising a plurality of correlated search query spikes;
identifying, for each respective location in the video program, a video scene boundary before and after the location;
constructing (<NUM>) a snippet of the video program by stitching together a plurality of portions of the video program that contain the locations corresponding to the plurality of correlated search query spikes, wherein the portions extend to the identified video scene boundaries; and
generating, for each video portion in the snippet and based on the respective location, a link to the video portion in the broadcast video program.