Ross’ PhD Blog Memex

• Currently Listening to: Barenaked Ladies — It’s All Been Done

A literature review is a standard part of any postgraduate’s endeavours, and usually makes up the majority of your first year or two. A good review sets up the landscape that you’re going to work within, saving you from duplicating effort and allowing you to identify the key players in your field. You don’t necessarily have to reel off a big document summarising your reading, but if you do it’s a fine head start on the first chunk of your thesis.

I had started my lit review last year, but it’s easy to fall into the trap of merely printing and filing papers without having read them. Then, in December at our second annual SRG-fest Joe gave an inspiring talk about structuring a literature review intelligently. Among his suggestions were to choose a handful of key conferences in your area and read every paper published in their proceedings for the last few years. For me, these conferences are places like InfoVis, ICAC, Pervasive and CHI.

Secondly he suggested building up a “mindmap” of the research areas that you’re actively engaging in. This has proven to be a very worthy excercise.

My (intimidating!) PhD mindmap

When drawn up like this my research interests seem both nicely structured but also worryingly broad. And I left out the stuff I’ll likely need to understand but currently have no interest in, like semantics, embedded systems and parallelism. My reading has been branching out a bit recently too; since I’ve started tracking my bookmarks on del.icio.us I discovered that I’m actually more interested in things like sociology and psychology than I thought.

If you imagine all the possible research that could be done in our field as a pie chart, the area I’m going to explore will end up being a thin sliver in that chart. Aaron always said that his job as my supervisor was to keep me anchored in that segment and not wander too far outside of it. Looks like he’s got his work cut out for him.

• Currently Listening to: Phoenix — Too Young

I attended the workshop on Software Engineering Challenges for Ubiquitous Computing (SEUC 2006) in Lancaster, presided over by Gerd Kortuem.

After a somewhat hurried paper submission about using AOP in automotive software, I decided to change tack, so my presentation was about what kind of problems software engineers in the automotive space are facing. Admittedly I wasn’t presenting any answers, but my presentation went well and, being the only presenter discussing automotive systems and autonomics explicitly, I got a number of interesting questions which created a good discussion.

Software Considerations for Automotive Pervasive Systems Talk given at SEUC2006, June 1–2, Lancaster UK.

Here’s an excerpt from my talk:

The modern car is a highly sensorial, complex pervasive system, with thousands of sensors and actuators and hundreds of microcontrollers controlling almost all aspects of the car’s operation; from the multimedia & entertainment systems (radio, DVD players) and navigation/mapping software, to communication both to the outside world and also on a more limited scale to other cars nearby on the road.

Finally, and most importantly, are the car’s safety systems. Most of the impetus for adding so much software to cars is the supposed benefits to driver safety. And when it works, this is great, but we must also recognise that the stakes are higher. There are dangers involved that most pervasive systems don’t have to be concerned with.

System Personalisation

Much of the talk and discussion involved the implications of personalisation in automotive systems. In the future and to an extent even now, you can choose which features you want your car to come shipped with. This is likely to increase in scale over time, so that a car’s base configuration can be permuted in thousands of ways for each buyer. Modules need to be unobtrusively integrated and interoperable.

Layered on top of this is the possibility of a car being modified, upgraded or damaged over time. Cars will have to be able to adapt to whatever components they have installed, and thus, there is a lot of autonomic computing involved.

Questions & Answers

A few brief (paraphrased) questions and answers that I remembered to write down (not guaranteed to be correct!):

Will hardware and software become increasingly decoupled in automotive systems?

This doesn’t seem to be the way it’s going. As far as I can see (and this was backed up at the workshop), the hardware and software systems seem to be getting more tightly coupled if anything.

What is the development process at the car OEMs?

I couldn’t answer this, but someone else stepped in and suggested that a lot of OEM’s in-house teams are actually graviating towards being software-only development houses, with hardware being contracted out to other companies.

Does the drive-by-wire filtering of a user’s input spoil the love of driving?

Not really a research question, but interesting nonetheless. I do wonder how many drivers could honestly say they’d prefer the primal thrill of risky, unrestricted driving over the increased safety and stability benefits of these modern cars.

• Currently Listening to: Albert Niland — Wuthering Heights

Say hello to my little friends.

I got word in April that my first paper, the alluringly-titled “Collaborating in Context: Immersive Visualisation Environments” which I submitted in March to the Context in Advanced Interfaces workshop at AVI06, had been accepted. So, Mark, Mike and I headed off to Venice for the week to watch presentations, ride around on boats and eat octopuses.

The paper concerns the design and development of our unique visualization lab here in UCD. My presentation at the workshop went fairly well, considering I had completed a cross-city dash minutes before starting (Venice is a big place!). My slides are available with the others at the workshop’s results page. My paper has been published in the ACM digital library.

AVI 06 proper was an excellent conference, with plenty of interesting work going on, and people to meet. My trip report is available:

Trip Report: AVI 2006 May 23–26, Venice Italy

Our own photos are online, and you can also check out the very lovely Geoffrey Ellis’ AVI photos (spot the goons!).

• Currently Listening to: Kate Bush — Cloudbusting

As part of the new structured PhD program in operation in CSI, we all have to give a talk on something relevant to our research.

I chose/it was suggested to me to present “fisheye” visualizations, a technique described by George Furnas in his seminal paper “Generalised Fisheye Views”, and the 20 years on review paper, “A Fisheye Follow-up: Further Reflections on Focus + Context”. This is a really interesting data filtering approach (and not a visual technique as the name might imply).

The talk seems to have gone down well, which is nice, as I have some workshop talks coming up later this month. Creating this presentation, the first I’ve given since I left IBM last September, has proven to be very good practise for preparing a talk, and then — erk! — fielding questions. My slides are linked below.

Talk: Information Visualization
Using View & Data Distortion

And here are some of the things I learned from my presentation:

1. Never, ever try and say “specificity” out loud in front of other people. That is all.

• Currently Listening to: The Strokes — Trying Your Luck

So, I got my first paper finished and submitted in time to a workshop at AVI 2006 entitled “Context in Advanced Interfaces.” Worked all the way up to 15 minutes before the deadline (which I’m told is “decent buffer”). An arduous but rewarding experience, and I couldn’t have done it without the help of our terrific support structures in the SRG, namely our academics and postdocs. As Lorcan put it so nicely, “Welcome to the anti-rat race dude.”

Update 2006/04/08: Got ‘er in.

• Currently Listening to: Metallica — Orion

So we’ve been thrashing out some ideas for our Distributed Systems practical, which is insanely tight on time.

The challenge is to build a distributed file system across the computers in the fourth year lab. The primary goal is robustness, but we’re also striving to make it as fast as possible. It’ll be tested by adding some text files to the system on some computer, allowing them to disseminate for a while, and then stressing the system through a combination of Steve flooding it with traffic and Paddy fervidly unplugging random machines from the network. We will presumably be assessed on the availability of the original files once the dust settles.

Here are my own, possibly naïve plans for how this is going to go down. These ideas are a distillation of some heated exchanges we had on Monday. They’re subject to change as I become privy to new information, man.

* The first task is to discover the other machines on the network. It has been suggested that Apple’s Bonjour networking system is ideal for dealing with “dynamic node membership”. Each machine will cultivate a peer list, and add or delete machines as they join, or are forcefully extricated, from the network.

* Each file will have to be broken up into chunks. The spec says they have to be split into 1KB chunks. Each of these will need to be packaged as an object, and be tagged with relevant metadata so we can tell which file it was originally part of. We then serialise the object for transfer, and deserialise when it’s received. This adds a considerable amount of overhead to the system, but it’s necessary as far as I can see. Some of the metadata properties each fragment needs are the source file’s original filename¹ and the part of the file it corresponds to (more on this in a moment).

* Each file is first slurped into a ByteArray. This means we can send various slices of the file to other machines on the network. Each slice (being the packaged 1KB chunks) will also have to store which part of the file they contain, which is simply their index into the file ByteArray. When reassembling the file, we first build up an empty ByteArray of the same size. We then send a call out to the other machines on the network, and they send back the fragments of the file we want. The full array is then folded back into a usable file.

* Each computer on the network will need to build up and maintain a listing of all the files — and fragments of files — that it currently stores (and yes, this means the hard drives on all the computers will fill up inexorably; this is the price we pay for true robustness). Each file is to be addressable by filename and by the hash of its contents. For this we need a HashMap with two keys for every value. The value they both point to is of course a key into another Map somewhere else, to avoid dangerous duplication.

* This index table will also store a record of the original file size and hash value of the full files². It does not need to store any reference to the data stored on any of the other computers.

* When a search request for a file (by filename or hash value) is received, the machine running our system (the “local machine”) first searches its own index to see if it has the file on its own hard drive, or has replicated parts of the file itself. If the full file hasn’t been found, it searches over k nearest neighbouring machines from its peer list, which are hopefully ordered by their ping.

* Yes, this may mean having to search every machine on the network in pursuit of a single missing kilobyte of the file. Creating a partly-centralised system like distributed hash tables has too many problems of their own. Primary among them being the fact that the hash table itself needs to be distributed and replicated, which is the problem we’re trying to solve in the first place. We still need to look a little deeper into this aspect.

* The key to this all working is that when we replicate a file, or part of a file, to another machine, we also send its corresponding record in the index table. This means that any computer that has part of a file also has a record of that in an easily-searchable format. So, when the search request propagates out to one of these remote nodes, it can very quickly ascertain whether it has part of the requested file or not, and return yay or nay.

* This discussion doesn’t attempt to guess at the “magic number” of nodes we should replicate file fragments to at a time. Logic would dictate that we should try to have every fragment of every file residing on at least three computers at a time if robustness is going to be maintained. There is likely some number to be deduced, based on the number of nodes in the network, the amount of files and amount of free space available, but we’re unlikely to work this out without first implementing the system.

1. Instead of storing the filename as text, it would be a nice optimisation to store a reference to the file’s record in the index table instead. ↩
2. This can be easily extended so that the index table holds additional metadata about each file, like singer and album details for music files. These would then also be made searchable. ↩

Update 2006/05/18: We successfully completed the assignment. Here’s my writeup comparing and contrasting current peer-to-peer systems.

Peer-to-Peer Systems Individual Research Report prepared for completion of Comp 4.14: Distributed Systems

• Currently Listening to: Modest Mouse — Float On

This paper describes visualising the process of looking after a medical patient, using multiple, simultaneous, tightly-coupled views.

@inproceedings{1019226,
 author = {Wolfgang Aigner and Silvia Miksch},
 title = {Supporting Protocol-Based Care in Medicine
   via Multiple Coordinated Views},
 booktitle = {CMV '04: Proceedings of the Second International
   Conference on Coordinated \& Multiple Views in Exploratory
   Visualization (CMV'04)},
 year = {2004},
 isbn = {0-7695-2179-7},
 pages = {118--129},
 doi = {http://dx.doi.org/10.1109/CMV.2004.19},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
}

Though the middle sections of this paper do not have much specifically to do with my own field of visualisation, they do contain a lot of good passages on visualisation techniques. Visualising time-orientated data is particularly interesting. They refer to the somewhat misleadingly named “fisheye view”, in which the focused element is enlarged and centred, and all other elements are distorted by shrinking and moving them outwards, which is a nice way to better make use of display space.

There is also a good introduction to using multiple simultaneous views, each focusing on different aspects of the data. They go about this by splitting the display area into a Logical View and a Temporal View. This approach could also be used to visualise sensor data — in effect explicitly denoting the scientific and information visualisation aspects.

There is also a section on setting up a user study to ascertain the needs, general practices and expectations of seasoned medical professionals. This is relevant as I may well have to set up some testing time with domain experts to test if our new visualisation environment is indeed more useful for collaboration than the way things are currently done.

The characteristics that the doctors and other staff identified as being important in such a system were non-surprising: intuitive interactions, a clean interface and flexibility were all mentioned. Designing for domain experts also raises a new point: the system will have to include a means for data input, which is a part of the UI that I hadn’t given much thought before.

• Currently Listening to: Arcade Fire — Neighbourhood #1 (Tunnels)

No, not the as-yet-unknown-quantity that is the paper I’m trying to put together for AVI 2006. I just got word from one of the editors at O’Reilly that the book I contributed to, PHP Hacks, has been published and is in shops. I should be getting my ‘author copy’ in the post over the next few days. Huzzah!

• Currently Listening to: The Strokes — What Ever Happened?

After an interesting meeting today, we’ve each chosen a website to extract data from, to be fed into construct as RDF. The idea of standardising on Python for all of the newly created sensors was brought up, which is good as I’ve already started working on my Python scraper.

Hidden Data

I didn’t mention this in the meeting, but some very useful data, like currency conversion rates, are generally not shown on public-facing websites. To get at them requires a form submission, and then scraping the resulting HTML page. Things I learned during my fourth year project may be able to help here, since one of the sites I tested on was this currency conversion page.

Access to a feed of realtime data costs $540 a year. With my project, for the cost of a HTTP GET request, you could have up to the minute data on any currency available in their system. This was made possible by a very useful Perl module called HTML::Form, which allowed me to simulate form submits, and thus retrieve the HTTP response page. Something similar is bound to exist for Python.

Working with Trees

There are two main approaches to screen-scraping: using heavy, regular expression-laden parsing for certain patterns of text in a string, or constructing a treelike representation of a page in memory, and then traversing this tree looking for certain elements. My favoured method is the latter, since it is generally more robust to small cosmetic changes to the underlying HTML page. Scraper rewrites are still required for when a page is reorganised, but this happens less frequently than a site having a few colours changed around.

Beautiful Soup is a very useful package for Python, which will robustly convert even an invalid HTML page into a tree, and then provides you the methods required to traverse the tree. This way, scrapers can be bashed out pretty quickly. Here’s some code to set it up; after this’ll come the page-specific code that extracts the relevant table rows or whatever is required.

import urllib, sys, re, BeautifulSoup

def get_page(url):
    """Fetches an arbitrary page from the web and prints it."""
    try:
        location = urllib.urlopen(url)
    except IOError, (errno, strerror):
        sys.exit("I/O error(%s): %s" % (errno, strerror))
    content = location.read()

    # Clear out all troublesome whitespace
    content = content.replace("\n", "")
    content = content.replace("\r", "")
    content = content.replace("\t", "")
    content = content.replace("> ", ">")
    content = content.replace("  ", " ")

    location.close()
    return content

def generate_tree(page):
    """Converts a string of HTML into a document tree."""
    return BeautifulSoup.BeautifulSoup(page)

Once you have this set up, fetching a certain element on a page becomes as easy as writing:

print generate_tree(get_page('http://www.imdb.com/')).first('table')

Polling Period

We discussed how often the sensors/scrapers should fetch their target webpage to re-parse it. Polling a page too often is likely to get your IP address blocked. Personally I don’t think this is as big a problem as was made out. Most RSS readers are designed to poll a feed once every 30 minutes to an hour. This is a reasonable period. Bar a few examples (stock quotes specifically), very few sites that we’re monitoring will be updating more frequently than that. In fact, the period could likely be increased. It would be relatively simple to set up a cron job to run each of the sensors in order every 30 minutes.

This approach could then be extended. RSS readers are/should be designed to honour various HTTP headers so that they don’t continually re-fetch the same feed over and over again if it’s not changing. All HTML files are sent with those same headers, so we could have conditions set up that the sensors will first do a HEAD request, and if we get a 304 response or if the Last Modified headers are within the last update cycle, we defer the update until the next cycle.

Ideally, the polling would be adaptive, so we have a single script that takes as input the derived update frequency of each page, and writes a new cron file with modified periodicity for each site. Thus, pages like the Dublin Bus timetables, which I’m working on, will be re-parsed very infrequently, since the site is rarely updated. Conversely, sites that serve constantly-updated information, like stock quotes and currency conversion rates, will be fetched much more often (but never more than a lower bound, like every 10 minutes).

I’ve begun learning some Python, primarily because Mark found an open source 3D graphics package called Blender, which uses packages written in Python.

So far, it looks like it’s similar in many ways to Perl, which is good because I already have plenty of experience with Perl, having used it for my final year project. Also, Lorcan is talking about doing some screen-scraping on major websites to glean data like movie showtimes and current stock prices, to be fed into Construct as contextual data.

I’ve done some screen-scraping in Perl before, but I’m guessing most of the others won’t want to code their screen-scrapers in Perl too. This will lead to serious code maintainability problems, which will invariably happen since every time the source website is updated you may have to recode some or all of your corresponding screen-scraper. Such is the life we’ve chosen. It would be best if we didn’t have to have designated caretakers for each module, so standardising on one language for them all would be nice. And I know which way the tide is turning (Joe characterised Perl with “I don’t like any language where my cat can walk across the keyboard and it will still compile” — touché).

Update: I’ve done some work on a scraper in Python.

We are preparing to install IBM’s Deep Computing Visualization software on a computer in the new Visualisation lab that’s hooked up to the DiamondTouch. This will allow us to both:

* “Explore the styles of interaction possible across different devices and a heterogeneous computing environment”
* Support simultaneous multi-user interactions across different displays

I am expecting to demo my simulation on the multiple displays in the Viz lab in the months ahead, so this will be a good introduction to the technology.

From the fact sheet (PDF):

High-end graphical images can be viewed in two visualization modes — SVN (Scalable Visual Networking) to increase screen resolution and multiplicity of physical displays; and RVN (Remote Visual Networking) to allow remote use of the application.

These two modes reflect two of the challenges in my PhD research: creating a visualisation of a large dataset across many displays, and to allow parts of the visualisation to migrate across devices.

• Currently Listening to: Ampop - My Delusions

After my initial foray into predicting the future was met with puzzlement, I’ve been thinking back over the idea of, as Aaron put it, “marrying the Scientific Visualisation with the Information Visualisation”. This seemed like the logical way to go, but right now it doesn’t look like what’s actually required or even desired for this project. Nonetheless, I want to write down the reasons I originally started thinking along this track.

Spatial Representation

First of all, because an autonomic system is made up of a large and fluctuating number of sensors and actuators, it made sense to have some form of spatial representation of where the sensors are located. This allows such actions as the person watching the visualisation saying “show me activity for the sensors at the rear of the car”, or for those clustered in the engine, for example. This would surely be a useful UI for interacting with the simulation.

Sensor Grouping

Beyond these ‘logical groupings’, they could also simply drag a box around the sensors they were interested in, and use the usual Shift-click/Ctrl-click interaction to add or remove sensors from their selection, and then generate the visualisation from this selection. Splitting the sensors driving the visualisation into groups like this would simplify the task of focusing on certain parts of the simulation, or moving parts of it onto other display devices (particularly low-power devices, with not enough processing power to generate the entire visualisation).

Using a 3D Camera

When sensors fail, as they are wont to do, the camera in the 3D environment can be positioned to show the location of the failure. This would allow the user to select nearby sensors and get realtime data from just those sensors surrounding the problematic one.