So’s your facet: Faceted global search for Mozilla Thunderbird

faceting-gloda-hover-davida-1

Following in the footsteps of the MIT SIMILE project’s Exhibit tool (originally authored by David Huynh) and Thunderbird Seek extension (again by David Huynh), we are hoping to land faceted global search for Thunderbird 3.0 (a la gloda) in beta 4.

I think it’s important to point out how ridiculously awesome the Seek extension is.  It is the only example of faceted browsing or search in an e-mail client that I am aware of.  (Note: I have to assume there are some research e-mail clients out there with faceting, but I haven’t seen them.)  Given the data model available to extensions in Thunderbird 2.0 and the idiosyncratic architecture of the UI code in 2.0, it’s not only a feature marvel but also a technical marvel.

Unfortunately, there was only so much Seek could do before it hit a wall given the limitations it had to work with.  Thunderbird 2.0’s per-folder indices are just that, per-folder.  They also require (fast) O(n) search on any attribute other than their unique key.  Although Seek populated an in-memory index for each folder, it was faced with having to implement its own global indexer and persistent database.

Gloda is now at a point where a global database should no longer be the limiting factor for extensions, or the core Thunderbird experience…

faceting-gloda-action-tag-hover-bienvenu-1

The screenshots are of a fulltext search for “gloda” in my message store.  The first screenshot is without any facets applied and me hovering over one of David Ascher’s e-mail address.  The second is after having selected the “!action” tag and hovering over one of David Bienvenu’s e-mail address.  Gloda has a concept of contact aggregation of identities but owing to a want of UI for this in the address-book right now, it doesn’t happen.  We do not yet coalesce (approximately) duplicate messages, which explains any apparent duplicates you see.

The current state of things is a result of development effort by myself and David Ascher with design input from Bryan Clark and Andreas Nilsson (with hopefully much more to come soon :).  Although we aren’t using much code from our previous exptoolbar efforts, a lot of the thinking is based on the work David, Bryan, and myself did on that.  Much thanks to Kent James, Siddharth Agarwal, and David Bienvenu for their recent and ongoing improvements to the gloda (and mailnews) back-end which help make this hopefully compelling UI feature actually usable through efficient and comprehensive indexing that does not make you want to throw your computer through a window.

If you use linux or OS X, I just linked you to try server builds.  The windows try server was sadly on fire and so couldn’t attend the build party.  The bug tracking the enhancement is bug 474711 and has repository info if you want to spin your own build.  New try server builds will also be noted there.  Please keep in mind that this is an in-progress development effort; it is not finished, there are bugs.  Accordingly, please direct any feedback/discussion to the dev-apps-thunderbird list / newsgroup rather than the bug.  Please beware that increases in awesomeness require that your gloda database be automatically blown away if you try the new version.  And first you have to turn gloda on if you have not already.

thunderbird, gloda, exptoolbar, protovis, paninaro, oh oh oh

exptoolbar-protovis-gloda-256

Thunderbird.  With the global database, gloda.  Using the exptoolbar extension.  Using the protovis javascript visualization library.  For reals!  Not a prank!  Just grab the most recent XPI or grab the repo.  And be using a nightly (beta 2 might work?)

What you are looking at:

  • The exptoolbar search results page, augmented with a visualization.
  • Each conversation with search results gets its own wedge.
    • Wedges can be distinguished because of the alternating background colors.
    • Conversations that you sent a message to will have a red shading to them.  The examples may be somewhat misleading because the account where a lot of my sent mail ends up is not part of the profile used to create the screenshots.
  • Each message is placed in its conversation wedge…
    • The radius is based on the ‘age’ of the message using a log-ish scale.  Interpolation is actually linear at each level (one day, one week, one month, three months, one year, 5 years, ‘forever’.)
    • The angular placement within the wedge is based on the author of the message.  Across all wedges the placement is the same.  This helps ‘bursty’ parts of conversations (which are extremely likely) be made more obvious, while also helping to provide some understanding of conversation dynamics.
  • Message shapes are determined by whether the message is starred (diamond), sent by a ‘popular’ contact (circle), or an unpopular one (cross).  The use of popularity is a temporary measure because current gloda in trunk does not cache address-book lookups, and they are expensive.  Once the new gloda search code lands with those changes, we can rely on the existence of an address book entry.  (Starring a contact using the new message reader adds them to your address book.)
  • Message opacity is determined by whether the message is a ‘hit’ or not.  All messages in a conversation are eventually retrieved, though initially we only have the hits.
  • Message color is determined by applied tags (using the closest tango color for the first tag), or whether the message is starred (closest tango color to yellow, where I think I had removed the yellow tango colors for some unknown reason, so we get green I guess).  It’s grey if the message has no tag or star.
  • The subject of the conversation is displayed in the wedge.

exptoolbar-protovis-seek-thunderbird-256

Things that are happy:

Things that are sad (aka caveats):

  • It would probably be better if the visualization was not radar-inspired.  Besides the perceptual reasons, the subjects are harder to read than they would be in an equivalent linear-styled visualization.
  • The visualization is not interactive.  protovis officially has no interaction support yet, but if you look in the (only available minified?) source, it’s almost there.  It might be entirely there, but it didn’t work for me immediately after a quick reading of the (indented) source.
  • There is some low probability failure that occurs during the visualization updating as gloda backfills the message collections.  If it happens on the last update, you can end up with a half-built visualization.  Re-running the search will generally resolve the issue.
  • The visualization does a pretty solid job of taking up all the screen real estate and has no way to be disabled, so you have to scroll past it every time.

Future work:

  • Interactivity.
  • Perhaps showing the gravatars for the people involved in a conversation at the outer rim of the wedge, positioning them based on the author positioning we determined.
  • Perhaps lose the radar motif.
  • Your thoughts / patches!

support your neighborhood Thunderbird global database

Do you know JavaScript?  Would you like to help improve Thunderbird and its exciting global database, gloda?  Now is your chance!  Check out these exciting bugs that are reasonably sized and independent tasks:

Exciting? Exciting!

I don’t know much about psychology, but I have heard that people on the internet see a call-to-arms like this and say “I’m sure someone else better qualified will step up, maybe even hundreds of them… I’ll just let them take care of it.”  I have news for you, people on the internet are lazy!  Oh, so lazy!  (I am reasonably confident that won’t happen.  If it does happen, I will find enough work for everyone to do while I retire to a life of luxury funded by my ability to inexplicably motivate large swathes of the internet to do my bidding.)

Important steps!

  1. Get yourself a copy of the comm-central codebase.
  2. Build thunderbird! (Actually, that above link covers it, but you might also want to check out the general building info page.)
  3. Dance a victory jig!
  4. Leave a note on one of those bugs saying that you are interested.  Or just e-mail me at asuth@mozillamessaging.com!

Thunderbird and gloda go to meme-town

Sure, a word cloud of your blog posts is cool… but what if you could take any search of your e-mail, and turn that into a word cloud?  And then, if you click on one of those words, your search constraints would be revised to use the word you clicked on (and you’d get a useful search result, not another word cloud)?  And what if that layout algorithm were not as good as wordle?  The future is now, people!  (At least if you install like 5 extra extensions out of mercurial.)

The screenshot above is from Thunderbird trunk with a hacked exptoolbar extension (generalized, committed changes happening soon), visophyte-js, and the new glodacloud extension.  It is a proof-of-easy-gloda-extensions as suggested by David Ascher.

The layout algorithm is what we in the business of making up terminology call a recursive sub-optimal tic-tac-toe subdivision thinger.  We under-use a neat (and somewhat slow) hack to find the bounds of the words through use of canvas.mozPathText and canvas.isPointInPath to sample a grid to know where the text is and isn’t.  It’s under-used because all we use it for right now is to find the actual height above the baseline that the text stretches to (because metrics only gives us the width).  We are lazy and don’t check below the baseline at all, and totally squander our chance to be cool and put small words in the gaps in larger words.  But given the amount of time spent, I’m very happy.

Oh, and of course it uses JS and Canvas.

I’ll be wanting that latte machine now…

in context

credits where credits due:

  • thread arcs a la the nice people at the IBM CUE group
  • the search view prototype is implemented by David Ascher.  the positioning of the visualization is on me as a quick hack, though.
  • the search view prototype is designed by Bryan Clark, and he has even better stuff on the way

The actual implementation is a first step of adapting knowledge from my python “visophyte” library to a JS implementation using canvas.  I am trying a more batch-oriented style of processing this time that uses explicit attributes for value-passing between logic blocks.  This is in comparison to the python implementation which is more functional in nature.  We’ll see how it turns out.

Thunderbird full-text search prototype a la SQLite FTS3

Full-text search using FTS3.

Full-text search with a contact constraint.

The global database sqlite file resulting from indexing all of mozilla.dev.apps.thunderbird is about 13M for something like 4500 messages.  We’re providing FTS3 with the bodies (but not attachments!) of all the newsgroup messages and the subjects of the messages which initiate new threads.  For real usage, we will need to also index the subjects of each message.

Note that the message bodies have not been processed at all by the Thunderbird/gloda code before handing them off to FTS3.  So quoted messages get indexed even though it’s a lot of excess data.  We’re relying on FTS3 to do all stop-words, etc.  FTS3’s Porter stemming/tokenization is in use.

Thunderbird contact auto-completion… with bubbles!

Autocompletion screenshot

Type type type type.  Autocomplete contact…

Completed contact becomes a bubble!  Bubble becomes a constraint, showing us only the messages involving the given contact.  (The idea is that you could then click on/select/whatever the bubble and change the constraint to be only to/from/cc/whatever if you are so inclined.)

Type type type, autocomplete, new constraint!  Now we’re looking at all the messages involving the two given contacts.  (Some of the messages with just one constraint were mailing list postings, but not explicitly involving the second contact.  This listing shows only messages where both contacts were directly involved.  We will have the ability to filter-out messages involving lists as desired, which may be desired by default in a case like this.)

What is exciting about this?

  • The contacts are matched using a suffix-tree implementation on a reduced set of contacts (as a first-pass).  In this case, those with sufficient ‘popularity’.  ‘Frecency’ a la ‘places’ is also planned.  And of course, we can hit the database as needed.  The suffix-tree is nice because it allows extremely rapid lookups while also allowing for substring matching.
  • The contact popularity is computed automatically by the gloda indexing process, taking into account both messages you receive and send.  (I think the current address-book code just increments popularity on send?)
  • I think the bubbles are cool.  (Hyperlink-styling would also work, but would not be cool.)
  • Having the text converted into an explicit object representation (bubbles) is better than just doing string filtering (as quicksearch does) because it allows explicit actions on the object given knowledge of the object type.
  • We can convert more than just contacts/identities to explicit objects.  As demonstrated at the summit, we have a plugin that detects bugzilla bug references in messages as well as (American/NANP-style) phone-numbers in messages.  We could detect these and promote them as well, etc.
  • The filtered messages are being delivered by gloda, the global database (backed by SQLite), which means that we aren’t searching just one folder.
  • There are a lot of places that you, the reader, will shortly be able to hack on and contribute to make this even more exciting.  A vicious cycle of exciting-ness will ensue until everyone is dancing in the streets.

thunderbird global database m1-ish

The ‘gloda’ (global database) and ‘expmess’ (experimental message view) Thunderbird extensions are nearly to milestone 1…

Thunderbird with gloda/expmess plugins m1-ish installed

The screenshot scenario is that we have 2 months of apache-dev archives in two separate folders, July and August.  We have a message selected in the month of July, yet the ‘data mine’ to the right is able to show the messages in the thread spanning both months (and therefore folders), as well as showing all the other messages sent by the author spanning both months (and therefore folders).

I’ll post again with some links and what not once I hit the actual milestone 1.  Be aware that every-day usability is targeted for milestone 3, but that should still happen pre-summit.

status/future fyi. no pictures.

I have accepted a position at Mozilla Messaging and will start at the end of March. Posting has been rare as of late and will be rare until then because my spare cycles are being given over to providing closure to my day-job projects, dealing with various hardware failures, and other small fires.

Hobby-wise, this will translate into a focus on visualizing e-mail from within Thunderbird. My nascent Python library, visophyte, will likely have a JavaScript sibling, but will not be abandoned.

Job-wise, I expect to focus on improving Thunderbird for both users and extension developers. Although my interest in creating a useful visualization extension will inform my efforts, it will not be my focus. Which is to say, do not worry that I will be engaging in flights of fancy and neglecting the core of Thunderbird. However, do be happy that good visualizations will depend on non-trivial data analysis and snappy, interactive behaviour and that this should translate into good things for Thunderbird, even if you don’t like shiny things.

It wasn’t an easy decision to leave my current employer (I have only great things to say about The PTR Group; check them out if you’re in the greater DC metro area), but Mozilla Messaging is an exceedingly rare opportunity that I could not pass up.

Thunderbird stacked linechart visualization

Stacked linechart visualization of j-devel by sender, march 05 through june 06, no sustain

The last post‘s visualization is put to work here visualizing the traffic on the j-devel mailing list (for the j text editor, but also beloved for armed bear common lisp) from March 2005 through now, June 13 2007, clustering on 7-day intervals. Each series is a specific author. ‘Sustain’, or the number of pixels of space to give to each series that doesn’t have traffic is at 0 because the number of one-time posters turns things into a mess of a lie. In the last post, sustain was at 2 because it made things prettier without significantly distorting the data. Decay might be a good compromise, although still introducing some distortion; really, the visualization then becomes a graph of ‘perceived activity’.

Not too many changes to do this; added a polygon renderer to the mozilla svg renderer backend and implemented an extremely naive type-dispatching in the thunderbird datafeed provider to fall back to the native python dispatcher so that it can process the aggregate nodes.

I should also note that there are just enough posters to the list to make the fallacy of using consecutive HSV points for consecutive data-series without additional variability a bad idea. At the bottom the two purplish colors pretty nearly blend together. Since the series may appear and disappear at will, it’s not sufficient to just hop the saturation or value between two values for alternating colors. Probably the thing to do is to ensure a minimal distance in the color-space and either spiraling in through the color wheel or just have multiple circles on the color wheel. We run out of usable colors eventually there too, but we can always fall-back to a graph-coloring algorithm to cheat and provide sufficient contrast between more closely spaced colors (in color-space; and forget perceptual color-space).

UPDATE:

Stacked linechart visualization of j-devel by sender, march 05 through june 06, no sustain, bottom align

Er, so, looking at the visualization a little more, I realized if I’m going to talk about distortion, I should probably admit that the naive centering-layout algorithm probably hoses things up too.  So, to my loyal readers entirely consisting of people foolish enough to click on links I send them via IM, you get a bonus visualization which is the exact same thing as the above, but with the alignment routine set to ‘bottom’, which is arguably more accurate.