Prospective search of objects using K-D forest

1. A method comprising, by a computing device:

receiving a content object; and

constructing a first k-dimensional tree in response to determining a second k-dimensional tree is storing information corresponding to a number of content objects that is equal to a number of nodes of the second k-dimensional tree, wherein:

the number of nodes of the second k-dimensional tree is smaller than a number of nodes of the first k-dimensional tree,

the first K-dimensional tree having a number of nodes at least equal to the received object plus the number of nodes of the second k-dimensional tree, the number of nodes of the first k-dimensional tree has twice the number of nodes of the second k-dimensional tree, and each node being configured to store a content object;

storing information corresponding to the received content object as a node in the first k-dimensional tree; and

moving information corresponding to a stored content object from each node of the second k-dimensional tree to a corresponding node of the first k-dimensional tree, wherein the corresponding node of the first k-dimensional tree is identified based at least in part on content of the content object.

2. The method of claim 1 , further comprising

Deleting a particular one of the stored content objects from the second k-dimensional forest, comprising:

locating a node of the second k-dimensional tree corresponding to the particular one of the stored content objects; and

marking the node in the second k-dimensional tree corresponding to the particular one of the stored content objects as being deleted from the second k-dimensional tree.

3. The method of claim 2 , wherein only information corresponding to stored content objects whose corresponding nodes in the second k-dimensional tree are not marked as being deleted are stored in moved to the first k-dimensional tree.

4. The method of claim 1 , further comprising:

creating a first entry in a cache corresponding to a cluster of content objects, the cache having a plurality of entries and each entry including a content object representative of the content objects of the cluster, a counter, a timestamp, and a list of content objects;

storing information of the received content object in the first entry as the representative object of the first entry;

initializing the counter of the first entry to 0; and

initializing the timestamp of the first entry to a time when the first entry is created.

5. The method of claim 1 , wherein the first-stored content object is an image, and wherein the content of the stored content object may be represented by a vector having plurality of elements.

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

receive a content object; and

construct a first k-dimensional tree in response to determining a second k-dimensional tree is storing information corresponding to a number of content objects that is equal to a number of nodes of the second k-dimensional tree, wherein:

the number of nodes of the second k-dimensional tree is smaller than a number of nodes of the first k-dimensional tree,

the first K-dimensional tree having a number of nodes at least equal to the received object plus the number of nodes of the second k-dimensional tree, the number of nodes of the first k-dimensional tree has twice the number of nodes of the second k-dimensional tree, and

each node being configured to store a content object;

store information corresponding to the received content object as a node in the first k-dimensional tree; and

move information corresponding to a stored content object from each node of the second k-dimensional tree to a corresponding node of the first k-dimensional tree, wherein the corresponding node of the first k-dimensional tree is identified based at least in part on content of the content object.

7. The media of claim 6 , wherein the software is further operable when executed to:

Delete a particular one of the stored content objects from the second k-dimensional forest, comprising:

Locate a node of the second k-dimensional tree corresponding to the particular one of the stored content objects; and

mark the node in the second k-dimensional tree corresponding to the particular one of the stored content objects as being deleted from the second k-dimensional tree.

8. The media of claim 7 , wherein only information corresponding to stored content objects whose corresponding nodes in the second k-dimensional tree are not marked as being deleted are moved to the first k-dimensional tree.

9. The media of claim 6 , wherein the software is further operable when executed to:

create a first entry in a cache corresponding to a cluster of content objects, the cache having a plurality of entries and each entry including a content object representative of the content objects of the cluster, a counter, a timestamp, and a list of content objects;

store information of the received content object in the first entry as the representative object of the first entry;

initialize the counter of the first entry to 0; and

initialize the timestamp of the first entry to a time when the first entry is created.

10. The media of claim 6 , wherein the stored content object is an image, and wherein the content of the stored content object may be represented by a vector having plurality of elements.

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

construct a first k-dimensional tree in response to determining a second k-dimensional tree is storing information corresponding to a number of content objects that is equal to a number of nodes of the second k-dimensional tree, wherein:

the number of nodes of the second k-dimensional tree is smaller than a number of nodes of the first k-dimensional tree,

the first K-dimensional tree having a number of nodes at least equal to the received object plus the number of nodes of the second k-dimensional tree, the number of nodes of the first k-dimensional tree has twice the number of nodes of the second k-dimensional tree, and

each node being configured to store a content object;

store information corresponding to the received content object as a node in the first k-dimensional tree; and

move information corresponding to a stored content object from each node of the second k-dimensional tree to a corresponding node of the first k-dimensional tree, wherein the corresponding node of the first k-dimensional tree is identified based at least in part on content of the content object.

12. The system of claim 11 , wherein the processors are further operable when executing the instructions to:

Delete a particular one of the stored content objects from the second k-dimensional forest, comprising:

Locate a node of the second k-dimensional tree corresponding to the particular one of the stored content objects; and

mark the node in the second k-dimensional tree corresponding to the particular one of the stored content objects as being deleted from the second k-dimensional tree.

13. The system of claim 12 , wherein only information corresponding to stored content objects whose corresponding nodes in the second k-dimensional tree are not marked as being deleted are moved to the first k-dimensional tree.

14. The system of claim 11 , wherein the processors are further operable when executing the instructions to:

create a first entry in a cache corresponding to a cluster of content objects, the cache having a plurality of entries and each entry including a content object representative of the content objects of the cluster, a counter, a timestamp, and a list of content objects;

store information of the received content object in the first entry as the representative object of the first entry;

initialize the counter of the first entry to 0; and

initialize the timestamp of the first entry to a time when the first entry is created.

15. The method of claim 5 , further comprising sorting the stored content objects based at least in part on determining a median value of each of the plurality of elements.

16. The media of claim 10 , wherein the software is further operable when executed to sort the stored content objects based at least in part on determining a median value of each of the plurality of elements.

17. The system of claim 11 , wherein the stored content object is an image, and wherein the content of the stored content object may be represented by a vector having plurality of elements, and wherein the processors are further operable when executing the instructions to sort the stored content objects based at least in part on determining a median value of each of the plurality of elements.