Enabling search for conversations with two messages each having a query team

• US 8,972,409 B2
• Filed: 08/29/2011
• Issued: 03/03/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): Pham, Michael
• Application Number:
  US13/220,668
• Publication Number:
  US 20130218897A1
• Time in Patent Office: 1,282 Days
• Field of Search: None
• 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 associates a first message having a first term with a conversation that includes at least a second message. The first term is not included in the second message and the second message includes a second term that is not included in the first message. The server stores, in the index, a plurality of index components for a same referenced object, including an index component indicative of the first term and an index component indicative of the second term. In some embodiments the same referenced object is associated with index components for a first sender of the first message and a second sender of the second message, so that a search for a conversation with messages from the first sender and the second sender retrieves the referenced object.

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, wherein the message includes a header and a message body and the respective term comprises text from the message body of the message, and wherein the message body is separate from the header of the message;

receiving a first message having a first term;

associating the first message with a conversation that includes at least a second message, wherein the first term is not included in the second message and the second message includes a second term that is not included in the first message; and

storing, in the index, a plurality of index components for a same respective referenced object, including an index component indicative of the first term and an index component indicative of the second term, wherein;

the index component for the second term includes a mapped location that corresponds to an original location of the second term in the conversation; and

the mapped location of the second term is in a predefined range of locations associated only with terms in the conversation that are in messages other than the first message.

2. The method of claim 1, wherein the index component for the second term includes a value identifying the index component for the second message as being associated with a message in the conversation other than the first message.

3. The method of claim 1, wherein:

the second term is also associated with a second referenced object; and

the first term is not associated with the second referenced object.

4. The method of claim 1, wherein:

the first message has a first sender; and

the second message has a second sender that is distinct from the first sender.

5. The method of claim 4, including, after receiving the first message:

receiving, from a client, a search query for conversations including at least one message from the first sender and at least one message from the second sender; and

in response to the search query, providing to the client a set of search results including information representing the conversation.

6. The method of claim 1, including, after receiving the first message:

receiving, from a client, a search query that includes the first term and the second term; and

in response to the search query, providing to the client a set of search results including information representing the conversation.

7. The method of claim 4, wherein:

the storing is performed without regard to whether or not the first message was addressed to the second sender or the second message was addressed to the first sender.

8. The method of claim 1, wherein the respective referenced object is a representative message of the conversation.

9. The method of claim 1, wherein, the respective referenced object is the first message and the index includes 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, including the first term; 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, including the second term;

wherein the first-message index components indicative of the plurality of message terms are distinguished from the first-message index components indicative of the 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 of the one or more conversation terms, wherein the respective address for a respective conversation term in the conversation is indicative of a mapped location of the respective conversation term within the address space for the first message.

10. The method of claim 9, 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.

11. The method of claim 1, wherein the respective referenced object is the conversation.

12. The method of claim 1, wherein:

the referenced object is the conversation including the first message and the second message, and the index includes a plurality of conversation index components that each include an identifier of the conversation, including;

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

one or more index components indicative of a plurality of second message terms in the second message, including the second term; and

the index components indicative of the plurality of first message terms are distinguished from the index components indicative of the plurality of second message terms by partitioning an address space for the conversation, the address space having a respective address for each first message term and each second message term, wherein the respective address for a respective term in the conversation is indicative of a mapped location of the respective term within the address space for the conversation.

13. The method of claim 12, wherein:

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

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

a mapped location of a second message term in the address space for the conversation 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 server 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;

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, wherein the message includes a header and a message body and the respective term comprises text from the message body of the message, and wherein the message body is separate from the header of the message;

receiving a first message having a first term;

associating the first message with a conversation that includes at least a second message, wherein the first term is not included in the second message and the second message includes a second term that is not included in the first message; and

storing, in the index, a plurality of index components for a same respective referenced object, including an index component indicative of the first term and an index component indicative of the second term, wherein;

the index component for the second term includes a mapped location that corresponds to an original location of the second term in the conversation; and

the mapped location of the second term is in a predefined range of locations associated only with terms in the conversation that are in messages other than the first message.

15. The system of claim 14, wherein:

the first message has a first sender; and

the second message has a second sender that is distinct from the first sender.

16. The system of claim 15, including instructions for, after receiving the first message:

receiving, from a client, a search query for conversations including at least one message from the first sender and at least one message from the second sender; and

in response to the search query, providing to the client a set of search results including information representing the conversation.

17. The system of claim 14, the one or more programs including instructions for, after receiving the first message:

receiving, from a client, a search query that includes the first term and the second term; and

in response to the search query, providing to the client a set of search results including information representing the conversation.

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 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, wherein the message includes a header and a message body and the respective term comprises text from the message body of the message, and wherein the message body is separate from the header of the message;

receive a first message having a first term;

associate the first message with a conversation that includes at least a second message, wherein the first term is not included in the second message and the second message includes a second term that is not included in the first message; and

store, in the index, a plurality of index components for a same respective referenced object, including an index component indicative of the first term and an index component indicative of the second term, wherein;

the index component for the second term includes a mapped location that corresponds to an original location of the second term in the conversation; and

the mapped location of the second term is in a predefined range of locations associated only with terms in the conversation that are in messages other than the first message.

19. The computer readable storage medium of claim 18, wherein:

the first message has a first sender; and

the second message has a second sender that is distinct from the first sender.

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

receive, from a client, a search query for conversations including at least one message from the first sender and at least one message from the second sender; and

in response to the search query, provide to the client a set of search results including information representing the conversation.

21. The computer readable storage medium of claim 18, the one or more programs including instructions which, when executed by the conversation server system, cause the conversation server system to, after receiving the first message:

receive, from a client, a search query that includes the first term and the second term; and

in response to the search query, provide to the client a set of search results including information representing the conversation.