1. A method of using a conversation-based messaging system, comprising: receiving a message; identifying an existing conversation, if any, to which the message best matches; associating the message with the best matching existing conversation, if any, and otherwise associating the message with a new conversation; and storing information about the message in a first data structure for the respective conversation.