Prospective search of objects using k-d forest

One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

• receive a content object;
• store content objects in a list;
• determine whether the list of the stored content objects is full, wherein the received content object is represented as a vector of elements and each of the stored content objects is represented as a vector of elements;
• identify a corresponding node of a k-dimensional tree for each of the stored content objects and the received content object based on determining one or more median vectors from the vectors of the stored content objects, wherein:
• each node of the k-dimensional tree is configured to store the vector of a particular one of the stored content objects or the received content object;
• the k-dimensional tree comprises a top level comprising a root node configured to store information corresponding to a particular one of the median vectors, the particular one of the median vectors corresponding to a median content object of the stored content objects;
• and
• the k-dimensional tree comprises a second level comprising a plurality of leaf nodes;
• move information corresponding to the vector of one or more of the stored content objects and the received content object from the list to the corresponding node of the k-dimensional tree;
• calculate a proximity measurement comprising a difference between a value of a first element of the vector of the received content object and a value of a first element of the particular one of the median vectors, wherein the vector of each node is representative of a cluster of content objects;
• identify a particular one of the clusters of content objects based on the proximity measurement;
• and
• update an entry of a cache corresponding to the identified cluster to include the received content object.

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 content object;
• store content objects in a list;
• determine whether the list of the stored content objects is full, wherein the received content object is represented as a vector of elements and each of the stored content objects is represented as a vector of elements;
• identify a corresponding node of a k-dimensional tree for each of the stored content objects and the received content object based on determining one or more median vectors from the vectors of the stored content objects, wherein:
• each node of the k-dimensional tree is configured to store the vector of a particular one of the stored content objects or the received content object;
• the k-dimensional tree comprises a top level comprising a root node configured to store information corresponding to a particular one of the median vectors, the particular one of the median vectors corresponding to a median content object of the stored content objects;
• and
• the k-dimensional tree comprises a second level comprising a plurality of leaf nodes;
• move information corresponding to the vector of one or more of the stored content objects and the received content object from the list to the corresponding node of the k-dimensional tree;
• calculate a proximity measurement comprising a difference between a value of a first element of the vector of the received content object and a value of a first element of the particular one of the median vectors, wherein the vector of each node is representative of a cluster of content objects;
• identify a particular one of the clusters of content objects based on the proximity measurement;
• and
• update an entry of a cache corresponding to the identified cluster to include the received content object.