Generating midstring query refinements

• US 8,577,913 B1
• Filed: 05/27/2011
• Issued: 11/05/2013
• Est. Priority Date: 05/27/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hansson, Othar, Das, Anwis, Home, James, Levin, Michael, Das, Abhinandan
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Waldron, Scott A
• Application Number:
  US13/118,196
• Time in Patent Office: 893 Days
• Field of Search: 707/767, 707/768, 715/856
• US Class Current: 707/767
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/3328 using graphical result space presentation or visualisation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 3/048 Interaction techniques based on graphical user interfaces [GUI]

Abstract

A system and method is provided for providing query suggestions, particularly midstring query completions for an original query being edited or hovered over. An original query is received from a client. One or more segments in the original query are identified including an anchor segment and zero or more remaining segments. The anchor segment is identified based on cursor placement within the original query. Then one or more sibling segments associated with the anchor segment are identified. The sibling segments are identified by the server system to be semantically distinct from anchor segment. Then one or more query refinement candidates are identified. A respective query refinement candidate includes a sibling segment in place of the anchor segment and includes the remaining segments, if any, of the original query. Then information including one or more of the query refinement candidates is sent to the client for presentation.

Claims

1. A method for query suggestion, performed on a server system having one or more processors and memory storing one or more programs for execution by the one or more processors to perform the method, comprising:

at the server system;

receiving an original query from a client distinct from the server system;

identifying one or more segments in the original query;

identifying an anchor segment of the one or more segments in the original query, wherein the anchor segment is identified based on cursor placement within the original query, and identifying zero or more remaining segments of the original query, excluding the anchor segment;

identifying one or more sibling segments associated with the anchor segment, wherein the one or more sibling segments are identified by the server system to be semantically distinct from anchor segment;

identifying one or more query refinement candidates, wherein a respective query refinement candidate includes a respective sibling segment in place of the anchor segment and includes the remaining segments, if any, of the original query;

sending to the client for presentation information including one or more of the query refinement candidates;

receiving from the client one or more deleted characters from the original query and any remaining characters from the original query, the remaining characters consisting of characters of the original query which are not deleted characters; and

reconstructing the original query from the deleted characters and the remaining characters;

wherein the one or more sibling segments are identified using an algorithm that identifies sibling segments that are conceptually related to the anchor segment; and

wherein, when the original query includes two or more segments, including the anchor segment and one or more remaining segments, identifying the one or more query refinement candidates comprises;

forming potential query refinement candidates from the identified sibling segments and the one or more remaining segments; and

excluding from the identified one or more query refinement candidates any of the potential refinement candidates not present in a predefined database of historical complete queries.

2. The method of claim 1, wherein a segment is identified as an anchor segment when the cursor position is within or directly adjacent to a word in the segment without modifying the original query.

3. The method of claim 1, wherein after an anchor segment has been identified, user initiated deletion of characters in the anchor segment does not affect the identification of the one or more sibling segments.

4. The method of claim 1, wherein the sibling segment is identified without regard to any characters in the anchor segment.

5. The method of claim 1, wherein the one or more sibling segments are identified from refinements to the anchor segment submitted by a user in a community of users.

6. The method of claim 1, wherein the one or more sibling segments are identified using an algorithm that identifies sibling segments that are conceptually related to the anchor segment.

7. The method of claim 1, wherein the one or more sibling segments are identified using an algorithm that identifies sibling segments that have similar meaning to the anchor segment.

8. The method of claim 1, wherein the one or more sibling segments are identified using an algorithm that identifies sibling segments that have similar meaning to the anchor segment;

and

wherein, when the original query includes two or more segments, including the anchor segment and one or more remaining segments, identifying the one or more query refinement candidates comprises;

forming potential query refinement candidates from the identified sibling segments and the one or more remaining segments; and

excluding from the identified one or more query refinement candidates any of the potential query refinement candidates not present in a predefined database of historical complete queries.

9. The method of claim 1, further comprising:

when the original query includes two or more segments,

identifying one or more remaining segments of the original query, excluding the anchor segment;

creating a template including the one or more remaining segments of the original query and a placeholder corresponding to the anchor segment; and

selecting one or more query refinement candidates in accordance with a requirement that the one or more query refinement candidates meet the template.

10. The method of claim 1, further comprising:

receiving from the client, one or more new characters inputted by the user;

creating a template including the zero or more remaining segments of the original query, and further including the one or more new characters; and

selecting one or more query refinement candidates that meet the template.

11. The method of claim 10, wherein when the one or more new characters inputted by the user are directly adjacent to a character of a remaining portion of the anchor segment, the template includes a revised segment comprising the remaining portion of the anchor segment and the adjacent one or more new characters.

12. The method of claim 1, further comprising, prior to the sending, selecting one or more of the query refinement candidates in accordance with one or more predefined criteria selected from the group consisting of popularity criteria, relevance to original query criteria, user interest criteria, quality criteria, and filter-out criteria;

wherein the one or more query refinement candidates sent to the client comprise the selected one or more query refinement candidates.

13. The method of claim 12, wherein selecting query refinement candidates comprises:

ranking the query refinement candidates based on popularity criteria; and

selecting a subset of the ranked query refinement candidates as query refinement candidates based in part the ranking.

14. The method of claim 13, wherein the selecting further comprises not selecting query refinement candidates that are irrelevant to the original query in accordance with the predefined criteria for relevance to original query.

15. The method of claim 12, wherein the selecting further comprises not selecting query refinement candidates that are misspelled, contain information that is at least potentially personally identifiable, or contain one or more terms in a predefined set of offensive terms.

16. The method of claim 1, further comprising:

when the original query includes two or more segments,

identifying the zero or more remaining segments comprises identifying one or more remaining segments of the original query, excluding the anchor segment; and

identifying the one or more query refinement candidates comprises identifying respective query refinement candidates that each include the sibling segment in place of the anchor segment and also includes the one or more remaining segments of the original query.

17. A server system, for query suggestion, comprising:

one or more processors; and

memory storing one or more programs to be executed by the one or more processors;

the one or more programs comprising instructions for;

receiving an original query from a client distinct from the server system;

identifying one or more segments in the original query;

identifying an anchor segment of the one or more segments in the original query, wherein the anchor segment is identified based on cursor placement within the original query, and identifying zero or more remaining segments of the original query, excluding the anchor segment;

identifying one or more sibling segments associated with the anchor segment, wherein the one or more sibling segments are identified by the server system to be semantically distinct from anchor segment;

identifying one or more query refinement candidates, wherein a respective query refinement candidate includes a respective sibling segment in place of the anchor segment and includes the remaining segments, if any, of the original query;

sending to the client for presentation information including one or more of the query refinement candidates;

receiving from the client one or more deleted characters from the original query and any remaining characters from the original query, the remaining characters consisting of characters of the original query which are not deleted characters; and

reconstructing the original query from the deleted characters and the remaining characters;

wherein the one or more sibling segments are identified using an algorithm that identifies sibling segments that are conceptually related to the anchor segment; and

wherein, when the original query includes two or more segments, including the anchor segment and one or more remaining segments, identifying the one or more query refinement candidates comprises;

forming potential query refinement candidates from the identified sibling segments and the one or more remaining segments; and

excluding from the identified one or more query refinement candidates any of the potential refinement candidates not present in a predefined database of historical complete queries.

18. The server system of claim 17, wherein the sibling segment is identified without regard to any characters in the anchor segment.

19. The server system of claim 17, wherein the one or more programs further comprise instructions for:

receiving from the client, one or more new characters inputted by the user;

creating a template including the zero or more remaining segments of the original query, and further including the one or more new characters; and

selecting one or more query refinement candidates that meet the template.

20. The server system of claim 19, wherein when the one or more new characters inputted by the user are directly adjacent to a character of a remaining portion of the anchor segment, the template includes a revised segment comprising the remaining portion of the anchor segment and the adjacent one or more new characters.

21. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions for:

at a server system;

receiving an original query from a client distinct from the server system;

identifying one or more segments in the original query;

identifying an anchor segment of the one or more segments in the original query, wherein the anchor segment is identified based on cursor placement within the original query, and identifying zero or more remaining segments of the original query, excluding the anchor segment;

identifying one or more sibling segments associated with the anchor segment, wherein the one or more sibling segments are identified by the server system to be semantically distinct from anchor segment;

identifying one or more query refinement candidates, wherein a respective query refinement candidate includes a respective sibling segment in place of the anchor segment and includes the remaining segments, if any, of the original query;

sending to the client for presentation information including one or more of the query refinement candidates;

receiving from the client one or more deleted characters from the original query and any remaining characters from the original query, the remaining characters consisting of characters of the original query which are not deleted characters; and

reconstructing the original query from the deleted characters and the remaining characters;

wherein the one or more sibling segments are identified using an algorithm that identifies sibling segments that are conceptually related to the anchor segment; and

wherein, when the original query includes two or more segments, including the anchor segment and one or more remaining segments, identifying the one or more query refinement candidates comprises;

forming potential query refinement candidates from the identified sibling segments and the one or more remaining segments; and

excluding from the identified one or more query refinement candidates any of the potential refinement candidates not present in a predefined database of historical complete queries.

22. The non-transitory computer readable storage medium of claim 21, wherein the sibling segment is identified without regard to any characters in the anchor segment.

23. The non-transitory computer readable storage medium of claim 21, wherein the one or more programs further comprise instructions for:

receiving from the client, one or more new characters inputted by the user;

creating a template including the zero or more remaining segments of the original query, and further including the one or more new characters; and

selecting one or more query refinement candidates that meet the template.

24. The non-transitory computer readable storage medium of claim 23, wherein when the one or more new characters inputted by the user are directly adjacent to a character of a remaining portion of the anchor segment, the template includes a revised segment comprising the remaining portion of the anchor segment and the adjacent one or more new characters.