OPTIMIZING A CONTENT INDEX FOR TARGET AUDIENCE QUERIES

• US 20150347482A1
• Filed: 08/10/2015
• Published: 12/03/2015
• Est. Priority Date: 12/04/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Bati, Hardik N., Mehta, Nihar N.
• Granted Patent: US 9,779,122 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Apparatus and methods are provided for indexing electronic content to be served to users'"'"' mobile and/or stationary communications and computing devices. An index is composed of multiple slices, with each slice storing multiple entries and each entry representing one content item or one campaign or collection of content items. An entry is populated with tokens representing attribute/value pairs of a target audience of the content item and/or property/value pairs of the item or the item'"'"'s campaign. A query or request to identify content items for serving to a particular user is similarly formatted with tokens representing attribute/value pairs of the user and/or item/campaign. Queries can then be executed rapidly across any or all index entries in any or all slices. Within a slice, entries may be sorted by value or score, and integer components within an individual entry may be sorted to facilitate rapid comparison with a query.

Claims

1. A method of operating a content index, the method comprising:

for each of multiple collections of electronic content, storing in an index a corresponding entry comprising a set of attribute tokens, wherein;

each attribute token represents an attribute of a target audience of the corresponding collection of electronic content and an associated value of the attribute;

the attribute tokens are arranged as one or more conjunctions of disjunctions; and

the attribute tokens are sorted into inverse order of a probability with which the attributes and associated values will match a set of attributes and associated values of an unknown target user of a future request for electronic content;

receiving a request for electronic content to serve to a first target user, the request comprising one or more attributes of the first target user;

for each of multiple entries of the index;

comparing the attributes represented by the attribute tokens with the one or more attributes of the request; and

aborting the comparison as soon as an attribute token conflicts with the one or more attributes, if such a conflict exists; and

in response to the request, outputting electronic content collections corresponding to one or more entries of the index.

2. The method of claim 1, wherein:

an index entry corresponding to a collection of electronic content further comprises a set of property tokens, each property token representing a property of the corresponding collection of electronic content; and

the request for electronic content further comprises one or more properties of electronic content desired to be served to the first user.

3. The method of claim 2, further comprising, for each of the multiple entries of the index:

comparing the one or more properties of the request with the properties represented by the set of property tokens of the index entry.

4. The method of claim 1, wherein storing in the index a first entry corresponding to a first collection of electronic content comprises:

receiving a first set of properties of the first collection of electronic content;

mapping the first set of properties to a first set of property tokens;

receiving a first set of attributes of a target audience of the first collection of electronic content, and corresponding values of the first set of attributes;

mapping the first set of attributes to a first set of attribute tokens; and

writing the first entry to the index to represent the first collection of electronic content, wherein the first entry comprises the first set of property tokens and the first set of attribute tokens.

5. The method of claim 4, further comprising, prior to writing the first entry to the index:

organizing the first set of attribute tokens as a sequence of token groups joined by conjunctions; and

within each token group comprising two or more attribute tokens;

sorting the two or more attribute tokens into the inverse order of probability with which the represented attributes and associated values will match the unknown target user of a future request for electronic content; and

joining the two or more attribute tokens by disjunctions.

6. The method of claim 1, further comprising:

analyzing feedback from multiple servings of collections of electronic content to calculate scores of the electronic content collections; and

sorting entries of the index according to their scores.

7. The method of claim 6, wherein the scores represent monetary values of the electronic content collections.

8. The method of claim 1, further comprising maintaining the index by:

separately queuing modifications to multiple entries in the index; and

for each index entry having multiple modifications queued;

collapsing the multiple modifications to a single modification; and

applying the single modification in place of the multiple modifications.

9. The method of claim 1, wherein:

each of the multiple electronic content collections is a campaign; and

each campaign includes one or more servable content items.

10. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

for each of multiple collections of electronic content, store in an index a corresponding entry comprising a set of attribute tokens, wherein;

each attribute token represents an attribute of a target audience of the corresponding collection of electronic content and an associated value of the attribute;

the attribute tokens are arranged as one or more conjunctions of disjunctions; and

the attribute tokens are sorted into inverse order of a probability with which the attributes and associated values will match a set of attributes and associated values of an unknown target user of a future request for electronic content;

receive a request for electronic content to serve to a first target user, the request comprising one or more attributes of the first target user;

for each of multiple entries of the index;

compare the attributes represented by the attribute tokens with the one or more attributes of the request; and

abort the comparison as soon as an attribute token conflicts with the one or more attributes, if such a conflict exists; and

in response to the request, output electronic content collections corresponding to one or more entries of the index.

11. The apparatus of claim 10, wherein:

an index entry corresponding to a collection of electronic content further comprises a set of property tokens, each property token representing a property of the corresponding collection of electronic content; and

the request for electronic content further comprises one or more properties of electronic content desired to be served to the first user.

12. The apparatus of claim 11, the memory further storing instructions that, when executed by the one or more processors, cause the apparatus to, for each of the multiple entries of the index:

compare the one or more properties of the request with the properties represented by the set of property tokens of the index entry.

13. The apparatus of claim 10, wherein storing in the index a first entry corresponding to a first collection of electronic content comprises:

receiving a first set of properties of the first collection of electronic content;

mapping the first set of properties to a first set of property tokens;

receiving a first set of attributes of a target audience of the first collection of electronic content, and corresponding values of the first set of attributes;

mapping the first set of attributes to a first set of attribute tokens; and

writing the first entry to the index to represent the first collection of electronic content, wherein the first entry comprises the first set of property tokens and the first set of attribute tokens.

14. The apparatus of claim 13, the memory further storing instructions that, when executed by the one or more processors, cause the apparatus to, prior to writing the first entry to the index:

organize the first set of attribute tokens as a sequence of token groups joined by conjunctions; and

within each token group comprising two or more attribute tokens;

sort the two or more attribute tokens into the inverse order of probability with which the represented attributes and associated values will match the unknown target user of a future request for electronic content; and

join the two or more attribute tokens by disjunctions.

15. The apparatus of claim 10, the memory further storing instructions that, when executed by the one or more processors, cause the apparatus to:

analyze feedback from multiple servings of collections of electronic content to calculate scores of the electronic content collections; and

sort entries of the index according to their scores.

16. The apparatus of claim 10, wherein:

each of the multiple electronic content collections is a campaign; and

each campaign includes one or more servable content items.

17. A system, comprising:

a first computer readable medium storing an index;

an index module comprising a second computer readable medium storing instructions that, when executed, cause the system to, for each of multiple collections of electronic content, store in the index a corresponding entry comprising a set of attribute tokens, wherein;

each attribute token represents an attribute of a target audience of the corresponding collection of electronic content and an associated value of the attribute;

the attribute tokens are arranged as one or more conjunctions of disjunctions; and

the attribute tokens are sorted into inverse order of a probability with which the attributes and associated values will match a set of attributes and associated values of an unknown target user of a future request for electronic content; and

a query module comprising a third computer readable medium storing instructions that, when executed, cause the system to;

receive a request for electronic content to serve to a first target user, the request comprising one or more attributes of the first target user;

for each of multiple entries of the index;

compare the attributes represented by the attribute tokens with the one or more attributes of the request; and

abort the comparison as soon as an attribute token conflicts with the one or more attributes, if such a conflict exists; and

in response to the request, output electronic content collections corresponding to one or more entries of the index.

18. The system of claim 17, wherein:

an index entry corresponding to a collection of electronic content further comprises a set of property tokens, each property token representing a property of the corresponding collection of electronic content;

the request for electronic content further comprises one or more properties of electronic content desired to be served to the first user; and

the third computer readable medium further stores instructions that, when executed, cause the system to, for each of the multiple entries of the index, compare the one or more properties of the request with the properties represented by the set of property tokens of the index entry.

19. The system of claim 17, wherein storing in the index a first entry corresponding to a first collection of electronic content comprises:

receiving a first set of properties of the first collection of electronic content;

mapping the first set of properties to a first set of property tokens;

receiving a first set of attributes of a target audience of the first collection of electronic content, and corresponding values of the first set of attributes;

mapping the first set of attributes to a first set of attribute tokens; and

writing the first entry to the index to represent the first collection of electronic content, wherein the first entry comprises the first set of property tokens and the first set of attribute tokens.

20. The system of claim 19, the second computer readable medium further storing instructions that, when executed, cause the system to, prior to writing the first entry to the index:

organize the first set of attribute tokens as a sequence of token groups joined by conjunctions; and

within each token group comprising two or more attribute tokens;

sort the two or more attribute tokens into the inverse order of probability with which the represented attributes and associated values will match the unknown target user of a future request for electronic content; and

join the two or more attribute tokens by disjunctions.