Tuesday, November 13, 2007

Chronoscope Released

Timepedia is happy to announce the first beta release of Chronoscope, our charting and visualization platform for Google Web Toolkit, as open source. Chronoscope provides several features for the AJAX developer:


  • Canvas abstraction for drawing vector graphs
  • Graph Style Sheets abstraction for configuring the look-and-feel of charts
  • Scalable multiresolution rendering supporting up to tens of thousands of points
  • Zoom and pan at interactive frame rates, from centuries to milliseconds
  • Auto-ranging, auto-layout of chart axes and ticks.
  • Auto-legend, and mini-chart Overview
  • Add pushpin markers, domain and range markers, and overlays like Google Maps
  • Bookmarkable chart state, works with Back button
  • JS interopability. GWT API can be used by pure Javascript programmers
  • Microformat support. Charts can be configured without programming.
  • Server-side Font assistance. Render rotated text.
  • Portable, Chronoscope is not tied to GWT, can be used to render from servlets, applets, or other environments.


You can see a demo of the chart in action on our demo site. WARNING: Chronoscope currently supports only Firefox, Safari, and Opera (with a few caveats) for the beta release. Internet Explorer is scheduled to be available soon through a Flash version.

Many of our readers have been eagerly awaiting the release, and we have been burning the midnight oil the last few weeks reorganizing, documenting, and cleaning up the code base for the public.

Chronoscope is free of charge, and is distributed under the LGPL. We hope that many people interested in charting and graphics within GWT will join the Chronoscope project at http://code.google.com/p/gwt-chronoscope and help us build an awesome visualization platform.

Timepedia has been working over the last two years on a search engine which indexes time-related quantitative data, and provides users tools to play with visualizing data, find interesting patterns, and communicating insights. We want to make Chronoscope the best visualization tool, but we need your help to make it better.

There are four ways you can help us:

1) Chronoscope contains a small unobstrustive credit "Powered by Timepedia Chronoscope" which can be switched off. If you use Chronoscope, and want to help us promote Chronoscope, you can choose to leave it switched on.

2) You can become active in contributing code to the project. See the project page.

3) You can choose to donate a small sum of money, whatever you deem appropriate.

4) If you are a commercial company, and interested in official technical support, we sell support licenses, as well as a non-LGPL licensed version. See http://timepedia.org/chronoscope/license if interested.

We thank everyone for their patience over the last month, and hope you think this project is as cool as we do.

For those interested in meeting in person to discuss GWT based visualization and vector graphics, Ray Cromwell will be presenting at the upcoming Voices that Matter: Google Web Toolkit conference. During Breakfast with the Speakers, or after the conference, feel free to hunt him down if you want to chat. For those who wish to register, you can use a code of "GW-CROM" during registration to get $100 off the registration price.

Thursday, October 4, 2007

Errata for AccordionPanel

There was an issue with IE7 (and probably IE6) with the Accordion shown in the previous article. The problem is, IE7 doesn't treat an element with overflow: hidden, height: 0px as expected (by making it invisible), instead, it shows it in full.

This is fixed by forcing standards mode with the following declaration in your HTML:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">

Wednesday, October 3, 2007

Designing a really simple GWT Accordion control

Yesterday, we started implementing some neat context-sensitive information features to Timepedia's "Timelord" GWT application, which integrates Chronoscope, Everett, and several other backend services, and I found myself in great need of an Accordion-like control.

Now, there are a great many accordion controls in third party JS libraries, many of them very slick and full featured, but I found that I didn't need so many features, and I'm trying to limit the number of pure-JS library wrappers I use in GWT because you lose alot of the benefits of the GWT Compiler when you wrap external JS libraries.

How hard could it be to cook up one in GWT? It turns out, not very hard it all.


Concept

What I want is a VerticalPanel or HorizontalPanel with the ability to open/close the nested widgets, preferably in a cool animated style. That means, we'll create either an Vertical or Horizontal Panel, store it in a Composite, and use even-numbered widget positions to store a Label, which when clicked, will expand odd-numbered widget positions from 0 to their desired width or height. We'll also simultaneously close any currently expanded widgets, back down to zero width/height. The only trick is to figure out what expanded width/height of a widget is.

Implementation

First, let's create a Composite to house a Vertical or Horizontal Panel.

public class AccordionPanel extends Composite {
private Panel aPanel;
private String animField;
private String animBounds;

final private static int NUM_FRAMES = 8;

private Widget currentlyExpanded = null;
private Label currentlyExpandedLabel = null;

public AccordionPanel(boolean horizontal) {
if (horizontal) {
aPanel = new HorizontalPanel();
animField = "width";
animBounds = "scrollWidth";
} else {
aPanel = new VerticalPanel();
animField = "height";
animBounds = "scrollHeight";
}
initWidget(aPanel);

setStylePrimaryName("accordion");
}

public AccordionPanel() {
this(false);
}


I don't really need a horizontal accordion, but I threw in support for it (untested) just in case. Here, if we are using a Vertical accordion, we are animating the height field, and the desired expansion size is in the "scrollHeight" field.

Next, we need a method for adding new widgets to an accordion.


public void add(String label, final Widget content) {
final Label l = new Label(label);
l.setStylePrimaryName(getStylePrimaryName()+"-title");
final SimplePanel sp=new SimplePanel();
sp.setWidget(content);

l.addClickListener(new ClickListener() {
public void onClick(Widget sender) {
expand(l, sp);
}
});
aPanel.add(l);
sp.setStylePrimaryName(getStylePrimaryName()+"-content");
DOM.setStyleAttribute(sp.getElement(), animField, "0px");
DOM.setStyleAttribute(sp.getElement(), "overflow", "hidden");
aPanel.add(sp);
}


Given a string label, and a widget, we do two things. First, we create a Label widget, and add a ClickListener to it. The ClickListener simple calls the expand() function with the label, and the content. Secondly, we wrap the content being added in a SimplePanel, to ensure we get a DIV around it which can be animated.

Finally, we add both the Label and the content wrapper to the underlying Vertical or Horizontal panel, set the primary style name of the label/content to be that of the AccordionPanel + "-title"/"-content", and then collapse the newly added component (height/width: 0, overflow: hidden)

We're almost done

Now all we have to do is implement the expand() function. We essentially want to run an animation loop, linearly interpolating between 0 and the max dimensions (for expansion) or the opposite for collapse.

Let's look at the implementation:

private void expand(final Label label, final Widget c) {

if(currentlyExpanded != null)
DOM.setStyleAttribute(currentlyExpanded.getElement(),
"overflow", "hidden");


Here we make sure that any previous expanded section is changed from overflow: auto back to overflow: hidden. Continuing further...

final Timer t = new Timer() {
int frame = 0;

public void run() {
if (currentlyExpanded != null) {
Widget w = currentlyExpanded;
Element elem = w.getElement();
int oSh = DOM.getIntAttribute(elem, animBounds);
DOM.setStyleAttribute(elem, animField, ""+(( NUM_FRAMES -
frame ) * oSh / NUM_FRAMES)+"px");

}

We create a Timer, whose run method will animate the collapse/expansion. We simultaneously collapse any currently expanded Widget and expand the target widget. All we have to do, is fetch the max dimensions from scrollHeight/scrollWidth, and then interpolate them down to zero for collapse.

if (currentlyExpanded != c) {
Widget w = c;
Element elem = w.getElement();
int oSh = DOM.getIntAttribute(elem, animBounds);
DOM.setStyleAttribute(elem, animField, ""+
(frame * oSh / NUM_FRAMES)+"px");
}
frame++;

Likewise for expansion, we simply interpolate from 0 to the maximum dimensions. Finally, we increment the frame, and we take care not to try and collapse and expand the same widget at the same time.


if (frame <= NUM_FRAMES) {
schedule(10);
} else {
if(currentlyExpanded != null) {
currentlyExpanded.removeStyleDependentName("selected");
currentlyExpandedLabel.removeStyleDependentName("selected");
}
c.addStyleDependentName("selected");
if(currentlyExpanded != c) {
currentlyExpanded = c;
currentlyExpandedLabel = label;
currentlyExpandedLabel.addStyleDependentName("selected");
Element elem = c.getElement();
DOM.setStyleAttribute(elem, "overflow", "auto");
DOM.setStyleAttribute(elem, animField, "auto");
} else {
currentlyExpanded = null;
}

}


Finally, we keep rescheduling our timer as long as we haven't reached our maximum number of frames. To finish, we add a final bit of polish, by adding a "selected" CSS class to the Label which is currently expanded. We also change the width/height and overflow fields back to auto.


}
};
t.schedule(10);


The last lines of the expand() function simply kick off our timer.

Here is the simple GWT Module to test

public class AccordionDemo implements EntryPoint {

/**
* This is the entry point method.
*/
public void onModuleLoad() {
AccordionPanel ap=new AccordionPanel();
AccordionPanel ap2=new AccordionPanel();

ap.add("Label 1", new HTML("Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Nam luctus urna vitae urna. Sed nisl. Praesent nisi nulla, malesuada quis, bibendum quis, egestas nec, pede. Donec ipsum. Duis nulla nisi, tristique eget, fermentum et, gravida non, lorem. Praesent mollis, arcu sed suscipit venenatis, velit erat sollicitudin quam, eget vestibulum odio enim nec libero. Praesent tellus. Vestibulum non justo. Aliquam semper. Nulla mauris ipsum, semper ut, dapibus quis, ultrices nec, est. Mauris nec nisl ut est posuere dignissim. Sed nec magna non purus eleifend mollis. Pellentesque orci. Integer sapien. Cras aliquam."));
ap.add("Label 2", new HTML("Ut tristique convallis nibh. Vestibulum eget nunc eget tellus varius sollicitudin. Vestibulum vestibulum ligula ac nulla. Nulla risus urna, euismod eget, accumsan vitae, posuere sit amet, eros. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean rhoncus pellentesque justo. Sed purus diam, bibendum ut, posuere a, feugiat sit amet, justo. Donec urna nulla, blandit in, gravida non, mattis a, turpis. Phasellus feugiat leo et justo. Maecenas quam nisl, consectetuer nec, auctor et, pharetra vel, tortor. Nunc justo nulla, tincidunt a, tempor id, viverra eget, sem. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Proin sagittis nonummy urna. Aenean quis massa ac massa rutrum ornare."));


ap2.setStylePrimaryName("accordion2");
ap2.add("Nested Label 1", new HTML("Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Nam luctus urna vitae urna. Sed nisl. Praesent nisi nulla, malesuada quis, bibendum quis, egestas nec, pede. Donec ipsum. Duis nulla nisi, tristique eget, fermentum et, gravida non, lorem. Praesent mollis, arcu sed suscipit venenatis, velit erat sollicitudin quam, eget vestibulum odio enim nec libero. Praesent tellus. Vestibulum non justo. Aliquam semper. Nulla mauris ipsum, semper ut, dapibus quis, ultrices nec, est. Mauris nec nisl ut est posuere dignissim. Sed nec magna non purus eleifend mollis. Pellentesque orci. Integer sapien. Cras aliquam."));
ap2.add("Nested Label 2", new HTML("Ut tristique convallis nibh. Vestibulum eget nunc eget tellus varius sollicitudin. Vestibulum vestibulum ligula ac nulla. Nulla risus urna, euismod eget, accumsan vitae, posuere sit amet, eros. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean rhoncus pellentesque justo. Sed purus diam, bibendum ut, posuere a, feugiat sit amet, justo. Donec urna nulla, blandit in, gravida non, mattis a, turpis. Phasellus feugiat leo et justo. Maecenas quam nisl, consectetuer nec, auctor et, pharetra vel, tortor. Nunc justo nulla, tincidunt a, tempor id, viverra eget, sem. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Proin sagittis nonummy urna. Aenean quis massa ac massa rutrum ornare."));
ap.add("Nested", ap2);

ap.add("Label 3", new HTML("Neque porro quisquam est qui dolorem ipsum quia dolor sit amet, consectetur, adipisci velit..."));



RootPanel.get("slot1").add(ap);

}

}


and the CSS rules used.

.accordion-title {
background: #EFEFE3 url(gray-bg.gif) repeat-x scroll 0%;
border: 0pt none;
padding: 3px;
color: white;
font-weight: bold;

}

.accordion-title-selected {
background: coral none;
}

.accordion {
width: 300px;

}

.accordion2-title {
background: #EFEFE3 url(gray-bg.gif) repeat-x scroll 0%;
border: 0pt none;
padding: 3px;
padding-left: 10px;
color: white;
font-weight: bold;

}

.accordion2-title-selected {
background: blueviolet none;
}

.accordion2 {
width: 300px;

}


-Ray
p.s. caveats. First, scrollHeight/scrollWidth don't always work. See quirksmode. Secondly, there is a chance you could click another label while an expansion is in progress, so you'll need to add an "isAnimating" flag so that expand() will do nothing if another expansion is in progress. Third, you may want ease-in/ease-out in the animation, so instead of a linear interpolation, drop in your favorite easein/out function (sine, 2x^3-3x^2, etc)

Saturday, September 15, 2007

Trying to resist Scala...must...not...succumb...

I've frequently been engaged in discussions regarding future Java language extensions (closures, etc) on forums like Javalobby and blogs like Neal Gafter's, and my co-workers aren't as big fans of Java as I am (being more inclined to Python and C), but moving away from Java is hard because of the incredible amount of useful libraries available, mature VM, and our favorite IDE - IntelliJ IDEA.

I would like to have a language, right now, that included a better static type system, first class functions, type inferencing, etc, but also allowed me to use all of my existing Java code, and run on top of a mature VM. Having Java-like performance would be a big plus.

And Scala seems to be it. I had looked at Scala a long time ago, but I hadn't realized how much progress they had made. Recently, I took another look at it, and boy oh boy, is it tempting. There seems to be almost no downside to writing future code in Scala, as it will run in the same VM as my other code, and seamlessly interoperate with Java classes, yet offers similar performance. And don't even get me started on Scala's DSL creation capability, which exceeds even Ruby (though still not Scheme)

However, two missing wishlist features gave me the excuse to leave it alone for now. For one, I told my coworkers that I am not switching to any new language which does not have a REPL. I had assumed that Scala was compiler-only. Secondly, no IntelliJ support is a big turnoff.

To my surprise, Scala *does have* a REPL interpreter. Whoops.

Only one excuse left. Please JetBrains, do not add first-class Scala support to IDEA. Do not tempt me to switch languages, I'm begging you! :)

-Ray

Thursday, September 13, 2007

Knowledge extraction with 2 dimensional regular expressions?

Some of my best and worst ideas come when I'm sitting on the toilet. I pretty much have an informal bookshelf next to it, which I use to refresh and reinforce my memories of galois theory, probability, or in this case, automata from time to time. I'm not getting any younger (almost 36) -- it's been ages since college -- so whatever time I can use to reinforce those neurons and keep those skills from slipping away is golden.

So, there I was, automata book in hand, thinking about how I could simplify and modularize, Tardis, Timepedia's web crawler, automated knowledge discovery extractor, and temporal query engine. One part of what Tardis does is look for time related information in documents, and extract timeseries and timeline information.

How it does this exactly, I won't say at this time, but it uses a large battery of heuristics and other classical algorithms. The problem is, this logic is cemented inside of Java code, a sort of implicit 'expert system' with a huge number of cases, and complex interactions. Extending this to support newly discovered rules is hard enough with the source code in hand, but impossible for the end user.

Wouldn't a DSL be better? But if so, which one? An expert system like CLIPS/JESS? Those risk alot of complexity as well as scalability issues. If this was simple text extraction, I'd give the users the ability to author custom regexp match/rewrite rules for particular documents, sort of a mini-online-SED. As you can imagine, a lot of time related information is two dimensional in nature, stored in documents in tabular form, so ordinary regexp's don't capture the problem.

Aha! What about two dimensional regular expressions? Do they even exist? By the time I had gotten off the toilet, I had already devised replacements for regular expression concatenation operators in the form of row/column concatenation operators. I knew however that I was not the first to think of this, so a quick Google Scholar search led me to this paper: Two-Dimensional Languages (1997), Dora Giammarresi, Antonio Restivo, Handbook of Formal Languages

At first glance, this looks like a fertile field, previously applied for recognizing graphical features in pictures. Could I extend it to my needs? More on that later. First, let's look at an example.

As you may recall, a classical regular expression consists of operations like concatenation, union, and Kleene star. Concatenation is usually represented by placing two symbols next to one another, such as "ab" which means "a + b" where + is the concatenation operation. Union is typically represented via the pipe character "|", so "a|b" means "a union b". Kleene star of course is the union of all possible concatenations, e.g. "(a|b)*" = e, a, b, a+b, a+a, b+b, aa+b, ab+a, etc.

The two dimensional analogues of these would row concatenation, column concatenation, and row/column Kleene star operators. Let us denote column concatenation as "+", and row concatenation as "/", so "a + b" recognizes "ab" as long as they are in the same row, and "a/b" recognizes "ab" as long as they are in the same column. Column-wise Kleene star as "+*" and row wise Kleene star as "/*".

Now let's try a problem, recognize the set of all "chessboards", encoded with the symbols 'b' for black, and 'w' for white squares. Here's an example chessboard:


b w b w b w b w
w b w b w b w b
b w b w b w b w
w b w b w b w b
...


First, we match the first row with "(b + w)+*". Next, we match the second row with "(w + b)+*", and then we concatenate these two expressions row wise, to form

"(b + w)+* / (w + b)+*"

This says match "bwbwbw..." followed on the next row by "wbwbwb...". Now all we've got to do is repeat this pattern row rise.

"( (b + w)+* / (w + b)+) )/*"

This will match the above chessboard pattern. I realize it may be confusing to represent column wise concatenation via '+' instead of the empty string as is traditional, but I wanted to make the separate row and column operators explicit and equal in importance.

Now, I was delighted that something like this could be done, and furthermore that theoretical results for NFAs, DFAs, and closure properties existed for such languages, but I still faced the problem that knowledge extraction seems to require processing values semantically, not just lexically, so I tabled it as just a nifty and cool area of research, but with no application to what we were doing.

That was, until I showed it to Mat, who came up with an additional step that would enabled 2D regexps such as those described above to be used by Tardis for time related extraction. And that story, I will leave for a future article. :) The lesson I learned however, is not to give up on an idea that may seem impractical until you've got input from other people.

In the mean time, check out the paper I linked.

-Ray

Wednesday, September 12, 2007

When algorithms work better than you dream...

So, Timepedia is building a time machine, right? It sounds pretentious, but for us, it's really a geeky moniker of love for our project, after all, is Google's "search engine" really an "engine"? How much horsepower does it have? :)

One part of Timepedia, readers of this blog are already familar with: Chronoscope. With Chronoscope, we are attempting to build an open platform of visualization tools for time oriented data, in much the same way that Google Maps and Google Earth deal with spatial data.

However, what good is a time machine, if you don't know where to go, or don't understand what you're looking at? Timepedia has another platform, aimed at data mining time related information, called Everett (owned and implemented by another Timepedia founder, Mat). Everett is a collection of many algorithms for both data mining, and forecasting, some of them bleeding edge academic research. When we started, we weren't sure which of them would work, or how well they would work, we only knew that they had promising features, so Everett was less of a end user product, and more of a research platform.

One of the tools of Everett is an algorithm that lets us find hidden recurring patterns in data, even in the presence of noise, or scaling. Last week, we tested the algorithm on real life data for the first time, and had one of those "holy cow!" moments, which don't occur too often for me personally, where your own code surprises you.

To give you an example, I fed Everett an 18,000 data point series of federal funds rates over the last few decades, and it identified a pattern that occured 3 times in history. Visualizing this in another tool we call Timelord (A Chronoscope married to Everett and other server-side services), I was puzzled as to the significance of these three sequences. My co-founder Shawn spent about 1 hour Googling, until he found the correlation: These sequences corresponded to international financial/currency crises (such as the Mexican currency crises), in which the Fed was forced to take action. The leadup to the crises appeared identical each time. A fluke? It sure the hell was very interesting.

I was worried it was a fluke, so I tried something more mundane. A time series of unemployment benefit expenditures in Indiana, and once again, Everett identified a series of puzzling repetitive sequences. What were they? The dates looked very familar, 1980-81, 1990-91, 2000-1...were they recessions? To check, I used Timelord to overlay a National Bureau of Economic Research official measure of economic expansions and contractions, and sure enough, these patterns intersected with NBER recessions. One other interesting property stood out, the patterns returned prefixed the recessions, that is, Everett was showing us a pattern that leads to a recession.

How cool is that? Ambition got the best of me, I went for broke: I tried a historical time series of average hurricane strength (saffir-simpson scale), as well as a yearly count. There appears to be good evidence that a 40-60 cyclical hurricane season exists, and I was hoping that Everett could find these patterns, but alas, it did not.

Still, the initial results are promising, and we hope that Everett will give average users an ability to query time in ways that have not been previously available.

So, if you're wondering why I haven't released Chronoscope yet, it's because I've been working on integrating Timelord with Everett. :)

-Ray
p.s. Timelord is another GWT application, making it our 4th major GWT application. Everett is C++ coupled via JNI a Java/GWT RPC interface, since performance is absolutely critical in Everett.

Converting to Guice, easier than I ever imagined.

I've been working the past month on revising the data layer of Timepedia, which has, shall we say, somewhat interesting storage requirements. However, the RDBMS related portions had become an enormous eyesore, with tons of handcoded hibernate DAO methods. I have been admiring Guice from afar for awhile, but delayed the pain of refactoring the RDBMS code until I had no choice.

Surprisingly, there was no pain at all!

I took a chance, and used Wideplay's warp-persist framework for Guice, deleted all of my DAO implementation classes in favor of Dynamic Finders, and wrote one Guice module (5 lines of Hibernate config code mostly), compiled, deployed, and prayed. Amazingly, it worked the first time. I was done, total conversion time: 30 minutes.

Now, it helps that I wasn't using Spring nor J2EE (I dislike bulky over designed frameworks with hideous XML configurations), but I think this is a good result for Guice. It reduced the number of lines of code (especially the Dynamic Finders) dramatically as well as the amount of configuration.

-Ray