SYSTEM AND METHOD TO STORE VIDEO FINGERPRINTS ON DISTRIBUTED NODES IN CLOUD SYSTEMS

• US 20150120750A1
• Filed: 09/24/2012
• Published: 04/30/2015
• Est. Priority Date: 06/15/2012
• Status: Active Grant

• Current Assignee: Qatar Foundation
• Original Assignee: Qatar Foundation
• Inventors: Hefeeda, Mohamed, Ahmed, Ahmed Abdelsadek
• Granted Patent: US 9,959,346 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957

Abstract

A method to design, implement and create distributed indexes for storing and comparing fingerprints of videos is presented. The method effectively utilises cloud computing platforms that offer varying amounts of computing resources. The method enables the distributed index to scale to large numbers of data points and the distributed index is robust to failures within the computing resources maintaining the index. The method minimizes the memory required to maintain the distributed index and reduces the I/O operations needed to process operations performed on the index. The method improves the efficiency of the index to process queries.

Claims

1. A method of processing video fingerprint data in a cloud infrastructure, the method comprising:

analysing video data;

extracting features from the video data to form the video fingerprint data, the video fingerprint data taking the form of multidimensional vectors;

computing meta data and data points from the multidimensional vectors;

inputting the meta data and the data points from the multidimensional vectors into a distributed index having multiple levels, the distributed index comprising a directing tree and leaf nodes, wherein multiple leaf nodes are bins;

storing the meta data relating to the multidimensional vectors in the directing tree;

storing the data points computed from the multidimensional vectors in the leaf nodes;

scaling the distributed index by increasing or decreasing a number of the leaf nodes in the distributed index ssize depending upon a number of the multidimensional vectors to be stored; and

distributing the leaf nodes across at least one client system.

2. The method of claim 1 further comprising:

determining potential bins of the bins to perform a nearest neighbour search.

3. The method of claim 1 further comprising:

maintaining a priority queue of nodes.

4. The method of claim 3 further comprising:

determining a query point;

inserting a root node of the directing tree into the priority queue;

determining a closest distance node from the priority queue to a query node;

wherein if the closest distance node is one of the multiple leaf nodes then;

determine the bin of the one of the multiple leaf nodes; and

search for a nearest neighbour to the query node in the bin;

wherein if the closest distance node is not one of the multiple leaf nodes then;

determine a distance from the query node to a child node wherein the child node is a child of the closest distance node; and

add the child node to the priority queue.

5. The method of claim 1 wherein the multidimensional vectors are extracted from the leaf nodes and compared against multidimensional vectors extracted from another video stream.

6. The method of claim 1 wherein the entirety of the distributed index is hosted on a remote system.

7. The method of claim 1 wherein only the leaf nodes are hosted on a remote system or systems.

8. The method of claim 1 further including determining a number of the levels (L) to be included in the distributed index by calculating a variance of the values to be stored in the distributed index.

9. The method of claim 8 wherein there are 2^L leaf nodes in the distributed index.

10. The method of claim 1 further including calculating a median value of the stored data points, and using them as split values at each level of the distributed index, dividing the data into two sub-sets.

11. The method of claim 10 wherein the two sub-sets are a left sub-set and a right sub-set.

12. The method of claim 11 wherein the median value process is repeated recursively.

13. The method of claim 1 wherein the method further includes searching for a nearest neighbour of a data point.

14. The method of claim 13 wherein the searching for the nearest neighbour of the data point includes traversing the directing tree.

15. The method of claim 14 wherein the searching for the nearest neighbour of the data point includes inserting a root of the directing tree into a priority queue.

16. The method of claim 1 wherein the number of the leaf nodes present in the distributed index is scaled by increasing a number of the levels in the distributed index.

17. The method of claim 16 wherein when the number of the levels is incremented by one, the number of the leaf nodes available is doubled.

18. The method of claim 16, further including calculating a median value of the data points to be stored.

19. The method of claim 1 further including processing the multidimensional vectors with a map reduce algorithm.

20. A system for processing video fingerprint data in a cloud infrastructure, the system having a video fingerprint processor and a distributed index, wherein:

the video fingerprint processor is configured to extract features from video data to create multidimensional vectors;

meta data and data points are computed from the multidimensional vectors;

the distributed index has multiple levels and is formed of a directing tree and at least one leaf node;

the directing tree is configured to store the meta data which relates to the multidimensional vectors;

the at least one leaf node is configured to store the data points computed from the multidimensional vectors;

multiple leaf nodes of the at least one leaf node are configured into bins;

the distributed index is scalable and is adapted to be increased or decreased in size dependent upon a number of the multidimensional vectors to be stored; and

the at least one leaf node is stored on a client system.

21. The system of claim 20 wherein the multidimensional vectors are extracted from at least one leaf node and are compared against multidimensional vectors extracted from another video stream, to detect similarities in the video streams.

22. The system of claim 20 wherein the entirety of the distributed index is hosted on a remote system.

23. The system of claim 20 wherein the at least one leaf node is hosted on a remote system.

24. The system of claim 20 wherein a number of the levels (L) to be included in the distributed index is determined by calculating a variance of the values to be stored in the distributed index.

25. The system of claim 24 wherein there are 2^L leaf nodes in the distributed index.

26. The system of any claim 20 wherein the distributed index is configured to calculate a median value of the stored data points and to use them as split values at each level of the distributed index, to divide the data into two sub-sets.

27. The system of claim 26 wherein the two sub-sets are a left sub-set and a right sub-set.

28. The system of claim 27 wherein the distributed index is configured to repeat the median value calculation recursively.

29. The system of claim 20 wherein the distributed index is further configured to search for a nearest neighbour of a data point.

30. The system of claim 29 wherein the search for the nearest neighbour of the data point includes traversal of the distributed index.

31. The system of claim 29 wherein the search for the nearest neighbour of the data point includes inserting a root of the directing tree into a priority queue.

32. The system of claim 20 wherein a number of the leaf nodes in the distributed index is scaled by increasing a number of the levels in the distributed index.

33. The system of claim 32 wherein when the number of the levels is increased by one, the number of the leaf nodes in the system is doubled.

34. The system of claim 32 wherein when the number of the levels in the distributed index is increased, the distributed index calculates a median value of the data points to be stored.

35. The system of claim 20 wherein the distributed index processes the multidimensional vectors with a map reduce algorithm.