LOCALLY OPTIMIZED FEATURE SPACE ENCODING OF DIGITAL DATA AND RETRIEVAL USING SUCH ENCODING

• US 20170154216A1
• Filed: 11/30/2015
• Published: 06/01/2017
• Est. Priority Date: 11/30/2015
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Kalantidis, Ioannis, Shamma, David, Kennedy, Lyndon
• Granted Patent: US 9,659,214 B1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 10/763 Non-hierarchical techniques, e.g. based on statistics of modelling distributions
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 30/19127 Extracting features by transforming the feature space, e.g. multidimensional scaling; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A digital document is represented as a set of codes comprising indices into a feature space comprising a number of subspaces, each code corresponds to one subspace and identifying a cell within the subspace. Each digital document can be represented by a code set, and the code set can be used as selection criteria for identifying a number of digital documents using each digital document'"'"'s corresponding code set. By way of some non-limiting examples, digital document code sets can be used to identify similar or different digital images, used to identify duplicate or nearly-duplicate digital images, used to identify similar and/or different digital images for inclusion in a recommendation, used to identify and rank digital images in a set of search results.

Claims

1. A method comprising:

generating, by a computing device, a feature vector for a digital document, the generated feature vector comprising a plurality of features of the digital document;

partitioning, by the computing device, the digital document'"'"'s feature vector into a plurality of feature vector segments, each feature vector segment corresponding to a subspace of a plurality of subspaces of a feature space, each subspace comprising a plurality of cells;

generating, by the computing device, a code vector for the digital document, each code in the digital document'"'"'s code vector corresponding to a respective subspace of the plurality subspaces of the feature space and identifying, using a corresponding feature vector segment, a cell of the respective subspace'"'"'s plurality of cells with which the digital document is most similar relative to other cells of the plurality in the respective subspace; and

making a determination, by the computing device, whether to select the digital document, in response to a digital document request, the determination comprising determining a score for the digital document by comparing the digital document'"'"'s code vector and a code vector associated with the digital document request to determine a number of matches and making the determination using the determined score.

2. The method of claim 1, wherein the digital document is a digital image, the feature vector comprising a number of features of the digital image.

3. The method of claim 1, generating a code vector further comprising:

determining, by the computing device, a vector representation for each cell in each subspace of the feature space using a plurality of digital documents, the vector representation for a given cell and a given subspace being determined using a corresponding segment of the vector representation of each of a number of digital documents of the plurality mapped to the given cell;

for each subspace of the plurality, determining a code for the digital document'"'"'s code vector corresponding to the subspace, the corresponding code identifying the cell of the plurality of cells in the subspace whose feature vector is more similar to the segment of the digital document'"'"'s vector representation corresponding to the subspace than the feature vectors of other cells of the plurality.

4. The method of claim 1, the determining a score comprising determining a similarity score between the digital document'"'"'s code vector and the digital document request'"'"'s code vector, the similarity score identifying a number of feature subspaces in which the digital document shares a same cell as the request, as indicated by the digital document'"'"'s code vector and the request'"'"'s code vector.

5. The method of claim 4, further comprising:

determining, by the computing device and using the number of common cells, whether the digital document is a near duplicate of another digital document represented by the request'"'"'s code vector.

6. The method of claim 1, making a determination further comprising:

the digital document request comprising a search request, the request'"'"'s code vector comprising search criteria for the search request, and the digital document is one of a plurality of digital documents each one having a corresponding code vector, the making a determination further comprising;

for each digital document of the plurality, determining the score for the digital document, the score representing a similarity between the digital document'"'"'s code vector and the digital document request'"'"'s associated code vector, the similarity being the number of feature subspaces in which the digital document shares a same cell as the request, as indicated by the digital document'"'"'s code vector and the request'"'"'s code vector;

ranking, by the computing device, the plurality of digital documents using the similarity determined for each digital document of the plurality; and

selecting, by the computing device, a number of top-ranked documents from the plurality of documents.

7. The method of claim 6, further comprising:

creating, by the computing device, an inverted index for each cell of each feature subspace, a cell'"'"'s inverted index identifying each digital document of the plurality mapped to the cell;

for each feature subspace'"'"'s code in the search criteria'"'"'s code vector;

performing, by the computing device, an inverted index look up using the feature subspace'"'"'s code to identify each digital document of the plurality in the inverted index that is associated with the cell identified using the feature subspace'"'"'s code; and

incrementing, by the computing device, the score associated with each identified digital document by one.

8. The method of claim 7, the performing and incrementing elements performed for each feature subspace are performed in parallel.

9. A system comprising:

at least one computing device, each computing device comprising a processor and a storage medium for tangibly storing thereon program logic for execution by the processor, the stored program logic comprising;

generating logic executed by the processor for generating a feature vector for a digital document, the generated feature vector comprising a plurality of features of the digital document;

partitioning logic executed by the processor for partitioning the digital document'"'"'s feature vector into a plurality of feature vector segments, each feature vector segment corresponding to a subspace of a plurality of subspaces of a feature space, each subspace comprising a plurality of cells;

generating logic executed by the processor for generating a code vector for the digital document, each code in the digital document'"'"'s code vector corresponding to a respective subspace of the plurality subspaces of the feature space and identifying, using a corresponding feature vector segment, a cell of the respective subspace'"'"'s plurality of cells with which the digital document is most similar relative to other cells of the plurality in the respective subspace; and

making logic executed by the processor for making a determination whether to select the digital document, in response to a digital document request, the determination comprising determining a score for the digital document by comparing the digital document'"'"'s code vector and a code vector associated with the digital document request to determine a number of matches and making the determination using the determined score.

10. The system of claim 9, wherein the digital document is a digital image, the feature vector comprising a number of features of the digital image.

11. The system of claim 9, the generating logic executed by the processor for generating a code vector further comprising:

determining logic executed by the processor for determining a vector representation for each cell in each subspace of the feature space using a plurality of digital documents, the vector representation for a given cell and a given subspace being determined using a corresponding segment of the vector representation of each of a number of digital documents of the plurality mapped to the given cell;

determining logic executed by the processor for determining, for each subspace of the plurality, a code for the digital document'"'"'s code vector corresponding to the subspace, the corresponding code identifying the cell of the plurality of cells in the subspace whose feature vector is more similar to the segment of the digital document'"'"'s vector representation corresponding to the subspace than the feature vectors of other cells of the plurality.

12. The system of claim 9, the determining logic executed by the processor for determining a score further comprising determining logic executed by the processor for determining a similarity score between the digital document'"'"'s code vector and the digital document request'"'"'s code vector, the similarity score identifying a number of feature subspaces in which the digital document shares a same cell as the request, as indicated by the digital document'"'"'s code vector and the request'"'"'s code vector.

13. The system of claim 12, the stored program logic further comprising:

determining logic executed by the processor for determining, using the number of common cells, whether the digital document is a near duplicate of another digital document represented by the request'"'"'s code vector.

14. The system of claim 9, further comprising:

the digital document request comprising a search request, the request'"'"'s code vector comprising search criteria for the search request, and the digital document is one of a plurality of digital documents each one having a corresponding code vector, the making logic executed by the processor for making a determination further comprising;

determining logic executed by the processor for determining, for each digital document of the plurality, the score for the digital document, the score representing a similarity between the digital document'"'"'s code vector and the digital document request'"'"'s associated code vector, the similarity being the number of feature subspaces in which the digital document shares a same cell as the request, as indicated by the digital document'"'"'s code vector and the request'"'"'s code vector;

ranking logic executed by the processor for ranking the plurality of digital documents using the similarity determined for each digital document of the plurality; and

selecting logic executed by the processor for selecting a number of top-ranked documents from the plurality of documents.

15. The system of claim 14, the stored program logic further comprising:

creating logic executed by the processor for creating an inverted index for each cell of each feature subspace, a cell'"'"'s inverted index identifying each digital document of the plurality mapped to the cell;

for each feature subspace'"'"'s code in the search criteria'"'"'s code vector;

performing logic executed by the processor for performing an inverted index look up using the feature subspace'"'"'s code to identify each digital document of the plurality in the inverted index that is associated with the cell identified using the feature subspace'"'"'s code; and

incrementing logic executed by the processor for incrementing the score associated with each identified digital document by one.

16. The system of claim 15, the performing and incrementing logic being performed for each feature subspace in parallel.

17. A computer readable non-transitory storage medium for tangibly storing thereon computer readable instructions that when executed cause at least one processor to:

generate a feature vector for a digital document, the generated feature vector comprising a plurality of features of the digital document;

partition the digital document'"'"'s feature vector into a plurality of feature vector segments, each feature vector segment corresponding to a subspace of a plurality of subspaces of a feature space, each subspace comprising a plurality of cells;

generate a code vector for the digital document, each code in the digital document'"'"'s code vector corresponding to a respective subspace of the plurality subspaces of the feature space and identifying, using a corresponding feature vector segment, a cell of the respective subspace'"'"'s plurality of cells with which the digital document is most similar relative to other cells of the plurality in the respective subspace; and

make a determination whether to select the digital document, in response to a digital document request, the determination comprising determining a score for the digital document by comparing the digital document'"'"'s code vector and a code vector associated with the digital document request to determine a number of matches and making the determination using the determined score.

18. The computer readable non-transitory storage medium of claim 17, wherein the digital document is a digital image, the feature vector comprising a number of features of the digital image.

19. The computer readable non-transitory storage medium of claim 17, the computer readable instructions that when executed cause the at least one processor to generate a code vector further cause the at least one processor to:

determine a vector representation for each cell in each subspace of the feature space using a plurality of digital documents, the vector representation for a given cell and a given subspace being determined using a corresponding segment of the vector representation of each of a number of digital documents of the plurality mapped to the given cell;

for each subspace of the plurality, determine a code for the digital document'"'"'s code vector corresponding to the subspace, the corresponding code identifying the cell of the plurality of cells in the subspace whose feature vector is more similar to the segment of the digital document'"'"'s vector representation corresponding to the subspace than the feature vectors of other cells of the plurality.

20. The computer readable non-transitory storage medium of claim 17, the computer readable instructions that when executed cause the at least one processor to determine a score further cause the at least one processor to determine a similarity score between the digital document'"'"'s code vector and the digital document request'"'"'s code vector, the similarity score identifying a number of feature subspaces in which the digital document shares a same cell as the request, as indicated by the digital document'"'"'s code vector and the request'"'"'s code vector.

21. The computer readable non-transitory storage medium of claim 20, the computer readable instructions that when executed further cause the at least one processor to:

determine, using the number of common cells, whether the digital document is a near duplicate of another digital document represented by the request'"'"'s code vector.

22. The computer readable non-transitory storage medium of claim 17:

the digital document request comprising a search request, the request'"'"'s code vector comprising search criteria for the search request, and the digital document is one of a plurality of digital documents each one having a corresponding code vector, the computer readable instructions that when executed cause the at least one processor to make a determination further cause the at least one processor to;

for each digital document of the plurality, determine the score for the digital document, the score representing a similarity between the digital document'"'"'s code vector and the digital document request'"'"'s associated code vector, the similarity being the number of feature subspaces in which the digital document shares a same cell as the request, as indicated by the digital document'"'"'s code vector and the request'"'"'s code vector;

rank the plurality of digital documents using the similarity determined for each digital document of the plurality; and

select a number of top-ranked documents from the plurality of documents.

23. The computer readable non-transitory storage medium of claim 22, the computer readable instructions that when executed further cause the at least one processor to:

create an inverted index for each cell of each feature subspace, a cell'"'"'s inverted index identifying each digital document of the plurality mapped to the cell;

for each feature subspace'"'"'s code in the search criteria'"'"'s code vector;

perform, an inverted index look up using the feature subspace'"'"'s code to identify each digital document of the plurality in the inverted index that is associated with the cell identified using the feature subspace'"'"'s code; and

increment the score associated with each identified digital document by one.

24. The computer readable non-transitory storage medium of claim 23, the performing and incrementing performed for each feature subspace are performed in parallel.