Managing presentation of online content

A method and apparatus for selectively publishing user-provided content items to other users is provided. In some instances, the content items are excluded from being rendered to a user according to one or more blocks that block the user from viewing content items provided by certain members. Managing blocks and excluding content is more efficiently achieved through the implementation of a Bloom filter that contains the blocked pairs of users. The Bloom filter can, using few computing resources, be queried to determine if a block does not exist between two users. If the Bloom filter returns an indication that a block might exist, the apparatus determines if a block is stored in an LRU cache of recently retrieved blocks. If the LRU cache does not identify a block, then a call to retrieve one or more blocked pairs is made to a data storage.

TECHNICAL FIELD

The present disclosure relates to computer data processing and, more specifically to, managing presentation of content items to users in an online social network.

BACKGROUND

In online social networks, members can post content items for presentation to other members. Typically, members receive only the content items posted by members that they have approved of in some way such as by accepting an invitation. The posts can have a variety of formats, including content items such as a user profile, a user status, content items shared by the user, comments by the user on content items posted by another user, and connections, links, or friendships between users. Different social networks can receive, manage, and present, different content items formats among their respective members.

In some social networks, a member can block other members from viewing content items posted by the blocking member. Further, the blocking member is blocked from accessing or viewing content items posted by the blocked members. A member might desire to block the blocked member for a variety of reasons such as the blocked member posting too much content items, the blocked member posting content items that the member finds distasteful, or the member simply not wanting to pursue a connection with the blocked member. Additionally, in some social networks, a first member “de-friending” (or removing) a second member as a connection is not sufficient to block the second member's content from being presented to the first member and/or to block the first member's content from being presented to the second member.

DETAILED DESCRIPTION

General Overview

In a social network, users can connect with other users in a number of ways. For example, some social networks allow users to create personal networks including friends, professional connections, family, and/or other acquaintances. In some social networks, users can subscribe to content items published by other users. In social networks, some users can block other users from viewing published content items and can block other user's content items from being presented to them. Thus, to a blocked user, the blocking user and his content items are not visible on the social network. The blocked user and the blocking user are together referred to as a blocked pair. Other users, however, can still view and interact with the blocked user's content items.

When a user visits a social networking site, the user is presented with content items published by other users. The other users can be within the user's personal network or outside the user's personal network. For example, the user may be presented with content items published by a second degree connection (e.g., a friend of a friend). Typically, users do not object to viewing content items published by people outside of their social network. However, a user may object to another user or content items posted by the other user of the social network and request that the social network block the user. Once the user is blocked, no content items posted by the user is provided to the other user in the blocked pair.

Due to the sheer number of users in the social network and that users can each have more than one hundred connections, checking for blocked users when rendering pages in the social network can be require large amounts of computational resources such as computing resources, memory resources, and network resources. To illustrate, each page presented to the user can include hundreds of user-submitted content items, each submitted by different users. When rendering a page, the author of each content item and the user for whom the page is rendered is compared to a list of blocked pairs. Because a page can include a great number of content items, this process is repeated hundreds of times, each resulting in a database hit. Additionally, some content items may be selected for a particular member because the author of the content item is a friend of a friend of a friend of the particular member. A determination should be made regarding whether the particular member blocked, not only the author of the content item, but also any of the “intermediate” friends between the author and the particular member. To reduce the number of database hits, a Bloom filter is used to store the blocked pairs. The Bloom filter results in no false negatives that can cause content items provided by a blocked user to be shown, requires less memory, and can be quickly queried.

System Overview

FIG. 1is a diagram of a system100for providing an online social network, according to some embodiments. System100is a computer-based system. The various components of system100are implemented at least partially by hardware at one or more computing devices, such as one or more hardware processors executing instructions stored in one or more memories for performing various functions described herein. System100illustrates only one of many possible arrangements of components configured to perform the functionality described herein. Other arrangements may include fewer or different components, and the division of work between the components may vary depending on the arrangement.

System100includes one or more user devices102A and102B running clients104A and104B, a network106, a server108, and data storage114. Each of the user devices102A and102B, server108, and data storage114is in wired or wireless communication with the network106.

User devices102A,102B comprise computing devices, including but not limited to, work stations, personal computers, general purpose computers, laptops, Internet appliances, hand-held devices, wireless devices, wired devices, portable or mobile devices, wearable computers, cellular or mobile phones, portable digital assistants (PDAs), smart phones, tablets, multi-processor systems, microprocessor-based or programmable consumer electronics, game consoles, set-top boxes, network PCs, mini-computers, and the like. Each of the user devices102A,102B includes clients104A,104B. Clients104A,104B include, but are not limited to, applications such as a web browser, software, and/or other executable instructions to facilitate various aspects of the techniques described herein. Clients104A,104B may also include additional applications or other interface capabilities to communicate with the server108and/or data storage114. User devices102A,102B may, depending on the embodiment, be located geographically dispersed from each other. Although two user devices102A,102B are shown inFIG. 1, more or less than two user devices102A,102B may be included in system100.

Network106comprises a communications network, such as a local area network (LAN), a wireless LAN (WLAN), a wide area network (WAN), a wireless WAN (WWAN), a metropolitan area network (MAN), an ad hoc network, an intranet, an extranet, a virtual private network (VPN), a portion of the Internet, the Internet, a portion of a public switched telephone network (PSTN), a cellular network, or a combination of two or more such networks. When network106comprises a public network, security features (e.g., VPN/SSL secure transport) may be included to ensure authorized access within system100.

Server108comprises one or more servers, computers, processors, database servers, and/or computing devices configured to communicate with the data storage114and/or user devices102A,102B via network106. Server108hosts one or more applications, websites, social networks, or other visual or user interface mechanisms related to techniques and data described in detail below. Server108may be located at one or more geographically distributed locations. Although one server108is shown inFIG. 1, system100may, depending on the embodiment, comprise one, two, or any number of servers108, which may work alone and/or collectively to provide the functionality described herein.

The server108comprises Bloom filter110and Least Recently Used (LRU) cache112. The Bloom filter110is a Bloom filter used to store records of blocked users for fast retrieval, as described below. The LRU cache112can store blocked pairs for a limited period of time when a page is being rendered. The Bloom filter110and LRU cache112are described below.

Data storage114comprises one or more databases or storage devices configured to store and maintain user profiles, data associated with user profiles, data associated with use of or access to user profiles, data derived from user profiles, and/or instructions for use by server108and/or clients104A,104B as described herein. Data storage114may, in some embodiments, be located at one or more geographically distributed locations relative to server108. Server108and/or clients104A,104B may, in some embodiments, access data storage114via network106. Alternatively, server108may access data storage114without use of network106. As another alternative, data storage114may be included within server108. System100may, depending on the embodiment, comprise one, two, or any number of data storages114configured to individually and/or collectively store the data described herein.

Blocking of Users

FIG. 2is a flowchart of a method200to add a blocked user to a bloom filter, according to some embodiments. The method200can be performed by the server108. The method200facilitates adding a blocked pair to a Bloom filter110. At some future point in time when rendering a page, the server108can query the Bloom filter110to identify whether two users constitute a blocked pair. The addition of the blocked pair to the Bloom filter110results in fewer calls made to the data storage114. Calling the data storage114is a computationally expensive process and reducing the number of calls can result in better performance of the server108.

In an operation202, the server108receives an instruction from a first user device102A operated by a first user to block a second user. By blocking the second user, the first user will no longer be able to view content items posted by, and/or commented on by, the second user, including a profile of the second user and, optionally, a listing of other users who are connected with the second user. Additionally or alternatively, by virtue of the first user blocking the second user, the second user will no longer be able to view content items posted by the first user, including a profile of the first user and a listing of other users who are connected with the first user.

FIG. 3depicts a portion of a user interface300comprising an option to block a user, according to some embodiments. The client104A on the user device102A presents the user interface300to the user. The instruction of operation202can be received via the user interface300. The user interface300comprises a presentation of a user profile of a second user, John Q. Smith. The user profile comprises the name302of the second user, an optional photo304of the user, and a menu306of options from which the first user can select.

As depicted, the menu306comprises an option to message John, an option to recommend John to other users, and an option to block John. In other embodiments, the menu306can include more or fewer options for interacting with John. For example, users can be given additional options such as, but not limited to, following John, subscribing to content items posted by John, subscribing to content items commented on by John, subscribing to content items “liked” by John, connecting to John, joining a group managed by John, and other ways of interacting with John or content items with which John interacted.

In some instances, the option to block John can be presented outside of a menu, such as appearing as a button in a dedicated location on John's profile page. In other instances, an option to block John can appear on other web pages hosted by the social network, such as a messaging page, a feed of content items presented to the first user, or a group or event page within the social network.

In some instances, when the option to block John is selected, a prompt to confirm that John be blocked by the first user is presented to the first user. Upon receiving the confirmation, the process200continues to operation206.

In the social network, each user is identifiable via a numerical user identifier assigned to the user when the user first registered with the social network. Each of the first and second user has a unique identifier. The unique identifiers can be stored in the data storage114and retrieved by the server108. In some embodiments, the data storage114has two columns, one for the user identifier of the member who initiated the block and the other for the user identifier of the member who was blocked.

Referring back to operation206ofFIG. 2, in some embodiments, the retrieved identifiers are compared to determine which of the two identifiers has a lower numerical value. For example, user identifier 123456789 has a lower numerical value that user identifier 987654321. The server108orders the user identifiers such that the user identifier having the lower numerical value is ordered before the user identifier having the higher numerical value, regardless of which user initiated the block. Once ordered, the user identifiers are concatenated into a single string. Continuing the above example, the server generates the concatenated string “123456789987654321”.

Because the user identifiers are ordered in the same way for the blocks, the blocks are bi-directional, meaning that neither user can see content items provided by the other. In some embodiments, it may be desirable to order the retrieved user identifiers of the users in the blocked pair based on which user initiated the block. This ordering can be used to facilitate one-directional blocks where the blocker can still view content items with which the blocked user interacts or content items with which the blocked user interacts are not presented to the blocker. For example, if user 123456789 initiated the block, the concatenated string is 123456789987654321; and if user 987654321 initiated the block, the resulting concatenated string is 987654321123456789.

In operation206, the server108stores the concatenated string in a Bloom filter.FIG. 4is an example of a Bloom filter400, according to some embodiments. A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. In a Bloom filter, false positive matches are possible, but false negatives are not. In other words, a query returns either “maybe” being in the set of blocked users or “not” in the set of blocked users. Concatenated strings can be added to the set, but not removed without regenerating the Bloom filter. The probability of false positives increases as more concatenated strings representing blocks are added to the set. An empty Bloom filter is a bit array of m bits, all set to 0. For each Bloom filter, there are k different hash functions defined, each of which maps or hashes the concatenated string to one of the m array positions with a uniform random distribution. As such, the concatenated string is hashed k number of times and is mapped to k different array positions.

For example, as depicted inFIG. 4, a bit array402has 12 bits. In actual implementations that support millions of blocked pairs, a bit array can comprise millions of bits. InFIG. 4, each concatenated string, representing a blocked pair, is hashed three times, using a different hash function each time. As such, concatenated string A404is hashed three times, resulting in bits at positions 0, 3, and 6 being set to 1. Using the same three hash functions, concatenated string B406is hashed three times, resulting in bits at positions 1, 3, and 7 being set to 1. Note that once a bit is set to one, it remains set at 1. Subsequent hashing resulting in the same bit position do not reset or change a bit already set to 1. Likewise, concatenated string C408is hashed using the same hash functions, resulting in bits at positions 0, 7, and 10 being set to 1. When a new instruction to block a member is received, the identifiers are concatenated, hashed using the same hash functions, and, if necessary, up to three additional bits are set to one.

Referring back toFIG. 2, the concatenated string of the users' identifiers is hashed using the different hash functions. The number of hash functions that are used may be selected by an administrator based on the desired false positive rate of the Bloom filter, and the amount of available memory and processing power. As described in connection withFIG. 4, one or more bits in the Bloom filter bit array402are set to 1, indicating that a user pair is maybe a blocked pair.

In an operation208, the concatenated string (or some other association between the blocked pair) is stored in the data storage114. The concatenated string or the individual user identifiers stored in association with one another can be stored in the data storage114with additional metadata, such as a timestamp indicating when the instruction to block was received, an indication of which user initiated the block, a count of a number of times either user has been blocked, or other data.

In some embodiments, the user who requested that another user be blocked can submit an instruction to remove the block using the client104A of the client device102A. The respective identifiers of the blocked users are retrieved from the data storage114. The Bloom filter110is regenerated with concatenated strings corresponding to other blocks still in force but without the concatenated strings corresponding to the removed block. The Bloom filter110can be regenerated on request or when an administrator-defined threshold is met. Examples of thresholds may include a number of removal requests received, a number of blocks maintained in the Bloom filter, or a period of time has elapsed.

Rendering of Content Items

FIG. 5is a flowchart of a method500of retrieving content items from a plurality of users for display to a user, according to some embodiments. The method500is performed when content items are displayed (or otherwise presented) to the user. The content items can be displayed as part of a feed associated with the user. The method500is performed to exclude content items associated with a blocked user from the content items rendered at the client104A of the user device102A.

In an operation502, the server108receives an instruction to retrieve content items from the client104A at the user device102A. The instruction can be generated based on a user navigating to the webpage of the social network using a web browser or the user opening a social network application. In some instances, the user can navigate within the client104A to particular content items, such as a particular post or set of comments.

In an operation504, for each content item retrieved in response to the request of operation502, the user identifier of the posting user and the user identifier of the requesting user are concatenated, resulting in a query string. Because the retrieved content items are received from a plurality of users, a plurality of query strings are generated. The strings may comprise the user identifier having a lower numerical value followed by the user identifier having the higher numerical value. Operation504may be repeated for each content associated with the content item, such as comments on a content item or “likes” of another content item. For example, a first user may have posted a content item, a second user may added an associated content item by commenting on the content item, and a third user may have added a third content item by virtue of having “liked” the content item. Thus, for a single content item, multiple query strings corresponding to associated content items may be generated.

In an operation506, server108queries the Bloom filter110for each query string of the plurality of query strings. The Bloom filter110contains the blocked pairs in the social network. To query for a particular blocked pair, the query string is fed to each of the k hash functions to get k array positions. If any one of the bits at these positions is 0, the query string is definitely not in the set. If query string is in the set, then all the bits would have been set to 1 when the string was inserted. If all of the elements are 1, then either the query string corresponds to a blocked pair, or the bits have by chance been set to 1 during the insertion of other concatenated strings resulting in a false positive.

In an operation508, the result of the query is evaluated to determine if the user-pair is a blocked pair. If not (e.g., if any bit is still 0), the method500proceeds to operation522where the content items posted by the other users are rendered at the user device of the requesting user.

If the user-pair may be a blocked pair (e.g., all of the bits are set to 1), the method500continues to operation510to determine if the Bloom filter110has returned a false positive. Depending on how the Bloom filter110is set up, the Bloom filter110can return a false positive as approximately 10% of all positive results. In an operation510, the server108determines whether the query string is stored in the LRU cache112.

The LRU cache112is maintained by the server108in memory separate from the data storage114. The LRU cache112may be maintained in a faster, and more expensive memory than memory included in the data storage114. The LRU cache114stores one or more query strings that correspond to blocked pairs stored in the data storage114for a limited period of time. The period of time may be selected by an administrator based on the amount of time it typically takes the server108to render the content items at the user device102A.

If the query string is not stored in the LRU cache112, in operation512, at least a portion of the blocks including the requesting user (such as where the user has been blocked by another user or where the user has blocked another user) are retrieved by the server108from the data storage114. Because this operation involves reading from data storage114, this operation consumes more computer resources and time than the other operations. In some embodiments, once one query string is identified as possibly being blocked by the Bloom filter110, the server108may retrieve from the data storage114all of the blocked pairs that include the user. Because the data storage114is not limited to storing all of the blocked pairs as concatenated strings, the data storage114can retrieve the blocks according to just the requesting user's identifier. The server108, upon obtaining the blocks from the data storage114, can generate concatenated strings of the users' identifiers as described herein.

In an operation516, the server108caches the concatenated strings (or other data identifying the blocked pair) in the LRU cache112. The LRU cache112stores the blocks for a limited period of time, such as 1 second, 5 seconds, 10 seconds. The LRU cache516can cache blocked pairs corresponding to a plurality of requesting users who are accessing the social network at approximately the same time. The LRU cache112deletes, or writes over, cached blocked pairs (which can be stored as concatenated strings) that are the least recently used in favor of more recently retrieved blocked pairs.

In some embodiments, a separate pre-cache memory is maintained from the LRU cache112. The pre-cache memory is dedicated to storing blocked pairs comprising users who are included in a number of blocked pairs. For these blocked pairs, too many calls are made to the data storage114, slowing down the social network. By caching these blocks separately, they can be accessed more quickly. Some of these users are celebrities whose content items can be auto-populated into user's feeds of content items. To be included in the pre-cache memory, the user has been blocked a threshold number of times, such as 10, 50, 100, or 1,000 times. An administrator can set the threshold to be included in the separate cache. In these embodiments, further operations are performed to check for blocks in the pre-cache memory and to exclude content items posted by the blocked user.

Returning to operation510, if one or more blocks including the requesting user are stored in the LRU cache112, the server108retrieves the blocked pairs from the LRU cache112. The blocked pairs in the LRU includes the blocked pairs that include the user.

In an operation520, the server108excludes content items from blocked users from retrieved content items that is rendered to the user. The content items can be filtered out according to the user identifier of the blocked user.

In an operation522, the content items from unblocked users are rendered. The content items can be rendered as part of a feed of content items, as an article or blog post having one or more comments associated with it, or as another form of web content items. The rendered content items do not include content items from users who are blocked from the viewing user.

Hardware Overview

Computer system600further includes a read only memory (ROM)608or other static storage device coupled to bus602for storing static information and instructions for processor604. A storage device610, such as a magnetic disk or optical disk, is provided and coupled to bus602for storing information and instructions.