Server side search with multi-word word wheeling and wildcard expansion

• US 7,769,804 B2
• Filed: 01/17/2006
• Issued: 08/03/2010
• Est. Priority Date: 01/17/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sharpe, Timothy D., Thiesson, Bo, Church, Kenneth W.
• Primary Examiner(s): Jacobs; Lashonda T
• Application Number:
  US11/333,486
• Publication Number:
  US 20070168469A1
• Time in Patent Office: 1,659 Days
• Field of Search: 709/203, 709/217, 709/219, 707/5, 707/7, 707/10
• US Class Current: 709/203
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The claimed subject matter provides systems and/or methods that expand input data. An interface can obtain input data and a wildcard insertion component can modify the input data to include at least one implicit wildcard inserted at an end of each intended word. Additionally, an expansion component can generate a candidate list of expanded data based at least in part on the input data including the at least one implicit wildcard utilizing a language model that provides likely expansions of wildcards. Further, the expansion component can evaluate the input data at a server side.

Claims

1. A system that evaluates wildcards, comprising:

an interface that receives input data at a server side, the input data is provided by a client component, the input data comprising at least one wildcard and at least one alphanumeric character;

a wildcard insertion component that evaluates the input data at the server side, the wildcard insertion component inserting at least one implicit wildcard into predefined locations of the input data in addition to the wildcard, the wildcard and the implicit wildcard comprising non-alphanumeric characters; and

an expansion component that evaluates the input data from the wildcard insertion component at the server side utilizing a language model to produce a set of expansions where the wildcard and the implicit wildcard are replaced with additional alphanumeric characters for at least one of the expansions of the set.

2. The system of claim 1, wherein the expansion component employs a suffix tree to produce the set of expansions.

3. The system of claim 2, wherein the suffix tree includes suffixes sorted by popularity and alphabetic order.

4. The system of claim 1, wherein the interface further receives a short message service (SMS) message containing the input data from the client component;

and wherein the expansion component evaluates the received SMS message and provides a return SMS message to the client component that includes n-best search results for the m-best expansions.

5. The system of claim 1, further comprising a local context component that provides expansions relevant to location data of the client component obtained from the client component.

6. The system of claim 5, wherein the local context component utilizes a language model that increases a likelihood of expansions related to places and decreases a likelihood of expansions related to people.

7. The system of claim 5, further comprising a search component that generates results corresponding to the location data for a selected expansion.

8. The system of claim 1, further comprising a filter component that filters a particular expansion from the set based on at least one of a nature of the particular expansion and a nature of a search result associated with the particular expansion.

9. The system of claim 1, further comprising a personalization component that utilizes a particular user'"'"'s preferences and historical data to generate a personalized set of expansions.

10. The system of claim 1, further comprising a rank component that provides an order for the expansions in the set based at least in part upon a likelihood corresponding to each of the expansions.

11. The system of claim 1, further comprising an embedding component that includes results from a search associated with a most likely expansion from the set along with the set of expansions.

12. The system of claim 1, wherein the predefined locations comprise ends of intended words as identified by a space following each of the intended words.

13. A computer-implemented method that facilitates evaluating a wildcard associated with input data, the method comprising computer-implemented operations for:

obtaining input data at a server from a client, the input data comprising at least one explicit wildcard and at least one alphanumeric character;

inserting at the server at least one implicit wildcard input data, the explicit wildcard and the implicit wildcard comprising non-alphanumeric characters;

generating expansions of the explicit wildcard and the implicit wildcard interspersed within the input data utilizing a language model by replacing the explicit wildcard and the implicit wildcard with additional alphanumeric characters; and

creating an order for the expansions in a candidate list that is provided to the client.

14. The computer-implemented method of claim 13, further comprising performing a search based upon a selected expansion from the candidate list.

15. The computer-implemented method of claim 13, creating the order further comprises ordering the expansions based on at least one of a popularity and an alphabetic order.

16. The computer-implemented method of claim 13, further comprising displaying the candidate list such that characters in the expansions that match the input data are visibly distinct from characters that replace the at least one wildcard.

17. The computer-implemented method of claim 13, further comprising filtering a particular expansion from the candidate list based on at least one of a nature of the particular expansion and a nature of a search result associated with the particular expansion.

18. The computer-implemented method of claim 13, further comprising receiving a short message service (SMS) message that includes the input data and transmitting a return SMS message that includes at least one of the candidate list and the n-best search results for the m-best expansions.

19. A system that evaluates a wildcard and performs a search, comprising:

means for receiving input data at a server from a client, the input data comprising at least one explicit wildcard and at least one alphanumeric character;

means for inserting at the server at least one implicit wildcard input data, the explicit wildcard and the implicit wildcard comprising non-alphanumeric characters;

means for generating expansions of the explicit wildcard and the implicit wildcard intermixed in the input data utilizing a language model by replacing the explicit wildcard and the implicit wildcard with additional alphanumeric characters; and

means for performing a search based at least in part upon a particular one of the expansions.

20. A system for evaluating wildcards, comprising:

an interface that receives input data at a server side, the input data is provided by a client component, the input data comprising at least one explicit wildcard and at least one alphanumeric character;

a wildcard insertion component that inserts at least one implicit wildcard into the input data in addition to the wildcard, the explicit wildcard and the implicit wildcard comprising non-alphanumeric characters;

an expansion component that evaluates the input data at the server side utilizing a language model to produce a set of expansions where the explicit wildcard and the implicit wildcard located in a midst of the input data are replaced with additional alphanumeric characters for at least one of the expansions of the set;

a local context component that provides expansions relevant to location data of the client component obtained from the client component;

a search component that generates results corresponding to the location data for a selected expansion;

a filter component that filters a particular expansion from the set based on at least one of a nature of the particular expansion and a nature of a search result associated with the particular expansion;

a personalization component that utilizes a particular user'"'"'s preferences and historical data to generate a personalized set of expansions;

a rank component that provides an order for the expansions in the set based at least in part upon a likelihood corresponding to each of the expansions; and

an embedding component that includes results from a search associated with a most likely expansion from the set along with the set of expansions.

21. The system of claim 20, wherein the language model is a trigram language model.

22. The system of claim 20, wherein the language model is based on web queries.

23. The system of claim 20, wherein the language model is based on syllabic elements.