Scalable, adaptable, and manageable system for multimedia identification

• US 9,058,355 B1
• Filed: 01/09/2014
• Issued: 06/16/2015
• Est. Priority Date: 06/18/2008
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Pereira, Jose Pio, Gajjar, Pradipkumar Dineshbhai, Merchant, Shashank, Ramanathan, Prashant, Stojancic, Mihailo M., Kulkarni, Sunil Suresh
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US14/151,335
• Time in Patent Office: 523 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

An architecture for a multimedia search system is described. To perform similarity matching of multimedia query frames against reference content, reference database comprising of a cluster index using cluster keys to perform similarity matching and a multimedia index to perform sequence matching is built. Methods to update and maintain the reference database that enables addition and removal of the multimedia contents, including portions of multimedia content, from the reference database in a running system are described. Hierarchical multi-level partitioning methods to organize the reference database are presented. Smart partitioning of the reference multimedia content according to the nature of the multimedia content, and according to the popularity among the social media, that supports scalable fast multimedia identification is also presented. A caching mechanism for multimedia search queries in a centralized or in a decentralized distributed system and a client based local multimedia search system enabling multimedia tracking are described.

Claims

1. A method for query caching, the method comprising:

generating signatures of a video content at a client, wherein the signatures are split into blocks of signatures and each block of signatures represents a non-overlapping segment of the video content;

generating a hash key from each block of signatures at the client, wherein a sequence of hash keys are generated at the client;

requesting a search of a remote reference database using the sequence of hash keys;

searching the remote reference database for a match with the sequence of hash keys to find search results for a match with at least one hash key of the sequence of hash keys;

sending to the client the search results linked with a matching hash key, wherein the results were generated from a previous full search of the remote reference database; and

storing the search results in a cache at the client, wherein the search results are accessible from the cache using the at least one hash key.

2. The method of claim 1 further comprising:

using a predetermined hashing function on the signatures to generate each cache key of the sequence of hash keys.

3. The method of claim 1 further comprising:

searching the remote reference database using the signatures in response to not finding a match to at least one hash key of the sequence of hash keys.

4. The method of claim 1, wherein the remote reference database is configured with a hash key storage unit which is searched with the sequence of hash keys.

5. The method of claim 4, wherein the hash key storage unit is a look-up table storage unit.

6. The method of claim 1, wherein each block of signatures represents a non-overlapping segment of predefined length of the video content.

7. A method for query caching, the method comprising:

generating signatures of a video content at a client, wherein the signatures are split into blocks of signatures and each block of signatures represents an overlapping segment of the video content;

generating a hash key from each block of signatures at the client, wherein a sequence of hash keys are generated at the client;

requesting a search of a remote reference database using the sequence of hash keys;

searching the remote reference database for a match with the sequence of hash keys to find search results for a match with at least one hash key of the sequence of hash keys;

sending to the client the search results linked with a matching hash key; and

storing the search results in a cache at the client, wherein the search results are accessible from the cache using the at least one hash key.

8. The method of claim 7 further comprising:

using a predetermined hashing function on the signatures to generate each cache key of the sequence of hash keys.

9. The method of claim 7 further comprising:

searching the remote reference database using the signatures in response to not finding a match to at least one hash key of the sequence of hash keys.

10. The method of claim 7, wherein the remote reference database is configured with a hash key storage unit which is searched with the sequence of hash keys.

11. The method of claim 10, wherein the hash key storage unit is a look-up table storage unit.

12. The method of claim 7, wherein each block of signatures represents an overlapping segment of predefined length of the video content.

13. The method of claim 7, wherein the results were generated from a previous full search of the remote reference database.

14. A computer readable non-transitory medium storing a computer program which causes a computer system to perform a method for query caching, the method comprising:

generating signatures of a video content at a client, wherein the signatures are split into blocks of signatures and each block of signatures represents a non-overlapping segment of the video content;

generating a hash key from each block of signatures at the client, wherein a sequence of hash keys are generated at the client;

requesting a search of a remote reference database using the sequence of hash keys;

searching the remote reference database for a match with the sequence of hash keys to find search results for a match with at least one hash key of the sequence of hash keys;

sending to the client the search results linked with a matching hash key; and

storing the search results in a cache at the client, wherein the search results are accessible from the cache using the at least one hash key.

15. The computer readable non-transitory medium method of claim 14 further comprising:

using a predetermined hashing function on the signatures to generate each cache key of the sequence of hash keys.

16. The computer readable non-transitory medium method of claim 14 further comprising:

searching a remote reference database using the signatures in response to not finding a match to at least one hash key of the sequence of hash keys.

17. The computer readable non-transitory medium method of claim 14, wherein the remote device is configured with a hash key storage unit which is searched with the sequence of hash keys.

18. The computer readable non-transitory medium method of claim 17, wherein the hash key storage unit is a look-up table storage unit.

19. The computer readable non-transitory medium method of claim 14, wherein the results were generated from a previous full search of the remote device.

20. The computer readable non-transitory medium method of claim 14, wherein the results were generated from a previous full search of a remote reference database in response to a miss in a hash key storage unit.