Retroactive search of objects using k-d tree

Abstract

In one embodiment, a method includes receiving a set of one or more content objects to be blacklisted; retrieving a set of currently blacklisted content objects; and determining a delta set of content objects that includes the content objects in the set of content objects to be blacklisted that are not included in the set of currently blacklisted content objects. Each of the content objects of the delta set is represented as a vector that includes a number of first elements. The method also includes retrieving, for each content object of a third set of content objects, a representation of the content object as a vector that includes a number of second elements; and identifying each content object in the third set whose content substantially matches at least one content object of the delta set.

What is claimed is: 
     
         1 . A method comprising:
 by a computing device, receiving a set of one or more content objects to be blacklisted;   by the computing device, retrieving a set of currently blacklisted content objects;   by the computing device, determining a delta set of content objects comprising the content objects in the set of content objects to be blacklisted that are not included in the set of currently blacklisted content objects, wherein each of the content objects of the delta set is represented as a vector comprising a plurality of first elements;   by the computing device, retrieving, for each content object of a third set of content objects, a representation of the content object as a vector comprising a plurality of second elements;   by the computing device, identifying each content object in the third set whose content substantially matches at least one content object of the delta set based on a determination as to whether calculated differences between the first elements and the corresponding second elements is less than a pre-determined threshold.   
     
     
         2 . The method of  claim 1 , wherein the set of currently blacklisted content objects comprises one or more of categories, and wherein the identification corresponds to a comparison of one or more of stored images to one or more of the categories. 
     
     
         3 . The method of  claim 1 , wherein the content objects are images and the identification is performed using an image-matching algorithm. 
     
     
         4 . The method of  claim 3 , wherein the image-matching algorithm is a discrete waveform transformation, singular value decomposition, or feature point based image hashing. 
     
     
         5 . The method of  claim 1 , wherein the set of content objects to be blacklisted comprise an updated blacklist. 
     
     
         6 . The method of  claim 1 , wherein the plurality of first elements represents content of the currently blacklisted content objects or the content objects to be blacklisted, and wherein the plurality of second elements represents content of content objects stored on a social-networking system. 
     
     
         7 . The method of  claim 1 , wherein the third set of content objects is stored in a k-dimensional tree. 
     
     
         8 . The method of  claim 7 , wherein:
 the k-dimensional tree comprises a root node and a plurality of sub-trees connected to the root node; and   the plurality of sub-trees comprises a plurality of nodes.   
     
     
         9 . The method of  claim 8 , wherein identifying each content object comprises identifying one of the sub-trees for a subsequent comparison based at least in part on a difference between a first element corresponding to a current node of the k-dimensional tree and a second element corresponding to the current node. 
     
     
         10 . The method of  claim 9 , wherein identifying each content object further comprises eliminating content objects of one or more unidentified sub-trees from the identification based at least in part on the difference between the first element corresponding to the current node of the k-dimensional tree and the second element corresponding to the current node being more than the pre-determined threshold. 
     
     
         11 . The method of  claim 10 , further comprising discarding a sub-tree of k-dimensional tree that corresponds to eliminated content objects. 
     
     
         12 . The method of  claim 8 , wherein identifying each content object comprises:
 calculating a difference between a first element corresponding to the root node and a second element corresponding to the root node; and   calculating a difference between a first element corresponding to a child node of the root node a second element corresponding to the child node, wherein the child node is identified based on the calculated difference of the root node.   
     
     
         13 . The method of  claim 7 , wherein each node of the k-dimensional tree stores the vector representing content of one of the content objects of the third set. 
     
     
         14 . The method of  claim 7 , wherein:
 each second element corresponds to a level of the k-dimensional tree; and   each content object of the third set is sorted within the k-dimensional tree based on a value of each second element.   
     
     
         15 . One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
 receive a set of one or more content objects to be blacklisted;   retrieve a set of currently blacklisted content objects;   determine a delta set of content objects comprising the content objects in the set of content objects to be blacklisted that are not included in the set of currently blacklisted content objects, wherein each of the content objects of the delta set is represented as a vector comprising a plurality of first elements;   retrieve, for each content object of a third set of content objects, a representation of the content object as a vector comprising a plurality of second elements;   identify each content object in the third set whose content substantially matches at least one content object of the delta set based on a determination as to whether calculated differences between the first elements and the corresponding second elements is less than a pre-determined threshold.   
     
     
         16 . The media of  claim 15 , wherein the third set of content objects is stored in a k-dimensional tree. 
     
     
         17 . The media of  claim 16 , wherein:
 the k-dimensional tree comprises a root node and a plurality of sub-trees connected to the root node; and   the plurality of sub-trees comprises a plurality of nodes.   
     
     
         18 . 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:
 receive a set of one or more content objects to be blacklisted; 
 retrieve a set of currently blacklisted content objects; 
 determine a delta set of content objects comprising the content objects in the set of content objects to be blacklisted that are not included in the set of currently blacklisted content objects, wherein each of the content objects of the delta set is represented as a vector comprising a plurality of first elements; 
 retrieve, for each content object of a third set of content objects, a representation of the content object as a vector comprising a plurality of second elements; 
 identify each content object in the third set whose content substantially matches at least one content object of the delta set based on a determination as to whether calculated differences between the first elements and the corresponding second elements is less than a pre-determined threshold. 
   
     
     
         19 . The system of  claim 18 , wherein the third set of content objects is stored in a k-dimensional tree. 
     
     
         20 . The system of  claim 19 , wherein:
 the k-dimensional tree comprises a root node and a plurality of sub-trees connected to the root node; and   the plurality of sub-trees comprises a plurality of nodes.