(due Thursday, Feburary 4th – for discussion in class. for reasons i do not understand, this posting didn’t work the first time, so I had to redo it)
This is a classic paper – but I want you to read it to inspire you to “think differently.” This paper is a great example of how you can take a problem with an “obvious” answer, and come up with something different.
When reading it, consider how their solution to showing a route breaks some of the “assumptions” we have about maps.
- Manessh Agarwalla and Chris Stolte. Rendering Effective Route Maps: Improving Usability Through Generalization. SIGGRAPH 2001. (pdf) (project page) (acm dl)
Think about the domain that you work in – what kinds of assumptions do people make that might be re-assessed to come up with new visualization? What other examples can you think of where challenging typical assumptions can lead to something interesting?
Everyone should comment on what kinds of assumptions can be challenged in visualizations. In class we’ll discuss how to use this to design novel visualizations.
This paper will also come up again when we talk about abstraction and generalization.
If you’re interested, here’s another (optional) paper with an even more non-standard approach to a similar problem:
- Patrick Degener, Ruwen Schnabel, Christopher Schwartz, and Reinhard Klein. IEEE Transactions on Visualization and Computer Graphics (Oct. 2008), 14:6(1452-1458) Presented at IEEE Visualization 2008. (project page with PDF)
Before class, comment on the paper (or papers if you read both), as well as to comment on challenging assumptions.
{ 20 comments }
I liked the described method and I’m surprised that I haven’t seen this on Google maps. There have been numerous times where I’ve printed a map from Google or Map quest and it’s been almost completely useless because of the scale.
This definitely falls on the present side of the present/explore spectrum and I think it succeeds because of how it handles scaling and how it quickly answers the questions that we have when we glance at a map while driving in the car. Standard routing applications seem to place us in something like a global reference frame in which north always points up and everything is to scale. This is fine when asking questions like how long it will take to get somewhere or whether there is a shorter route. When driving, however, questions like; where do I turn, which way do I turn, and did I just miss my turn are much more relevant and can’t be extracted from the standard routing techniques.
As far as technical challenges that could use I can think of three off the top of my head.
The first is software. I’ve personally experienced sitting down in front of 10000 lines of code, having hundreds of question, but having no good method of finding the answers. For large functions where variables are haphazardly declared, I would like to know what other places in the source code use that variable and how changing it in one part might affect the others. I might want to look for refactoring opportunities. I might want to quickly find the definition of a global variable or quickly determine the struct types of a long chain of member accesses. A lot of these are implemented in IDE’s like Eclipse, but I think there is some much more that could be done.
On a similar topic, I think there is a big assumption made in the area of business software such as VBA. The assumption is that the software needs to be in a programming language that is edited with a text editor. Often these scripts are extremely short and are programmed by people who have no training in programming techniques. What if these scripts could be generated using something like a flow chart, where the flow chart was the actual script.
On an even similar topic, I think there is a big assumption with spreadsheet applications. That assumption is that they are required to use the tabular form. When boiled down, I think that excel can be viewed as a list of dependencies in which the dependency names are very structured. If you remove the structure, then cells can become anything, including any number of GUI components.
I’ve been put through several ‘non-programming’ programming environments. One example is E-Prime, a software package for designing psychological experiments. It essentially gives you a flow chart to build a program.
In very limited domains, they can work acceptably (E-Prime has let many non-programmers run experiments) but when you hit the limit of its capabilities, you’re done. It’s hard to provide something as capable as a programming language without, y’know, giving people a programming language.
Visual programming is an age old topic, with pros and cons. There are some interesting reasons why it never quite catches on (often having to do with scalability). But there are some nice success stories (generally places where the programs have bounded complexity, and debugging / transfer between people / readability is not such an issue).
Not quite visual programming (which almost always produces verbose, convoluted and redundant code), but PLT Scheme’s IDE is rather nice the way it highlights inter-dependencies between the variables. Whenever I program in any language, I always remember PLT Scheme.
I’m not sure if this is along the lines of what you’re thinking of, but take a look at Resolver One… it might be interesting.
OK. Degener et al is the first paper that has blown my mind. The idea that space (in a non-relativistic environment) is not necessarily an immutable grid is just… crazy. And the fact that in testing, subjects were not only able to use the maps, but use them more effectively than traditional maps is really awesome. The subjects have, I’m quite sure, never used anything like them before. Unless they watch a lot of Tim Burton movies, maybe.
Or, another way to look at it: route-finding on this scale isn’t about turns and exact distances so much as it is about salient landmarks. Even if this technique doesn’t catch on (and there are some real logistical challenges to using it in the real world), this makes me think about techniques for making physical spaces easier to learn and navigate.
Seriously: If you were thinking of not reading this paper, read it. It’s off the hook.
Agarwalla, on the other hand, was a major head-slap, “why didn’t I think of this one?” paper. For printed directions, this is simply better than the more detailed maps from Google, etc. (Problem: too much data. Solution: summarize.) Again, in route finding, the exact details of paths just aren’t that important; landmarks are.
On challenging assumptions in a domain I’m familiar with: I’ve been doing a lot of work lately with eyetracking data (subjects look at pictures, we record where they’re looking). Everyone pictures this data as a series of dots or circles or lines, numbered over time. However, it’s really 3D data — x, y, time. Perhaps time could be pulled out into a z dimension. With some work, you might be able to draw subjects’ gaze paths like a tunnel through Jell-o. And with clever clustering and statistics, you might be able to show differences between groups…
A couple of assumptions are common in fMRI and, I suspect, really hurt people doing research. First is the assumption that there’s too much data to glean any meaning from the raw data — in essence, the first time most people see the data is after massive data reduction. And second is that the data (essentially a series of 3D images, sampling little volumes of brain matter) is inherently a picture of a brain. It can be interpreted and used that way, but getting investigators out of the “this is a picture of a brain” mindset might help them remember that really, this is a matrix of numbers, and you can (and should!) do math using it.
I read both the papers from two different perspectives. (1) Academic
(2) Technology Observer ( to understand future impact of an idea).
Last paragraph is about my domain work and some challenges that can be
solved by visualization.
/////////////////////////////////////////////////////////////////////////
Academic View and Comments:
/////////////////////////////////////////////////////////////////////////
First let me describe my academic view on papers. Both the papers are nice.
They have identified some problems with the existing methods and they
systematically and with great clarity propose some solutions which are
elegant and present them with convincing analysis that the solutions are
good.
//////////////////////////////////////////////////////////////////////////
Technology Observer’s View
//////////////////////////////////////////////////////////////////////////
First paper, by Maneesh describes some problems with the scaling. I have
used Google Maps for almost 5-6 years now and with the text information
( Take the ramp onto I-55 S, take the exit 269. Go 100 miles etc) and
some image, I never had any problem reaching to the destination. In this paper,
the authors says that scaling remove short roads. But my view is that
we need both real view ( which has linear scale ) and the distorted scale
presented by them in order to have clear understanding of the location.
Also according to psychology global view is far more important than the
local view. I don’t think that we are so dump that we can not find the house
that is around the corner. I am quite sure, if the proposed solution were
accepted by the Google, then Maneesh would have written a paper on “How
Global View enhances Effective Routing”.
Second paper describes routing in Hotels, resorts and museums. Well the
problem and solution presented by the authors gives me a feeling of science
fiction stories, where some human land-up in some a great five star hotel on
mars and in order to find his room, he has supercomputer( that he always carry)
that can do image warping at blazing speed, do ray tracing and render
photo-realistic images faster than the time to walk maximum 500 feet on foot.
On earth, when it will become feasible ? Wondering what the great explorers
of 16th century might be thinking of 21st century science, when they had only
simple magnetic compass to navigate the earth.
///////////////////////////////////////////////////////////////////////////
Domain Challenges
///////////////////////////////////////////////////////////////////////////
I have been working on Computational Geometry problems for almost 10 years
now, and I firmly believe that designing correct and robust algorithms in
geometry are extremely hard. A single wrong predicate ” Given a point, tell
if it is on left or right side of a given line” could be a simple problem
at first glance but considering all the degenerate cases, floating point
arithmetics on real computers, such a simple problem could have non-trivial
solutions. With my own experience, when some bugs in CG comes, there is no
better solution than using some visualization tools to identify the case for
which algorithm failed. Debugging CG code in three or higher dimensions is
still an open issue.
When I read the Figure 1 of the paper, the first impression to me is that the standard map is the whole dataset and the LineDrive is a subset that extracts all the useful information from it, while the written one is personalized. The main goal of the map is to drive to the right destination, not to explore the whole state or estimate the time. Therefore, it is reasonable to break the assumption of scale, which I believe is quite essential in designing maps. A written route is easy to read and follow, but I always keep a standard map in my vehicle if possible and my personal experience is that when I miss the correct turn I will not be lost. By using a map with more information, I need to stop and read the map carefully, instead of a glance as using a LineDrive.
Assumptions are important in my research of statistics, and it is sometimes make the plots not very informational. One good example is outlier. Keeping outliers in the plots may result in that those data behaving normally may be compressed to small regions. Another example is the distribution of data. The regression plot, one of the most common plots, is not that meaningful if the data violate the normal distribution assumption. Sometimes people normalize the data before analysis. Similarly, the independence assumption among variables can be challenged.
Both of these papers presented some very unique concepts with respect to visualizing the real world. With respect to the technical nature of the papers, however, I found there to be striking differences between them.
Agrawala’s paper seems to be extremely thorough in explaining all of the factors considered in the design. The authors seem to have anticipated most situations that may come up during the use of their maps and really maintained a focus on this user-centric design. However, it appeared as if little reasoning as to the final execution is provided and a good deal of the paper is spent discussing the actual algorithms implemented, several of which seem almost too common place to be explained in a paper intended for publication in a technical venue.
The second paper, on 3D route visualization, presents a very novel technique which definitely has the “cool” factor. The authors focus heavily on the execution of their tool and put a good deal of thought into the technical aspects of their design. However, as the user testing seems to indicate, the actual usability concerns of the tool appear to have not received due attention. Viewing the sample images provided in the paper, I have a hard time imagining how the paper would be able to be useful for any real life situations. The issues of occlusion and direction seem to be too great to overcome in the current implementation for any route longer than one that could simply be memorized. The idea seems really great, so I hope I’m wrong on this one. It definitely will be a difficult problem to solve regardless.
The idea of challenging assumptions is common across both papers though. This is starting to feel like a common theme in visualization itself. The idea of showing potentially massive amounts of data in a single image requires violating assumptions for small-scale data presentation in order to abstract the data into a structure that can be represented in a single comprehensible view. By challenging the assumptions of the nature of the data itself, such abstraction is possible, thereby facilitating the exploration of increasingly large bodies of data.
Both papers are fascinating, and wonderful applications of the “science of visualization” to more practical problems. I was already aware of Agarwala line-drive work which became the basis of MapBlast until Microsoft bought it and killed it. It seems to now be available only via SpatialPoint, a Microsoft business partner. In any case, I remember seeing line-drive a long time ago and was just thrilled to see this utterly simple yet logical and so effective visualization of driving directions. Love this work.
I found Degener, et. al. tackling an interesting problem as well, however, a lot less interesting than Agarwala. Degener, et. al. are solving the problem of “seeing around the corner,” which, by its nature, is only applicable for short distances, and in closed environments. Thus, it is more limited in scope. Btw, the math was over my head, so I just glazed over it.
The paper gives me a new angle on how to visualize the route on a map. I guess google simply mark the route on the map without any artifacts. The three techniques involved in LineDrive: Length Generalization, Angle Generalization, and Shape Generalization are very practical considerations for a good route visualization.
However, I guess the usefulness of this technique is limited, that is also the reason why car GPS is popular nowadays. If the route is long, it will become difficult for people to locate where they are. (See example Figure 14) The benefit of GPS is to give turn-by-turn notification so that the drivers do not have to remember where they need to turn.
I am working on the visualization of large relational database. Many years, people assume that the data should be stored in relational schema (e.g. table) for efficient query. That is true, but relationship between data has been ignored, since data in rows and columns of table only show what they are (e.g. Author Name, Paper Title, Year, Venue), but not the relationship between them (e.g. who and who are coauthor ship).
To understand the relationship between data, we need to get rid of the old assumption (data should be stored in table), and represent each data record as a node in graph, where there is an edge between two nodes iff they are in some relationship. By doing this, we emphasize the edges in the graph, which is the relationship, instead of the content of each data record.
Map generalization has been performed since the first maps were scratched into the ground. It stands to reason that the application of different generalization techniques such as selection, simplification, omission, aggregation, exaggeration and addition would find their way into the digital delivery mechanisms available today.
The Agrawala and Stolte paper is a good example of scale-dependant, rule-based cartography that serves to provide greater effectiveness through the extraction of unnecessary data. A satellite photo is not a map, for example, because no generalization has occurred. A blending of art and science must be applied to a satellite photo in order to transform it into a meaningful representation of the spatial inventory. In a similar fashion, LineDrive relies on scientific principles and algorithms while considering aesthetic qualities that are appealing to the user. I’m looking forward to any class discussion regarding the benefits and drawback of data omission (in particular) as it relates to effective visual communication.
One idea that jumped out at me is that maybe instead of the randomized solution they went with, involving complicated scoring functions, what if you simply take the log of all road lengths, represent each road as a straight-line or elliptical segment between starting point and ending point preserving the angles of intersections, and finally resolve false intersections by making minimal perturbations in road length or intersection angle. There should be no need to randomly iterate, though it could turn out that there are cases where this wouldn’t work, probably in cases where the original road segment has a lot of winding in it, and has intersections. It seems surprising that self-intersections would occur often enough to deserve this level of detail, though I agree that if they occur, not depicting them could be unnerving to the driver. (Haven’t I already been here?)
One of the things that struck me is that much of the actual work in implementing the system is in finding exception cases, and trying to prevent them from making it into the final product – and that while a lot of may seem to be ad-hoc at first, there may be no more “elegant” solution. (See especially the sections on removing missing and false intersections.) This is not meant as a criticism of the work, but rather an observation of some of the problems encountered in visualization – note that intersections are essentially marks, and an important visual channel, yet they are not a first-order drawn entity, or at least, false intersections are not. Rather, they are a result of the placement of other entities (roads), and are not planned. This suggests that in general, one class of problems in visualization is that visual channels can interact constructively or destructively to produce second- or nth-order effects which are *perceived* as visual channels, even though they are not intended that way. Unfortunately, when nth-order interactions are involved, combinatorially large spaces may need to be searched. Where spatial channels are involved, layout will need to address such problems, but what about other channels? (One could look at the Hue Blending paper as one way of sorting out interference between different color channels in a relatively straight-forward way, for instance.)
Also, as I’m probably going to end up being the stickler on language in this group, I might as well dive in. I find it interesting that they seem to use the word “generalization” in a domain-specific sense, meaning something like “expanding the set of potential visual representations of the same data”. I.e., if you expand the set of potential visualizations of the same data, you are “generalizing” it, for instance by distorting the road lengths or intersection angles. Any lossy encoding of data begs the question, “what is the signal, and what is noise?” The did a good job of addressing the question in this case.
They also use the word “clean” a lot, and it is a crucial concept – their representation is better largely because it is clean. What does “clean” mean, then? I think it should mean “using the fewest marks, with the least ‘pop-out’ or attention-grabbing characteristics needed to communicate the necessary information”, which is something like Tufte’s efficiency, but I would be interested in hearing other notions of what constitutes cleanliness. For instance, maybe it could mean something about visual channels not *conflicting*, or interfering with the viewer’s reception of information in other channels.
Finally, I have a suspicion that the reason you don’t see this in google or yahoo maps is that it may not run in under one second. Also, it would have to be rendered separately from whatever map the user may have been looking at originally, which may interrupt their work-flow. They acknowledge the Vicinity corporation… Vicinity’s web page links to something called MapBlast (http://www.mapblast.com/) which doesn’t appear to use LineDrive. MapBlast appears to have been acquired by MSN – makes you wonder what MSN did with the technology.
> They acknowledge the Vicinity corporation… Vicinity’s web
> page links to something called MapBlast
> (http://www.mapblast.com/) which doesn’t appear to use
> LineDrive. MapBlast appears to have been acquired by
> MSN – makes you wonder what MSN did with the technology.
They killed it. It used to appear on mapblast, and used to be my favorite for directions (Gmaps didn’t exist). And then it appeared on MSN maps for a bit. But, I am not sure anyone uses MSN maps anyway. I was trying to investigate where it went, and it seems to have been acquired by a company called SpatialPoint that licenses Microsoft’s MapPoint technology. SpatialPoint is an independent company, and is an MS-business-partner.
In effect, line drive directions are gone.
The LineDrive paper presents a very effective way to give concise and useful directions at a glance. By using a nonlinear mapping and removing unnecessary details, they were able to emphasize the detail where it mattered (in the small turns). This reminds me a lot of the odd proportions and exaggerated motions used in animations. Looking back at how lineDrive achieved this, I think that the most important part of their method is that they took the time to figure out what detail was removable. By doing this, and using the non linear spatial mapping, they effectively mapped the route into a space that gave a more equal weight to each of the perceptual dimensions needed to answer the question “where do I turn next, and in which direction?”
In my current line of work, I have been thinking a lot about what makes a good abstraction. While “it depends” is probably the most correct answer in general, when one has a specific aim it is easier to answer. A good abstraction removes information without removing, and sometimes even enhancing, meaning.
As far as implicit assumptions, I think that most people usually try to map things on a linear scale. Whenever one is trying to design a visualization, it is important to think about the issue of scale. For example, one of the examples someone gave above was about outliers in scatter plots. If the aim is to be able to see the outliers, while at the same time not clumping up the inliers, then perhaps a linear mapping of the axis is not the best choice.
Agrawala et.al paper did some interesting work and is also a good example of how to apply human psychology research in designing better interfaces. But LineDrive seems to have some significant issues that need to be resolved before there work become part of mainstream mapping tool. For example, I am not sure that simulated annealing algorithm can be efficient used to add a new set of roads to already generalized routes (e.g. if navigator stray to some previously computed map). Also their algorithm might be very slow when trying to run it for finding routes for long distance trips.
One domain related assumption that I can think of is related to visualization of routes of local area or wide area network computers. It seems to be a general approach to try to show network connection between each and every node in the network along with some specific labels. This is usually a lot of information making the visualization very complex. I think, we can get rid of this clutter by totally moving away from modeling network graphs as nodes and links between these nodes.
The Stanford paper is really fantastic. In this GPS era, route map is still an effective method for travelling. The authors are really good at standing and viewing from a point of the specific enduser group, and thus make a very good abstraction for the most important details. For me, the really surprising thing is that how they find this problem neglected by most of us, whose significant elements are also easy to find.
I’m not familiar with the technical part of the paper, so not much comment at the implementation details. However, I’m a little bit confused about the algorithm they fix the orientation of the roads. In my opinion, the angle at the turn point is most determined by the angle between the starting section of next road and the ending section of current road. So can we just define a segmentation small enough at the starting and ending part of the road, and then fix the angle and do some adjustments? What’s the difference and the drawback of this straight forward method comparing to the dynamic one used by the authors?
Though the work is really excellent, there are some defects to me, firstly, turn orientation is extremely helpful for novice drivers, as they can determine beforehead which line to follow to avoid frequent line-changings, so explicit display of left and right turn (as most of GPS did) at each turning point might be helpful. Another thing is the authors did not distinguish the “actual turning point” (by which I mean crossing and those needs decision) and turning with road itself, thus, some of the dots on the map might not need to be displayed explicitly, as too much dots might be a new source of clutterring. Only those dots at the road points which need decision might be necessary.
I read LineDrive. It was the first paper I have ever seen the procedures to get a better design, so I learned that even label layout is not simple and that the main problem, road layout is divided into 4 criteria to satisfy each of them.
They assumed the use of cognitive psychology (route as a sequence of turns) will improve the readings of map through length, angle, and shape generalizations. Looking at the generated map, it is similar to the map we would draw in hand but it might be confusing to figure out right or left turn at a glance while driving.
Agarwalla and Stolte’s paper on Linedrive is a great case that makes you say “it’s so obvious, why didn’t they invent it before”. By systematically skewing the data and discarding information that would be regarded crucial in other mappings, it serves the ultimate goals of presentation much more efficiently. As a result of sophisticated algorithms to get rid of scales and exaggerating landmark turnpoints, the output is closer in intuitiveness to the direction maps produced by human hands.
I found that in some ways this approach looks similar to the heuristics of the human cognition itself, which relies more on mental shortcuts rather than pieces of pure logic and facts. However, It should be taken into account that we are prone to understand scale as information in looking at maps if we are not already familiar in disregarding scale such as in a direction map. If scale does not carry (or skew) information but the viewer intuitively looks for meanings in the scale, the communication could be distorted.
To me, the most impressive thing about this paper (other than it being pretty interesting and accessible) is that it acknowledged almost all the questions I had when I started reading it, such as whether the 2200 testers just looked at a LineDrive map or actually used it for navigation, and whether they added context. They even specifically said crossroads would be helpful in case someone got lost, which were almost exactly my thoughts when I started reading the paper. Unfortunately, it didn’t answer all the problems in a satisfying way, except to say that the system isn’t perfect and LineDrive maps should be used in conjunction with more tradition maps. Also, it looked like all the roads had been simplified to straight lines, so I’m curious as to how badly it distorts directional data when mapping routes involving things like beltlines.