Real-time content searching in social network

Patent metadata

Field	Value
Publication number	US-9582587-B2
Application number	US-201615257830-A
Country	US
Kind code	B2
Filing date	Sep 6, 2016
Priority date	Feb 11, 2010
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

Abstract

Indexing and retrieving real time content in a social networking system is disclosed. A user-term index includes user-term partitions, each user-term partition comprising temporal databases. As a post is received from a user, a user identifier, a post identifier, and a post is extracted. An object store communicatively coupled to a temporal database for recently received content is queried to determine whether terms in the post has already been stored. A term identifier is stored in the user-term index with the user and post identifiers. A forward index stores the post by post identifier. Responsive to a search query, the user-term index is searched by the user's connections and the terms. A real time search engine compiles the results of the user-term index query and retrieves the stored posts from the forward index. The search results may then be ranked and cached before presentation to the searching user.

First claim

What is claimed is:

1. A computer implemented method comprising:
receiving a query from a client device associated with a user, the query comprising a term associated with a term identifier;
searching, based in part on the term identifier, a first portion of a user-term index comprising time-ordered database shards of records for post identifiers of posts that include the term and that are associated with connections of the user, where the user-term index comprises shards of records that are searched from newest to oldest, the searching comprising:
matching the term identifier to corresponding term identifiers in shards of records within the selected portion, the selected portion including user identifiers associated with connections of the user, and wherein the matching identifies post identifiers for posts that include the term and are associated with a connection of the user; and

retrieving posts from an index using the identified post identifiers, the retrieved posts for presentation to the user.

2. The computer implemented method of claim 1 , wherein data in the user-term index is arranged by the user identifiers and includes a plurality of user identifiers associated with a plurality of users of a social networking system and a plurality of term identifiers associated with a plurality of terms used by the plurality of users.

3. The computer implemented method of claim 1 , further comprising:
response to not reaching a threshold number of retrieved posts, searching, based in part on the term identifier, a second portion of the user-term index that comprises shards of records that are older than those in the first portion, and the shards of records in the second portion of the user-term index are searched from newest to oldest.

4. The computer implemented method of claim 1 , further comprising:
performing a hash function on the term to generate a term identifier;
querying for the term identifier in an object store associated with the most recent database shard in the selected partition of the user-term index; and
allocating memory in the object store for the term identifier responsive to not finding the term identifier in the object store.

5. The computer implemented method of claim 1 , wherein searching, based in part on the term identifier, the first portion of the user-term index comprising time-ordered database shards of records for post identifiers of posts that include the term and that are associated with connections of the user comprises:
performing a hash function to associate the user identifier to a particular partition of the user-term index; and
selecting the particular partition of the user-term index.

6. The computer implemented method of claim 4 , wherein the hash function takes a modulo of the user identifier by the number of partitions.

7. The computer implemented method of claim 1 , wherein the time-ordered database shards of records comprises a shard for each day of the month, a shard for each month of the year, or a shard for each hour of the day.

8. The computer implemented method of claim 1 , further comprising:
determining that all of the shards are filled to capacity; and
creating a new shard, and setting the new shard as the most recent database shard.

9. The computer implemented method of claim 1 , further comprising:
deleting the oldest shard, of the time-ordered database shards of records; and
deleting an object store associated with the oldest shard.

10. A computer implemented method comprising:
searching, based in part on a term identifier associated with a term, a first portion of a user-term index comprising time-ordered database shards of records for post identifiers of posts that include the term and that are associated with connections of a user, where the user-term index comprises shards of records that are searched from newest to oldest, the searching comprising:
matching the term identifier to corresponding term identifiers in shards of records within the selected portion, the selected portion including user identifiers associated with connections of the user, and wherein the matching identifies post identifiers for posts that include the term and are associated with a connection of the user; and

retrieving posts from an index using the identified post identifiers, the retrieved posts for presentation to the user.

11. The computer implemented method of claim 10 , further comprising:
response to not reaching a threshold number of retrieved posts, searching, based in part on the term identifier, a second portion of the user-term index that comprises shards of records that are older than those in the first portion, and the shards of records in the second portion of the user-term index are searched from newest to oldest.

12. The computer implemented method of claim 10 , further comprising:
performing a hash function on the term to generate a term identifier;
querying for the term identifier in an object store associated with the most recent database shard in the selected partition of the user-term index; and
allocating memory in the object store for the term identifier responsive to not finding the term identifier in the object store.

13. The computer implemented method of claim 10 , wherein searching, based in part on a term identifier associated with a term, the first portion of the user-term index comprising time-ordered database shards of records for post identifiers of posts that include the term and that are associated with connections of a user comprises:
performing a hash function to associate the user identifier to a particular partition of the user-term index; and
selecting the particular partition of the user-term index.

14. The computer implemented method of claim 13 , wherein the hash function takes a modulo of the user identifier by the number of partitions.

15. The computer implemented method of claim 10 , wherein the time-ordered database shards of records comprises a shard for each day of the month, a shard for each month of the year, or a shard for each hour of the day.

16. The computer implemented method of claim 10 , further comprising:
determining that all of the shards are filled to capacity; and
creating a new shard, and setting the new shard as the most recent database shard.

17. The computer implemented method of claim 10 , further comprising:
deleting the oldest shard, of the time-ordered database shards of records; and deleting an object store associated with the oldest shard.

18. A computer program product comprising a non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to perform steps comprising:
receiving a query from a client device associated with a user, the query comprising a term associated with a term identifier;
searching, based in part on the term identifier, a first portion of a user-term index comprising time-ordered database shards of records for post identifiers of posts that include the term and that are associated with connections of the user, where the user-term index comprises shards of records that are searched from newest to oldest, the searching comprising:
matching the term identifier to corresponding term identifiers in shards of records within the selected portion, the selected portion including user identifiers associated with connections of the user, and wherein the matching identifies post identifiers for posts that include the term and are associated with a connection of the user; and

retrieving posts from an index using the identifi

Assignees

• Facebook Inc

Inventors

• Wable Akhil
• Yan Hong
• Ahrens Spencer G
• Lee Yofay Kari
• Yang Guizhen

Classifications

• G06F17/30867 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic

• G06F17/30551

  Physics · mapped topic

• G06F17/30631

  Physics · mapped topic

• G06F17/30628

  Physics · mapped topic