Retroactive search of objects using k-d tree

Abstract

In one embodiment, a method includes at time t 2 , determining a delta set of first objects representing a difference between a first set of first objects at time t 1 and a second set of first objects at time t 2 ; comparing the delta set of first objects with a set of second objects represented as a balanced k-dimensional tree; and identifying each second object whose content substantially matches content of at least one first object from the delta set of first objects.

What is claimed is: 
     
       1. A method comprising, by a computing device:
 at time t 2 , determining a delta set of first objects representing a difference between a first set of first objects at time t 1  and a second set of first objects at time t 2 , wherein each first object is a first image, wherein the first set of first objects is represented as a first k-dimensional tree, and wherein the second set of first objects is represented as a second k-dimensional tree; 
 for each first object, generating n elements, x 1  . . . x n , representing the content of the first object; 
 comparing the delta set of first objects with a set of second objects represented as a balanced k-dimensional tree, wherein each second object is a second image; 
 for each second object, generating n elements, y 1  . . . y n , representing the content of the second object, wherein when comparing the content of a second object with the content of a first object, the content of the second object substantially matches the content of the first object if 
 
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
               ⁢ 
               
                 
                   ( 
                   
                     
                       x 
                       i 
                     
                     - 
                     
                       y 
                       i 
                     
                   
                   ) 
                 
                 2 
               
             
           
         
       
       is less than a pre-defined threshold; and
 identifying each second object whose content substantially matches content of at least one first object from the delta set of first objects. 
 
     
     
       2. The method of  claim 1 , further comprising
 representing the set of second objects as the balanced k-dimensional tree, comprising: 
 for each second object, generating k elements representing the content of the second object; 
 partitioning the set of second objects into the balanced k-dimensional tree based on the k elements of each second object, comprising: 
 for each node at each level i of the k-dimensional tree, 
 if a sub-set of second objects belonging to a sub-tree associated with the node has one second object, then store the one second object in the node; and 
 if the sub-set of second objects belonging to the sub-tree associated with the node has multiple second objects, then 
 sort the sub-set of second objects according to their respective (i mod k)th one of the k elements; 
 storing a median second object in the node; 
 storing any second objects to the left of the median second object in a left sub-tree of the node; and 
 storing any second objects to the right of the median second object in a right sub-tree of the node. 
 
     
     
       3. The method of  claim 1 , further comprising:
 between time t 1  and time t 2 , receiving one or more new first objects; and 
 adding the new first objects to the first set of first objects to obtain the second set of first objects. 
 
     
     
       4. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
 at time t 2 , determine a delta set of first objects representing a difference between a first set of first objects at time t 1  and a second set of first objects at time t 2 , wherein each first object is a first image, wherein the first set of first objects is represented as a first k-dimensional tree, and wherein the second set of first objects is represented as a second k-dimensional tree; 
 for each first object, generate n elements, x 1  . . . x n , representing the content of the first object; 
 compare the delta set of first objects with a set of second objects represented as a balanced k-dimensional tree, wherein each second object is a second image; 
 for each second object, generate n elements, y 1  . . . y n , representing the content of the second object, wherein when comparing the content of a second object with the content of a first object, the content of the second object substantially matches the content of the first object if 
 
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
               ⁢ 
               
                 
                   ( 
                   
                     
                       x 
                       i 
                     
                     - 
                     
                       y 
                       i 
                     
                   
                   ) 
                 
                 2 
               
             
           
         
       
       is less than a pre-defined threshold; and
 identify each second object whose content substantially matches content of at least one first object from the delta set of first objects. 
 
     
     
       5. The media of  claim 4 , wherein the software is further operable when executed to
 represent the set of second objects as the balanced k-dimensional tree, comprising: 
 for each second object, generate k elements representing the content of the second object; 
 partition the set of second objects into the balanced k-dimensional tree based on the k elements of each second object, comprising: 
 for each node at each level i of the k-dimensional tree, 
 if a sub-set of second objects belonging to a sub-tree associated with the node has one second object, then store the one second object in the node; and 
 if the sub-set of second objects belonging to the sub-tree associated with the node has multiple second objects, then 
 sort the sub-set of second objects according to their respective (i mod k)th one of the k elements; 
 store a median second object in the node; 
 store any second objects to the left of the median second object in a left sub-tree of the node; and 
 store any second objects to the right of the median second object in a right sub-tree of the node. 
 
     
     
       6. The media of  claim 4 , wherein the software is further operable when executed to:
 between time t 1  and time t 2 , receive one or more new first objects; and 
 add the new first objects to the first set of first objects to obtain the second set of first objects. 
 
     
     
       7. A system comprising:
 one or more processors; and 
 a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to: 
 at time t 2 , determine a delta set of first objects representing a difference between a first set of first objects at time t 1  and a second set of first objects at time t 2 , wherein each first object is a first image, wherein the first set of first objects is represented as a first k-dimensional tree, and wherein the second set of first objects is represented as a second k-dimensional tree; 
 for each first object, generate n elements, x 1  . . . x n , representing the content of the first object; 
 compare the delta set of first objects with a set of second objects represented as a balanced k-dimensional tree, wherein each second object is a second image; 
 for each second object, generate n elements, y 1  . . . y n , representing the content of the second object, wherein when comparing the content of a second object with the content of a first object, the content of the second object substantially matches the content of the first object if 
 
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
               ⁢ 
               
                 
                   ( 
                   
                     
                       x 
                       i 
                     
                     - 
                     
                       y 
                       i 
                     
                   
                   ) 
                 
                 2 
               
             
           
         
       
       is less than a pre-defined threshold; and
 identify each second object whose content substantially matches content of at least one first object from the delta set of first objects. 
 
     
     
       8. The system of  claim 7 , wherein the processors are further operable when executing the instructions to
 represent the set of second objects as the balanced k-dimensional tree, comprising: 
 for each second object, generate k elements representing the content of the second object; 
 partition the set of second objects into the balanced k-dimensional tree based on the k elements of each second object, comprising: 
 for each node at each level i of the k-dimensional tree, 
 if a sub-set of second objects belonging to a sub-tree associated with the node has one second object, then store the one second object in the node; and 
 if the sub-set of second objects belonging to the sub-tree associated with the node has multiple second objects, then 
 sort the sub-set of second objects according to their respective (i mod k)th one of the k elements; 
 store a median second object in the node; 
 store any second objects to the left of the median second object in a left sub-tree of the node; and 
 store any second objects to the right of the median second object in a right sub-tree of the node. 
 
     
     
       9. The system of  claim 7 , wherein the processors are further operable when executing the instructions to:
 between time t 1  and time t 2 , receive one or more new first objects; and 
 add the new first objects to the first set of first objects to obtain the second set of first objects.