Street Selection and Self-Organizing Maps

Maps have become an essential part of many of our lives, helping us to get from one place to another for centuries. With the widespread availability of relatively recent digital technologies, such as Google Maps, the need to display maps at different resolutions has never been greater.

Think of the kinds of features that are shown in this map of Canada:


View Larger Map

Not a lot is shown beyond a bit of water and some major political markings. When zooming into Ontario, bodies of water become more clear and major roads are now shown:


View Larger Map

Finally, much more detail, including local roads, is possible when looking at just the city of Ottawa:


View Larger Map

There is obviously some decision making happening behind the scenes in order to display the most important features for a particular level of zoom (or resolution, as it were).

Let's look specifically at road networks, ignoring the other features for this discussion. There are two levels of work to be done when determining what roads should be shown at a particular level of detail. This whole process is known as generalization, since we must decide what subset of all the available information will be shown.

The first step of generalization involves examining the model of the road network and using information about street connections, types, and so on to pick out the most important or relevant pieces to show.

Once we have the data that is to be visualized, the second step analyzes the geometric properties of the chosen roads and uses the results to simplify the graphical rendering of the roads. For example, a road with many small bends that can't be rendered onto the screen as such will be simplified to a straight line instead.

It is in the first step that self-organizing maps (or SOMs) can play a role. These maps are actually neural networks that are used to cluster and visualize data. To make a longish story short (and simplified), you create vectors with as many dimensions as you have numerical properties about each item you want to cluster. Using these numbers, the SOM sorts out the data so that items that are most alike end being "close" together. You might, for example, have a SOM that is represented by a two dimensional grid, and the input vectors will be organized into the cells based on their similarities.

In the case of selecting roads from a network, there are some obvious numerical values that can be used to describe each street for use in the SOM, such as length. There are, however, also some less obvious choices that seem to help categorize roads in a more useful way. A good list of attributes for each road is as follows:

• Number of streets that intersect this one
• A measure of closeness between this road and all others around it, using shortest path distances
• A measure of betweenness, the proportion of shortest paths between all other roads that pass through this one
• Length and width (i.e. number of lanes)
• A numerical representation of the class of road (i.e. avenue, street, highway, freeway, etc)
• Speed limit

Using these properties, roads can be clustered into a SOM. We can then pick a group of similar roads very easily. If we are careful about using the numerical properties so that when the value increases, so does the corresponding importance of the road, we can simply pick the SOM cells with the highest average values for the vectors stored within. These roads will be used in the map's final generalization.

For more information, please have a look at my final project for the GIS class I took in the fall semester. I implemented street selection using SOMs. The file includes my write-up of the project as well as the Java code used. Be sure to look at the README file if you plan to play with it as you will need to do a bit of work to set things up.

Women in CS a Big Success!

Although it's been a couple of weeks since the event was held, I wanted to update you all on how successful the women's evening I organized ended up being! If you happen to be a female in a computer program at your school, you might be able to get funding from your department to hold a similar event. Trust me, when the girls stay until 8pm on a Friday evening and are excited for the next meet up, it's worth the effort!

Our get together featured a Carleton computer science alumnus named Melissa. She graciously agreed to spend her Friday evening telling the current collection of female students about her experiences both at Carleton and at her new job as a software team lead. The audience was relieved to hear that being one of the few women in the field was not really so bad. In fact, other than the occasional effort on the part of the males to speak a bit less brusque around her, she found it to be perfectly ok to be different!

One really good piece of advice from Melissa was about finding some time to be girly. You won't necessarily have much opportunity to do that nine to five, so trying out some other activities where you either simply get to interact with other women or actually do girly things is important. For example, Melissa sells Mary Kay products because of the meetings with other women who do the same. You might enjoy book clubs, photography groups, and so on.

Of course, this event was made possible thanks to the Google Ambassador Program! Google supplied the pizza and, as an added bonus for this specific event, some neat giveaway swag as well!

Each participant received a Google umbrella and sticky notes with the Google Women logo. In addition, a few lucky winners were drawn for a really nice mug!



A huge thanks to Carleton's School of Computer Science, Google, Melissa, and everyone who attended this event, and hope to see you next time!

Why I Like Grad School

As I sit here in a momentary pause between one major end-of-semester project and another, at my dining room table because my office desk has become so piled up with 'to-do' stuff that I can't even use it until after the holiday clean-up, I can't help but reflect on my first semester of grad school.

Sure, the work can accumulate pretty quickly and unexpectedly at the end of the term, but here's the good part: this is the work that you pick out for yourself! Term projects, while they obviously have to fall into the realm of the courses they are assigned in, can be also related to anything you want.

Take my GIS class as an example. I could have chosen a project that would help me remember some of the material I learned in the computational geometry grad class I took in the last year of my undergrad. Or perhaps I could explore some interesting user interface programming and design. Or maybe learn a whole new data structure for storing massive amounts of spatial data. Instead, I decided to do a project that uses artificial intelligence techniques. It's an area that I've been somewhat intrigued by but know little about. I'll get into more details some other day, but the teaser is that I will be using Self-Organizing Maps to select relevant roads from a road network.

The other nice bonus about these projects is that you usually only have to choose a journal or conference paper and implement something described therein. In certain cases, this is a godsend, as it is slightly less dangerous (and hopefully less work) than researching something completely new. This is the route I took for the GIS class. On the other hand, you usually can go the research route and try something new. I did this for my other class on Entertainment Technologies, but I don't want to give any details yet on the off chance that I can actually go somewhere with that research.

All in all, it's not so bad being busy working on something you're interested in. Stressful, yes, but also kind of fun. Remember that when selecting a topic for your next school project.

Career Day

A local high school is hosting a career day tomorrow, and I am going to be presenting with my supervisor here at Carleton's School of Computer Science. I am hoping that this opportunity to talk about what computer science is all about in front of two different groups of high school students will help me determine which topics they are interested in and use that information when preparing for the mini-course I'm giving this spring.

The presentation as it already exists is pretty good. The main idea is to show the students various aspects of computer science -- from graphics and geometry to computational biology to networking and security (and a few in between) -- using some fun examples the students can relate to.

I added a few fun slides in hopes that we might be able to keep their attention for the whole 40 minutes we have to talk. For example, after mentioning games and graphics, I stuck in a video trailer for Grand Turismo HD, which showcases the best graphics I've ever seen for a video game. To tie together the slides on networking and security, I added a snapshot of Facebook. I'm hoping to add just a little bit about audio because not many people realize how well computer science and music can tie together.

Here's hoping that we can convince a few young adults to consider pursuing a career in computer science, particularly here at Carleton!

Geek Envy

I recently received my Google Summer of Code t-shirt in the mail. Here are a couple of photos showing its awesomeness:



In related news from the Why Google Is So Well Loved department, I also received some swag for my Women in CS event coming up in December. I got enough umbrellas and sticky notepads for everyone who signed up (and for my guest speaker), and a few really nice mugs that I will probably draw names for. All of this has the Google women's logo, which I have never personally even seen before, making it rare in my eyes, and all the more special. I am certain that everyone who attends our event in a couple of weeks is going to love this stuff!