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

• US 8,583,654 B2
• Filed: 08/29/2011
• Issued: 11/12/2013
• 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:
  US13/220,666
• Publication Number:
  US 20130218896A1
• Time in Patent Office: 806 Days
• Field of Search: 707/741, 707/673, 707/696, 707/999.101
• US Class Current: 707/741
• 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 conversation server system having one or more processors and memory stores a plurality of index components in an index. The server receives a first message, associates the first message with a conversation having one or more other messages and identifies quoted text in the message based on text that occurs in one or more of the other messages. The server stores, in the index, a plurality of first-message index components including one or more index components that correspond to terms in original text of the first message and one or more index components that correspond to terms that occur in the quoted text, where the first-message index components for original text of the first message are distinguished from the first-message index components for quoted text of the first message in the index.

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;

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 of the conversation; and

updating, in 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 first message; and

 

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

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; and

wherein, in the index, the one or more index components indicative of the terms that occur in original text of the first message are distinguished from the one or more index components indicative of terms in the first message that occur only in the quoted text of the first message by partitioning an address space for the first message, the address space having a respective address for each term that occurs in original text of the first message and each term that occurs in quoted text of the first message, wherein the respective address for a respective term in the quoted text of the first message is indicative of a mapped location of the respective term within the address space for the first message.

2. The method of claim 1, further comprising:

responsive to a search query having one or more query terms;

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.

3. 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.

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

5. 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.

6. The method of claim 1, including, 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.

7. The method of claim 1, including:

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.

8. The method of claim 1, including:

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.

9. The method of claim 1, including:

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.

10. The method of claim 1, including:

receiving a search query having one or more query terms; and

performing a search of the index to identify messages including one or more of the query terms, wherein index components corresponding to terms in the quoted text are ignored while performing the search.

11. The method of claim 1, including:

receiving a search query having one or more query terms;

identifying the conversation including the first message as matching the search query, wherein the original text of the first message includes a first set of one or more terms that match one or more of the query terms and the quoted text of the first message includes a second set of one or more terms that match one or more of the query terms;

highlighting terms in the first set of terms; and

foregoing highlighting terms in the second set of terms.

12. The method of claim 11, including:

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

highlighting terms in the third set of terms.

13. 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.

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;

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 of the conversation; and

updating, in 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 first message; and

 

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

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; and

wherein, in the index, the one or more index components indicative of the terms that occur in original text of the first message are distinguished from the one or more index components indicative of terms in the first message that occur only in the quoted text of the first message by partitioning an address space for the first message, the address space having a respective address for each term that occurs in original text of the first message and each term that occurs in quoted text of the first message, wherein the respective address for a respective term in the quoted text of the first message is indicative of a mapped location of the respective term within the address space for the first message.

15. The system of claim 14, wherein the one or more programs further comprising instructions for:

responsive to a search query having one or more query terms;

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.

16. The system of claim 14, including instructions for:

receiving a search query having one or more query terms; and

performing a search of the index to identify messages including one or more of the query terms, wherein index components corresponding to terms in the quoted text are ignored while performing the search.

17. The system of claim 14, including instructions for:

receiving a search query having one or more query terms;

identifying the conversation including the first message as matching the search query, wherein the original text of the first message includes a first set of one or more terms that match one or more of the query terms and the quoted text of the first message includes a second set of one or more terms that match one or more of the query terms;

highlighting terms in the first set of terms; and

foregoing highlighting terms in the second set of terms.

24. The system of claim 14, 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.

25. The system of claim 14, 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, and wherein the mapped location of the particular term is in a predefined range of locations associated only with terms in the quoted text.

18. 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;

update the index by;

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

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

update, in 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 first message; and

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

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; and

wherein, in the index, the one or more index components indicative of the terms that occur in original text of the first message are distinguished from the one or more index components indicative of terms in the first message that occur only in the quoted text of the first message by partitioning an address space for the first message, the address space having a respective address for each term that occurs in original text of the first message and each term that occurs in quoted text of the first message, wherein the respective address for a respective term in the quoted text of the first message is indicative of a mapped location of the respective term within the address space for the first message.

19. The computer readable storage medium of claim 18, wherein the one or more programs further comprising instructions to:

responsive to a search query having one or more query terms;

identify 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.

20. The computer readable storage medium of claim 18, including instructions which, when executed by a conversation computer system with one or more processors, cause the conversation computer system to:

receive a search query having one or more query terms; and

perform a search of the index to identify messages including one or more of the query terms, wherein index components corresponding to terms in the quoted text are ignored while performing the search.

21. The computer readable storage medium of claim 18, including instructions which, when executed by a conversation computer system with one or more processors, cause the conversation computer system to:

receive a search query having one or more query terms;

identify the conversation including the first message as matching the search query, wherein the original text of the first message includes a first set of one or more terms that match one or more of the query terms and the quoted text of the first message includes a second set of one or more terms that match one or more of the query terms;

highlight terms in the first set of terms; and

forego highlighting terms in the second set of terms.

22. The computer readable storage medium of claim 18, 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.

23. The computer readable storage medium of claim 18, 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, and wherein the mapped location of the particular term is in a predefined range of locations associated only with terms in the quoted text.