NATURAL LANGUAGE QUERY PROCESSING

• US 20080263019A1
• Filed: 04/18/2008
• Published: 10/23/2008
• Est. Priority Date: 09/24/2001
• Status: Active Grant

• Current Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Original Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Inventors: Chevsky, Gary, Harrison, Tom, Lowe, John, Barrett, Michael E., Reddi, Swarup
• Granted Patent: US 7,917,497 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An enhanced natural language information retrieval technique tokenizes an incoming query, comparing the tokenized representation against a collection of query templates. Query templates include a first portion having one or more query patterns representative of a query and in a form suitable for matching the tokenized representation of an incoming query. Query templates also include one or more information retrieval commands that are designed to return information relevant to those query patterns in its first portion. The enhanced natural language information retrieval technique selects those query templates that are determined to be most relevant to the incoming query (via its tokenized representation) and initiates one or more information retrieval commands associated with the selected query templates.

Claims

1-23. -23. (canceled)

24. A natural language method to tokenize a query, comprising:

identifying semantic units in a query;

associating a token with each uniquely identified semantic unit;

identifying stems for one or more of the tokens;

identifying lexical equivalents for one or more of the tokens; and

representing the query as an ordered combination of the identified stems and tokens.

25. The method of claim 24, wherein the act of identifying a semantic unit comprises identifying single words, multiple word phrases, and arbitrary but predefined character strings.

26. The method of claim 25, wherein the act of identifying arbitrary but predefined character strings comprises identifying email addresses, telephone numbers, acronyms, time indications, state designations, addresses or uniform resource locators (URLs).

27. The method of claim 24, wherein the act of associating comprises using one or more dictionaries.

28. The method of claim 24, wherein the act of identifying lexical equivalents comprises identifying misspellings, synonyms or hyponyms for at least one of the identified semantic units.

29. The method of claim 28, wherein the act of identifying lexical equivalents further comprises associating each of the identified lexical equivalents for a semantic unit with that semantic unit'"'"'s token.

30. The method of claim 24, wherein the act of representing comprises combining two or more of the identified tokens in an ordered sequence to represent a meaning of the query.

31. The method of claim 30, wherein the act of combining two or more identified tokens in an ordered sequence comprises one or more logical operators.

33. A natural language query template accessible by a program being executed on a programmable control device, comprising:

a first portion having a sequence pattern representing a query, wherein the sequence pattern includes an ordered sequence of one or more required elements and zero or more optional elements; and

a second portion having a dynamic command sequence for generating a response to the query.

32. The method of claim 40, wherein the act of combining two or more identified tokens in an ordered sequence comprises a proximity connector.

34. The natural language query template of claim 33, wherein the sequence pattern comprises one or more tokens, each of said one or more tokens associated with a semantic unit of the query.

35. The natural language query template of claim 34, wherein the one or more tokens represent a single word, a multiple word phrase or an arbitrary but predefined character string in the query.

36. The natural language query template of claim 35, wherein an arbitrary but predefined character string comprises an email addresses, a telephone number, an acronym, a time indication, a state designation, an addresses or a uniform resource locators (URLs).

37. The natural language query template of claim 33, wherein the first portion comprises two or more sequence patterns.

38. The natural language query template of claim 33, wherein the command sequence comprises a computer executable instruction.

39. The natural language query template of claim 38, wherein the computer executable instruction comprises a BAG OF WORDS search command.

40. The natural language query template of claim 38, wherein the computer executable instruction comprises a SOFT AND search command.

41. The natural language query template of claim 38, wherein the computer executable instruction comprises a SOFT NOT search command.

42. The natural language query template of claim 38, wherein the computer executable instruction comprises a search command, a SQL database query, a uniform resource locator (URL) display command or a operating system call.

43. The natural language query template of claim 42, wherein the computer executable instruction initiates a communication between a user submitting the query and a service provider organization.

44. The natural language query template of claim 43, wherein the communication comprises a Internet chat communication.

45. The natural language query template of claim 43, wherein the communication comprises an email communication.

46. The natural language query template of claim 38, wherein the command sequence comprises a static command sequence.

47. The natural language query template of claim 38, wherein the command sequence comprises a dynamic command sequence.

48. The natural language query template of claim 47, wherein the command sequence comprises a slot that is filled-in with a token from the sequence pattern from the first portion.

49. The natural language query template of claim 33, wherein the second portion comprises two or more command sequences.

50. The natural language query template of claim 49, wherein each of the two or more command sequences are selected for execution.

51. The natural language query template of claim 49, wherein one of the two or more command sequences are selected for execution.

52. A method to index data, comprising:

identifying semantic units in each of a plurality of data units;

associating an identified semantic unit with a location in each of the data units in which the identified semantic unit is found;

associating tokens with each uniquely identified semantic unit; and

indexing the tokens.

53. The method of claim 52, wherein the act of identifying semantic units comprises identifying single words, multiple word phrases, and arbitrary but predefined character strings.

54. The method of claim 53, wherein the act of identifying arbitrary but predefined character strings comprise identifying email addresses, telephone numbers, acronyms, time indications, state designations, addresses or uniform resource locators (URLs).

55. The method of claim 53, wherein the act of identifying comprises using a dictionary.

56. The method of claim 53, wherein the act of identifying semantic units further comprises identifying misspellings, stems, synonyms, or hyponyms for at least one of the identified semantic units.

57. The method of claim 53, wherein the act of identifying further comprises identifying syntactic elements in at least one of the data units.

58. The method of claim 57, wherein the act of identifying syntactic elements comprise identifying line breaks, paragraph breaks, or sentence breaks.

59. The method of claim 52, wherein the act of identifying data units comprise identifying text documents, web pages, uniform resource locators (URLs) or database tables.

60. The method of claim 52, wherein the act of indexing comprises organizing the identified tokens in a predetermined lexical ordering.