Short-term hashes.

(54) Title: SHORT TERM DISPERSIONS.

(54) Title: SHORT-TERM HASHES.

(57) Summary

In one embodiment, a server receives a search query, the server determines search terms based on the received search query, each search term including a prefix and a suffix; For each of the search terms, the server generates a first binary number based on the prefix and suffix of the search terms, and accesses and retrieves the search results for each search term from data stores by spreading the first binary number, the server also adds search results for the respective search terms.

(57) Abstract

In one embodiment, a server receives a search query; the server determines search terms based on the received search query, each search term including a prefix and a suffix; for each of the search term, the server generals a first binary number based on the each search term's prefix and suffix, and accesses and retrieves search results of the each search term from data stores by hashing the first binary number; the server also aggregates search results of the respective search terms.

I KNOW

<img file="MX348259B_D0001.tif" />

PATENT TITLE No. 348259

Owner (s): FACEBOOK, INC.

Address: 1601 Willow Road, Menlo Park, California, 94025, USA

Name: SHORT TERM DISPERSIONS.

Classification

CIP:

G06F17 / 30

CPC:

G06FJ7,

17/30949; G06F17 / 30958

Inventor (s)

US

The patent reference

<img file="MX348259B_D0002.tif" />

ero:

, 772 eligible, counted arw raffle pa

TUDOR BQSI ^ N] 9OREN BOGH LASSEN Imemacional ion

MX / a / 2015 /

Pal r

Validity: Date of Date of E years ienti ition:

I went with

201 dustrial.

In accordance with the as of the date of presentation

Who subscribes this title (Official Gazette of the Federation 01/25/2006, 05/06/2009, 06/01/2010, Regulation of the Mexican Institute articles 1^or, 3^or, 4^or, 5^or fraction V subsection aJH 12/27/1999, amended on 10/10/2002, Deputy Generals 29/0, Coordinator, Departmental Directors and other subordinates of the Institute 08/04/2004 and 09/13/2007).

(2012]

SF- 1

4,> / 10. t / 2012 fartíí rgánicc '12 / a <of Industrial Property / 1999, 01/26/2004, 06/16/2005, a), 4 and 12^or sections I and 111 of / 2004, 07/28/2004 and 09/07/2007); of Industrial Property (DOF

oMrdo that delegates powers to Directors>, Divisional Deputy Directors, Coordinators 2/1999, amended on 02/04/2000, 07/29/2004,

This document is signed with an advanced electronic signature (FIEL), based on articles 7 BIS 2 of the Industrial Property Law; 3 of its Regulations, and 1 section III, 2 section V, 26 BIS and 26 TER of the Agreement establishing the guidelines for the use of the Payment and Electronic Services Portal (PASE) of the Mexican Institute of Industrial Property, in the procedures indicated.

THE DIVISIONAL DIRECTOR OF PATENTS

NAHANNY CANAL REYES

<img file="MX348259B_D0003.tif" />

Original string;

NAHANNY MARISOL CANAL REYES | 00001000000403262793 | Administration Service

Tax | 1695 || MX / 2017/43507 | MX / a / 2015/012619 | PCT patent title | 1220 | RRGO | Page (s) | bQbU4wYzQBXFoX1 R4W0 / S01 PEP4 =

Digital stamp;

ixrxg0u6vmvfNZcyov1b6v60HkzTyixAgfERE7L4UomnTDG7Hw3d8umNdmjnyujOkzc5Pfh2KrZMz48j4O1m0MSZ4z

OTSBQ + Y + CZ6eyVzocFro3Ova0tv4NP6gUrpjaFQP9LvXTb9XvktVbLceNpe7mBHRAa4665j9EI57L3HWutf2A9TCKx

XVg / ggFIXikhBd4GISX3D8FNO585 / myol1 EY4yng7ovKNrbyHCTG / 6E8vNBWjVjXsN7AxE6UbhlJLDw5KCI1VWLUJM

PSicS4RHEO4pWM / rGq831XeZoy1Q / gWKUxlvFKLtSusJh0mBcnh + iNNsfUz5tBFCF66BYr2w ==

Arenal No. 550, Floor 1, Pueblo Santa María Tepepan, Xochrmilco. 16020, Mexico City.

¢ 55) 53340700 www.gob.mx/impi

<img file="MX348259B_D0004.tif" />

MX / 2017/43507

<img file="MX348259B_D0005.tif" />

IMPI

INSTITUTO MEXICANO M LA n »HEDAD INtUSTTlAL

DISPERSIONS OF CORSO TERM.

TECHNICAL FIELD

This description generally refers to a social media system.

BACKGROUND

A social networking system, which may include a social networking website, may allow its users (such as individuals or organizations) to interact with it and with each other through it. The social media system may, with input from a user, create and store in the social media system a user profile associated with the user. The user profile may include demographic information, communication channel information, and information about the user's personal interests. The social media system may also, with input from a user, create and store a record of the user's relationships with other users of the social media system, as well as provide services (e.g., wall posts, photo sharing, organization of event, messaging, games, or advertisements) to facilitate social interaction between two or more users.

The social media system may send through one or more networks, content or messages related to its services to a

<img file="MX348259B_D0006.tif" />

mobile or other computing device of a user. A user can also install software applications on a user's mobile or other computing device to access a user's user profile and other data within the social media system. The social networking system can generate a customized set of content objects to present a user, such as a news feed of aggregated stories from other users connected to the user.

BRIEF DESCRIPTION OF PARTICULAR MODALITIES

Particular modalities describe methods for indexing a database based on search term structures. Particular modalities can represent a search term with a binary number and index search results of the search term by spreading the binary number. Instead of using a fixed length for binary numbers representing search terms, particular modalities can reduce the lengths of binary numbers by determining for each search term a prefix and suffix for each search term, and determining a length of a binary number representing each search term based at least in part on an object type of the suffix of each search term. Particular ways in that way can reduce hash table sizes to index search terms with numbers

<img file="MX348259B_D0007.tif" />

IMPI

MEXICAN INSTITUTE

KU FMm * AT fNOUSTWAl Shortest-length binaries representing search terms.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 shows an illustrative network environment associated with a social media system.

Figure 2 shows an illustrative social graph.

Figure 3 shows an illustrative method for indexing a database based on search term structures.

Figure 4 shows an illustrative computer system.

DESCRIPTION OF ILLUSTRATIVE MODALITIES

Figure 1 shows an illustrative network environment 100 associated with a social media system. The network environment 100 includes a user 101, client system 130, a social networking system 160, and a third party system 170 connected to each other by a network 110. Although Figure 1 illustrates a particular layout of user 101, client system 130, social media system 160, third party system 170, and network 110, this description contemplates any suitable layout of user 101, client system 130, system of social media 160, third party system 170, and network 110. As an example and not by way of limitation, two or more of the client system 130, social media system 160,

IMPI

INSTITUTO MtXICAN · DE LAMtBHfOAD INDUSTlUAi.

and third party system 170 can connect to each other directly, bypassing network 110. As another example, two or more of client system 130, social media system 160, and third party system 170 can be physically or logically co-located. each other in whole or in part. Furthermore, although Figure 1 illustrates a particular user number 101, client systems 130, social network systems 160, third party systems 170, and networks 110, this description contemplates any suitable user number 101, client systems 130, social media systems 160, third party systems 170, and networks 110. As an example and not by way of limitation, the network environment 100 may include multiple users 101, client system 130, social network systems 160, third party systems 170, and networks 110.

In particular embodiments, user 101 can be an individual (human user), an entity (for example a company, business, or third party application), or a group (for example individuals or entities) that interacts or communicates with or through the social network system 160. In particular embodiments, the social network system 160 may be a network-addressable computing system that hosts an online social network. The social system 160 may generate, store, receive, and send social network data, such as, for example, user profile data, concept profile data, social graph information, or other suitable data related to the social network. online. The social media system

160 can be accessed by the other components of the

<img file="MX348259B_D0008.tif" />

IMPI

MEXICAN INSTITUTE

M LA PROREDA »INDUSTRIAL red 100 either directly or in particular modalities, the system will include an authorization server (or through ^Fn of social media 160 may another suitable component (s)) that allows users 101 to choose whether or not to have their actions recorded by the social media system 160 or shared with other systems (for example, third-party systems 170) , for example, by setting appropriate privacy settings. A privacy setting a user can determine what information associated with the user can be registered, how information associated with the user can be registered, when information associated with the user can be registered, who can register information associated with the user, with whom associated information can be shared with the user, and for what purposes information associated with the user may be registered or shared. Authorization servers may be used to enforce one or more privacy settings on users of the social media system 30 through blocking, data dispersal, anonymity, and other suitable techniques as appropriate. In particular embodiments, third party system 170 can be a network addressable computing device that can host web sites and applications. Third party system 170 can generate, store, receive, and send third party system data, such as, for example, web pages, text, images, video, audio, or applications. The third party system 170 can be accessed by the other components of the network environment 100 either directly

<img file="MX348259B_D0009.tif" />

IMPI iNrntvTo muucan · M LA M «ncOAD INtUSnUAL or through the network 110. In particular modalities, one or more users 101 can use one or more client systems 130 to access, send data to, and receive data from the social network system

160 or third party system 170. Client system 130 may access social media system 160 or third party system 170 directly, through network 110 or through a third party system. As an example and not by way of limitation, client system 130 may access third party system 170 through social media system 160. The client system 130 can be any suitable computing device, such as, for example, a personal computer, laptop computer, cell phone, smartphone, or tablet computer.

This description contemplates any suitable network 110. As an example and not by way of limitation, one or more network portions 110 may include an ad hoc network, an intranet, an extranet, a virtual private network (VPN), a local area network (LAN), a wireless LAN (WLAN), a wide area network (WAN), a wireless WAN (WWAN), a metropolitan area network (WAN), a portion of the Internet, a portion of the public switched telephone network (PSTN), a telephone network cellular, or a combination of two or more of these. Network 110 may include one or more networks 110.

Links 150 may connect client system 130, social media system 160, and third party system 170 to communication network 110 or to each other. This description contemplates₇

I MEXICAN INSTITUTE

Μ THE FROHEBAD C¿ ^ 3TjCp INDUSTRY!

any of the suitable 150 links. In particular embodiments, one or more links 150 include one or more links by cable (such as for example Digital Subscriber Line (DSL) or Cable Data Service Interface Specification (DOCSIS)), wireless (such as for example Wi -Fi or worldwide interoperability for microwave access (WiMAX)), or optical (such as for example synchronous optical network (SONET) or synchronous digital hierarchy (SDH)). In particular embodiments, each of one or more links 150 includes an ad hoc network, an intranet, an extranet, a VPN, a LAN, a WLAN, a WAN, a WWAN, a MAN, a portion of the Internet, a portion of the PSTN, a cellular technology-based network, a satellite communications technology-based network, another link 150, or a combination of two or more such links 150. Links 150 do not necessarily need to be the same throughout the network environment 100. One or more first links 150 may differ in one or more respects from one or more second links 150.

Figure 2 shows an illustrative social graph 200. In particular embodiments, the social network system 160 can store one or more social charts 200 in one or more data stores. In particular embodiments, the social graph 200 may include multiple nodes, which may include multiple user nodes 202 or multiple concept modes 204, and multiple edges 206 connecting the nodes. The social graph 200 illustrated in Figure 2 is shown, for didactic purposes, in

OR MUICAN INSTITUTE ^or M LA ΙΜΗΙΙλ »

INDUSTRIAL a two-dimensional visual map representation. In particular embodiments, a social media system 160, client system 130, or third party system 170 can access social graph 200 and related social graph information for suitable applications. The nodes and edges of the social chart 200 can be stored as data objects, for example, in a data store (such as a social chart database). Such data storage may include one or more searchable or queryable indices of nodes or edges of the social graph 200.

In particular embodiments, a user node 202 may correspond to the user of the social media system 160. As an example and not by way of limitation, a user may be an individual (human user), an entity (eg, a company, business, or third-party application), or a group (for example, individuals or entities) that interacts or communicates with or through the social media system 160. In particular embodiments, when a user registers for an account with the social network system 160, the social network system 160 can create a user node 202 corresponding to the user, and store the user node 202 in one or more storages. of data. The users and user nodes 202 described herein may, where appropriate, refer to registered users and user nodes 202 associated with registered users. In addition or as an alternative, the users and user nodes 202 described here

IMPI tNSTTHJTO MEXICANO DE LA M »HE» AD INDUSTRIAL may, where appropriate, refer to users who have not registered with the social networking system 160. In particular modalities, a user node 202 may be associated with information provided by a user or information collected by various systems, including social media system 160. As an example and not by way of limitation, a user may provide their name, profile picture, contact information, date of birth, gender, marital status, family status, employment, educational background, preferences, interests, or other demographic information. . In particular embodiments, a user code 202 may be associated with one or more data objects that correspond to information associated with a user. In particular embodiments, a user node 202 can correspond to one or more web pages.

In particular embodiments, a concept node 204 may correspond to a concept. As an example and not by way of limitation, a concept may correspond to a place (such as, for example, a movie theater, restaurant, historic place, or city); a website (such as, for example, a website associated with a social media system 160 or a third party website associated with a web application server); an entity (such as, for example, a person, business, group, sports team, or celebrity); a resource (such as, for example, an audio file, video file, digital photo, text file, structured document, or application) that can be uploaded within the social media system 160 or on a

<img file="MX348259B_D0010.tif" />

external server, such as a web application server; intellectual property (such as, for example, a sculpture, painting, film, game, song, idea, photograph, or written work); a game; an activity; an idea or theory; another suitable concept; or two or more of such concepts. A concept node 204 may be associated with information from a concept provided by a user or information collected by various systems, including social media system 160. As an example and not by way of limitation, the information in a concept may include a name or a title; one or more images (for example, an image of the cover of a book); a location (for example, an address or geographic location); a website (which can be associated with a URL); contact information (for example a phone number or an email address); other suitable concept information; or any suitable combination of such information. In particular embodiments, a concept node 204 may be associated with one or more data objects that correspond to information associated with concept node 204. In particular embodiments, a concept node 204 may correspond to one or more web pages.

In particular embodiments, a node in the social graph 200 can represent or be represented by a web page (which can be referred to as a "profile page"). Profile pages can be hosted by or accessible by the social media system 160. Profile pages can also be hosted by

<img file="MX348259B_D0011.tif" />

ΙΝ5ΤΤΠΓΤΟ MEXICANO MLAPRONÍDAD industrial third party websites associated with a serviHnr ría *? Roora part 170. As an example and not by way of limitation, a profile page that corresponds to a particular external web page may be the particular external web page and the profile page may correspond to a particular concept node 204. The profile pages may be viewed by all or a selected subset of other users. As an example and not by way of limitation, a user node 202 may have a corresponding user profile page in which the corresponding user can add content, make statements, or otherwise express himself. As another example and not by way of limitation, a concept node 204 may have a corresponding concept profile page in which one or more users can add content, make statements, or express themselves, particularly regarding the concept corresponding to the concept node. concept 204.

In particular embodiments, a concept node 204 may represent a third party web page or resource hosted by a third party system 170. The third party web page or resource may include, among other elements, content, a selectable icon or another, or other interoperable object (which can be implemented, for example, in JavaScript, AJAX, or PHP code) that represent an action or activity. As an example and not by way of limitation, a third party web page may include a selectable icon such as "like", "post", "eat", "recommend", or other appropriate action or activity. A user who sees

<img file="MX348259B_D0012.tif" />

IMPI nrcrm τ · Mexican r> f LA nt »« € »AD INDUSTRIA!

the third party web page may perform an action by selecting one of the icons (eg, "eat"), which causes a client system 130 to send a message to the social media system 160 indicating a user's action. In response to the message, the social media system 160 may create a border (eg, a "eat" border) between a user node 202 that corresponds to the user and a concept node 204 that corresponds to the web page or resource of third party and storage edge 206 in one or more data stores.

In particular embodiments, a pair of nodes in the social graph 200 can be connected to each other by one or more edges 206. An edge 206 connecting a pair of nodes can represent a relationship between the pair of nodes. In particular embodiments, an edge 206 can include or represent one or more data objects or attributes that correspond to the relationship between a pair of nodes. As an example and not by way of limitation, a first user may indicate that a second user is a "friend" of the first user. In response to that prompt, the social media system 160 may send a "friend request" to the second user. If the second user confirms the "friend request", the social media system 160 can create an edge 206 that connects the user node 202 of the first user to the user node 202 of the second user on the social graph 200 and storage edges 106 as social graph information in one or more of the data stores. In the example in Figure 2, the graph

<img file="MX348259B_D0013.tif" />

IMPI irermJWMuucwo DE LA MkDPIlBAD INDUSTRIAL social 200 includes a border 206 that indicates a friendship relationship between user nodes 102 of user “A” and user “B” and an border that indicates a friendship relationship between user nodes 202 of user “ C "and user" B ". Although this description describes or illustrates particular edges 206 with particular attributes connecting particular user nodes 202, this description contemplates any of suitable edges 206 with any of the suitable attributes connecting user nodes 202. As an example and not by way of limitation, a 206 border may represent a friendship, family relationship, business or employment relationship, fan relationship, follower relationship, visitor relationship, subscriber relationship, superior / subordinate relationship, relationship reciprocal, non-reciprocal relationship, other suitable type of relationship, or two or more of such relationships. Furthermore, although this description generally describes nodes as being connected, this description also describes users or concepts as being connected. Here, references to users or concepts that are connected may, where appropriate, refer to nodes that correspond to other users or concepts that are connected in the social graph 200 by one or more edges 206.

In particular embodiments, an edge 206 between a user node 202 and a concept node 204 may represent a particular action or activity performed by a user associated with user node 202 towards a concept associated with a concept node 204. As an example and not by way of limitation, as illustrated

IMPI

INSTITUTO MEXICANO OF LAPROMEBAD INDUSTRIAL in Figure 2, a user may “like it”, he may have “attended”. "Reproduced", "heard", "cooked", "worked on", or "seen", or a concept, each of which may correspond to an edge type or subtype. A concept profile page that corresponds to a concept node 204 may include, for example, a selectable "register" icon (such as, for example, a clickable "register" icon). or a selectable “add to favorites” icon. Similarly, after a user clicks on these icons, the social networking system 160 may create a "favorites" border or a "register" border in response to a user action that corresponds to a respective action. As another example and not by way of limitation, a user (user "C") can listen to a particular song ("Ramble On") using a particular application (SPOTIFY, which is an online music application). In this case, the social media system 160 can create a "listened" border 206 and a "used" border (as illustrated in Figure 2) between user nodes 202 that correspond to the user and concept nodes. 204 that correspond to the song or application to indicate that the user listened to the song and used the application. Additionally, the social media system 160 may create a "played" border 206 (as illustrated in Figure 2) between concept nodes 204 that correspond to the song and the application to indicate that the particular song was played by the application. particular. In this case, the edge of "played" 206 corresponds to an action performed by an external application (SPOTIFY) on a

<img file="MX348259B_D0014.tif" />

external audio file (the song “Imayine). Airi'iqw — thisThe description describes particular edges 206 with particular attributes that connect user nodes 202 and concept nodes 204, this description contemplates any of the suitable edges 206 with any of the suitable attribute that connects user nodes 202 and concept nodes 204. Furthermore, while this description describes edges between a user node 202 and a concept node 204 that represents an individual relationship, this description contemplates edges between a user node 202 and its concept node 204 that represent one or more relationships. As an example and not by way of limitation, a border 206 can represent so much that a user would like to use a particular concept. Alternatively, another edge 206 may represent each type of relationship (or multiples of an individual relationship) between a user node 202 and a concept node 204 (as illustrated in Figure 2 between user node 202 for user "E" and concept node 204 for "SPOTIFY").

In particular embodiments, the social network system 160 can create a border 206 between a user node 202 and a concept node 204 in social graphics 200. As an example and not by way of limitation, a user viewing a concept profile page (such as, for example, when using a web browser or a special purpose application hosted by the user's client system 130) may indicate that you like the concept represented by concept node 204 when clicking or selecting a "like" icon, that

<img file="MX348259B_D0015.tif" />

IMPI

INSTITUTO MEX1CAN · • F POREDAD INDUSTRIAL may cause the user's client system 130 to send to the social media system 160 a message indicating that the user likes the concept associated with the concept profile page. In response to the message, the social media system 160 may create a border 206 between the user node 202 associated with the user node and concept 204, as illustrated by the "like" border 206 between the user node and concept 204. In particular embodiments, the social networking system 160 can store an edge 206 in one or more data storage. In particular embodiments, a border 206 may be automatically formed by the social media system 160 in response to a particular user action. As an example and not by way of limitation, if a first user uploads an image, watches a movie, or listens to a song, a border 206 may be formed between user nodes 202 that correspond to the first user and concept nodes 204 that correspond to those concepts. Although this description describes forming particular edges 206 into particular shapes, this description contemplates forming any of suitable edges 206 into any suitable shape.

Furthermore, the degree of separation between any two nodes is defined as the minimum number of jumps (or edges) required to traverse the social graph from one node to the other. A degree of separation between two nodes can be considered a measure of the relationship between the users or the concepts represented by the two nodes in the social graph.

<img file="MX348259B_D0016.tif" />

IMPI

INSTITUTO MEXICANO rw Ι.Λ «OHEDAD INBUSTEIAl

As described above, a network siStSrna'tie ^ S SOUlaltTS can store social graph information and other information related to social networking system in one or more data stores. In particular embodiments, the information stored in the data stores can be organized according to specific data structures. Each data store can be a relationship, column, map, or other suitable database. Particular modalities contemplate any of the appropriate types of database. Additionally, each data warehouse (or partition) can be maintained by separate servers or in separate physical locations. In particular modalities, they can provide interfaces that allow the social network system, a client system, or third party system to handle, receive, modify, add, or delete the information stored in the data storage.

A search query submitted to a database can include one or more keyword phrases such as "Pi," "Downton Abbey," "NBA All Star Game," or "world's tallest mountain." A database can index search results for a keyword phrase by dispersing the keyword phrase. For example, a database index server can store, modify, retrieve, or delete search results for a keyboard phrase by applying a hash function to the keyword phrase for a resulting hash value, and store or search the results

<img file="MX348259B_D0017.tif" />

IMPI

MEXICAN INITITUTE

DE LA FROR1IDAP INDUSTRIAL database search in a ublUTüTOll LUI i effundiente to the resulting hash value. That is, a database search index may comprise a hash table associated with the hash function. However, since keyword phrases can be very long, just scattering keyword phrases can result in a very long search index for a database, and can cause higher cost or lower performance when accessing data stored in the database. Particular modalities describe methods for reducing a size of a search index. Particular modalities can determine one or more search terms for a search query by a database, and index the database based on structures of the search terms.

Figure 3 illustrates an illustrative method 300 for indexing a database based on search term structures. Method 300 can be implemented by one or more computing devices (eg, servers) of a social media system, or any suitable system comprising one or more data stores or databases. Method 300 can start at step 310. In particular modalities, in step 310, one or more computing devices of the social network system can receive a search query. For example, a received search query can comprise structured or substantially unstructured text stream sent by a user through a PHP process (Hypertext Preprocessor)

<img file="MX348259B_D0018.tif" />

IMPI

INSTITUTO MEXICANO OF LA HtOPItDA · INDUSTRIAL hosted by the social media system. For cjerrrple, the search query received may be "who are John and Bob's mutual friends?", "Who are tagged in this photo?", "Find interesting places near San Carlos, CA", "who among my friends register in this restaurant? ”, or“ who liked this publication? ”.

In particular embodiments, in step 320, one or more computing devices of the social network system may determine one or more search terms based on the received search query. In particular embodiments, each search term can comprise a prefix and a suffix.

For example, for the received search query "Who are John and Bob's mutual friends?", Computing devices may determine a user ID <177> for "John" and a user ID <213> for "Bob ”. The computing devices may determine that the received search query can be composed of two search terms "friends: <177>" and "friends: <213>. Each of the determined search terms includes a "friends:" prefix (that is, friends of) and a suffix to a user identifier (<177> or <213>). Expected search results for each search term may comprise a list of user identifiers (for example, a list of users who are friends of users <177>). Compute devices can determine results of the received search query by applying an AND operator to the two search results.

<img file="MX348259B_D0019.tif" />

IMPIi

INSTITUTE MLX1CANC DE LA MOHEDA ·

INBUSTUA1 expected search of the two terms of húcqnada datarminarlne (friends AND: <1 77> friends: <21 3>).

For example, computing devices may determine that the received search query "who are tagged in this photo" may be composed of a search term "tagged_in_photo: <65199>", prefixed with a prefix "tagged_in_photo" (that is, users which are tagged in a photo) and a suffix in a photo flag <65199> for “this photo”. Expected results of the search term may comprise a list of user ids that correspond to users tagged in photo <651 99>.

For example, computing devices may determine that the search query received 'Find interesting places near San Carlos, CA' can be composed of a search term 'places_in: <752039>', prefixed with 'places_in' (places on a map tile) and a suffix on a map or tile identifier <752039> that corresponds to “San Carlos, CA”. Here, a map can represent a geographic area, such as the world, a portion of the world, or any suitable area. The map can be divided into map tiles, where each map tile represents a particular geographic area on the map. For example, the map tile <752039> corresponding to San Carlos, CA may comprise a rectangular area with four corners of (37.52, -122.24), (37.52, -122.30), (37.47, -122.30) and (37.47, -122.24) in graphic coordinates. Results

IMPI

ΙΝΓΓΓΠΠΌ ΜΪΧΚΑΝΟ ΜΙΑ Μ MUW 'INDUSTRY!

<img file="MX348259B_D0020.tif" />

The expected search term “places_in: <752039>” can comprise a list of place identifiers (or any of the appropriate concepts), where each place (or concepts) has a location within the rectangular area of ​​the map tile <752039 >.

In particular embodiments, at step 330, for each of the search terms, the computing devices may generate a first binary number, based on each prefix or suffix of the search term. The computing devices can generate a second binary number based on the prefix and generate a third binary number based on an object type of the suffix. Computing devices can generate the first binary number by concatenating the second and third binary numbers.

The computing device may first generate a second binary number for each search term based on each search term prefix. For example, computing devices can assign a search term prefix to a second binary number that is 10 bits long. The 10-bit length for the second binary number can allow the second binary number to represent up to about 1,000 (2¹⁰) different prefixes such as "friends:", "tagged_in_photo:", and "places_in:" described above. Other examples of prefixes may include "posts_of:" (posts by a user), "comments_de" (users wanted comments on a post), and "Likes_of:" (users who like

INSTITUTO MEX1CAN * IW LA FHOnWAD INDUmUAL a publication, a photo, or any i'ünveplu udiuuade). Particular modalities contemplate any of the suitable prefixes of search terms. The computing devices can access a mapping table stored in a social networking system data store and look up the mapping table for a particular 10-bit binary number representing a particular prefix.

The computing devices may generate a third binary number for each search term based on a type of each search term suffix or each type of search term suffix object. The computing devices can determine a length of a third binary number based on the object type of each search term suffix. The computing devices can determine a length of the third binary number for a particular object type so that the length is large enough to uniquely represent all possible objects of the particular object type stored in the social media system. The length of the third binary number can also be greater than twice long enough to represent only all possible objects of the particular object type to avoid collisions associated with a hash function. Here, a collision can indicate that two different input values ​​(hash keys) supplied to a hash function can result in an identical result (hash value). A collision does not have a one-to-one mapping property as desired for

<img file="MX348259B_D0021.tif" />

IMPI

INSTITUTO MEXICANO Oí LA PftOm »AD INDUSTRIAL indexed. For example, computing devices can generate a 37-bit binary number for a suffix of a user identifier. That is, a user identifier can be converted to a 37-bit binary number. A 37-bit binary number may be enough to represent only 2¹⁵ different users of the social media system. As another example, computing devices can generate a 64-bit binary number for a suffix of a concept identifier (eg, a place identifier). That is, a concept identifier can be converted to a 64-bit binary number. A 64-bit binary number may be sufficient to represent only 2³⁰ different nodes of social media system concept. As yet another example, computing devices can generate a 32-bit binary number for a suffix of a map mosaic identifier. That is, a map mosaic identifier can be converted to a 32-bit binary number. A 32-bit binary number may be enough to represent only 2¹⁵ different map tiles for maps stored in the social media system. In particular modalities they contemplate any type of object with a suitable suffix. For example and without limitation, a suffix object type can correspond to a user, a place, a concept, a map tile, a post, a photo, a place, an application, an event, a web page, or a video. .

In particular modalities, the computing devices can generate the first binary number by concatenating the second and

<img file="MX348259B_D0022.tif" />

IMPI

INSTITUTO MLXICANO OE LA RROFttDAD INDUSTRIAL the third binary number. For example, the first binary number for the search term "friends: <177>" may comprise a (second) 10-bit binary number representing the prefix "friends:", concatenated by a (third) 37-bit binary number which represents the suffix <177>. Thus, the first binary number for the search term "friends: <177>" is 47 bits long. As another example, the first binary number for the search term “tagged_in_photo: <65199>” may comprise a (second) 10-bit binary number representing the prefix “tagged_in_photo:”, concatenated by a (third) binary number of 64 bits representing the suffix <65199>. Thus, the first binary number for the search term "tagged_in_photo: <65199>" is 64 bits long. As yet another example, the first binary number for the search term "places_in: <752039>" comprises a (second) 10-bit binary number representing the prefix "places_in:", concatenated by a (third) binary number of 32 bits representing the suffix <752039>. Thus, the first binary number for the search term “places_in: <752039>” is 42 bits long.

In particular embodiments, at step 340, for each search term, the computing devices can access and retrieve one or more search results for the search term from one or more data stores by scattering the first binary number. Compute devices can spread the first binary number with a suitable hash function. That is to say,

<img file="MX348259B_D0023.tif" />

IMPI

INSTITUTO MEXICANO rw LA FHOMEDAn IN8USTXIAE data stores can index search results for the first binary number that corresponds to each search term with one or more hash tables associated with the hash function. In some embodiments, computing devices can apply an invertible transform function to the first binary number before spreading the first binary number with a suitable hash function. In this case, the first binary number may have a "lumpy" characteristic since most of the "1" bits are within a certain bit range in the first binary number. The invertidle transform function can transform the first lumpy binary number to a more evenly distributed form (eg, "1" bit is more evenly distributed among all the bits of the first binary number), thereby avoiding possible collisions associated with the function. hash. Here, an invertible function F has a behavior in that x = F '¹ (F (x)), where F '¹ is the inverse of F.

In particular embodiments, the data stores can hold a plurality of hash frames. Each hash box can index search results for each search term of a particular suffix object type. That is, data stores can index search results based on an object type of a search term suffix. For example, data stores may maintain a hash table for search terms with user object type suffixes (for example, "friends: <177>" where the

<img file="MX348259B_D0024.tif" />

IMPI

INSTITUTO MEXICANO DE LA η TIMA »INDUSTRIAL suffix <177> is a user identifier). Data stores can hold another hash box for search terms with concept object type suffixes (for example, “tagged_in_photo: <65199>” where <65199> is a concept identifier). Data stores can hold yet another hash box for search terms with map tile object type suffixes (for example, "places_in: <752039>" where <752039> is a map tile identifier). Furthermore, each hash box can comprise one or more prefix maps that can index prefixes of search terms. In one embodiment, each of the data stores may be configured to store objects of an individual object type. For example, a data store may be configured to store user objects (and information associated with each stored user object). Other data storage may be configured to store concept objects (and information associated with each stored concept object). A third data store may be configured to store map tile objects (and information associated with each stored map tile object). Each of the data stores may comprise one or more hash frames described above.

By comparison, without using different length binary numbers to represent search terms based on each type of search term suffix object described

<img file="MX348259B_D0025.tif" />

IMPI

INSTITUTO MEXICANO K LA MONEDAD INDUSTRIAL previously, a long binary number h। ¡»« P? -?

represent any of the search terms for any type of suffix object (or lack thereof). For example, a 96-bit binary number can be used to uniquely represent any of the search terms for the social media system. However, a corresponding individual hash box used to index search terms represented by 96-bit binary numbers can be as large as the hash boxes used to index search terms with the shorter binary numbers described above. That is, particular modalities can determine a search term structure in the search term prefix and suffix, and represent the search term with a shorter binary number based on the suffix object type, thereby reducing frame sizes. hash. For example, particular modalities can reduce a total size of hash boxes by more than 20% for the social media system.

In one embodiment, the computing devices can generate the first binary number without generating a second binary number and a third binary number as described above. For example, computing devices can generate a 64-bit binary number representing a search term, if computing devices cannot determine a prefix or suffix for the search term. Computing devices can access and retrieve one or more test results from data stores.

<img file="MX348259B_D0026.tif" />

IMPI

INSTITUTO MEJUCAN · DE LA FROFIEDAD INDUSTRIAL search for the search term when dispér ^ iF he nilITIUlU Ullldllu of 64 bits.

In particular embodiments, in step 350, the computing devices can aggregate search results for the respective search terms. For example, for the search query received "who are mutual friends of John and Bob?" described above, computing devices can retrieve a first set of results (eg, users <1>, <3>, <11>) from the data store for the search term "friends: <177>". Compute devices can retrieve a second set of results (for example, users <1>, <11>, <17>, <28>) from the data stores for the search terms "friends: <213>". Compute devices can aggregate search results by ANDing the first and second groups of results, generating aggregated search results (for example, users <1>, <11>).

Particular modalities may repeat one or more steps of the method of Figure 3, where appropriate. Although this description describes and illustrates particular steps of the method of Figure 3 as occurring in a particular order, this description contemplates any suitable steps of the method of Figure 3 occurring in any suitable order. Furthermore, although this description describes and illustrates particular components, devices, or systems that carry out particular steps of the method of Figure 3, this description contemplates any

<img file="MX348259B_D0027.tif" />

IMPI

INSTITUTO MEXICANO LA PROM EDA · INDUSTRIAL suitable combination of any suitable component, device, or system that carries out any of the appropriate steps of the method in Figure 3.

Figure 4 shows an illustrative computer system 400. In particular embodiments, one or more computer systems 400 perform one or more steps of one or more methods described or illustrated herein. In particular embodiments, one or more computer systems 400 provide functionality described or illustrated herein. In particular embodiments, software running on one or more computer systems 400 performs one or more steps of one or more methods described or illustrated herein or provides functionality described or illustrated herein. Particular modalities include one or more portions of one or more computer systems 400. Here, reference to a computer system may encompass a computing device, and vice versa, where appropriate. In addition, reference to a computer system may encompass one or more computer systems, where appropriate.

This description contemplates any suitable number of computer systems 400. This description contemplates the computer system 400 taking any suitable physical form. As an example and not by way of limitation, computer system 400 may be an embedded computer system, a system on chip (SOC), a single card computer (SBC) system (such as, for example, a computer in module (COM) or system in module (SOM)), a desktop computer system, a

<img file="MX348259B_D0028.tif" />

laptop or notebook computer system, ύΠ interactive computer, macrocomputer, network of computer systems, mobile phone, personal digital assistant (PDA), server, tablet computer system, or a combination of two or more of these. Where appropriate, the computer system 400 may include one or more computer systems 400; be unitary or distributed; span multiple locations; span multiple machines; span multiple data centers; or reside in a cloud, which can include one or more cloud components on one or more networks. Where appropriate, one or more computer systems 400 may perform without substantial spatial or temporal limitation one or more steps of one or more methods described or illustrated herein. As an example and not by way of limitation, one or more computer systems 400 may perform in real time or batch mode one or more steps of one or more methods described or illustrated herein. One or more computer systems 400 may perform at different times or at different locations one or more steps of one or more methods described or illustrated herein, where appropriate.

In particular embodiments, computer system 400 includes a processor 402, memory 404, storage 406, an input / output (I / O) interface 408, a communication interface 410, and a common conductor 412. Although this description describes and illustrates a particular computer system that has a particular number of particular components in a particular arrangement, this description contemplates any computer system

<img file="MX348259B_D0029.tif" />

having any suitable number of any suitable components in any suitable arrangement.

In particular embodiments, processor 402 includes hardware for executing instructions, such as those that make up a computer program. As an example and not by way of limitation, to execute instructions, processor 402 can retrieve (or search) instructions from an internal register, an internal cache, memory 404, or storage 406; decode and execute them; and then write one or more results to an internal register, internal cache, 404 memory, or 406 storage. In particular embodiments, processor 402 can include one or more internal caches for data, instructions, or addresses. This description contemplates processor 402 including any suitable number of any suitable internal caches, where appropriate. As an example and not by way of limitation, processor 402 may include one or more instruction caches, one or more data caches, and one or more lateral translation buffers (TLBs). Instructions in the instruction caches can be copies of instructions in memory 404 or storage 406, and the instruction caches can speed up retrieval of those instructions by processor 402. The data in the data caches can be copies of data in memory 404 or storage 406 for instructions that are executed in processor 402 to operate;

<img file="MX348259B_D0030.tif" />

IMPI

INSTITUTO MEXICANO DE LA FROREDAD INDUSTRIA!

the results of Previous Instructions executes4a «- M-4J- ^ u ££ &amp; adA £, 402 for access by subsequent instructions executing in processor 402 or to write to memory 404 or storage 406; or other suitable data. Data caches can speed up read or write operations by processor 402. TLBs can speed up virtual address translation for processor 402. In particular embodiments, processor 402 can include one or more internal registers for data, instructions, or addresses. This description contemplates processor 402 including any suitable number of any suitable internal registers, where appropriate. Where appropriate, processor 402 may include one or more arithmetic logic units (ALUs); be a multi-core processor; or include one or more 402 processors. Although this description describes and illustrates a particular processor, this description contemplates any suitable processor.

In particular embodiments, memory 404 includes main memory for storing instructions for processor 402 to execute data for processor 402 to operate. As an example and not by way of limitation, computer system 400 may load instructions from storage 406 or other source (such as, for example, another computer system 400) to memory 404. Processor 402 can then load instructions from memory 404 to an internal register or internal cache. To execute the instructions, the processor 402 can retrieve the

<img file="MX348259B_D0031.tif" />

IMPI

INrrtTUTO MUICAN · MUMUWISPAD INDUSTUAL instructions from the internal register or internal cache memory and decode them. During or after execution of instructions, processor 402 may write one or more results (which may be intermediate or final results) to the internal register or internal cache. Processor 402 can then write one or more of those results to memory 404. In particular embodiments, processor 402 only executes instructions in one or more internal registers or internal caches or memory 404 (as opposed to storage 406 or elsewhere) and operates only on data in one or more internal registers or internal caches. or in memory 404 (as opposed to storage 406 or elsewhere). One or more common memory leads (each which may include a common address lead and a common data lead) may couple processor 402 to memory 404. Common lead 412 may include one or more common memory leads, such as outlined below. In particular embodiments, one or more memory management units (MMU) residing between processor 402 and memory 404 facilitate access to memory 404 requested by processor 402. In particular embodiments, the memory 404 includes random access memory (RAM). This RAM can be volatile memory, where appropriate. Where appropriate, this RAM can be dynamic RAM (DRAM) or static RAM (SRAM). In addition, where appropriate, this RAM can be single port RAM or multiple ports. This description contemplates „IMPIAS

4 INJTTTVT · MEXICAN J tt the nonciMü or ^ 3L · any suitable RAM. Memory 404 may include one or more memories 404, where appropriate. Although this description describes and illustrates particular specification, this description contemplates any suitable specification.

In particular embodiments, storage 406 includes bulk storage for data or instructions. As an example and not by way of limitation, storage 406 may include a hard disk drive (HDD), a floppy disk drive, flash memory, an optical disk, a magneto-optical disk, magnetic tape, a driver unit. Universal Serial Common (USB) or a combination of two or more of these. Storage 406 may include removable or non-removable (or fixed) media, where appropriate. Storage 406 may be internal or external to computer system 400, where appropriate. In particular embodiments, storage 406 is solid state, non-volatile memory. In particular embodiments, storage 406 includes read-only memory (ROM). Where appropriate, this ROM may be mask-programmed ROM, programmable PROM (PROM), erasable PROM (EPROM), electrically erasable PROM (EEPROM), electrically alterable ROM (EAROM), flash memory, or a combination of two or more of these. these. This description contemplates mass storage 406 taking any suitable physical form. Storage 406 may include one or more storage control units that facilitate communication between processor 402 and storage.

<img file="MX348259B_D0032.tif" />

406, where appropriate. Where appropriate, storage 406 may include one or more storage 406. Although this description describes and illustrates particular storage, this description completes any suitable storage.

In particular embodiments, the I / O interface 408 includes hardware, software, or both, that provide one or more interfaces for communication between the computer system 400 and one or more I / O devices. The computer system 400 may include one or more of these I / O devices, where appropriate. One or more of these I / O devices may allow communication between a person and computer system 400. As an example and not by way of limitation, an I / O device may include a keyboard, numeric keypad, microphone, monitor, mouse, printer, scanner, speaker, still camera, stylus, tablet, touch screen, trackball, video camera. , another suitable I / O device, or a combination of two or more of these. An I / O device can include one or more sensors. This description contemplates any of the suitable I / O devices and any of the suitable I / O interfaces 408 therefor. Where appropriate, I / O interface 408 may include one or more software devices or drivers that allow processor 402 to drive one or more of these I / O devices. The I / O interface 408 may include one or more I / O interfaces 408, where appropriate. Although this description describes and illustrates a particular I / O interface, this description contemplates any interface

<img file="MX348259B_D0033.tif" />

l / O adequate.

In particular embodiments, communication interface 410 includes hardware, software, or both that provide one or more interfaces for communication (such as, for example, packet-based communication) between computer system 400 and one or more other communication systems. computer 400 or one or more networks. As an example and not by way of limitation, communication interface 410 may include a network interface controller (NIC) or network adapter to communicate with an Ethernet or other cable-based network or wireless NIC (WNIC) or wireless adapter. to communicate with a wireless network, such as a Wi-Fi network. This description contemplates any suitable network and any suitable communication interface 410 therefor. As an example and not by way of limitation, the computer system 400 can communicate with an ad hoc network, a personal area network (PAN), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), or one or more portions of the Internet or a combination of two or more of these. One or more portions of one or more of these networks can be wired or wireless. As an example, the computer system 400 can communicate with a wireless PAN (WPAN) (such as, for example, a Bluetooth WPAN), a Wi-Fi network, a WiMAX network, a cell phone network (such as, for example, a global system for mobile communications (GSM) network, or other suitable wireless network or a combination of two or more of these. The computer system

<img file="MX348259B_D0034.tif" />

400 it can include any communication interface — AXQu_a &lt;i ^ w * da - for any of these networks, where appropriate. Communication interface 410 may include one or more communication interfaces 410, where appropriate. Although this description describes and illustrates a particular communication interface, this description contemplates any suitable communication interface.

In particular embodiments, common conductor 402 includes hardware, software, or both that couple components of the computer system 400 together. As an example and not by way of limitation, common driver 412 may include an accelerated graphics port (AGP) or other common graphics driver, an Enhanced Industry Standard Architecture (EISA) common driver, a front-side common driver (FSB), a HYPERTRANSPORTE (HT) interconnect, an Industry Standard Architecture (ISA) common conductor, an INFINIBAND interconnect, a low terminal count common conductor (LPC), a memory common conductor, a common microchannel architecture (MSA) driver, a common Peripheral Component Interconnect (PCI) driver, a common PCI Express (PCIe) driver, a common Serial Advanced Technology Attach (SATA) driver, a common driver local video electronics standards association (VLB), or other suitable common conductor or a combination of two or more of these. Common conductor 412 may include one or more common conductors 412, where appropriate. Although this description describes and illustrates a particular common conductor, this

<img file="MX348259B_D0035.tif" />

description contemplates any common conductor ui 11 Ibiluii ^ xIOTI— suitable.

Here, a computer-readable non-transient storage medium or media may include one or more semiconductor-based or other integrated circuits (ICs) (such as, for example, field-programmable gate array (FPGA) or application-specific ICs ( ASIO)), Hard Disk Drives (HDD), Hybrid Hard Drives (HHD), Optical Disks, Optical Disk Drives (ODD), Magneto-Optical Disks, Magneto-Optical Drives, Floppy Disks, Floppy Disk Drives (FDD) , magnetic tapes, solid state drives (SSD), RAM drives, SECURE DIGITAL drives or cards, any other suitable non-transient computer-readable storage media, or any suitable combination of two or more of these, where appropriate. A non-transient computer-readable storage medium can be volatile, non-volatile, or a combination of volatile and non-volatile, where appropriate.

Here, "or" is inclusive and non-exclusive, unless expressly stated otherwise or otherwise indicated by context.

Therefore, "A or B" herein means "A, B, or both," unless expressly stated herein or otherwise indicated by context. Furthermore, "and" is both one and more, unless expressly stated otherwise or otherwise indicated by context.

Therefore, "A and B" here means "A and B, together or separately," unless expressly stated otherwise.

<img file="MX348259B_D0036.tif" />

IMPIÍ

INSTITUTO MEXICANO Dt LA FROFtEDAD INDUSTRIAL or otherwise indicated by context.

The scope of this description encompasses all changes, substitutions, variations, alterations, and modifications to the illustrative embodiments described or illustrated herein that one skilled in the art would understand. The scope of this description is not limited to the illustrative embodiments described or illustrated herein. Furthermore, although this description describes and illustrates respective modalities here as including particular components, elements, functions, operations, or steps, any of these modalities may include any combination or change of any of the components, elements, functions, operations, or steps. described or illustrated anywhere herein that one skilled in the art would understand. Furthermore, reference in the appended claims to an apparatus or system or a component of an apparatus or system that is adapted for, arranged for, capable of, configured for, enabled for, operable for, or operative to perform a particular function encompasses that device, system, component, whether or not this or that particular function is activated, turned on, or unlocked, as long as that device, system, or component is thus adapted, arranged, capable, configured, enabled operable, or operative.

<img file="MX348259B_D0037.tif" />

IMPI

INSTITUTE MUCAN

M LA FROTIIDA »industrial