System and method to store video fingerprints on distributed nodes in cloud systems

• US 9,959,346 B2
• Filed: 09/24/2012
• Issued: 05/01/2018
• Est. Priority Date: 06/15/2012
• Status: Active Grant

• Current Assignee: Qatar Foundation
• Original Assignee: Qatar Foundation
• Inventors: Hefeeda, Mohamed, Ahmed, Ahmed Abdelsadek
• Primary Examiner(s): Hutton, Nan
• Application Number:
  US14/399,690
• Publication Number:
  US 20150120750A1
• Time in Patent Office: 2,045 Days
• 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 utilizes 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;

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 size depending upon a number of the multidimensional vectors to be stored;

distributing the leaf nodes across at least one client system;

searching for a nearest neighbour of a data point;

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

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

if the closest distance node is a leaf node or a bin, adding the closest distance node to a list of preferred bins;

if the closest distance node is not a leaf node or a bin, determining a distance from the query node to a child node wherein the child node is a child of the closest distance node and adding the child node to the priority queue; and

terminating if a maximum number of bins is reached or the priority queue is empty,

wherein the directing tree contains no data points but contains the meta data computed from the multidimensional vectors; and

the leaf nodes contain data points which are apportioned to each respective leaf node in a predetermined manner so that each of the leaf nodes contains data points that are relatively close to other data points in the same leaf node as compared to the data points in other leaf nodes.

2. The method of claim 1 further comprising:

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

3. The method of claim 1 further comprising:

maintaining a priority queue of nodes.

4. 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.

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

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

7. 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.

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

9. 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.

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

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

12. The method of claim 1 wherein the searching for the nearest neighbor of the data point includes traversing the directing tree.

13. 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.

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

15. The method of claim 13 further including calculating a median value of the data points to be stored.

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

17. The method of claim 1 further comprising repeating the determining a closest distance node from the priority queue to a query node;

the adding the closest distance node to a list of preferred bins if the closest distance node is a leaf node or a bin;

the determining a distance from the query node to a child node wherein the child node is a child of the closest distance node and adding the child node to the priority queue if the closest distance node is not a leaf node or a bin; and

the terminating if a maximum number of bins is reached or the priority queue is empty.

18. 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;

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;

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

the distributed index is configured to search for a nearest neighbour of a data point in the multiple leaf nodes;

the search for the nearest neighbour of the data point includes inserting a root of the directing tree into a priority queue;

the distributed index is configured to determine a closest distance node from the priority queue to a query node;

if the closest distance node is one of the multiple leaf nodes, the distributed index is configured to add the closest distance node to a list of preferred bins;

if the closest distance node is not one of the multiple leaf nodes, the distributed index is configured to 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; and

the distributed index is configured to terminate if a maximum number of bins is reached or the priority queue is empty,

wherein the directing tree contains no data points but contains the meta data computed from the multidimensional vectors; and

the leaf nodes contain data points which are apportioned to each respective leaf node in a predetermined manner so that each of the leaf node contains data points that are relatively close to other data points in the same leaf node as compared to the data points in other leaf nodes.

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

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

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

22. The system of claim 18 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.

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

24. The system of claim 18 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.

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

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

27. The system of claim 18 wherein the search for the nearest neighbor of the data point includes traversal of the distributed index.

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

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

30. The system of claim 28 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.

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

32. The system of claim 18 wherein the distributed index is further configured to repeat the determining a closest distance node from the priority queue to a query node;

the adding the closest distance node to a list of preferred bins if the closest distance node is a leaf node or a bin;

the determining a distance from the query node to a child node wherein the child node is a child of the closest distance node and adding the child node to the priority queue if the closest distance node is not a leaf node or a bin; and

the terminating if a maximum number of bins is reached or the priority queue is empty.