Patent Publication Number: US-8539161-B2

Title: Pre-fetching content items based on social distance

Description:
BACKGROUND 
     Web sites enable users to post messages, images, music, video clips, and more for sharing with other users. For example, some users post hundreds of new photos each month. Because of the high volume and availability of this social content, selecting content of interest for a particular user to consume is time-consuming. Further, because of the high-latency and low-bandwidth of existing cellular data networks, users often have poor experiences when browsing large sets of data such as photos. Some existing systems enable the user to subscribe to receive newly posted content of interest from various content providers or authors. These existing systems, however, do not scale well as the user (and a computing device of the user) quickly becomes inundated with content with each additional subscription. 
     Other existing systems enable the content provider to establish permissions allowing users to access selected content from the content provider. Such systems, however, fail to account for preferences of the user as well as computing resources available to the user. 
     SUMMARY 
     Embodiments of the disclosure enable the selective retrieval of content items based on social distance and device constraints. A list of content items is accessed. Each of the content items on the list has an associated content provider. Each content provider has an associated social distance value. The social distance value represents a relationship between the content provider and a user. Constraints associated with a computing device of the user are determined. One or more of the content items on the list are selectively retrieved based on the social distance value and as a function of the determined constraints. The content items are selectively retrieved prior to receiving a request from the user for the content items. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is an exemplary block diagram illustrating a computing device receiving content items from a plurality of content providers. 
         FIG. 2  is an exemplary flow chart illustrating the selective retrieval of content items based on social distance and device constraints. 
         FIG. 3  is an exemplary flow chart illustrating the pre-fetching of content items associated with ranked content providers. 
         FIG. 4  is an exemplary block diagram illustrating a mobile computing device communicating with a web service to download photos and music. 
     
    
    
     Corresponding reference characters indicate corresponding parts throughout the drawings. 
     DETAILED DESCRIPTION 
     Referring to the figures, embodiments of the disclosure enable, at least, a heuristic pre-fetch of content items based on a social distance between a user  102  and content providers  105 . The pre-fetched content items represent the content items determined to be of possible interest to the user  102  based on the social distance. Aspects of the disclosure prioritize resource usage on a computing device  104  of the user  102  providing greater value per cost (e.g., storage space, battery, bandwidth, etc.). In some embodiments, the computing device  104  includes a mobile computing device  402  such as a mobile telephone with limited resources. 
     The user  102  has a relationship with each of the content providers  105 . The closeness of each relationship varies based on each of the content providers  105 . For example, the user  102  may be a relative or close friend of one of the content providers  105 . In such an example, the user  102  has a strong interest in viewing content items from that content provider  105 . In another example, the user  102  is only an acquaintance of the content provider  105  and has not historically shown interest in the content provider  105  or the content items of the content provider  105 . In such an example, the user  102  may have only marginal interest in viewing new content items from this content provider  105 . 
     A social distance value represents a degree of closeness between the user  102  and each of the content providers  105 . The social distance value is associated with one user and one of the content providers  105 , although different content providers  105  may have the same social distance value for the same user. The social distance value may be implicitly or explicitly defined or calculated (e.g., see  FIG. 3 ). Exemplary social distance values may range from zero to one or zero to one hundred, or may be selected from any defined set or range of values. 
     Referring again to  FIG. 1 , an exemplary block diagram illustrates the computing device  104  receiving content items from the plurality of content providers  105 . The elements illustrated in  FIG. 1  operate to enable selective pre-fetch of the content items. For example, the content items are pre-fetched as the user  102  browses other content items (e.g., active pre-fetch), or the content items are pre-fetched while the computing device  104  is idle (e.g., background pre-fetch). 
     In some embodiments, the computing device  104  represents the mobile computing device  402  such as illustrated in  FIG. 4 . In other embodiments, the computing device  104  represents a plurality of computing devices programmed to implement the functionality described herein. Alternatively or in addition, a portion of the functionality is performed by other computing devices (e.g., executing a web service). 
     The computing device  104  communicates with content providers  105 , such as content provider # 1  through content provider #N, via a network  103  such as the Internet. The content providers  105  represent, for example, distributors or repositories of content such as social networking web sites or photo sharing web sites. In other embodiments, the content providers  105  represent content authors. The computing device  104  includes at least a memory area  106  and a processor  108 . The memory area  106 , or other computer-readable media or machine-readable media, stores user data  110 . The user data  110  may include data particular to one or more of the users  102  of the computing device  104 . The user data  110  may be stored locally as in the example of  FIG. 1 , or stored remotely such as by a web service (e.g., a social content web service storing user profile information) and synchronized to the computing device  104 . In some embodiments, the user data  110  includes an interaction history  112  describing interactions between the user  102  and the content provider  105 . For example, the user data  110  includes a browsing history. Other exemplary user data  110  includes any user  102  behavior when consuming the content items including, for example, dwell time on particular content items. 
     The memory area  106  further stores a list  116  of content items. In some embodiments, the list of contents items includes a “what&#39;s new” feed of content recently made available. For example, the content items include one or more of the following: image files, video files, text files, blog postings, electronic mail messages, instant messages, audio clips, hyperlinks, and micro-blog postings. The list  116  of content items is received from at least one of the content providers  105 , or from a front-edge server (not shown). The list  116  of content items may be obtained, retrieved, received, accessed, pushed, pulled, or the like, on a regular basis, periodic basis, or on demand by the user  102 . For example, the computing device  104  may actively seek the list  116  of content items or may passively receive the list  116  of content items at regular intervals, in various embodiments. 
     In some embodiments, a portion of the memory area  106  includes a cache  114  such as a variable-size cache (e.g., a cache having a variable amount of memory allocated thereto from a file system). In other embodiments (not shown), the cache  114  is associated with another storage area either within the computing device  104  or accessible by the computing device  104 . The cache  114  stores one or more of the content items received from the content providers  105 . In some embodiments, the cache  114  is a fixed-size cache that has been allocated a particular amount of memory from a file system. 
     The memory area  106 , or one or more computer-readable media, further stores computer-executable components for implementing aspects of the disclosure. Exemplary components include a score component  118 , a feed component  120 , a resource component  122 , and a maintenance component  124 . These components are described below with reference to  FIG. 3 . 
     In general, the memory area  106  is associated with the computing device  104 . For example, in  FIG. 2 , the memory area  106  is within the computing device  104 . However, the memory area  106  includes any memory area internal to, external to, or accessible by computing device  104 . Further, the memory area  106  or any of the data stored thereon may be associated with any server or other computer, local or remote from the computing device  104  (e.g., accessible via a network). 
     The processor  108  includes any quantity of processing units, and is programmed to execute computer-executable instructions for implementing aspects of the disclosure. The instructions may be performed by the processor  108  or by multiple processors executing within the computing device  104 , or performed by a processor external to the computing device  104  (e.g., by a cloud service). In some embodiments, the processor  108  is programmed to execute instructions such as those illustrated in the figures (e.g.,  FIG. 2  and  FIG. 3 ). 
     Referring next to  FIG. 2 , an exemplary flow chart illustrates the selective retrieval of content items based on social distance and device constraints. The content items include, for example, audio, text, video, and images data (e.g., files, streamed data, etc.). In some embodiments, the content items include electronic mail messages, and text messages. When the list  116  of content items is received at  202 , one or more constraints associated with the computing device  104  are determined at  204 . For example, the computing device  104  retrieves, receives, or accesses the list  116  of content items from one of the content providers  105  or from another entity. In some embodiments, the list  116  of content items is sorted by the content providers  105  according to the social distance values. The computing device  104  receives the sorted list, and is able to quickly identify the content provider  105  “closest” to the user  102  based on the social distance value. In other embodiments, the computing device  104  receives an unsorted list  116  of content items and sorts the content items by the social distance value of the content providers  105  associated with each of the content items on the list. In such embodiments, the content items associated with a first-ranked content provider  105  are retrieved before content items associated with lesser-ranked content providers  105  are retrieved. 
     Exemplary constraints associated with the computing device  104  include hardware and/or software constraints such as storage constraints, battery/power constraints, and bandwidth constraints. The determined constraints represent, for example, an available amount of storage on the computing device  104 , a remaining amount of battery power on the computing device  104 , and available bandwidth resources. The bandwidth resources represent, for example, available bandwidth between the computing device  104  and the content providers  105 . Other exemplary constraints include limitations or configurations relating to processing power (e.g., the processor  108  usage rate exceeds a pre-defined threshold, etc.). Still other exemplary constraints are associated with software executing on the computing device  104  (e.g., a quantity of threads exceeds a pre-defined threshold value). 
     Content items are selectively retrieved at  206  from the content providers  105  based on the determined constraints and the social distance values for each of the content providers  105 . In some embodiments, selectively retrieving the content items includes retrieving the content items associated with a first-ranked content provider  105  and then only a portion of the content items associated with one or more of the lower-ranked content providers  105  (e.g., a second-ranked content provider  105 ). In other embodiments, only content items associated with content providers  105  having social distance values exceeding a pre-defined threshold are retrieved. 
     In some embodiments, the operations at  202 ,  204 , and  206  are performed prior to receiving a request from the user  102  for the content items that have been selectively retrieved. For example, the operations are performed as the user  102  is browsing the Internet, a photo collection, a music library, etc. The content items are pre-fetched and cached in anticipation of receiving the request from the user  102  for one or more of the cached content items (e.g., pre-fetch the content items moments before the user  102  requests the content items). Aspects of the disclosure are then able to quickly deliver the requested content items to the user  102  responsive to receiving the request. Such embodiments of the disclosure improve the user experience on the computing device  104 . 
     Referring next to  FIG. 3 , an exemplary flow chart illustrates the pre-fetching of content items associated with ranked content providers  105 . At  302 , user  102  interaction with the content providers  105  is monitored. For example, aspects of the disclosure identify the content providers  105  associated with images selected and viewed by the user  102 , measure and store a quantity of time the user  102  spends browsing a photo gallery of a particular one of the content providers  105 , count messages exchanged between the user  102  and the content providers  105 , and the like. In some embodiments, the data from the monitored interactions is stored as a portion of the user data  110  in the memory area  106 . 
     At  304 , the social distance value for each of the content providers  105  is calculated based at least on the user interaction monitored at  304 . Each of the content providers  105  then has a social distance value associated therewith. The social distance value is representative of a relationship between the content provider  105  and the user  102 . The social distance value may be calculated based in part on the user data  110  including calendar events, electronic mail messages, interaction history  112 , and the like. In some embodiments, a fitness function is used to calculate the social distance value. 
     Table 1 below illustrates exemplary variables, values, and weights for calculating the social distance values. In some embodiments, the variables are calculated in a rolling 30-day window, or shorter if the cache history is shorter. 
     
       
         
           
               
             
               
                 TABLE 1 
               
             
            
               
                   
               
               
                 Exemplary Variables, Values, and Weights 
               
               
                 for Calculating Social Distance Values. 
               
            
           
           
               
               
               
               
            
               
                 Variable 
                 Values 
                 Weight 
                 Notes 
               
               
                   
               
               
                 Percentage of the 
                  0%-100% 
                 0.4 
                 Clicking on the 
               
               
                 content provider&#39;s photo 
                   
                   
                 album title or any 
               
               
                 events drilled into by the 
                   
                   
                 thumbnail associated 
               
               
                 user 
                   
                   
                 with the photo event 
               
               
                   
                   
                   
                 counts in this 
               
               
                   
                   
                   
                 variable. 
               
               
                 Quantity of comments 
                 0-4  
                 0.2 
                 The user 
               
               
                 made by the user on 
                   
                   
                 commenting on at 
               
               
                 this content provider&#39;s 
                   
                   
                 least one photo a 
               
               
                 photos 
                   
                   
                 week equates to full 
               
               
                   
                   
                   
                 weight. 
               
               
                 Quantity of times the 
                 0-12 
                 0.1 
                 The user opening the 
               
               
                 user opened the contact 
                   
                   
                 contact card of the 
               
               
                 card of this content 
                   
                   
                 content provider 
               
               
                 provider 
                   
                   
                 more than three 
               
               
                   
                   
                   
                 times a month 
               
               
                   
                   
                   
                 equates to full 
               
               
                   
                   
                   
                 weight. 
               
               
                 Quantity of messages 
                 0-30 
                 0.3 
                 The user trading a 
               
               
                 the user has exchanged 
                   
                   
                 message every day 
               
               
                 with this content provider 
                   
                   
                 on average equates to 
               
               
                   
                   
                   
                 full weight. 
               
               
                   
               
            
           
         
       
     
     In some embodiments, the values in Table 1 are combined according to the weights in a linear fashion (e.g., summed) to calculate the social distance value. In other embodiments, the values are combined in other mathematical ways, or augmented with additional data or calculations, to calculate the social distance values. 
     When the computing device  104  receives the list  116  of content items at  306 , the computing device  104  pre-fetches one of the content items at  308  from the content providers  105  who are ranked in order of social distance values. The content item is retrieved from the highest-ranking content provider  105  rather than a lower-ranking content provider  105 . In some embodiments, a plurality of the content items is pre-fetched at  308 . For example, two content items may be retrieved at a time. 
     Resources on the computing device  104  are also monitored. For example, the available storage space, bandwidth, and battery power level are monitored at regular or irregular intervals. If one or more of the resources are exhausted (e.g., at levels that violate or exceed pre-defined thresholds) at  310 , resource maintenance is performed. For example, cache maintenance is performed at  312 . Exemplary cache maintenance includes deleting older content items from the cache  114 , compressing content items, and other routine or typical cache maintenance items. The age of content items in the cache  114  is determined by, for example, an item date associated with each of the content items. The item date corresponds to the most recent date/time the computing device  104  refreshed, accessed, pre-fetched, sent, or received the content item. For example, full screen images may be removed from the cache  114 , except for the most recent ten images or images less than twelve hours old. Image metadata and thumbnails older than 72 hours may also be removed. In some embodiments, the cache maintenance is also performed on a regular basis (e.g., each day and/or when the computing device  104  powers on). After performing the cache maintenance at  312 , another content item is pre-fetched at  308 . 
     If the resources of the computing device  104  are not exhausted at  310 , another content item is pre-fetched at  308 . 
     In some embodiments, at least some of the operations illustrated in  FIG. 3  are performed prior to receiving a request from the user  102  for the retrieved content items. In this manner, aspects of the disclosure observe the user interactions, and pre-fetch the content items believed to be of interest to the user  102  prior to the user  102  actually requesting those content items. Aspects of the disclosure provide an improved user experience when browsing photos or other content on the computing device  104 . Analogously, aspects of the disclosure enable a graceful degradation of the user experience when resources on the computing device  104  become more limited. 
     In some embodiments, one or more computer-executable components, such as the components illustrated in  FIG. 1 , execute on the computing device  104  to perform the operations illustrated in  FIG. 3 . The score component  118 , when executed by the processor  108 , causes the processor  108  to calculate the social distance value for each of the content providers  105 . The feed component  120 , when executed by the processor  108 , causes the processor  108  to access the list  116  of content items. The resource component  122 , when executed by the processor  108 , causes the processor  108  to monitor available storage in the memory area  106  (e.g., the cache  114 ) of the computing device  104 . In other embodiments, the available storage is in a removable storage area such as a flash drive. In an example in which the resource component  122  determines that the monitored storage exceeds a pre-defined threshold value, the maintenance component  124  further deletes at least one of the content items stored in the memory area  106 . 
     The maintenance component  124 , when executed by the processor  108 , causes the processor  108  to selectively retrieve one or more of the content items on the list based on the social distance value calculated by the score component  118  and based on the available storage monitored by the resource component  122 . The retrieved content items are stored in the memory area  106 . In some embodiments, the retrieval occurs prior to receiving a request from the user  102  for the content items. 
     The resource component  122  further monitors various other resources such as a battery level. If the battery level reaches, exceeds, passes, violates, or otherwise crosses a pre-defined threshold, the maintenance component  124  ceases to retrieve the content items until the battery is charged (or charging). 
     In some embodiments, the score component  118  calculates the social distance value based on a plurality of configurable parameters. In some embodiments, the configurable parameters are determined from one or more of the following: a frequency of access by the user  102  to content items associated with each of the content providers  105 , a quantity of comments posted by the user  102  for the content items associated with each of the content providers  105 , and a quantity of messages exchanged between the user  102  and each of the content providers  105 . 
     In some embodiments, the operations illustrated in  FIG. 2  and  FIG. 3  are performed by the computing device  104 . In other embodiments, one or more of the operations illustrated in  FIG. 2  or  FIG. 3  are performed by another computing device (e.g., as a web service). 
     In other embodiments, at least a portion of the functionality of the computing device  104  is performed by an entity (e.g., processor  108 , web service, server, application program, computing device, etc.) remote from the computing device  104  of the user  102 . 
     Referring next to  FIG. 4 , an exemplary block diagram illustrates the mobile computing device  402  communicating with a web service  404  to download photos and music. The user  102  operates the mobile computing device  402  to interact with the web service  404 . The web service  404  includes any combination of computing devices providing the content items. Other users  406  or entities provide the content items to the web service  404 . In this example, the other users  406  constitute the content providers  105 . 
     In an example, the user  102  browses photos and music via a browser executing on the mobile computing device  402 . The user  102  views some thumbnail images, and tags the names of a few friends in a “spring break” photo album. Aspects of the disclosure pre-fetch full screen images for the thumbnails associated with the tagged friends. If any of the pre-fetched full screen images have comments or other tags, aspects of the disclosure also fetch the comments and tags. When the user  102  selects one of the thumbnails to view a full screen image, the full screen image has already been fetched and is displayed instantly. 
     Further Examples 
     Various implementations of the disclosure are contemplated. During operation in one example, the computing device  104  receives a “What&#39;s New” feed of the latest social events. The feed includes, for example, subject display names, identifiers such as users, object display names or identifiers such as photo albums, strings denoting relationships such as “John became friends with Jane”, and the like. In this example, the computing device  104  ranks the content providers  105  associated with the photo albums listed in the “What&#39;s New” feed according to the social distance value of each of the content providers  105 . The list of ranked content providers  105  is pruned to include only those content providers  105  with a social distance value exceeding a pre-defined threshold value (e.g., only those content providers  105  deemed close enough to the user  102 ). 
     Photos from all of the new albums from the first-ranked content provider  105  (e.g., author of the photo album) are pre-fetched, starting with the most recent album first. For example, the computing device  104  pre-fetches the first eighteen thumbnails in the photo album and the full screen images associated with those thumbnails. Alternatively, the computing device  104  pre-fetches the first nine thumbnails and up to the first five full screen images associated with those thumbnails. Once all the albums from the first-ranked content provider  105  have been pre-fetched, a fraction of the photos from the new albums for the second-ranked content provider  105  is pre-fetched. For example, the fraction is determined by the ratio of the social distance value of the second-ranked content provider  105  to the social distance value of the first-ranked content provider  105 , rounded down to the nearest whole album. 
     The pre-fetching process continues in this manner through the successive ranked content providers  105  until a termination condition is reached. The termination condition is dependent on various resources on the computing device  104 , as described elsewhere herein (e.g., available storage, battery, and bandwidth). One example termination condition occurs when storage space has been reduced such that pre-fetching another album or photo would clear cache data from an album less than twelve hours old. Another termination condition occurs when pre-fetching consumes more than ten percent of the remaining battery power. For example, if the battery has twenty percent power remaining, the termination condition is when two percent of that power has been used for a particular pre-fetch operation. Another example is that pre-fetching does not occur if the batter power remaining is less than a particular threshold (e.g., twenty percent). Yet another termination condition occurs when bandwidth usage has been exceeded. For example, the pre-fetching operations are allotted a configurable amount of bandwidth per day. When the allotted bandwidth has been used, the pre-fetching operations cease. For example, if a pre-fetching update occurs every four hours, and there is a limit of six megabytes of bandwidth per day, pre-fetching ceases when one megabyte has been used for a particular pre-fetch update. 
     Examples of the pre-fetch operations are next described. In one example, there are three megabytes of cache space available and five megabytes full. The cache  114  is at minimum state so background pre-fetch does not execute. However, aspects of the invention round-robin the full screen binaries: when the user  102  requests another photo, the oldest cached photo is deleted to make space. In another example, the variable-size cache is full of fifty megabytes of data, while the rest of the storage medium has fifty megabytes available for other storage uses. If the user  102  downloads music files and fills all but 1.5 megabytes of the previously available fifty megabytes on the storage medium, aspects of the disclosure will reduce the cache size during the next cache maintenance operation. In still another example, the user  102  uses messaging but not photos. For this user  102 , the pre-fetch operations turn off after seven days, any pre-fetched content items are removed thirty days later, and the cache  114  is disabled (returning the cache space to the computing device  104  for other uses). In yet another example, there are 0.1 megabytes of cache space available out of five megabytes of allotted cache space, and five megabytes of storage space remaining on the storage medium. The pre-fetch operations store the content items in the 0.1 megabytes of available cache space, then the pre-fetch operations cease. 
     Exemplary Operating Environment 
     By way of example and not limitation, computer readable media comprise computer storage media and communication media. Computer storage media store information such as computer readable instructions, data structures, program modules or other data. Communication media typically embody computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism and include any information delivery media. Combinations of any of the above are also included within the scope of computer readable media. 
     Although described in connection with an exemplary computing system environment, embodiments of the invention are operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with aspects of the invention include, but are not limited to, mobile computing devices, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, gaming consoles, microprocessor-based systems, set top boxes, programmable consumer electronics, mobile telephones, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like. 
     Embodiments of the invention may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. The computer-executable instructions may be organized into one or more computer-executable components or modules. Generally, program modules include, but are not limited to, routines, programs, objects, components, and data structures that perform particular tasks  310  or implement particular abstract data types. Aspects of the invention may be implemented with any number and organization of such components or modules. For example, aspects of the invention are not limited to the specific computer-executable instructions or the specific components or modules illustrated in the figures and described herein. Other embodiments of the invention may include different computer-executable instructions or components having more or less functionality than illustrated and described herein. 
     Aspects of the invention transform a general-purpose computer into a special-purpose computing device when configured to execute the instructions described herein. 
     The embodiments illustrated and described herein as well as embodiments not specifically described herein but within the scope of aspects of the invention constitute exemplary means for prioritizing usage of resources on the computing device  104  based on a social distance between the user  102  and the content providers  105 , and exemplary means for prioritizing content retrieval on the computing device  104  based on the social distance between the user  102  and the content providers  105 . 
     The order of execution or performance of the operations in embodiments of the invention illustrated and described herein is not essential, unless otherwise specified. That is, the operations may be performed in any order, unless otherwise specified, and embodiments of the invention may include additional or fewer operations than those disclosed herein. For example, it is contemplated that executing or performing a particular operation before, contemporaneously with, or after another operation is within the scope of aspects of the invention. 
     When introducing elements of aspects of the invention or the embodiments thereof, the articles “a,” “an,” “the,” and “said” are intended to mean that there are one or more of the elements. The terms “comprising,” “including,” and “having” are intended to be inclusive and mean that there may be additional elements other than the listed elements. 
     Having described aspects of the invention in detail, it will be apparent that modifications and variations are possible without departing from the scope of aspects of the invention as defined in the appended claims. As various changes could be made in the above constructions, products, and methods without departing from the scope of aspects of the invention, it is intended that all matter contained in the above description and shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.