Query Construction on Online Social Networks

Abstract

In one embodiment, a method includes, by one or more computing systems sending, to a client system of a user, query tokens to be presented to the user, wherein each query token is based on a natural-language string and comprises references to objects associated with an online social network, and wherein the query tokens are selected based on user preferences of the user, receiving, from the client system, a selection of a query token of the query tokens, determining completion tokens that correspond with the selected query token based on the references associated with the selected query token, sending, to the client system, the completion tokens to be presented to the user, receiving, from the client system, a structured query comprising the selected query token and a selected completion token, and sending, to the client system, instructions for presenting search results matching the structured query to the user.

What is claimed is: 
     
         1 . A method comprising, by one or more computing systems:
 sending, to a client system of a first user, one or more query tokens to be presented to the first user, wherein each query token is based on a natural-language string and comprises references to one or more objects associated with an online social network, and wherein the one or more query tokens are selected based on user preferences of the first user;   receiving, from the client system, a selection of a query token of the one or more query tokens;   determining one or more completion tokens that corresponds with the selected query token based on the references associated with the selected query token;   sending, to the client system, the one or more completion tokens to be presented to the first user;   receiving, from the client system, a structured query comprising the selected query token and a selected completion token; and   sending, to the client system, instructions for presenting one or more search results matching the structured query to the first user.   
     
     
         2 . The method of  claim 1 , further comprising:
 generating, in response to receiving the structured query, the one or more search results matching to the structured query.   
     
     
         3 . The method of  claim 1 , wherein:
 the structured query is based on a natural-language string corresponding to the natural-language string of the selected query token.   
     
     
         4 . The method of  claim 1 , further comprising:
 receiving, from the client system, an unstructured text query from the first user;   parsing the unstructured text query into one or more n-grams; and   identifying one or more of the query tokens based at least in part on one or more of the n-grams matching one or more objects referenced by the query token.   
     
     
         5 . The method of  claim 4 , wherein the matching comprises matching one or more of the n-grams to a character string associated with the object referenced by the query token. 
     
     
         6 . The method of  claim 4 , further comprising:
 filtering one or more of the query tokens based at least in part on one or more of the n-grams not matching the object referenced by the query token.   
     
     
         7 . The method of  claim 4 , further comprising:
 identifying one or more of the completion tokens based at least in part on one or more n-grams subsequently provided in response to the selection of the query token.   
     
     
         8 . The method of  claim 4 , wherein the receiving of the unstructured text query comprises receiving, from the client system, one or more characters of a character string as the first user enters the character string into a graphical user interface at the client system. 
     
     
         9 . The method of  claim 8 , wherein the graphical user interface comprises a search-query field of a native application associated with the online social network. 
     
     
         10 . The method of  claim 1 , further comprising:
 sending, to the client system, one or more of the completion tokens to be presented, wherein one or more of the completion tokens are selected based at least in part on each presented completion token being associated with the selected query token.   
     
     
         11 . The method of  claim 1 , wherein accessing one or more of the completion tokens comprises:
 identifying a type associated with the objects referenced by the selected query token; and   identifying one or more completion tokens associated with the determined type of the objects.   
     
     
         12 . The method of  claim 1 , further comprising:
 ranking the completion tokens based at least in part on a popularity measure associated with a combination of the selected query token and each completion token.   
     
     
         13 . The method of  claim 12 , wherein the popularity measure is based at least in part on a search-query history of users of the online social network. 
     
     
         14 . The method of  claim 1 , further comprising ranking the completion tokens based at least in part on a calculated affinity of the selected query token to each completion token. 
     
     
         15 . The method of  claim 14 , wherein the ranking is further based on a combination of the selected query token and the calculated affinity to each completion token. 
     
     
         16 . The method of  claim 1 , further comprising:
 receiving, from the client system, one or more characters subsequent to the selection of the completion token;   sending, to the client system in response to receiving the one or more characters, one or more modifying completion tokens to be presented, wherein each modifying completion token is based on a natural-language string corresponding to the natural-language string associated with the query token and comprises references to one or more objects associated with the online social network;   receiving, from the client system, a selection of at least one of the modifying completion tokens; and   generating, in response to receiving the selection of the at least one of the modifying completion tokens, one or more modified structured queries corresponding to the selected modifying completion token, each modified structured query comprising references to the one or more objects referenced in the selected modifying completion token.   
     
     
         17 . The method of  claim 16 , further comprising:
 generating, in response to the generation of the one or more modified structured queries, the one or more search results matching each of the one or more modified structured queries.   
     
     
         18 . The method of  claim 1 , further comprising:
 accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, wherein each query token comprises references to zero or more nodes and one or more edges, and each query token corresponds to a particular type of completion token, and wherein each completion token comprises references to one or more nodes and zero or more edges, and each completion token being of the particular type corresponding to the selected query token, and wherein the structured query comprising references to the zero or more of the nodes and the one or more edges referenced in the selected query token and references to the one or more of the nodes and the zero or more of the edges of the selected completion token.   
     
     
         19 . One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
 send, to a client system of a first user, one or more query tokens to be presented to the first user, wherein each query token is based on a natural-language string and comprises references to one or more objects associated with an online social network, and wherein the one or more query tokens are selected based on user preferences of the first user;   receive, from the client system, a selection of a query token of the one or more query tokens;   determine one or more completion tokens that corresponds with the selected query token based on the references associated with the selected query token;   send, to the client system, the one or more completion tokens to be presented to the first user;   receive, from the client system, a structured query comprising the selected query token and a selected completion token; and   send, to the client system, instructions for presenting one or more search results matching the structured query to the first user.   
     
     
         20 . A system comprising: one or more processors; and a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:
 send, to a client system of a first user, one or more query tokens to be presented to the first user, wherein each query token is based on a natural-language string and comprises references to one or more objects associated with an online social network, and wherein the one or more query tokens are selected based on user preferences of the first user;   receive, from the client system, a selection of a query token of the one or more query tokens;   determine one or more completion tokens that corresponds with the selected query token based on the references associated with the selected query token;   send, to the client system, the one or more completion tokens to be presented to the first user;   receive, from the client system, a structured query comprising the selected query token and a selected completion token; and   send, to the client system, instructions for presenting one or more search results matching the structured query to the first user.