Affine Transformation

I've been working on a personal project for data presentation and exploration. It is very much a work in progress but as part of the development I've come across some interesting little technical problems to solve. I hope to eventually have a longer series of posts along the lines of 'building your own data tools;' however, until I find the time to give that the attention it needs, I plan on posting some smaller entries centered around these technical problems.

One of the early challenges I came across when plotting data was mapping the input values to the fixed amount of space I had on screen. For example, if I generate a window that is 600px wide I can only support a range of input values less than or equal to 600 (using a naive approach of each value in the range maps to a pixel on screen). Supporting an input range greater than 600 values requires some level of mapping between the input values and the available pixels on the screen. There are simple conversions for specific input ranges (e.g. when the range is close to a multiple of the number of pixels) but a more general solution is necessary to handle arbitrary input data sets.

The way I ended up solving this was to use an affine transformation to map the input domain to a fixed pixel range. This is how scales work in D3.js if you are familiar with that JavaScript library. For example, if my input values come from [-100, 100] but I need my output values to fall within [28,63] then applying this transformation would look something like the image below:

Notice that the minimum value in the input interval (-100) maps directly to the minimum value in the output interval (28). Values along the input interval are mapped to the output interval preserving the relative position within each. The equation to do this is:

\[ range_{x} = (domain_{x} - domain_{a}) * ((range_{b} - domain_{a}) / (domain_{b} - domain_{a})) + range_{a} \]

Where domain and range are defined by the intervals \([domain_{a}, domain_{b}]\) and \([range_{a},range_{b}]\), respectively. Neither the domain nor the range is required to have a 0 as one of the endpoints and the intervals can be either increasing or decreasing. This generality is helpful in a variety of contexts. For example:

Setting Borders

The viewport used to plot data may not always use all available pixels of the window; multi-plot windows or viewports that have a border are two examples. In the case where there is a border around the plot (allowing for labels and tick marks) that area should not be considered as part of the range of the viewport. Instead, a window with 600px width that uses 30px on either side for border should use a range of [30,570] - the equation above makes this easy.

Inverted Axis

In most window coordinate systems the origin is at the top left of the screen. That means increasing y-axis values (from the window perspective) are typically decreasing data set y-axis values. Using a negative range makes this translation simple. Consider a 600px window height: mapping a domain to the range [600,0] automatically handles the inverted axis problem.

Another way that this simplifies things is when there is a need to 'flip' the layout of a graph. For example, in the two images below the data is the same; the only difference is the range. Having the ability to easily manipulate target ranges for the input data allows me to cycle through multiple views of the same data without much work on the backend.

 

Visualizing Internet Activity

I've recently been playing with the idea of visualizing the network demand for various activities related to everyday Internet use. Most times the browser presents a view that abstracts this behind-the-scenes activity to provide a seamless experience to the user. Even so, it can be enlightening to peel back the layers just a bit to peek at what is really happening.

In the images below I've tried to present this underlying activity in a way that is intuitive without drowning the reader with information. This is still a work in progress but I feel as though this is a decent start toward that goal.

The graphs below represent network traffic related to three types of activity one might typically engage in while online: browsing facebook, watching a youtube video, and downloading a large file. Each 'bubble' represents a packet; radius is the relative packet size; individual connections are annotated with unique colors; and I add jitter in an attempt to alleviate over-plotting.

The above is the graph for facebook. There is an initial burst of activity to load all the components when you first log in; as you scroll down the page more content is loaded to extend the page on-demand (these are the narrow vertical impulses throughout the graph); then, around time 250 there is a large amount of activity related to opening a photo album and browsing through the pictures. As can be seen by the transitioning colors there are a variety of individual connections used over the course of the facebook session.

This next graph is a view of what happens when watching a youtube video. Again, there is a quick burst to load the page and several connections are used to do this. Once the video is playing, however, there is only very periodic bursts of activity. In fact, if you observe the video progress bar as you watch the video you will notice that youtube front-loads a portion of the video immediately and then, as you start to need more content, requests the next section of the video.

Finally, this is a view of what a large file download requires: very few connections and a consistent, heavy flow of packets across the network.

From an end user point-of-view, the experience related to each of these activities is the same: open a browser, click a few buttons and receive content. The resources and demand to deliver this content, however, is entirely distinct from that experience.

That's the key

A while back I cam across a post on Stephen Wolfram's blog where he presented the personal analytics of his life. As part of this post, there is a plot showing the keystroke activity of his life over the last 10 years. I want to ignore the resolve needed to conduct such an experiment for a moment and consider how he might have set something like that up.

[Update: see the corollary to this post - generating keyboard events - here]

I'm interested in data. I have a few logs of things I do on a daily basis but they are all collected proactively - I write entries into these logs in order to keep them current. I want to set up something similar to this key logger to automate this process for me. I'll mostly ignore that this is a potential security risk in that I will be capturing all keystrokes on the computer - including username and password information. To partially mitigate this I wont store the key information, I'll only keep the time the event occurred. This limits the amount of information in my database - I wont be able to see how my distribution of characters matches that of commonly used data, for instance - but it saves me from having to worry about how and where I store this information. Stephen Wolfram's post includes details about the actual keys so if my data starts to look interesting perhaps I'll transition to keeping that information as well.

I run Linux so I figured this would be rather straightforward: somehow hook into the X windowing subsystem and register for all keyboard events. Unfortunately, such an approach is not directly possible using Xlib (depending on which stackoverflow answer you read, it may not be possible at all). It turns out that it is rather difficult to ask X to just 'give me everything.' Things, as it were, are destined for a particular location (read: window) and asking for other windows' events doesn't make much sense in the general case. I had hoped there would be something akin to a callback list for registered components that I would be able to insert an entry into. Xlib is not designed that way (at least not in any documentation I can find).

To avoid having to hack the X window event delivery system I started to look at how these events are realized by X itself. In the guts of the device initialization configuration there is something similar to the following:

Section "InputClass"
    Identifier "evdev keyboard catchall"
    MatchIsKeyboard "on"
    MatchDevicePath "/dev/input/event*"
    Driver "evdev"
EndSection

which is using one of the /dev/input/event* devices. These are character devices set up by evdev to handle generic input events from a variety of sources: joysticks, mice, keyboards, and so on. One nice thing about these devices is they can be opened and read from as if they were regular files. So, if I can figure out which of the /dev/input/event* devices corresponds to the keyboard I should have access to the events that X is handing off to the child windows.

It turns out that there are two directories that exist to facilitate this type of search: /dev/input/by-id/ and /dev/input/by-path/. Searching either of the two of them for something like *-kbd you can find the exact device linked to a keyboard (if you have multiple keyboards attached you will need to further disambiguate). For example, in my /dev/input/by-path/ there are the following:

pci-0000:00:04.0-event-mouse -> ../event4
pci-0000:00:06.0-usb-0:1:1.0-event-mouse -> ../event3
pci-0000:00:06.0-usb-0:1:1.0-mouse -> ../js0
platform-i8042-serio-0-event-kbd -> ../event2
platform-i8042-serio-1-event-mouse -> ../event5
platform-i8042-serio-1-mouse -> ../mouse1

According to this (and some mappings provided in /usr/include/linux/input.h) I can now collect all keystrokes generated by my machine from /dev/input/event2 without having to devise a way to convince X to hand them over.