Indexing quoted text in messages in conversations to support advanced conversation-based searching

• US 9,262,455 B2
• Filed: 10/30/2013
• Issued: 02/16/2016
• Est. Priority Date: 07/27/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Palay, Andrew J.
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US14/067,855
• Publication Number:
  US 20140089280A1
• Time in Patent Office: 839 Days
• Field of Search: 707/741, 707/673, 707/696, 707/999.101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: H04L 51/216 Handling conversation history, e.g. grouping of messages in sessions or threads

Abstract

A method for indexing quoted text includes, obtaining a plurality of index entries in an index. A respective index entry corresponds to a respective term in one or more messages, and has a plurality of index components; a respective index component identifies a message associated with the respective term. The method further includes, responsive to receiving a first message; updating the index by: associating the first message with a conversation having one or more other messages; identifying text in the first message as quoted text based on text that occurs in one or more of the other messages; and updating, in the index, first-message index components that each includes an identifier of the first message, which includes original text index components and quoted text index components. The quoted text index components include information indicating that the corresponding terms are terms in the quoted text of the first message.

Claims

1. A method comprising:

at a computer having one or more processors and memory storing one or more programs for execution by the one or more processors so as to perform the method;

obtaining a plurality of index entries in an index, a respective index entry corresponding to a respective term in one or more messages, and having a plurality of index components, a respective index component of the respective index entry identifying a message that is associated with the respective term;

responsive to receiving a first message having a message body and a message header;

updating the index by;

associating the first message with a conversation having one or more other messages;

identifying text in the message body of the first message as quoted text based on text that occurs in one or more of the other messages of the conversation; and

adding, to the index, a plurality of first-message index components that each includes an identifier of the first message, including;

 

one or more original text index components that correspond to terms that occur in original text of the message body of the first message; and

 

one or more quoted text index components that correspond to terms in the message body of the first message that occur in the quoted text of the first message; and

responding to a search query having one or more query terms by;

identifying messages including at least one query term in the one or more query terms by searching the index, wherein the searching distinguishes between (A) matches of a query term with original text index components and (B) matches of a query term with quoted text index components, and preparing a response to the search query that includes search results corresponding to the identified messages;

wherein the one or more quoted text index components include information indicating that the corresponding terms are terms in the quoted text of the first message.

2. The method of claim 1, wherein a respective index component for a particular term in the quoted text includes a mapped location that corresponds to an original location of the particular term in the quoted text.

3. The method of claim 2, wherein the mapped location of the particular term is in a predefined range of locations associated only with terms in the quoted text.

4. The method of claim 1, wherein identifying quoted text in the first message includes:

comparing text in the first message to text from a prior message in the conversation;

identifying matching text in the prior message; and

identifying the matching text as quoted text.

5. The method of claim 1, further comprising:

after identifying quoted text in the first message;

receiving a second message that is a prior message in the conversation;

associating the second message with the conversation; and

updating the quoted text in the first message based on the text that occurs in the second message.

6. The method of claim 1, further comprising:

deleting a respective message that is a prior message in the conversation; and

updating the quoted text in the first message based on the text that occurred in the respective message.

7. The method of claim 1, further comprising:

receiving a request for the first message; and

in response to the request,

formatting for display a portion of the first message that excludes at least a portion of the quoted text.

8. The method of claim 1, further comprising:

receiving a request for the conversation including the first message; and

in response to the request,

formatting for display a portion of the first message that excludes the quoted text and at least a portion of a second message in the conversation that includes the quoted text.

9. The method of claim 1, wherein responding to the search query includes ignoring quoted text index components of the index while searching the index to identify messages including at least one query term in the one or more query terms of the search query.

10. The method of claim 1,

wherein responding to the search query includes identifying a respective message as matching the search query, the respective message having original text and quoted text, identifying a first set of one or more terms in the original text of the respective message that match one or more of the query terms, and identifying a second set of one or more terms in the quoted text of the respective message that match one or more of the query terms;

and

wherein preparing the response to the search query includes;

highlighting, in the response, terms in the first set of terms; and

forgoing highlighting, in the response, terms in the second set of terms.

11. The method of claim 10, further comprising:

identifying a third set of one or more terms in a second message that match one or more of the query terms; and

highlighting, in the response, terms in the third set of terms.

12. The method of claim 1, wherein:

the address space for the first message is partitioned using a set of one or more high order address bits to specify partitions;

a mapped location of a term that occurs in original text of the first message in the address space for the first message is specified by an address having one or more high order address bits with a first value; and

a mapped location of a term that occurs in quoted text of the first message in the address space for the first message is specified by an address having one or more high order address bits with a second value different from the first value.

13. The method of claim 1, wherein

each original text index component includes a first indicator indicative of original text and mapped location information indicative of a location of a term within the first message, and

each quoted text index component includes a second indicator indicative of quoted text and mapped location information indicative of a location of a term within the first message.

14. A conversation computer system, comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

obtaining a plurality of index entries in an index, a respective index entry corresponding to a respective term in one or more messages, and having a plurality of index components, a respective index component of the respective index entry identifying a message that is associated with the respective term;

responsive to receiving a first message having a message body and a message header;

updating the index by;

associating the first message with a conversation having one or more other messages;

identifying text in the message body of the first message as quoted text based on text that occurs in one or more of the other messages of the conversation; and

adding, to the index, a plurality of first-message index components that each includes an identifier of the first message, including;

 

one or more original text index components that correspond to terms that occur in original text of the message body of the first message; and

 

one or more quoted text index components that correspond to terms in the message body of the first message that occur in the quoted text of the first message; and

responding to a search query having one or more query terms by;

identifying messages including at least one query term in the one or more query terms by searching the index, wherein the searching distinguishes between (A) matches of a query term with original text index components and (B) matches of a query term with quoted text index components, and preparing a response to the search query that includes search results corresponding to the identified messages;

wherein the one or more quoted text index components include information indicating that the corresponding terms are terms in the quoted text of the first message.

15. The system of claim 14, wherein responding to the search query includes:

identifying a respective message as matching the search query, the respective message having original text and quoted text, identifying a first set of one or more terms in the original text of the respective message that match one or more of the query terms, and identifying a second set of one or more terms in the quoted text of the respective message that match one or more of the query terms; and

wherein preparing the response to the search query includes;

highlighting, in the response, terms in the first set of terms; and

foregoing highlighting, in the response, terms in the second set of terms.

16. The system of claim 14, wherein the one or more programs further comprise instructions to ignore quoted text index components of the index while searching the index to identify messages including at least one query term in the one or more query terms of the search query.

17. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions which, when executed by a conversation computer system with one or more processors, cause the conversation computer system to:

obtain a plurality of index entries in an index, a respective index entry corresponding to a respective term in one or more messages, and having a plurality of index components, a respective index component of the respective index entry identifying a message that is associated with the respective term;

responsive to receiving a first message having a message body and a message header;

update the index by;

associate the first message with a conversation having one or more other messages;

identify text in the message body of the first message as quoted text based on text that occurs in one or more of the other messages of the conversation; and

add, to the index, a plurality of first-message index components that each includes an identifier of the first message, including;

one or more original text index components that correspond to terms that occur in original text of the message body of the first message; and

one or more quoted text index components that correspond to terms in the message body of the first message that occur in the quoted text of the first message;

respond to a search query having one or more query terms by;

identifying messages including at least one query term in the one or more query terms by searching the index, wherein the searching distinguishes between (A) matches of a query term with original text index components and (B) matches of a query term with quoted text index components, and preparing a response to the search query that includes search results corresponding to the identified messages;

wherein the one or more quoted text index components include information indicating that the corresponding terms are terms in the quoted text of the first message.

18. The computer readable storage medium of claim 17, wherein the one or more programs further comprise instructions to ignore quoted text index components of the index while searching the index to identify messages including at least one query term in the one or more query terms of the search query.

19. The computer readable storage medium of claim 17,

wherein responding to the search query includes identifying a respective message as matching the search query, the respective message having original text and quoted text, identifying a first set of one or more terms in the original text of the respective message that match one or more of the query terms, and identifying a second set of one or more terms in the quoted text of the respective message that match one or more of the query terms;

and

wherein preparing the response to the search query includes;

highlighting, in the response, terms in the first set of terms; and

forgoing highlighting, in the response, terms in the second set of terms.