Efficient indexing of feed updates for content feeds

• US 10,353,907 B1
• Filed: 05/23/2016
• Issued: 07/16/2019
• Est. Priority Date: 03/30/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gupta, Ankit, Shah, Parinkumar D., Ghike, Swapnil A., Hiremagalur Venkatesh, Raghu Ram, Gupta, Shubham, Sumbaly, Roshan R.
• Primary Examiner(s): Tran, Loc
• Application Number:
  US15/162,491
• Time in Patent Office: 1,149 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

The disclosed embodiments provide a system for processing data. During operation, the system stores a set of feed updates associated with a set of entities in descending chronological order within a set of resizable blocks. For each entity in the set of entities, the system generates an index containing one or more lists of resizable blocks storing a subset of the feed updates associated with the entity, wherein the one or more lists are sorted in descending chronological order. The system then uses the index to generate a content feed containing a selection of the feed updates for outputting to a viewer.

Claims

1. A method, comprising:

for each entity in a set of entities within an online network, generating a corresponding index comprising one or more lists of resizable blocks storing feed updates associated with the entity, wherein each list of resizable blocks is associated with a different feed update type;

storing a set of new feed updates associated with the entities in descending chronological order by, for each entity;

using the index corresponding to the entity to match one or more attributes of a new feed update associated with the entity to a key for a list of resizable blocks, wherein;

each resizable block represents a storage block in memory; and

the key for the list of resizable blocks includes the feed update type associated with the list and an entity ID for the entity;

writing the new feed update to a first resizable block in the list; and

when a size limit of the first resizable block is exceeded by a write of another new feed update to the first resizable block;

adding a second resizable block to the list; and

storing a portion of feed updates associated with the first resizable block in the second resizable block;

using the indexes to generate, by a computer system, a content feed comprising a selection of stored feed updates for outputting to a viewer;

generating a visual representation of the content feed comprising the selected feed updates; and

presenting the visual representation of the content feed to the viewer.

2. The method of claim 1, wherein using the indexes to generate the content feed comprises:

identifying a subset of the entities associated with the viewer;

using the indexes to retrieve a set of recent feed updates associated with the subset of entities;

calculating a set of relevance scores representing a relevance of the recent feed updates to the viewer; and

ranking the recent feed updates by the relevance scores.

3. The method of claim 2, wherein using the indexes to generate the content feed further comprises:

applying one or more filters to the set of recent feed updates prior to ranking the recent feed updates by the relevance scores.

4. The method of claim 2, wherein using the indexes to retrieve the set of recent feed updates comprises:

using metadata in the indexes to access a subset of the resizable blocks comprising a time range of feed updates in the content feed.

5. The method of claim 4, wherein the metadata comprises:

a first timestamp of an oldest feed update in a resizable block;

a second timestamp of a newest feed update in the resizable block; and

a number of feed updates in the resizable block.

6. The method of claim 1, wherein storing the portion of feed updates associated with the first resizable block in the second resizable block comprises:

moving the portion of feed updates from the first resizable block to the second resizable block.

7. The method of claim 1, wherein the one or more attributes comprise:

an entity identifier; and

a feed update type.

8. The method of claim 1, wherein the entity is at least one of:

a user;

a company;

an educational institution;

a group;

a skill; and

a tag.

9. The method of claim 1, wherein each of the feed updates comprises:

an entity identifier;

an update identifier;

a feed update type; and

a time of creation.

10. The method of claim 1, wherein the set of feed updates comprises at least one of:

a post;

an article;

a job listing;

a like;

a share;

a comment;

a follow;

a connection;

an interaction with a group;

a profile update;

a profile view;

a click; and

a hide.

19. The method of claim 1, wherein:

each resizable block in the list of resizable blocks is associated with a unique key that includes the entity ID, the feed update type and a non-negative integer representing a position of the resizable block in the list of resizable blocks.

11. 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 entity in a set of entities within an online network, generate a corresponding index comprising one or more lists of resizable blocks storing feed updates associated with the entity, wherein each list of resizable blocks is associated with a different feed update type;

store a set of new feed updates associated with the entities in descending chronological order by, for each entity;

using the index corresponding to the entity to match one or more attributes of a new feed update associated with the entity to a key for a list of resizable blocks, wherein;

each resizable block represents a storage block in memory; and

the key for the list of resizable blocks includes the feed update type associated with the list and an entity ID for the entity;

writing the new feed update to a first resizable block in the list; and

when a size limit of the first resizable block is exceeded by a write of another new feed update to the first resizable block;

adding a second resizable block to the list; and

storing a portion of feed updates associated with the first resizable block in the second resizable block;

use the indexes to generate a content feed comprising a selection of stored feed updates for outputting to a viewer;

generate a visual representation of the content feed comprising the selected feed updates; and

present the visual representation of the content feed to the viewer.

12. The apparatus of claim 11, wherein using the indexes to generate the content feed comprises:

identifying a subset of the entities associated with the viewer;

using the indexes to retrieve a set of recent feed updates associated with the subset of entities;

calculating, for the set of recent feed updates, a set of relevance scores representing a relevance of the recent feed updates to the viewer; and

ranking the recent feed updates by the relevance scores.

13. The apparatus of claim 12, wherein using the indexes to retrieve the set of recent feed updates comprises:

using metadata in the index to retrieve a subset of the resizable blocks comprising a time range of feed updates in the content feed.

14. The apparatus of claim 13, wherein the metadata comprises:

a first timestamp of an oldest feed update in a resizable block;

a second timestamp of a newest feed update in the resizable block; and

a number of feed updates in the resizable block.

15. The apparatus of claim 11, wherein storing the portion of feed updates associated with the first resizable block in the second resizable block comprises:

moving the portion of feed updates from the first resizable block to the second resizable block.

16. The apparatus of claim 11, wherein the one or more attributes comprise:

an entity identifier; and

a feed update type.

20. The apparatus of claim 11, wherein:

each resizable block in the list of resizable blocks is associated with a unique key that includes the entity ID, the feed update type and a non-negative integer representing a position of the resizable block in the list of resizable blocks.

17. A system, comprising:

one or more processors; and

a storage mechanism comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to store a set of feed updates associated with a set of entities within an online network in descending chronological order by, for each entity;

using the index corresponding to the entity to match one or more attributes of a new feed update associated with the entity to a key for a list of resizable blocks, wherein;

each resizable block represents a storage block in memory; and

the key for the list of resizable blocks includes the feed update type associated with the list and an entity ID for the entity;

writing the new feed update to a first resizable block in the list; and

when a size limit of the first resizable block is exceeded by a write of another new feed update to the first resizable block;

adding a second resizable block to the list; and

storing a portion of feed updates associated with the first resizable block in the second resizable block; and

an indexing apparatus comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to;

for each entity in a set of entities within an online network, generating a corresponding index comprising one or more lists of resizable blocks storing feed updates associated with the entity, wherein each list of resizable blocks is associated with a different feed update type;

use the indexes to generate a content feed comprising a selection of stored feed updates for outputting to a viewer;

generate a visual representation of the content feed comprising the selected feed updates; and

present the visual representation of the content feed to the viewer.

18. The system of claim 17, wherein using the indexes to generate the content feed comprises:

identifying a subset of the entities associated with the viewer;

using the indexes to retrieve a set of recent feed updates associated with the subset of entities;

calculating, for the set of recent feed updates, a set of relevance scores representing a relevance of the recent feed updates to the viewer; and

ranking the recent feed updates by the relevance scores.