HK1217794B - Systems and methods for addressing a media database using distance associative hashing - Google Patents

Description

System and method for addressing a media database using distance-associative hashing

Priority claim

This application constitutes a continuation-in-part of U.S. Patent Application No. 12/788,721, filed May 27, 2010, and issued as U.S. Patent No. 8,595,781 on November 6, 2013, entitled “METHODS FOR IDENTIFYING VIDEO SEGMENTS AND DISPLAYING CONTEXTUAL TARGETED CONTENT ON A CONNECTED TELEVISION,” which application is a non-provisional application claiming the benefit of U.S. Provisional Patent Application No. 61/182,334, filed May 29, 2009, entitled “SYSTEM FOR PROCESSING CONTENT INFORMATION IN A TELEVIDEO SIGNAL,” and filed December 29, 2009, entitled “CONTEXTUAL TRARGETING BASED ON DATA RECEIVED FROM This application is a non-provisional application that is a continuation-in-part of U.S. Patent Application No. 61/290,714, entitled “CONTEXTUALLY TARGETED CONTENT ON A CONNECTED TELEVISION SYSTEM” filed on May 27, 2010; this application is a continuation-in-part of U.S. Patent Application No. 14/089,003, entitled “__”, filed on November 25, 2013; this application is a continuation-in-part of U.S. Patent Application No. 61/290,714, entitled “CONTEXTUALLY TARGETED CONTENT ON A CONNECTED TELEVISION SYSTEM” filed on March 17, 2014; and this application is a continuation-in-part of U.S. Patent Application No. 14/089,003, entitled “__”, filed on November 25, 2013; and this application is a continuation-in-part of U.S. Patent Application No. 14/089,003, entitled “__”, filed on March 17, 2014 RELEVANTCONTENT (System and method for identifying video clips for displaying contextually relevant content)"; this application further constitutes a continuation-in-part of U.S. patent application No. **/***,***, filed on March 17, 2014, entitled "System and method for real-time television ad detection using an automated content recognition database"; this application further constitutes a continuation-in-part of U.S. patent application No. **/***,***, filed on March 17, 2014, entitled "System and method for real-time television advertisement detection using an automated content recognition database"; this application further constitutes a continuation-in-part of U.S. patent application No. **/***,***, filed on March 17, 2014, entitled "System and method for on-screen graphics detection"; this application further constitutes a continuation-in-part of U.S. patent application No. **/***,***, filed on March 17, 2014, entitled "System and method for on-screen graphics detection"; this application further constitutes a continuation-in-part of U.S. patent application No. **/***,***, filed on March 17, 2014, entitled "Systems and methods for improving server and client performance in real-time television advertisement detection" and Methods for Identifying Video Segments Displayed on Remotely Located Televisions. The foregoing applications are either currently co-pending or are applications that claim the benefit of the filing date of currently co-pending applications.

Field of the Invention

The present invention generally relates to matching unknown media data (eg, video or audio clips) with massive databases of reference media files.

background

Systems for automatic content recognition (ACR) of audio or video media are well known to those skilled in the art. However, such ACR systems present many technical challenges, including managing potentially very large databases of encoded audio or video information and managing the large indexes required to address the information in the databases.

It is also well known to those skilled in the art that large database indexes (such as those used in the present invention) can be generated using certain hash functions. Another method of addressing a database can be through the use of a binary tree structure also known as a b-tree. Both methods are commonly used in data management systems.

Regardless of the method used to index a large database, the index is often too large to reside in its entirety in the main memory of a computer server, such as that used in a typical ACR system. When the database cannot be fully stored in the computer system's memory, it is typically stored on disk storage, and portions of the database are then read into memory in blocks corresponding to the index values that provide the addresses. This method of recalling partial database information is also known to those skilled in the art as "paging," a process common to many different computer software systems.

The present invention is an extension of the invention referenced above and is a system and method for matching unknown digital media (such as television programs) with a database of known media using signal processing means that employ a modified path tracing algorithm (as described in the first invention).

Another novel aspect of the systems and methods disclosed herein is a distance-associative hash indexing means that can be subdivided into a plurality of independently addressable segments, wherein each of the segments can address a portion of a database, and each of the segments can reside in its entirety in the main memory of a server device. The resulting server cluster of indexing means each hosts a sector of an index that addresses associated data of a larger database of searchable audio or video information. This indexing means of the present invention results in a significant improvement in the speed and accuracy of ACR systems that are enabled to identify unknown media even when a television monitor is showing content while a user is changing channels, rewinding, fast forwarding, or even pausing video from a digital video recorder.

Overview

In some embodiments, an exemplary method involving using distance-associative hashing to address a media database may include receiving one or more indications of a sample of a video fragment; determining, for at least one fragment of the sample of the video fragment including at least one or more pixels of at least one fragment, an algorithmically derived value for the one or more pixels of each fragment; subtracting a midpoint value established for each fragment from an average value for each fragment; transforming the values resulting from the subtraction using a pre-derived function to evenly distribute the values; constructing a hash value based on the transformed values; referencing multiple most significant bits of the constructed hash value to determine a database sector; and storing at least the hash value on the determined database sector.

In some embodiments, one or more processing devices are used to at least partially implement at least one of the receiving, determining, subtracting, transforming, constructing, referencing, or storing of the aforementioned exemplary method. In some embodiments of the aforementioned exemplary method, receiving one or more indications of samples of the video segment may include receiving one or more indications of at least one of a frame or a still image. In some embodiments of the aforementioned exemplary method, receiving one or more indications of samples of the video segment may include receiving one or more indications of samples of the video segment, the one or more indications of samples of the video segment being associated with at least one indication of a channel, at least one indication of the video segment, and at least one indication of a time code offset from a start of the video segment.

In some embodiments of the aforementioned exemplary methods, determining, for the at least one slice of the sample of the video segment including the at least one or more pixels of the at least one slice, the algorithmically derived value for the one or more pixels of each slice comprises determining, for the at least one slice of the sample of the video segment including the at least one or more pixels of the at least one slice, an average value for the one or more pixels of each slice. In some embodiments of the aforementioned exemplary methods, subtracting a midpoint value established for each slice from the average value for each slice may comprise subtracting a midpoint value established for each slice from the average value for each slice, the midpoint value established for each slice having been previously determined for a plurality of channels over at least one time period using data from each slice.

In some embodiments of the aforementioned exemplary method, transforming the values resulting from the subtraction using a pre-derived function to evenly distribute the values may include forming a variable matrix including at least the values resulting from the subtraction; obtaining a static matrix that, when intersected with the variable matrix, more evenly distributes the transformed values; and computing a dot product of the variable matrix with the static matrix, the dot product including at least the more evenly distributed transformed values. In some embodiments of the aforementioned exemplary method, obtaining the static matrix that, when intersected with the variable matrix, more evenly distributes the transformed values may include using position-sensitive hashing to determine the static matrix that, when intersected with the variable matrix, more evenly distributes the transformed values of the variable matrix based at least in part on one or more previously obtained hash values.

In some embodiments of the aforementioned exemplary method, constructing a hash value from the transformed values may include constructing a hash value from the transformed values including reducing the fidelity of the transformed values by at least reducing each transformed value to a binary representation. In some embodiments of the aforementioned exemplary method, reducing the fidelity of the transformed values by reducing each transformed value to a binary representation may include determining, for each transformed value, whether the transformed value is a positive number, and assigning one to the hash value if the transformed value is positive, and otherwise assigning zero to the hash value.

In some embodiments of the aforementioned exemplary method, referencing the constructed plurality of most significant bits of the hash value to determine the database sector may include referencing the constructed plurality of most significant bits of the hash value to determine a database server, wherein the plurality of most significant bits are predetermined to address a plurality of database servers, wherein the plurality of database servers associated with the plurality of most significant bits are established such that at least one index associated with the database sector can reside entirely in memory of the corresponding database server. In some embodiments of the aforementioned exemplary method, storing at least the hash value on the determined database sector may include storing at least the hash value on the determined database sector, including storing at least one indication of a channel, at least one indication of a video segment, and at least one indication of a time code offset from a start of the video segment at a database location based at least in part on the hash value.

In one or more alternative embodiments of the aforementioned exemplary methods, a plurality of related systems include, but are not limited to, circuitry and/or programming for implementing the method embodiments referenced herein; depending on the design choices of the system designer, such circuitry and/or programming may actually be any combination of hardware, software, and/or firmware configured to implement aspects of the methods referenced herein.

In various embodiments, an exemplary method involving addressing a media database using distance-associative hashing may include receiving a hint constructed by one or more operations associated with media storage operations; referencing a plurality of most significant bits of the received hint to determine a database sector; and returning at least one indication of at least one candidate from the database sector based at least in part on the received hint.

In some embodiments of the foregoing exemplary method, receiving a hint (the hint constructed by one or more operations associated with media storage operations) may include receiving a hint associated with a sample of a video buffer of a client system, including at least receiving one or more indications related to a time instant associated with the sample of the video buffer of the client system. In some embodiments of the foregoing exemplary method, receiving a hint (the hint constructed by one or more operations associated with media storage operations) may include receiving a hint associated with a sample of a video buffer of a client system, the hint being determined at least in part by hashing at least some values associated with the video buffer.

In some embodiments of the foregoing exemplary method, receiving a hint associated with a sample of a video buffer of the client system, the hint determined at least in part by hashing at least some values associated with the video buffer, may include receiving a hint associated with a sample of a video buffer of the client system, the hint determined at least in part by hashing at least some values associated with the video buffer, the hash based at least in part on one or more of at least one operand or at least one algorithm also used in an associated media storage operation. In some embodiments of the aforementioned exemplary method, receiving a hint (the hint being constructed by one or more operations associated with a media storage operation) may include receiving a hint determined by one or more operations comprising at least the following: receiving one or more indications of at least one content of a video buffer of a client system; determining, for at least one slice of the at least one content of the video buffer comprising at least one pixel of at least one slice, an algorithmically derived value for the one or more pixels of the at least one slice; subtracting a midpoint value from an average value for each slice; transforming the values resulting from the subtraction; constructing a hash value based on the transformed values; and associating the hint at least in part with the constructed hash value, wherein at least one of the determining operation, the subtracting operation, the transforming operation, or the constructing operation utilizes one or more of at least one operand or at least one algorithm that is also used in the associated media storage operation.

In some embodiments of the aforementioned exemplary methods, returning at least one indication of at least one candidate from the database sector based at least in part on the received hint may include returning at least one indication of at least one candidate from the database sector based at least in part on a Probability Point Location in an Equal Sphere ("PPLEB") algorithm as a function of the received hint. In some embodiments of the aforementioned exemplary methods, returning at least one indication of at least one candidate from the database sector based at least in part on the received hint may include returning at least one indication of at least one candidate from the database sector that is within a predetermined inverse percent distribution radius of the received hint based at least in part on the received hint.

In one or more alternative embodiments of the aforementioned exemplary methods, a plurality of related systems include, but are not limited to, circuitry and/or programming for implementing the method embodiments referenced herein; depending on the design choices of the system designer, such circuitry and/or programming may actually be any combination of hardware, software, and/or firmware configured to implement aspects of the methods referenced herein.

In various embodiments, an exemplary method involving addressing a media database using distance-associative hashing may include receiving at least one indication of at least one candidate and at least one indication of at least one prompt; adding tokens to a bin associated with at least one received candidate; and determining whether the number of tokens within the bin exceeds a value associated with a probability that the client system is displaying a specific video clip associated with the at least one prompt, and if the number of tokens within the bin exceeds the value associated with the probability that the client system is displaying the specific video clip associated with the at least one prompt, returning at least some data associated with the specific video clip based at least in part on the bin.

In some embodiments of the aforementioned exemplary method, adding the token to a bin associated with at least one received candidate may include adding the token to a time bin associated with the at least one received candidate. In some embodiments of the aforementioned exemplary method, adding the token to a bin associated with the at least one received candidate may include determining a relative time, including subtracting a candidate time associated with the at least one candidate from an arbitrary time associated with the at least one prompt; and adding the token to the time bin associated with the candidate based at least in part on the determined relative time. In some embodiments of the aforementioned exemplary method, the method may include removing one or more tokens from a time bin based at least in part on an elapsed time period.

In one or more alternative embodiments of the aforementioned exemplary methods, a plurality of related systems include, but are not limited to, circuitry and/or programming for implementing the method embodiments referenced herein; depending on the design choices of the system designer, such circuitry and/or programming may actually be any combination of hardware, software, and/or firmware configured to implement aspects of the methods referenced herein.

In various embodiments, an exemplary system involving addressing a media database using distance-associative hashing may include, but is not limited to: one or more computing devices; and one or more instructions that, when executed on at least some of the one or more computing devices, cause at least some of the one or more computing devices to at least perform the following operations: receive at least one rasterized video stream; create at least one hash value associated with at least one sample of at least one received rasterized video stream; determine at least one database sector for storing the at least one created hash value; and store the at least one created hash value on the at least one determined database sector.

In various embodiments, an exemplary system involving addressing a media database using distance-associative hashing may include, but is not limited to: one or more computing devices; and one or more instructions that, when executed on at least some of the one or more computing devices, cause at least some of the one or more computing devices to at least perform the following operations: receive one or more instructions associated with at least one video buffer of at least one client system; determine a hint based at least in part on the at least one video buffer and at least one time associated with the at least one video buffer, wherein one or more of at least one operand or at least one function associated with determining the hint is also used in an associated media storage operation; reference multiple most significant bits of the determined hint to determine a database sector; and return at least one indication of at least one candidate from the determined database sector based at least in part on the determined hint.

In various embodiments, an exemplary system involving addressing a media database using distance-associative hashing may include, but is not limited to, one or more computing devices; and one or more instructions that, when executed on at least some of the one or more computing devices, cause at least some of the one or more computing devices to at least perform the following operations: receive at least one indication of at least one candidate and at least one indication of at least one prompt; add tokens to a box associated with at least one received candidate; and determine whether the number of tokens within the box exceeds a value associated with a probability that the client system is receiving a specific video clip associated with at least one received prompt, and if the number of tokens within the box exceeds a value associated with the probability that the client system is receiving a specific video clip associated with at least one received prompt, return at least some data associated with the specific video clip based at least in part on the box.

In addition to the foregoing, various other method, system, and/or program product embodiments are set forth and described in the text of this disclosure (eg, claims, drawings, and/or detailed description) and/or as taught in the accompanying drawings.

The foregoing is a summary and therefore (necessarily) contains simplifications, generalizations, and omissions of detail; therefore, those skilled in the art will appreciate that the summary is illustrative only and is not intended to be limiting in any way. Other aspects, embodiments, features, and advantages of the devices and/or processes and/or other subject matter described herein will become apparent from the teachings set forth herein.

BRIEF DESCRIPTION OF THE DRAWINGS

Certain embodiments of the present invention are described in more detail below with reference to the following drawings.

FIG1 illustrates the construction of a sectorized video matching database, as taught by the present invention, beginning with an initial video ingestion or capture process that is subsequently continuously updated. A television display system 101 and its corresponding television display memory buffer 103 are shown as potential embodiments of the system. The allocation of pixel tiles 102 and the calculation of values 105 using some algorithmic approach known to those skilled in the art are performed for each pixel tile, and the resulting data structure is created and then timestamped to produce a "hint" 106, which may also have additional metadata associated with it.

FIG. 2 illustrates the use of a distance-associative hashing process to process hint data 201 and generate a hash index 202 , and further illustrates a sectorized addressing scheme 203 to store data in related groups (buckets) 206 .

Figure 3: shows real-time capture of unknown television content for identification from a connected television monitor or the like 301. A pixel tile is typically defined as a square pixel region of a video buffer 303 having dimensions of approximately ten pixels by ten rows of pixels 304, however, any reasonable shape and size may be used. The number of pixel tile locations may be anywhere between ten and fifty locations within the video buffer and are processed 305 for sending hint data 306 to a central server device.

FIG. 4 illustrates extracting a plurality of candidate cue values 401 from a reference (matching) database bucket 404 and applying the cue values 403 to a path tracing content matching process 402 as taught in the first invention referenced above.

Figure 5 shows a data structure of bins that hold tokens used to score candidate values from the matching database. As the search proceeds through time, the bins are "leaky" and tokens expire over time.

FIG6 shows a typical memory paging scheme for accessing a large database as taught in the prior art.

FIG7 illustrates the creation of a hash value which involves several steps starting with computing the median value for each of a large number of points that make up the samples from the video frame.

Figure 8 shows how the hash value is calculated.

FIG. 9 illustrates the beneficial results of using the median of pixel positions as part of the process of calculating a hash value.

Figure 9a illustrates the problem of not using the median when partitioning a multidimensional dataset.

Figure 9b demonstrates the benefit of finding the median of a dataset.

FIG10 illustrates an operational flow representing several example operations for addressing a media database using distance-associative hashing.

FIG11 shows an alternative embodiment of the operational flow of FIG10 .

FIG12 shows an alternative embodiment of the operational flow of FIG10.

FIG13 shows an alternative embodiment of the operational flow of FIG10.

FIG14 shows an alternative embodiment of the operational flow of FIG10.

FIG. 15 shows an alternative embodiment of the operational flow of FIG. 10 .

FIG16 shows an alternative embodiment of the operational flow of FIG10.

FIG17 shows an alternative embodiment of the operational flow of FIG10.

FIG18 shows an alternative embodiment of the operational flow of FIG10.

FIG19 shows an alternative embodiment of the operational flow of FIG10.

FIG. 20 illustrates various operational flows representing several example operations for addressing a media database using distance-associative hashing.

FIG. 21 illustrates an alternative embodiment of the operational flow of FIG. 20 .

FIG. 22 illustrates an alternative embodiment of the operational flow of FIG. 20 .

FIG. 23 illustrates an alternative embodiment of the operational flow of FIG. 20 .

24 illustrates another operational flow representing several example operations for addressing a media database using distance-associative hashing.

FIG. 25 illustrates an alternative embodiment of the operational flow of FIG. 24 .

FIG26 shows an alternative embodiment of the operational flow of FIG24.

FIG. 27 illustrates a system for addressing a media database using distance-associative hashing.

FIG. 28 illustrates another system for addressing a media database using distance-associative hashing.

FIG. 29 illustrates yet another system for addressing a media database using distance-associative hashing.

Detailed description

As described in the aforementioned disclosure, the first invention related to the present invention is a system and method for matching an unknown video with a database of known videos using novel signal processing techniques, such as a modified path tracing algorithm, among other techniques.

The novel approach of the new invention is its distance-associated hashing, which, along with providing database access using sectorized indices, provides a computationally efficient means for matching unknown media segments with a reference database of known media (e.g., audio or video content).

This indexing approach of the present invention results in significant improvements in the speed and accuracy of ACR systems, which are enabled to track the identity of media even when a television monitor is showing content while a user is changing channels, rewinding, fast forwarding, or even pausing video from a digital video recorder.

A system will be described for both the creation and updating of a media matching database, as well as subsequent access, that generates and addresses a sectorized database so that each of these database sectors can reside in the main memory of a corresponding plurality of server devices without resorting to paging within each of the corresponding server devices. This common approach to addressing the sectorized database through locality-sensitive hashing provides significant improvements in operational efficiency.

The construction of the sectorized video matching database begins with the process shown in FIG1 . The television system 101 decodes the television signal and places the contents of each video frame into a video frame buffer in preparation for display or further processing of the pixel information of the video frame. The television system can be any television decoding system that can decode a television signal, either from baseband or from a modulated television source, and fill the video frame buffer with decoded RGB values corresponding to the frame size specified by the video signal. Such systems are well known to those skilled in the art.

The system of the present invention first establishes a reference database of television program fingerprints described as prompts or prompt values in the original application and then continuously updates it. For the purpose of establishing the reference database of video prompts, the present invention collects one or more video slices 102 read from the video frame buffer 103. The video slices can be of any shape or pattern, but for the purpose of this example, they should be 10 pixels in the horizontal direction multiplied by 10 pixels in the vertical direction. Also for the purpose of this example, it is assumed that there are 25 pixel slice positions evenly distributed within the boundaries of the buffer in the video frame buffer, although they are not necessarily evenly distributed. Each pixel should be composed of a red value, a green value and a blue value 104, which are usually represented by an eight-bit binary value for each color, totaling 24 bits or three bytes per slice position.

This composite data structure is populated with the average pixel values of a plurality of pixel slice locations from the video buffer. A pixel slice is defined as a generally square pixel region of the video buffer having a size of approximately ten pixels by ten rows of pixels 304. The number of pixel slice locations may typically be between ten and fifty locations within the video buffer.

These average pixel values 305 are combined with a time code 306 that references a "time of day" from the television system's processor device. The time of day is defined as the time in fractions of a second that have elapsed since midnight on January 1, 1970, which is a well-established convention in computing systems, particularly Unix (or Linux) based systems.

Additionally, as taught in the original patent application, metadata may be included and defined with data structure 106, referred to as tag fingerprints, "cues," or "points." Such metadata attributes may be derived from closed caption data from the currently displayed video program, or they may be keywords extracted by a speech recognition system operating within a processor device of the television system that converts video from the corresponding television program into textual information. The textual information may then be retrieved for relevant keywords or sent in its entirety as part of the cue data structure to a central server device for further processing.

Those hint records 201 are passed to a hash function 202 in Figure 2, which uses a position-sensitive hashing algorithm based on the Probabilistic Point Location in Equal Sphere ("PPLEB") algorithm to generate a hash value 203. This hash value is calculated based on the average pixel value from the hint record (fingerprint) 207, and the process associates 206 data with similar values into groups called buckets.

The ten by ten pixel patch 302 shown in this particular example would have one hundred pixels and mathematically averaged separately for red, green and blue values to produce an average pixel value 305. Alternatively, any averaging function could be used instead of a simple average.

A plurality of such pixel slices are extracted from the video frame. For example, if 25 such pixel slices are extracted from the video frame, the result will be a point representing a position in a 75-dimensional space. The skilled person will appreciate that such a large search space will require a significant amount of computing resources to locate (even approximately) the value in conjunction with the other 74 values representing a video frame.

Advantages of the distance-associative hashing system and method described herein are reduced computational load and increased accuracy in matching an unknown video frame to a database of known video frames.

Creating a hash value involves several steps, which begin with calculating the algorithmically derived value for each point, as shown in 701 to 775 in Figure 7. A useful means of algorithmically deriving the median value has been found by summing each point of each frame of each program stream or video channel maintained by a matching database over a period of approximately 24 hours. The median value of each point is found from this summing process. The next step in deriving the final hash value is to subtract the average value from the point value of each corresponding point, where row 801 minus row 802 equals row 803. The result is a positive or negative value to which the pre-derived hash function is applied. Typically, the result of the point value minus the average value of the corresponding point is arranged in a matrix, and a similar matrix that constitutes the pre-derived hash value (or hash key) is used to calculate the dot product of the matrix. Then, the result of the dot product of the two matrices is further transformed to one or zero based on the sign of the product matrix elements. Typically, a technician will set a positive value to one and a negative value to zero.

The resulting hash value points to values that are more or less evenly distributed across the data storage area. The hash value 203 can be further divided ( FIG. 2 ) such that the 'n' most significant bits 205 address one of the 2 ⁿ (2^n) sectors of the database. The remaining bits 206 address individual 'buckets' of the addressed sector of the database, as will be described in more detail below.

The partition points of the hash values defining the address spaces of the various sectors are calculated so that the index of the data of a database sector fits within the memory boundaries of those processor systems of the memory sector. Otherwise, the database will be subject to paging which will reduce the effectiveness of this process.

Comparing the systems and methods taught by the present invention with those known to those skilled in the relevant art, FIG6 illustrates a typical paging approach. In FIG6 , assume that the example system is attempting to match unknown data with a server of known data. An index 602 is used to address only a portion of the data 605 that can fit in the main memory of the CPU 606. This data is searched, and if the result is negative, another data fragment is fetched into main memory 603 and the search continues.

This access method using paging is common but significantly reduces the efficiency of the computer system. In practice, this approach cannot be used with ACR systems that search large media databases because the read/write speed of the hard drive is not fast enough to keep up with the task. Many different algorithmic approaches have been developed over the years to solve this problem of splitting the search into multiple smaller parts and distributing the smaller searches to multiple computer server systems.

A well-known example is probably the rather large Google search engine. Those skilled in the art will recognize that this system is one of the largest computer systems ever built. The speed and accuracy of the Google search process are remarkable. However, the Google search approach is significantly different and is completely unsuitable for matching unknown media with a database of known media, even if the two databases are of the same very large size. This is because the Google search approach employs a map-reduce algorithm, which is designed for searching large databases of essentially unrelated data. While more advanced than paging systems, map-reduce is a computationally intensive process that also requires considerable data communication bandwidth between the participating computer systems. In contrast, the present invention is efficient in its use of processing and communication resources.

In the present invention, a distance-associative hash function provides a means for addressing a database by sector, allowing the data for the addressing means to fit within the main memory of individual server devices in a server group. Grouping is accomplished by grouping distance-related data in a multidimensional array into the same sector using a distance-associative hashing step as a means for achieving the grouping. The sector identifier used to address the data element is calculated from a hash index, which is generated from the process by extracting a subset of the total bits of the hash function and using the subset to address the desired sector in which to store the data in the reference database.

In this way, the hash index subset is the address of the sector (called a bucket in the first invention) containing the distance associated with multiple hash values. The remaining portion of the hash address is then used to address the bucket of the sector for storing new data. Alternatively, the sector address can be found by hashing the first hash value again.

This system and method of database addressing through multiple hash indexing steps results in an efficient database access scheme that has significant performance benefits and increased efficiency over the traditional database access methods described above.

Distance-associative hashing provides a means of quickly addressing very complex (multi-dimensional) databases by finding data that is not an exact match but is within a predetermined radius (distance-associative) of the value being sought. Importantly, sometimes this means of addressing will result in no matches at all. Where commercially oriented databases cannot tolerate inaccuracies, the media matching system can easily tolerate lost matches and will simply continue the matching process once the next data received and taught in the first patent arrives. Of course, data from unknown sources to be determined by the ACR system arrives periodically, but can be commanded by the system of the present invention to arrive at different intervals based on requirements for accuracy or by requirements imposed by the state of the system (e.g., when the system may be approaching overload), and these sending clients are then commanded to send a lower sampling rate. For example, a typical data reception rate might be an interval of 1/10 of a second.

For a reference media database, a set of pixel values is derived from each video frame from each video source to be part of the reference database. The broadcast time of the video program is then attached to the set of pixel values, along with certain metadata, which is information about the program, such as a content identifier (ID), program title, actor names, airtime, a brief synopsis, etc. The metadata is typically obtained from a commercial electronic program guide source.

The array of processed pixel values with the time code plus metadata added is then stored in a reference database, and the address of the stored data is then added to the hash index at the corresponding hash value and sector ID value. In addition, a second database index is established and maintained by using the content ID from the metadata as another means for addressing the reference database.

The process of building and continually updating the database is continuous, and the number of days of data maintained by the database is based on the needs of the user but may range from one day to one month, for example.

The process of identifying unknown video segments from data received from a large number of client devices begins with a procedure similar to the procedure used above to establish a reference database. In Figure 3, this procedure involves a television monitor 301, such as a popular flat-screen HDTV of the type commonly referred to as a smart TV, wherein the TV includes a processing device with memory capable of executing applications similar to the type found on today's popular smartphones. The system of the present invention samples a region 302 of the video frame buffer 301 in a generally large number of locations. The samples have the same size, shape, and position as the pixel slices used in the process of establishing the reference database. Each of these collected pixel slices is then processed algorithmically to produce calculated values for the red value, green value, and blue value of each slice in a manner identical to the method used to create the reference database.

The system of the present invention then calculates a distance-associative hash index of the collected averages, identical to the content ingestion function described above. Also identical to the ingestion system described above, the resulting sector identification (ID) value is extracted as a subset of the total bits of the hash index. The remainder of the hash index is used to address the desired sector, searching it for all candidate (potential) matches belonging to the same bucket as the unknown data point.

Optionally, if a good guess for a match (a successful match) is obtained from the above process, the system of the present invention will also use the content ID index to collect candidates from the database for the sectors created during the ingestion process as described above, belonging to potential content IDs, to address multiple reference hints within a time radius r' around the timestamp (of the successfully matched candidate). Next, as taught in the first patent, duplicate candidates and candidates that are too far away (radius r) from the unknown point are removed.

In order to test the matching of an unknown video clip against a reference database of known video data, assume a list of candidates from the previous step, where each candidate (i.e., each possible match) has associated with it the following data items: content ID, media time, inverse percent distribution radius calculated as the distance from the current unknown point (to the unknown video stream), where 100% represents the exact value of the unknown point and 0% is a value outside the radius r (distribution) from the unknown point.

In the memory of the matching system of the present invention, a data structure 502 is allocated for each matching candidate 501. This data structure consists of, among other things, arbitrary time bins grouped by some arbitrary amount (e.g., approximately one second). For the purposes of this example, assume that the data structure consists of one hundred bins representing ten-second video cue points. These bins are typically not equally spaced in time.

For each candidate found in the reference (matching) database: First, the relative time is calculated by subtracting the candidate time from the arbitrary time of the unknown video. The candidate time is the play time of each video cue associated with the candidate during the reference program broadcast.

The arbitrary time of the unknown video is generated from the television monitor by an application of the present invention running in the television's memory or in a set-top box attached to the television. The application sends this time along with the sampled video cue points to the central server device of the present invention. Time is well known to those skilled in the art and commonly used in computer systems. It is expressed as the current number of time units since January 1, 1970.

For example, if the time difference between any time from the TV (in the home) and the real media time is 100 seconds, then the relative time of those candidates that are actually a match should be close to that value. Likewise, candidates that are not good matches are unlikely to have relative times close to 100 seconds in this example.

In the candidate data structure, when a cue point of the unknown video matches a reference cue point, the system of the present invention adds a token to the corresponding box of the candidate data structure. The system then repeats the process for the next candidate as described in the previous paragraph.

Another and important step for scoring the results is to apply a time discount to all bins. This is a relatively simple process that decrements the values in all bins by a small amount for each time period. The skilled person will recognize that this is a "leaky bucket" scoring method. By definition, over multiple cycles of the process, bins that are no longer filled by matching cue points will eventually be decremented to zero. Similarly, bins that are slowly being filled by random noise in the system will also be decremented. Therefore, the time discount eventually clears the bins that are filled by false positive matches and random noise. The skilled person will also clearly see that without the time discount binning, all bins will eventually fill to capacity and no results can be obtained from the process.

The time discount will also decrement to zero any bin (such as 503) that is above a level matching threshold 504 when the video stream from the client television monitor is changed in any way by any of the following: changing the channel, rewinding, fast forwarding, pausing the video, etc.

The content is declared a match if any bin of the candidate data structure, such as bin 503, is above a certain threshold 504. Further means of qualifying a match might include testing for consecutive matches of candidate segments for greater than a certain number of seconds (e.g., three seconds).

FIG8 illustrates how hash values are calculated. First, the median value for each pixel position contributing to the video fingerprint is found by summing the values at that position over many days of collected values from multiple television channels representing typical television programs to be identified by the present invention. Once the median value is determined, it can be used as a constant indefinitely without the need for further calculations or adjustments. The pixel value sent from the client to the server matching system is first processed by subtracting the median value of that pixel position. The resulting result is stored in a matrix along with the other pixel positions of the video frame, and an appropriate hash function is applied to the matrix. Multiple hash values are then derived from the resulting dot products.

FIG9 illustrates the beneficial results of using the median of pixel positions as part of the process of calculating hash values. Graph 901 shows the resulting curve of the output of a typical, unoptimized hash function, which has a relatively small number of hash values occupying a relatively narrow range on the left side of the curve. The resulting median 902 is relatively low. Graph 903 illustrates the beneficial redistribution of hash values resulting from calculating the median for each pixel position participating in the matching process and applying the median as part of the hash function. The distribution of hash values is more spread out, accompanied by an increase in the median of all hash keys 904.

9 a shows what happens to the data set when no median is found before the data set is partitioned. If the system samples sixteen pixel positions of each video frame and if each pixel position has a red pixel value, a green pixel value, and a blue pixel value, there will be 64 dimensions (or axes) to the figure. For the purpose of illustration, in this example, the data set only includes two sample points 906 and 908 of a single video frame. Further, this example assumes that only a single brightness value is obtained at each pixel point. By dividing the data set into a clockwise sector 907 c and a counterclockwise sector 907 cc on the diagonal direction 907 and the vertical axis 908 and the horizontal axis 906 intersecting at the zero value 905, there are only two sectors 910 and 911 of the eight sectors between the two pixel positions.

FIG9 b illustrates the benefit of finding the median value for each pixel position. This example continues with the assumption that the pixel values are single brightness values ranging from zero to 255, although the absolute values are not important to the method. This example illustrates the simplifying assumption that the median value is 128 for both pixel positions. Now, by shifting the partition point to 905′, the vertical and horizontal axes are shifted to 908′ and 906′, respectively. The diagonal slice 909 is shifted to 909′. It is clear from the diagram that all eight sectors now contain data.

When partitioning a data set in this way, the calculated median value is neither necessarily nor required to be in the middle of the data set. The desired result is to disperse the data so that when the data is partitioned and assigned to each server, the system accesses the servers more uniformly. On the contrary, if the unoptimized data of Figure 9 is partitioned between eight servers as shown, only two of the eight accessed servers will be seen. In the method shown in Figure 9b, by those color values at each pixel position and by the example of 16 pixel positions, the actual calculation results in the application of 48 medians calculated as a 48-dimensional graph. Further, as needed, more than one data splicing can be performed around each middle point of the 48-dimensional graph, so that the data set generated by the slice can be assembled within the operational constraints of the system's separate computer servers. In any case, data will be found most of the time on the clockwise and counterclockwise sides of each partition slice.

FIG10 illustrates an operational flow 1000 representing several example operations for addressing a media database using distance-associative hashing. In FIG10 and in the following figures, which include various examples of operational flows, discussion and illustration are provided with respect to the aforementioned examples of FIG1 through FIG9 and/or with respect to other examples and contexts. However, it should be understood that these operational flows can be performed in many other environments and contexts and/or in modified versions of FIG1 through FIG9. Furthermore, while the various operational flows are presented in the illustrated sequence, it should be understood that the various operations can be performed in an order other than that illustrated, or can be performed simultaneously.

After a start operation, operational flow 1000 moves to operation 1002. Operation 1002 depicts receiving one or more indications of samples of a video segment. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9, these indications may be associated with one or more pixel slices from an ingest system.

Then, operation 1004 depicts determining, for the at least one tile of the sample of the video segment including at least one or more pixels of the at least one tile, an algorithmically derived value for the one or more pixels of each tile. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , an average value of the red pixels in each tile, the green pixels in each tile, and the blue pixels in each tile may be calculated.

Operation 1006 then depicts subtracting the midpoint value established for each slice from the mean for each slice. For example, as shown in and/or described with respect to Figures 1-9, the median value for each pixel location contributing to the video fingerprint can be found by summing those values for that location over a number of days of collected values from multiple television channels at that location.

Then, operation 1008 has described using the function that is derived in advance to transform these values that produce due to this subtraction to distribute these values evenly.For example, as shown in Figure 1 to Figure 9 and/or about it, these values that are produced by subtraction fill a matrix.Can calculate the dot product of that matrix and the static matrix that is derived in advance.This static matrix that is derived in advance can be determined before operational flow 1000 is instantiated and can be optimized in an algorithmic manner based on the data that was taken in in the past, thereby make multiple matrices that intersect with it will produce the result that is more evenly distributed than the result directly from the subtraction operation.

Then, operation 1010 depicts constructing a hash value from these transformed values. For example, as shown in and/or described with respect to Figures 1-9, the values capable of maintaining RGB values are reduced to bit form so that the hash value can be a bit string.

Operation 1012 then depicts referencing the most significant bits of the constructed hash value to determine a database sector. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , a plurality of bits may be predetermined such that the predetermined plurality of bits of the hash value are used to address one or more database sectors.

Operation 1014 then depicts storing at least the hash value on the determined database sector. For example, as shown in and/or described with respect to FIG. 1-9 , the hash value may be stored in a bucket that includes other mathematically close hash values, where the hash values are associated with at least a specific video segment and offset.

FIG11 illustrates an alternative embodiment of the example operational flow 1000 of FIG10. FIG11 illustrates an example embodiment in which the operational flow 1000 may include at least one additional operation. The additional operation may include operation 1102.

Operation 1002 illustrates using one or more processing devices to at least partially implement at least one of the receiving operation 1002, determining operation 1004, subtracting operation 1006, transforming operation 1008, constructing operation 1010, referencing operation 1012, or storing operation 1014. In some examples, one or more computer processors may be used to at least partially implement one of the aforementioned operations. Other processing devices may include application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), digital signal processors (DSPs), or any other circuitry configured to implement the results of at least one of the aforementioned operations.

FIG12 illustrates an alternative embodiment of the example operational flow 1000 of FIG10 . FIG12 illustrates an example embodiment in which operation 1002 may include at least one additional operation. The additional operation may include operation 1202 and/or operation 1204 .

Operation 1202 illustrates receiving one or more indications of at least one of a frame or a still image. For example, as shown in and/or described with respect to Figures 1 to 9, a sample of a video segment may comprise a single frame of a video stream. Such a frame may be a 30 fps video frame. In various embodiments, a sample of a video segment may be a still image or a portion of a video segment that may be imaged at a rate other than 30 times per second.

Further, operation 1204 illustrates receiving one or more indications of samples of the video segment, the one or more indications of the samples of the video segment being associated with at least one indication of a channel, at least one indication of the video segment, and at least one indication of a time code offset from the start of the video segment. For example, as shown in and/or described with respect to FIGURES 1-9, data associated with the video segment (which may be a program title and/or other metadata associated with the video segment), the channel from which the program was ingested, and the time offset from the start of the program may be received from, for example, a channel guide associated with a channel being monitored by the ingestion system.

FIG13 illustrates an alternative embodiment of the example operational flow 1000 of FIG10. FIG13 illustrates an example embodiment in which operation 1004 may include at least one additional operation 1302.

Operation 1302 illustrates determining, for each slice of the sample of the video segment including at least one or more pixels of the at least one slice, an average of the one or more pixels of the at least one slice. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , the algorithmic operation for reducing the one or more pixels in the slice to a single value may be, for example, an arithmetic average.

FIG14 illustrates an alternative embodiment of the example operational flow 1000 of FIG10. FIG14 illustrates an example embodiment in which operation 1006 may include at least one additional operation 1402.

Operation 1402 illustrates subtracting a midpoint value established for each shard from the mean value for each shard, the midpoint value established for each shard having been previously determined for a plurality of channels over at least one time period using data from each shard. For example, as shown in and/or described with respect to FIGURES 1-9, a median value may be determined, the median value being determined for each shard, wherein the median value is established for the shard at the same time of ingestion as in the operation of determining the segments on the client system, the median value being established as a constant value derived from monitoring the same shard across many channels over an extended period of time (a month, a year, etc.).

FIG15 illustrates an alternative embodiment of the example operational flow 1000 of FIG10. FIG15 illustrates an example embodiment in which operation 1008 may include at least one additional operation. The additional operation may include operation 1502, operation 1504, and/or operation 1506.

Operation 1502 illustrates forming a variable matrix including at least the values resulting from the subtraction. For example, as shown in and/or described with respect to FIGs. 1-9, values are arranged in a matrix, the values resulting from a subtraction operation that subtracts a median value established over time for each slice from an average value for the instantaneous frame being ingested.

Operation 1504 illustrates obtaining a static matrix that, when intersected with the variable matrix, will more evenly distribute the transformed values. For example, as shown in and/or described with respect to Figures 1 through 9, the matrix can be determined based on a mathematical analysis of a previously obtained data set of hash values. The matrix can be mathematically optimized so that, when used as an operand in a dot product operation with a continuous variable matrix, the corresponding continuous result matrix will include a plurality of values that are more evenly distributed along the distribution curve than the variable matrix prior to the dot product operation.

Operation 1506 illustrates calculating a dot product of the variable matrix with the static matrix, the dot product including at least the more evenly distributed transformed values. For example, as shown in and/or described with respect to Figures 1-9, the variable matrix including the multiple values resulting from the subtraction operation may be intersected with a static matrix that has been predetermined to more evenly distribute the data represented by the variable matrix, thereby causing the resulting matrix to be more spread out rather than clustered around a particular portion of the distribution.

Figure 16 illustrates an alternative embodiment of the example operational flow 1000 of Figure 10. Figure 16 illustrates an example embodiment in which operation 1504 may include at least one additional operation 1602.

Operation 1602 illustrates determining, using locality-sensitive hashing, a static matrix that, when intersected with a variable matrix, more evenly distributes the transformed values of the variable matrix based at least in part on one or more previously obtained hash values. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , locality-sensitive hashing techniques may be used to analyze previously captured video samples to produce matrices such that, when used as operands in a dot product operation with a successive variable matrix, the corresponding successive result matrices include values that are more evenly distributed along a distribution curve than the variable matrix prior to the dot product operation.

FIG17 illustrates an alternative embodiment of the example operational flow 1000 of FIG10 . FIG17 illustrates an example embodiment in which operation 1010 may include at least one additional operation. The additional operation may include operation 1702 and/or operation 1704 .

Operation 1702 illustrates constructing a hash value from the transformed values, including reducing the fidelity of the transformed values by at least reducing each transformed value to a binary representation. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , each value of the result matrix from the dot product operation may be reduced from, for example, an 8-bit value from 0 to 255 (or from -127 to 128) to a single bit, either one or zero.

Operation 1702 may include operation 1704. Operation 1704 illustrates determining, for each transformed value, whether the transformed value is a positive number, and if the transformed value is a positive number, assigning a one to the hash value, and otherwise assigning a zero to the hash value. For example, as shown in and/or described with respect to Figures 1 to 9, each value between 1 and 128 of the result matrix from the dot product operation may be reduced to a bit value of 1, and each value between -127 and 0 of the result matrix from the dot product operation may be reduced to a bit value of 0.

FIG18 illustrates an alternative embodiment of the example operational flow 1000 of FIG10. FIG18 illustrates an example embodiment in which operation 1012 may include at least one additional operation 1802.

Operation 1802 illustrates referencing a plurality of most significant bits of the constructed hash value to determine a database server, wherein the plurality of most significant bits are predetermined to address a plurality of database servers, wherein the plurality of database servers associated with the plurality of most significant bits are established such that at least one index associated with a database sector can reside entirely within the memory of the corresponding database servers. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , a plurality of most significant bits of 2 bits can be selected such that the 2 bits can provide four different values (00, 01, 10, and 11), each of which can be assigned to a different database sector. The plurality of most significant bits of the hash value can be established to provide a sufficient number of servers such that the content associated with the plurality of hash values can completely fit within the memory of a particular database sector, which can be a database server, a cluster partner, a virtual machine, and/or another type of database node. The number of bits does not necessarily but may exactly represent the maximum number of database sectors at any given time (i.e., where 6 bits may be selected to provide addressing of up to 64 database sectors, the system may operate with fewer servers (e.g., 60 sectors) or with a maximum of 64 sectors).

FIG19 illustrates an alternative embodiment of the example operational flow 1000 of FIG10. FIG19 illustrates an example embodiment in which operation 1014 may include at least one additional operation 1902.

Operation 1902 illustrates storing at least the hash value on the determined database sector, including storing at least one indication of a channel, at least one indication of a video clip, and at least one indication of a time code offset from the start of the video clip at a database location based at least in part on the hash value. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , data associated with the video clip (which may be a program title and/or other metadata associated with the video clip), the channel from which the program was ingested, and the time offset from the start of the program may be stored either with the hash value or in a location associated with and/or referenced by the hash value, which storage may be in the same or a different sector, server, or database as the hash value.

FIG20 illustrates an operational flow 2000 representing several example operations for addressing a media database using distance-associative hashing. In FIG20 and in the following figures, which include various examples of operational flows, discussion and illustration are provided with respect to the aforementioned examples of FIG1 through FIG9 and/or with respect to other examples and contexts. However, it should be understood that these operational flows can be performed in many other environments and contexts and/or in modified versions of FIG1 through FIG9. Furthermore, while the various operational flows are presented in the illustrated sequence, it should be understood that the various operations can be performed in an order other than the illustrated order or can be performed simultaneously.

After a start operation, operational flow 2000 moves to operation 2002. Operation 2002 depicts receiving a hint, constructed by one or more operations associated with a media storage operation. For example, as shown in and/or described with respect to Figures 1-9, at least some data associated with a sample of video data taken from a specific client system is received. This data may be associated with a slice corresponding to the same client system as defined by the ingestion operation. The data may be algorithmically processed using the same operations as the ingestion operation to obtain a hash value. Accordingly, if a specific frame associated with a specific time offset of a specific program on a specific channel is ingested and hashed, resulting in a hash value associated with that specific frame, then the same hash operation applied to the ingested frame will result in the same hash value as would be generated by the hash operation performed on the ingested frame if that specific frame were sampled while being displayed on the client system. However, in contrast to a hash value prepared during ingestion, the hint of operation 2002 represents data associated with the sample of video data from the specific client system. The hint may be received, for example, via an HTTP request.

Operation 2004 then depicts referencing the most significant bits of the received hint to determine the database sector. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , the bits of the same hint defined by the most significant bits used to reference the database sector during ingestion are checked. For example, if the first two bits of the hash value at ingestion were used to store the hash value at a specific database sector, the same first two bits of the hint associated with the sample of video data from the client system are used to address the specific database sector.

Operation 2006 then depicts returning at least one indication of at least one candidate from the database sector based at least in part on the received hint. For example, as shown in and/or described with respect to Figures 1-9, multiple hash values that exactly match the hint or are near the hint are returned as one or more of multiple suspects or candidates. Candidates may be returned within a specified percentage radius. Candidates may be returned based on a nearest neighbor algorithm or a modified nearest neighbor algorithm.

Figure 21 illustrates an alternative embodiment of the example operational flow 2000 of Figure 20. Figure 21 illustrates an example embodiment in which operation 2002 may include at least one additional operation. The additional operation may include operation 2102, operation 2104, and/or operation 2106.

Operation 2102 illustrates receiving a hint associated with a sample of a video buffer of a client system, including receiving at least one or more indications associated with a time instant associated with the sample of the video buffer of the client system. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , the hint may include or be associated with a time offset associated with an arbitrary time. For example, the time offset may be calculated from January 1, 1970.

Operation 2104 illustrates receiving a hint associated with a sample of a video buffer of a client system, the hint being determined at least in part by hashing at least some values associated with the video buffer. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , one or more operands may be used as constants to reduce a plurality of slices associated with the video buffer to a bit string via one or more mathematical operations or algorithms, the constants being pre-derived by operations such as those described elsewhere herein with respect to hashing.

Operation 2016 illustrates receiving a hint associated with a sample of a video buffer of a client system, the hint being determined at least in part by hashing at least some values associated with the video buffer, the hash being based at least in part on one or more of at least one operand or at least one algorithm also used in an associated media storage operation. For example, as shown in and/or described with respect to FIG1-9, at least some data associated with the sample of the video buffer representing what the television screen displayed at a particular time quantum is processed by an operation utilized by an ingestion operation and/or utilized in conjunction with a data location common to the ingestion process and/or involving constant values for operands utilized by the ingestion process. For example, the number of tiles analyzed during ingestion can also be used to provide a hint associated with a particular client system. The size of the pixel tiles analyzed during ingestion can also be used to provide a hint associated with a particular client system. The same pre-derived static matrix used to more evenly distribute hash values during ingestion can also be used during hashing of data associated with a particular client system.

Figure 22 illustrates an alternative embodiment of the example operational flow 2000 of Figure 20. Figure 22 illustrates an example embodiment in which operation 2002 may include at least one additional operation. The additional operation may include operation 2202, operation 2204, operation 2206, operation 2208, operation 2210, operation 2212, and/or operation 2214.

Operation 2202 illustrates receiving one or more indications of at least one content of a video buffer of a client system. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , pixel values for red pixels, green pixels, and blue pixels at each pixel location at each predefined slice of the video buffer of the client system may be read for each frame, or for every three frames, or for every ten frames, or for every second, or at some other interval. These indications (pixel values or other data) may be received by a control on the television, by control logic on the television, by a system coupled to a media server, or elsewhere.

Operation 2204 illustrates determining, for the at least one tile of the at least one item of content of the video buffer including at least one or more pixels of the at least one tile, an algorithmically derived value for the one or more pixels of each tile. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , pixel values for red pixels, green pixels, and blue pixels at each pixel location at each predefined tile of the video buffer for the client system may be averaged.

Operation 2206 illustrates subtracting a midpoint value from the average for each shard. For example, as shown in and/or described with respect to Figures 1 to 9, a midpoint value at each shard established by analysis of the ingested content is determined. Once determined by a system associated with the media database and the ingestion system, the midpoint value for each shard can be provided, for example, to the client system. These midpoint values can be updated from time to time (hourly, daily, monthly, yearly). These midpoint values provided for hashing data associated with the client system's video buffer can be the same midpoint values used to hash the incoming content at the time of ingestion.

Operation 2208 shows that these values produced due to this subtraction are transformed.For example, as shown in Figure 1 to Figure 9 and/or described about it, these values produced by subtraction are filled in the matrix and intersect with the predefined static matrix.Can be during the process of converting the pixel slice data associated with the frame in the video buffer into prompts at the client system, perform the dot product operation of these two matrices intersecting, so that prompts are sent in the HTTP request rather than in the actual pixel slice data, resulting in a compact HTTP message.Predefined static matrix can be provided to the client system before transformation and can be the same matrix that is generated to more evenly distribute multiple hashed values when ingested.Predefined static matrix can be updated from time to time at the client system.Alternatively, the slice data (with or without other metadata) can be sent to different systems for processing and/or hashing from the client system (for example, TV).

Operation 2210 illustrates constructing a hash value based on these transformed values. For example, as shown in and/or described with respect to Figures 1 to 9, the values in the matrix resulting from intersecting a matrix having values associated with the video buffer with a pre-derived static matrix can be reduced to a plurality of bits, wherein a single bit replaces each 8-bit value in the matrix. In other embodiments, the constructed hash value can include a different number of bits for each value in the matrix. In various embodiments, the constructed hash value can have the same number of bits as the values in the matrix, or can be a direct representation of the values in the matrix.

Operation 2212 illustrates associating the hint at least in part with the constructed hash value. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , a bit string constructed from the transformed matrix may be the hint, or the constructed bit string may be associated with a time (e.g., a moment in time) to form a hint, or other data (e.g., an IP address or other identifier associated with the client television or a control on the client television) may be associated to form a hint. Alternatively, the hint may include or be otherwise associated with any other metadata associated with the audiovisual content at the client system.

Operation 2214 illustrates that at least one of the determining operation 2204, the subtracting operation 2206, the transforming operation 2208, or the constructing operation 2210 utilizes one or more of the at least one operand or the at least one algorithm that is also used in the associated media storage operation. For example, as shown in and/or described with respect to FIG. 1 through FIG. 9 , one or more parameters including one or more of a definition of the number of pixel tiles, a definition of the size of the pixel tiles, a predefined median value associated with the pixel tiles, or a predefined static matrix may be provided to the client TV, the one or more parameters also being utilized by the ingestion process such that multiple operations applied to samples from the video buffer will result in the same hash value as would have been produced if that frame (e.g., the same video segment and time offset) had been ingested and hashed.

FIG23 illustrates an alternative embodiment of the example operational flow 2000 of FIG20 . FIG23 illustrates an example embodiment in which operation 2006 may include at least one additional operation. The additional operation may include operation 2302 and/or operation 2304.

Operation 2302 illustrates returning at least one indication of at least one candidate from the database sector based at least in part on a Probability Point Location in Equal Sphere ("PPLEB") algorithm as a function of the received cue, such as returning at least one candidate or suspect from a media database constructed and/or modified by an ingestion process representing a waypoint that is close to the cue (e.g., a neighbor, a nearest neighbor, within a radius, from within the same bucket, belonging to the same ring, etc.) as shown in and/or described with respect to FIGs. 1-9.

Operation 2304 illustrates returning, based at least in part on the received hint, at least one indication of at least one candidate from the database sector that is within a predetermined inverse percentile distribution radius of the received hint, such as, for example, returning at least one candidate or suspect associated with locality-sensitive hashing of at least one of the hint and the hash value as shown in and/or described with respect to FIG. 1-9 .

FIG24 illustrates an operational flow 2400 representing a number of example operations for addressing a media database using distance-associative hashing. In FIG24 and in the following figures, which include various examples of operational flows, discussion and illustration are provided with respect to the aforementioned examples of FIG1 through FIG9 and/or with respect to other examples and contexts. However, it should be understood that these operational flows can be performed in many other environments and contexts and/or in modified versions of FIG1 through FIG9. Furthermore, while the various operational flows are presented in the illustrated sequence, it should be understood that the various operations can be performed in an order other than the illustrated order or can be performed simultaneously.

After a start operation, operational flow 2400 moves to operation 2402. Operation 2402 depicts receiving at least one indication of at least one candidate and at least one indication of at least one hint. For example, as shown in and/or described with respect to FIGURES 1-9, a hash value associated with a video buffer of the client system is determined, along with one or more associated candidates or suspects.

Then, operation 2404 depicts adding a token to a bin associated with at least one received candidate. For example, as shown in and/or described with respect to FIGURES 1-9, scoring the candidate is performed by adding a token to a bin corresponding to the candidate/suspect, the token being a value that increments, for example, each time the token is incremented by one.

Operation 2406 then depicts determining whether the number of tokens within the bin exceeds a value associated with a probability that the client system is displaying a specific video segment associated with the at least one prompt, and if the number of tokens within the bin exceeds the value associated with the probability that the client system is displaying the specific video segment associated with the at least one prompt, returning at least some data associated with the specific video segment based at least in part on the bin. For example, as shown in and/or described with respect to Figures 1-9, the determination of the specific video segment and the specific offset of the video segment is probabilistically determined by the scores associated with the bins.

Figure 25 illustrates an alternative embodiment of the example operational flow 2400 of Figure 24. Figure 25 illustrates an example embodiment in which operation 2404 may include at least one additional operation 2502.

Operation 2502 illustrates adding a token to a time bin associated with at least one received candidate. For example, as shown in and/or described with respect to Figures 1-9, the data structure associated with the candidate/suspect may include arbitrary time bins grouped by arbitrary time.

FIG26 illustrates an alternative embodiment of the example operational flow 2400 of FIG20 . FIG26 illustrates an example embodiment in which operation 2404 may include at least one additional operation. The additional operation may include operation 2602 and/or operation 2604. Furthermore, operational flow 2400 may include at least one additional operation 2606.

Operation 2602 illustrates determining a relative time, including subtracting a candidate time associated with the at least one candidate from an arbitrary time associated with the at least one prompt, such as, for example, subtracting a time offset of a video segment associated with the candidate from an arbitrary time associated with a moment of receiving a prompt from a client system (a television, a set-top box, or an article, a machine, or a combination thereof that displays and/or provides and/or receives video content), as shown in and/or described with respect to FIG. 1 through FIG. 9 .

Operation 2604 illustrates adding a token to a time bin associated with the candidate based at least in part on the determined relative time. For example, as shown in and/or described with respect to FIGURES 1-9, when a cue point associated with the client system matches or nearly matches a reference cue point associated with the media database, a token may be added to the bin, which may include incrementing a value associated with the bin or other means of tracking bin operations.

Operation 2606 illustrates removing one or more tokens from a time bin based at least in part on the elapsed time period. For example, as shown in and/or described with respect to FIGURES 1-9, a bin may be leaked such that data and/or tokens associated with old suspects/candidates may be released from the bin, which may include decrementing a value associated with the bin or other means of tracking bin operations.

In various embodiments, a pixel position may relate to one or more colors and/or color spaces/models (e.g., red, blue, green; red, blue, green, and yellow; cyan, magenta, yellow, and black; a single pixel value uniquely identifying a color, e.g., a 24-bit value associated with a pixel position; hue, saturation, brightness; etc.). Different numbers of pixels in a tile may be used, and the tiles need not be square tiles. Furthermore, the resolution of the client system's video buffer may vary. The resolution and/or color density at the client system and the ingest system may vary. The system may operate at different raster resolutions (including, but not limited to, 1920 by 1080, 3840 by 2160, 1440×1080, 1366×768, or other resolutions). It is expected that over the next twenty years, an increase in the pixel resolution of common programs, televisions, and/or client systems will occur; while the number of pixel tiles, their size, sampling rate, or other aspects may vary, the same basic operations may be utilized. Further, upconversion, downconversion, or other conversion operations associated with resolution and/or color density may occur and/or be inserted between other operations described herein.

FIG27 illustrates an example system 2700 in which embodiments may be implemented. System 2700 includes one or more computing devices 2702. System 2700 also illustrates a framework 2704 for facilitating communication between the one or more computing devices and one or more client devices 2706. System 2700 also illustrates one or more client devices 2706. In some embodiments, the one or more client devices may be between the one or more computing devices. System 2700 also illustrates at least one non-transitory computer-readable medium 2708. In some embodiments, 2708 may include one or more instructions 2710 that, when executed on at least some of the one or more computing devices, cause at least some of the one or more computing devices to perform at least the following operations: receive at least one rasterized video stream; create at least one hash value associated with at least one sample of at least one received rasterized video stream; determine at least one database sector for storing the at least one created hash value; and store the at least one created hash value on the at least one determined database sector. In various embodiments, the one or more instructions may be executed on a single computing device. In other embodiments, some portions of the one or more instructions may be executed by a first plurality of the one or more computing devices, while other portions of the one or more instructions may be executed by a second plurality of the one or more computing devices.

FIG28 illustrates an example system 2800 in which embodiments may be implemented. System 2800 includes one or more computing devices 2802. System 2800 also illustrates a framework 2804 for facilitating communication between the one or more computing devices and one or more client devices 2806. System 2800 also illustrates one or more client devices 2806. In some embodiments, the one or more client devices may be between the one or more computing devices. System 2800 also illustrates at least one non-transitory computer-readable medium 2808. In some embodiments, 2808 may include one or more instructions 2810 that, when executed on at least some of the one or more computing devices, cause at least some of the one or more computing devices to perform at least the following operations: receive one or more instructions associated with at least one video buffer of at least one client system; determine a hint based at least in part on the at least one video buffer and at least one time associated with the at least one video buffer, wherein one or more of at least one operand or at least one function associated with determining the hint is also used in an associated media storage operation; reference a plurality of most significant bits of the determined hint to determine a database sector; and return at least one indication of at least one candidate from the determined database sector based at least in part on the determined hint. In various embodiments, the one or more instructions may be executed on a single computing device. In other embodiments, some portions of the one or more instructions may be executed by a first plurality of computing devices among the one or more computing devices, while other portions of the one or more instructions may be executed by a second plurality of computing devices among the one or more computing devices.

FIG29 illustrates an example system 2900 in which embodiments may be implemented. System 2900 includes one or more computing devices 2902. System 2900 also illustrates a framework 2904 for facilitating communication between the one or more computing devices and one or more client devices 2906. System 2900 also illustrates one or more client devices 2906. In some embodiments, the one or more client devices may be between the one or more computing devices. System 2900 also illustrates at least one non-transitory computer-readable medium 2908. In some embodiments, 2908 may include one or more instructions 2910 that, when executed on at least some of the one or more computing devices, cause at least some of the one or more computing devices to perform at least the following operations: receive at least one indication of at least one candidate and at least one indication of at least one hint; add tokens to a bin associated with at least one received candidate; and determine whether the number of tokens in the bin exceeds a value associated with a probability that the client system is receiving a specific video segment associated with the received at least one hint, and if the number of tokens in the bin exceeds the value associated with the probability that the client system is receiving the specific video segment associated with the received at least one hint, return at least some data associated with the specific video segment based at least in part on the bin. In various embodiments, the one or more instructions may be executed on a single computing device. In other embodiments, some portions of the one or more instructions may be executed by a first plurality of computing devices among the one or more computing devices, while other portions of the one or more instructions may be executed by a second plurality of computing devices among the one or more computing devices.

Certain aspects of the present invention include processing steps and instructions described herein in algorithmic form. It should be noted that these processing steps and instructions of the present invention can be embodied in software, firmware, or hardware, and when embodied in software, can be downloaded to reside on and operate from different platforms used by real-time network operating systems.

The present invention also relates to an apparatus for performing the operations herein. The apparatus may be specially constructed for the required purpose, or it may comprise a general-purpose computer selectively activated or rearranged by a computer program stored in the computer. Such a computer program may be stored on a computer-readable storage medium, such as, but not limited to, any type of disk, including a floppy disk, an optical disk, a CD-ROM, a magneto-optical disk, a read-only memory (ROM), a random access memory (RAM), an EPROM, an EEPROM, a magnetic or optical card, an application-specific integrated circuit (ASIC), or any type of medium suitable for storing electronic instructions, and each coupled to a computer system bus.

Additionally, the computers or computing devices referred to in this specification may include a single processor or may employ a multi-processor design for increased computing capability.

The algorithm and display proposed herein are not inherently related to any particular computer or other device. According to the teachings of this paper, various general-purpose systems can also be used together with the program, or it can be convenient to build a more specialized device to perform the required method steps. The required structure for a variety of these systems will appear from the above description. In addition, the present invention is not described with reference to any specific programming language or operating system. It should be appreciated that various programming languages and operating systems can be used to implement the teachings of the present invention as described herein.

The systems and methods, flow charts, and structured block diagrams described in this specification can be implemented in a computer processing system including program code comprising program instructions executable by the computer processing system. Other implementations can also be used. In addition, the flow charts and structured block diagrams described herein describe specific methods and/or corresponding actions that support multiple steps and corresponding functions (these steps and corresponding functions support the disclosed structural means), and can also be used to implement corresponding software structures and algorithms, and their equivalents.

Embodiments of the subject matter disclosed in this specification can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a tangible program carrier for execution by or to control the operation of a data processing apparatus. The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, or a combination of one or more of these.

A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files storing multiple portions of one or more modules, subroutines, or code). A computer program can be deployed to be executed on one computer or on multiple computers located at one site or distributed across multiple sites and interconnected by a suitable communication network.

The processes or logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions of operating on input data and generating output. These processes or logic flows can also be performed by an apparatus, and the apparatus can also be implemented as a special-purpose logic circuit, such as an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

The essential element of a computer is a processor for executing instructions and one or more memory devices for storing instructions and data. Usually, a computer will also include one or more storage devices (such as, magnetic disks, magneto-optical disks, or optical disks) for storing data or be operatively connected to receive data therefrom or transmit data thereto or both receive and transmit data. However, a computer does not need to have such a device. The processor suitable for executing a computer program only includes, by way of example and not limitation, any one or more processors of a general-purpose microprocessor and a special-purpose microprocessor and a digital computer of any kind. Usually, a processor will receive instructions and data from a read-only memory or a random access memory or both.

To provide for user or administrator interaction with the systems described herein, embodiments of the subject matter described in this specification can be implemented on a computer having a display device (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user, and a keyboard (e.g., a mouse or trackball) and a pointing device through which the user can provide input to the computer. Other types of devices can also be used to provide for user interaction. For example, feedback provided to the user can be any form of sensory feedback, such as visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, voice, or tactile input.

The embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back-end component including one or more data servers, or includes a front-end component (such as a client computer) having one or more middleware components (such as an application server), or includes a front-end component (such as a client computer) having a graphical user interface or a web browser (through which a user or administrator can interact with certain implementations of the subject matter described in this specification), or any combination of one or more such back-end components, middleware, or front-end components. The components of the system can be interconnected through any digital data communication form or medium (such as a communication network). The computing system can include a client and a server. The client and server are typically remote from each other and typically interact through a communication network. The relationship between the client and the server is generated by means of computer programs running on respective computers and having a client-server relationship with each other.

While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any invention or of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions. Certain features that are described in this specification in the context of separate embodiments may also be implemented in combination in a single embodiment.

Conversely, various features described in the context of a single embodiment may also be implemented in multiple embodiments separately or in any suitable subcombination. Furthermore, although features may be described above as functioning in certain combinations and even initially claimed as such, one or more features from the claimed combination may in some cases be separated from the combination, and the claimed combination may be directed to subcombinations or variations of the subcombinations.

Similarly, although operations are depicted in a specific order in the accompanying drawings, this should not be understood as requiring that such operations be performed in the specific order shown or in an ordered order, or that all of the operations shown can be performed to achieve the desired results. In some cases, multitasking and parallel processing may be advantageous. Moreover, the separation of different system components in the above-described embodiments should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

This specification has been written to set forth the best mode of the present invention and to provide a number of examples to describe the invention and to enable one skilled in the art to make and use the invention. This specification has been written not to limit the invention to the precise terms set forth. Thus, while the invention has been described in detail with reference to the examples set forth above, variations, modifications, and alterations to these examples may be made by one skilled in the art without departing from the scope of the invention.

Claims (19)

1. A method for addressing a media database using distance-associative hashing, the method comprising: receiving one or more indications of samples of a video segment; determining, for a patch of one or more pixels of the sample, an algorithmically derived value of the one or more pixels; deriving a new value by subtracting a midpoint value established for the slice from the algorithmically derived value; transforming the new value, wherein the transforming comprises uniformly distributing the value using a pre-derived function; generating a hash value, wherein said generating comprises using at least said transformed new value; determining a database sector by referencing a plurality of most significant bits of the hash value, wherein the plurality of most significant bits are predetermined to be an address of a corresponding database sector, and wherein one or more remaining bits of the hash value address respective buckets of the database sector; and The hash value is stored on the database sector. 2. The method of claim 1, wherein at least one of receiving, determining, deriving, transforming, generating, referencing, or storing is at least partially implemented using one or more processing devices. 3. The method of claim 1 , wherein the receiving comprises: One or more indications of frames or still images are received. 4. The method of claim 1, wherein the one or more indications are associated with an indication of a channel, an indication of a video segment, or an indication of a time code offset from the start of the video segment. 5. The method of claim 1, wherein the midpoint value has been previously determined for a plurality of channels over a time period using data from the slices. 6. The method of claim 1 , wherein the transforming comprises: forming a variable matrix including at least the new value; obtaining a static matrix that more evenly distributes values when intersected with the variable matrix; and Calculate the dot product of the variable matrix and the static matrix. 7. The method of claim 6, wherein the obtaining comprises: A static matrix that more evenly distributes values of the variable matrix when intersected with the variable matrix is determined based on one or more previously obtained hash values using locality-sensitive hashing. 8. The method of claim 1 , wherein said generating comprises: A hash value is generated from at least the transformed new value by reducing the fidelity of the transformed new value by reducing the transformed new value to a binary representation. 9. The method of claim 8, wherein the reducing comprises: It is determined whether the transformed new value is a positive number, and if the transformed new value is a positive number, one is assigned to the hash value, otherwise zero is assigned to the hash value. 10. The method of claim 1, wherein the storing comprises: An indication of a channel, an indication of a video segment, or an indication of a time code offset from the start of the video segment is stored at a database location based at least in part on the hash value. 11. A method for addressing a media database using distance-associative hashing, the method comprising: Receiving a prompt, the prompt generated by one or more operations, wherein the one or more operations include: receiving one or more indications of contents in a video buffer of a client system; determining, for a tile of one or more pixels of the content, an algorithmically derived value of the one or more pixels; deriving a new value by subtracting the midpoint value from the algorithmically derived value; transforming the new value, wherein the transforming comprises uniformly distributing the value using a pre-derived function; generating a hash value, wherein said generating comprises using at least said transformed new value; and associating a hint at least in part with the hash value; determining a database sector by referencing a plurality of most significant bits of the hash value, wherein the plurality of most significant bits are predetermined to be an address of a corresponding database sector, and wherein one or more remaining bits of the hash value address respective buckets of the database sector; and An indication of a candidate from the database sector is returned based at least in part on the received hint. 12. The method of claim 11, wherein receiving the prompt comprises: A hint is received associated with a sample in a video buffer of a client system, wherein the hint comprises one or more indications related to a time instant associated with the sample in the video buffer of the client system. 13. The method of claim 11, wherein the hint is associated with samples in a video buffer of the client system, and wherein the hint is determined at least in part by hashing at least some values associated with the video buffer. 14. The method of claim 13, wherein the hash value is generated based at least in part on one or more of at least one operand or at least one algorithm also used in an associated media storage operation. 15. The method of claim 11, wherein at least one of the determining, deriving, transforming, or generating operations utilizes one or more of at least one operand or at least one algorithm also used in an associated media storage operation. 16. The method of claim 11, wherein the returning comprises: At least one indication of at least one candidate from the database sector is returned based at least in part on a probabilistic point location in an equal sphere algorithm as a function of the received hint. 17. The method of claim 11, wherein the candidate item is within a predetermined inverse percentage distribution radius of the received prompt. 18. A system for addressing a media database using distance-associative hashing, the system comprising: one or more processors; and One or more instructions, when executed by the one or more processors, cause the one or more processors to perform the following operations: receiving one or more indications of samples of a video segment; determining, for a patch of one or more pixels of the sample, an algorithmically derived value of the one or more pixels; deriving a new value by subtracting a midpoint value established for the slice from the algorithmically derived value; transforming the new value, wherein the transforming comprises uniformly distributing the value using a pre-derived function; generating a hash value, wherein said generating comprises using at least said transformed new value; The database sector is determined by referencing a plurality of most significant bits of the hash value, wherein the plurality of most significant bits are predetermined to be the address of the corresponding database sector, and wherein one or more of the hash values A plurality of remaining bits addresses respective buckets of the database sector; and The hash value is stored on the database sector. 19. A machine for addressing a media database using distance-associative hashing, the machine comprising: circuitry configured to receive one or more indications of samples of a video segment; circuitry configured to determine an algorithmically derived value for a tile of one or more pixels of the sample; circuitry configured to derive a new value by subtracting a midpoint value of the slice from the algorithmically derived value; circuitry configured to transform the new value, wherein the transforming comprises uniformly distributing the value using a pre-derived function; circuitry configured to generate a hash value, wherein said generating comprises using at least said transformed new value; circuitry configured to determine a database sector by referencing a plurality of most significant bits of the hash value, wherein the plurality of most significant bits are predetermined to be an address of a corresponding database sector, and wherein one or more remaining bits of the hash value address respective buckets of the database sector; and Circuitry is configured to store the hash value on the database sector.