Index entries configured to support both conversation and message based searching

• US 9,009,142 B2
• Filed: 08/29/2011
• Issued: 04/14/2015
• 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): Beausoliel, Jr., Robert
• Assistant Examiner(s): HOANG, HAU HAI
• Application Number:
  US13/220,664
• Publication Number:
  US 20130262438A1
• Time in Patent Office: 1,324 Days
• Field of Search: None
• US Class Current: 707/722
• 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, a respective index entry corresponding to a respective term 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. The server receives a first message, associates the first message with a conversation having at least one other message and stores, in the index, a plurality of first-message index components that each include an identifier of the first message. The first-message index components include one or more index components indicative of a plurality of message terms in the first message and one or more index components indicative of one or more conversation terms in the conversation, the one or more conversation terms comprising one or more terms that are not in the first message.

Claims

1. A method comprising:

at a server 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;

storing a plurality of index entries in an index, a respective index entry corresponding to a respective term 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;

receiving a first message;

associating the first message with a conversation having at least one other message; and

storing, in the index, a plurality of first-message index components that each include an identifier of the first message, including;

one or more index components indicative of a plurality of message terms in the first message; and

one or more index components indicative of one or more conversation terms in the conversation, the one or more conversation terms comprising one or more terms that are not in the first message;

wherein a respective first-message index component indicative of a conversation term in the conversation includes a value identifying the respective index component as being associated with a conversation term not in the first message.

2. The method of claim 1, wherein the one or more conversation terms include one or more terms that occur in both the first message and a second message in the conversation other than the first message.

3. The method of claim 2, wherein:

the one or more conversation terms include a plurality of terms that occur in both the first message and a second message in the conversation other than the first message;

the plurality of terms occur in a first order in the first message; and

the set of terms occur in a second order, different from the first order, in the second message.

4. The method of claim 1, wherein a respective index component indicative of a conversation term includes a mapped location that corresponds to an original location of the conversation term in the conversation.

5. The method of claim 4, wherein the mapped location of the respective index component indicative of the conversation term is in a predefined range of locations associated only with conversation terms.

6. The method of claim 1, wherein, in the index, the one or more index components indicative of the message terms are distinguished from the one or more index components indicative of the conversation terms.

7. The method of claim 6, wherein the one or more index components indicative of the plurality of message terms are distinguished from the one or more index components indicative of conversation terms by partitioning an address space for the first message, the address space having a respective address for each message term and for each conversation term, wherein the respective address for a respective conversation term in the first conversation is indicative of a mapped location of the respective conversation term within the address space for the first message.

8. The method of claim 7, 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 message term 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 conversation term 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.

9. The method of claim 1, wherein:

the one or more first-message index components include one or more index components indicative of message terms in original text in the first message and one or more index components indicative of message terms in quoted text of the first message; and

in the index, the index components indicative of message terms in the quoted text of the first message are distinguished from the index components indicative of message terms in the original text of the first message.

10. The method of claim 1, further comprising:

storing, in the index, a first-message index component that identifies the first message as a representative message of the conversation.

11. The method of claim 10, including:

receiving a second message subsequent to receiving the first message;

associating the second message with the conversation;

storing, in the index, one or more second-message index components that each include an identifier of the second message, including;

one or more index components indicative of a plurality of message terms in the second message;

one or more index components indicative of one or more conversation terms in the conversation, the one or more conversation terms comprising one or more terms that are not in the second message; and

an index component identifying the second message as the representative message of the conversation; and

removing, from the index, the first-message index component that identifies the first message as the representative message of the conversation.

12. The method of claim 11, further comprising, after receiving the second message:

removing, from the index, the one or more first-message index components indicative of conversation terms.

13. The method of claim 1, further comprising storing a plurality of messages associated with a plurality of conversations, wherein:

each conversation includes a respective representative message;

for each conversation, a respective property of the conversation comprises a corresponding property of the representative message of the conversation; and

the method includes sorting or filtering a list of conversations in accordance with the respective property.

14. The method of claim 1, further comprising, after storing, in the index, the one or more first-message index components indicative of the one or more conversation terms in the conversation:

detecting a modification of a respective message of the one or more other messages in the conversation; and

in response to detecting the modification, updating the one or more first-message index components indicative of the conversation terms that are stored in the index in accordance with the modification of the respective message.

15. The method of claim 1, wherein each conversation includes a respective representative message, the method further including:

receiving a search query from a client;

identifying one or more conversations that match the search query; and

sending, to the client, information enabling display of search results including representations of at least a subset of the conversations that match the search query, wherein the representations of conversations are sorted in accordance with one or more properties of the respective representative messages of corresponding conversations.

16. The method of claim 1, including:

removing a respective message other than the first message from the conversation; and

after removing the respective message, removing from the index one or more first-message index components indicative of one or more conversation terms that occurred in the respective message.

17. The method of claim 1, including:

storing, in the index, an index entry corresponding to a predefined term, wherein the index entry corresponding to the predefined term includes a plurality of index components corresponding to respective messages of a plurality of messages, and the predefined term is an indicator that the respective messages have been marked as active messages; and

in response to a request to ignore a particular message in the plurality of messages, removing the respective index component corresponding to the particular message from the index entry corresponding to the predefined term.

18. The method of claim 1, further comprising, in accordance with a determination that a same logically complete text string occurs in the first message and in the at least one other message in the conversation:

storing, in the index, first-message index components that correspond to the occurrence of the terms in the logically complete text string in the first message; and

forgoing storage of, in the index, first-message index components that correspond to the occurrence of the terms in the logically complete text string in the at least one other message.

19. The method of claim 18, wherein the logically complete text string is one of:

a word, a sentence, a paragraph or block of quoted text.

20. A conversation server system, comprising:

one or more physical 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;

storing a plurality of index entries in an index, a respective index entry corresponding to a respective term 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;

receiving a first message;

associating the first message with a conversation having at least one other message; and

storing, in the index, a plurality of first-message index components that each include an identifier of the first message, including;

one or more index components indicative of a plurality of message terms in the first message; and

one or more index components indicative of one or more conversation terms in the conversation, the one or more conversation terms comprising one or more terms that are not in the first message;

wherein a respective first-message index component indicative of a conversation term in the conversation includes a value identifying the respective index component as being associated with a conversation term not in the first message.

21. The system of claim 20, wherein, in the index, the one or more index components indicative of the message terms are distinguished from the one or more index components indicative of the conversation terms.

22. The system of claim 20, including instructions for storing a plurality of messages associated with a plurality of conversations, wherein:

each conversation includes a respective representative message;

for each conversation, a respective property of the conversation comprises a corresponding property of the representative message of the conversation; and

the method includes sorting or filtering a list of conversations in accordance with the respective property.

23. The system of claim 20, including instructions for, after storing, in the index, the one or more first-message index components indicative of the one or more conversation terms in the conversation:

detecting a modification of a respective message of the one or more other messages in the conversation; and

in response to detecting the modification, updating the one or more first-message index components indicative of the conversation terms that are stored in the index in accordance with the modification of the respective message.

24. 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 server system with one or more processors, cause the conversation server system to:

store a plurality of index entries in an index, a respective index entry corresponding to a respective term 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;

receive a first message;

associate the first message with a conversation having at least one other message; and

store, in the index, a plurality of first-message index components that each include an identifier of the first message, including;

one or more index components indicative of a plurality of message terms in the first message; and

one or more index components indicative of one or more conversation terms in the conversation, the one or more conversation terms comprising one or more terms that are not in the first message;

wherein a respective first-message index component indicative of a conversation term in the conversation includes a value identifying the respective index component as being associated with a conversation term not in the first message.

25. The computer readable storage medium of claim 24, wherein, in the index, the one or more index components indicative of the message terms are distinguished from the one or more index components indicative of the conversation terms.

26. The computer readable storage medium of claim 24, including instructions which, when executed by a conversation server system with one or more processors, cause the conversation server system to store a plurality of messages associated with a plurality of conversations, wherein:

each conversation includes a respective representative message;

for each conversation, a respective property of the conversation comprises a corresponding property of the representative message of the conversation; and

the method includes sorting or filtering a list of conversations in accordance with the respective property.

27. The computer readable storage medium of claim 24, including instructions which, when executed by a conversation server system with one or more processors, cause the conversation server system to, after storing, in the index, the one or more first-message index components indicative of the one or more conversation terms in the conversation:

detect a modification of a respective message of the one or more other messages in the conversation; and

in response to detecting the modification, update the one or more first-message index components indicative of the conversation terms that are stored in the index in accordance with the modification of the respective message.