Scalable, adaptable, and manageable system for multimedia identification

• US 8,655,878 B1
• Filed: 05/06/2011
• Issued: 02/18/2014
• Est. Priority Date: 05/06/2010
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Kulkarni, Sunil Suresh, Pereira, Jose Pio, Gajjar, Pradipkumar Dineshbhai, Merchant, Shashank, Ramanathan, Prashant, Stojancic, Mihailo
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US13/102,479
• Time in Patent Office: 1,019 Days
• Field of Search: None
• US Class Current: 707/736
• 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 creating a distributed reference multimedia database, the method comprising:

splitting a reference multimedia database into a first identifiable portion and a second identifiable portion;

storing the first identifiable portion at a first search server and the second identifiable portion at a second search server;

assigning a first query to the first search server based on the first identifiable portion stored therein and a second query to the second search server based on the second identifiable portion stored therein; and

searching for the first query at the first search server in parallel with the second query at the second search server to find a first content stored in the first identifiable portion and a second content stored in the second identifiable portion that have a close match to the associated first query and to the associated second query;

generating a hash key array from fingerprint signatures and metadata of multimedia content stored in the reference multimedia database;

splitting the hash key array into a first hash key array for the first identifiable portion and a second hash key array for the second identifiable portion;

storing the first hash key array in the first server to provide link reference addresses to multimedia content stored in the first server; and

storing the second hash key array in the second server to provide link reference addresses to multimedia content stored in the second server.

2. The method of claim 1, wherein the first and second identifiable portions of the reference database are randomly selected portions.

3. The method of claim 1, wherein the first and second identifiable portions of the reference database are selected according to categories identified by metadata associated with the multimedia content stored in the identifiable portions.

4. The method of claim 1, wherein the first and second identifiable portions of the reference database are selected according to a reverse categorical splitting which distributes multimedia content of the same category across the first and second identifiable portions.

5. The method of claim 1 further comprising:

determining a first capacity of the first identifiable portion, a second capacity of the second identifiable portion, and a size of an update determined during the searching of the first query in parallel with the second query;

selecting the first identifiable portion or the second identifiable portion according to whether the update of the determined size cannot be stored in the first identifiable portion or cannot be stored in the second identifiable portion;

providing a write lock for the selected identifiable portion;

updating the capacity of the selected identifiable portion to accommodate the determined size of the update;

storing the update in the selected identifiable portion; and

releasing the write lock.

6. The method of claim 1 further comprising:

updating a selected identifiable portion during the searching of an associated query in multiple chunks of multimedia content, wherein the updates are accomplished as single entity updates done in parts.

7. The method of claim 1 further comprising:

updating a selected identifiable portion during the searching of an associated query in multiple chunks of multimedia content, wherein the updates to the selected identifiable portion are received from multiple sources.

8. The method of claim 7, wherein the updates to the selected identifiable portion is a deletion of a chunk of multimedia content from the selected identifiable portion.

9. The method of claim 1, further comprising:

reporting the first content and the second content in parallel to a client, wherein the client requested the first query and the second query.

10. The method of claim 1, wherein the first search server and the second search server are grouped to form a combined search cluster.

11. The method of claim 1, wherein a plurality of query signatures are assigned to the first search server and for each query signature a score is derived which are combined for the plurality of query signatures to give an overall score for a particular reference database clip associated with the query signatures.

12. The method of claim 1 further comprising:

combining results from the first search server and from the second search server to generate a final result.

14. The method of claim 12 further comprising:

storing a copy of the first identifiable portion and the first hash key array in a third search server configured to operate in parallel with the first server;

assigning a second query to the third search server; and

searching for the second query at the third search server using the first hash key array in parallel with the search for the first query at the first search server using the first hash key array.

15. The method of claim 14 further comprising:

assigning a third query to the first search server; and

searching for the third query at the first search server using the first hash key array in parallel with the search for the second query at the third search server using the first hash key array and in parallel with the search for the first query at the second search server using the second hash key array.

16. The method of claim 12, wherein the first search server is a cluster of servers each having a copy of the first identifiable portion in a local reference database.

17. The method of claim 12 further comprising:

determining a first capacity of the first identifiable portion, a second capacity of the second identifiable portion, and a size of an update determined during search operations on an associated search server;

selecting the first identifiable portion or the second identifiable portion according to whether the update of the determined size cannot be stored in the first identifiable portion or cannot be stored in the second identifiable portion;

providing a write lock for the selected identifiable portion;

updating the capacity of the selected identifiable portion to accommodate the determined size of the update;

storing the update in the selected identifiable portion; and

releasing the write lock.

18. The method of claim 12 further comprising:

updating a selected identifiable portion during the searching of an associated query in multiple chunks of multimedia content, wherein the updates are accomplished as single entity updates done in parts.

19. The method of claim 12 further comprising:

updating a selected identifiable portion during the searching of an associated query in multiple chunks of multimedia content, wherein the updates to the selected identifiable portion are received from multiple sources.

20. The method of claim 19, wherein the updates to the selected identifiable portion is a deletion of a chunk of multimedia content from the selected identifiable portion.

21. The method of claim 12, wherein the most sought content is determined by keeping track of a number of matching search queries to determine reference content having the number of matching search queries greater than a prespecified most sought threshold.

13. A method for creating a tiered multimedia reference database, the method comprising:

splitting a reference multimedia database into a first identifiable portion having multimedia content representing most sought content and a second identifiable portion representing remaining content;

generating a first hash key array for the first identifiable portion and a second hash key array for the second identifiable portion;

storing the first identifiable portion and the first hash key array at a first search server and the second identifiable portion and the second hash key array at a second search server coupled to the first search server;

assigning a first query to the first search server; and

searching for the first query at the second search server using the second hash key array if a search for the first query at the first search server using the first hash key array is not successful to find multimedia content stored in the first search server.

22. A method for creating a distributed reference multimedia database, the method comprising:

generating a hash key array from fingerprint signatures and metadata of multimedia content stored in a reference multimedia database;

splitting the hash key array into a first hash key array for a first reference multimedia content stored on a first search server in a first multimedia database and a second hash key array for a second reference multimedia content stored on a second search server in a second multimedia database;

storing the first hash key array in the first search server to provide link reference addresses to the first reference multimedia content;

storing the second hash key array in the second search server to provide link reference addresses to the second reference multimedia content;

searching for a first query using the link reference addresses to the first reference multimedia content based on a first type of content stored therein to find a first content that has a close match to the first query; and

in parallel with searching for the first query, searching for a second query using the link reference addresses to the second reference multimedia content based on a second type of content stored therein to find a second content that has a close match to the second query.

23. The method of claim 22, wherein reference multimedia content is randomly selected for storage in the first multimedia database and for storage in the second multimedia database.

24. The method of claim 22, wherein a first category of reference multimedia content is selected for storage in the first multimedia database and a second category of reference multimedia content is selected for storage in the second multimedia database.

25. The method of claim 22 further comprising:

splitting the hash key array into a third hash key array for a third reference multimedia content stored on a third search server in a third multimedia database;

storing the third hash key array in the third search server to provide link reference addresses to the third reference multimedia content;

searching for a third query in the third reference multimedia content based on a third type of content stored therein to find a third content that has a close match to the third query.

26. The method of claim 25, wherein the third search server is organized in a hierarchical arrangement with the first search server and with the second search server.