View source

Lecture on Oct 6, 2008

[http://vis.berkeley.edu/courses/cs294-10-fa08/WWW/lectures-WWW/spatialLayout ''Slides'']

===Readings===
'''Same readings as for [[Using Space Effectively: 2D II]] lecture. However, you are still responsible for making a comment on this lecture.'''

*A general cartographic labeling algorithm, Edmondson, Marks & Shieber ([http://www.eecs.harvard.edu/shieber/Biblio/Papers/gen-label.pdf pdf])
*A survey of automated layout techniques for information presentations, Lok and Feiner ([http://www1.cs.columbia.edu/%7Elok/papers/layoutsurvey.pdf pdf])
*Dynamic space management for user interfaces, Bell & Feiner ([http://monet.cs.columbia.edu/publications/uist00.pdf pdf])
''Optional Readings''
*Rendering effective routemaps, Agrawala & Stolte ([http://graphics.stanford.edu/papers/routemaps/rtmaps.pdf pdf])
*Artistic resizing, Dragicevic et al. ([http://www.intuilab.com/artresize/artresize.pdf pdf]) 
*Adaptive grid-based document layout, Jacobs et al. ([http://portal.acm.org/citation.cfm?id=882353&coll=GUIDE&dl=GUIDE&CFID=64288392&CFTOKEN=3178345 acm])
*[http://i11www.ira.uka.de/~awolff/map-labeling/bibliography/maplab_date.html Map labeling bibliography]
''Demonstrations''  
*[http://www.cs.umd.edu/hcil/excentric/ Excentric labels]

== Seth Horrigan - Oct 04, 2008 10:05:26 pm ==

Reading the cartographic labeling piece reminded me once more what a complex task mapping truly is. With exposure to thousands of years of cartographic artistic and scientific skill culminating in McNally road atlases and Google Maps, I too often simply accept that excellent maps are the state of normalcy. The artistic detail that has historically gone into the work of great cartographers (and sometimes still does) is often entirely lost on me until I delve into a works like Tufte illustrating the attention to detail contained in Swiss alpine maps where everything from the subtle gradations in shadowing convey geographic information. 

In light of this, I find it especially interesting to read a piece from the mid-1990s showing some of the evolution of the cartographic skill from a hand-crafted artisan skill to an efficient computer-generated interactive visualization such as we see with Google Maps, MSN maps, or Mapquest. Today I see creeks, parks, cities, roads, even landmarks clearly and cleanly labeled and can zoom to different levels of data instantaneously while losing none of the readability (although some of the finer details as is the case with all maps). It is good to see research in the computer sciences being applied to improve the life of people throughout the US and hopefully the world.

It is also strange to see a computer-science related paper spanning 19 pages. Also, although the authors were at points rather verbose (I transgression of which I am often guilty), for the most part the paper contained entirely substance.

== NickDoty - Oct 06, 2008 02:30:02 pm ==

I'm not sure I'm convinced by the usefulness of the excentric labels demo.  By dragging a lens of arbitrary size and shape over the map and redrawing labels with lines to the points they label, you definitely can quickly see the labels from a zoom size that you wouldn't be able too otherwise.  But it seems that this could also be accomplished with a lens that simplify magnifies the area (like a moving fisheye distortion, or a magnifying loupe) and traditional labeling techniques, where the labels don't jump around.

I could see some usefulness for the office map example, hovering over a small office you might want to see the labels of the people in that room.  But again it doesn't help to have a lens of arbitrary size and shape.  Why would I want to see the names of all the people in this office and also possibly the next door office if my circle happens to overlap that office as well?  I think the important distinction here is that you might want to inquire about a particular object represented by an image on a map or graph, but then the tool should be related to selecting that item, not a arbitrary lens.  If we are using an arbitrary lens approach, why not use a simple magnification approach?

== Matt Gedigian - Oct 06, 2008 03:31:04 pm ==

Here is an outtake from the movie Helvetica, where Massimo Vignelli talks about the design of the NYC Subway map: [http://www.helveticafilm.com/vignellimap.html Vignelli interview].
 
And here a bunch of animal shapes that can be found in the London tube map: [http://www.animalsontheunderground.com/ animals on the underground].

== Kuang - Oct 06, 2008 04:20:39 pm ==

Automatic layout algorithms are engaged in something inherently heuristic. Here is a slightly different way to bring people into the loop: For an algorithm like simulated annealing, write the Perturb and Penalty functions as Mechanical Turk tasks. 

Is there existing work around this kind of human aided layout automation? The key difference is that we're not capturing human expertise (designer), but rather taste (user). Because taste is non-deterministic, it is a semantic equivalent to the goal of Perturb.

== Maneesh Agrawala - Oct 06, 2008 05:17:55 pm ==

'''Kuang''', Joe Marks has done some nice work on human-guided optimization for layout. This paper on 
[http://portal.acm.org/ft_gateway.cfm?id=331778&type=pdf&coll=ACM&dl=ACM&CFID=5376308&CFTOKEN=11751368 human guided search] is a nice place to start. Another paper in this direction covers Joe's work on [http://portal.acm.org/ft_gateway.cfm?id=258887&type=pdf&coll=ACM&dl=ACM&CFID=5376308&CFTOKEN=11751368 design galleries].

== Ketrina Yim - Oct 06, 2008 08:00:25 pm ==

I didn't expect to see AI techniques being applied to visualization. Who would've thought that constraint satisfaction, simulated annealing, and A* search could find their way into allowing a computer to choose a layout? Of course, that was before I learned that most layout criteria could be encoded heuristically. Perhaps I should look more closely at how I or others judge the quality of a particular visualization layout, to get a better idea of how penalty functions can be constructed.

More surprising, however, was the demo of automated pie chart labeling. Considering the enormous search space, the program was quite fast in finding the optimal labeling (in my opinion). Does the program really converge so quickly, or did it settle for the best it could find within N iterations?

== Scott Murray - Oct 06, 2008 08:39:39 pm ==

Has anyone used the New York Times Reader application?  I can't use it (the Mac version is buggy), but from the screenshots I've seen, it uses an adaptive document layout model to format different kinds of content (articles, series of photos, crosswords, etc.) for optimal viewing on your display, no matter the dimensions or resolution.  Of course, there are some limits (the Reader app doesn't run on small-screen PDAs, for example), but I'd consider it a real-world application of the Microsoft Research technology we saw demonstrated in class today.

== Simon Tan - Oct 06, 2008 11:41:42 pm ==

Seeing the dynamic text reflowing and layout changing of Adaptive Document Layout techniques reminded me of all the e-book reading software out there.

For example, Adobe Digital Editions (which used to be their E-book Reader software) does the same reflowing of text when you resize the application's window. When generating new e-books from HTML or Word documents, it lays out images mostly inline with the text; however, it allows these to be resized dynamically as well. With professionally-created e-books, I believe it supports various layout styles that the authors can designate, though I am not sure to what extent they can say which layout is best for which screen size. Microsoft Reader also did the same reflowing of text, though it was much more noticeable if you varied the font size of the material greatly. Also, there is a lot of software out there that accept raw content as input and produce a nice columned "reading view" (e.g. Web Eyes).

I understand the reasoning for designers' resistance to all these products that mangle with their layouts, but it is clear that they have come about for a reason. All of these approaches to dynamic document layout are an attempt to provide the most information possible on a screen while considering a human's innate reading ability to allow for a comfortable experience. I should be free to reflow my text and adjust its size in order to prevent eye strain. I'm noticing that a lot of web designers are trying to reclaim this control through the "single-column, fixed width" layout pattern you see on many websites and blogs - something I really can't stand.

== Matt Gedigian - Oct 12, 2008 10:24:55 pm ==

There is a program called [http://www.princexml.com/ PrinceXML] (a pun on "prints" I think), which handles some superset of the CSS used by your browser.  It doesn't, as far as I know, support some of the far out things that Adaptive Document Management does (like different croppings of the same image).  But in the this [http://www.youtube.com/watch?v=vcXUrNSvjhU Google Tech Talk] they discuss some of the debate between hand-layout and automatic layout.  

The New Yorker style layout was great.

== Michael So - Oct 12, 2008 10:21:32 pm ==

About distortions in consideration to spatial layout, I never really thought of them before as being beneficial or useful.  In fact, I don't think I really considered them in thinking about spatial layouts.  The comparison between the distorted London Underground map and the undistorted one, I think, really shows the usefulness of distortions.  It really does in fact make a more readable map and communicates effectively to a person how to get from one place to another, even though the map is distorted.  You would think a distortion would mislead you, but instead it does the opposite.  Another good example of distortion being better than not-distortion is mentioned in the Route Maps reading.  Standard computer-generated route maps apparently use a constant scale factor and one disadvantage of this non-distortion is that short roads are either really small or disappear.  With distorted maps, the lengths of these short roads can be exaggerated so that they can be seen.  Even though the scale is not consistent, the distorted route map conveys more information and as a result is more effective at showing a clear route to some destination.  I guess you could say that it's sometimes ok to have some lie or exaggeration within a visualization if it helps communicate a truth (like "there's a short road here where you make a left at the fork", or something).

== David Poll - Oct 13, 2008 12:51:03 am ==

@Scott Murray 

Indeed, the NYT Reader does use adaptive layout like we saw in class.  I knew I'd seen it somewhere before, but couldn't put my finger on it.  I actually remember -- I was an intern in the division of Microsoft where WPF (.NET 3.0's new UI technology) was being developed a few months before .NET 3.0 came out.  The NYT Reader was one of those launch apps that was supposed to get a big "Wow!", and it really did.  I'd be really curious to see what it took for them to build that, and how they choose the layouts dynamically.  I have a pretty clear technical picture of why WPF works so well for these types of applications (I used it for Assignment 3!) -- my question more relates to which mechanisms they used to specify how layouts should change over time.  Regardless, it's one hell of an interesting app to use.  It's funny -- we talked about consistency in these apps, and that it was very easy to lose one's place because of the dynamic content.  But in practice, I as a reader don't spend much time resizing the app just to see how the layout changes.  I keep the app open at one size, and read the article.  I actually don't find it to be nearly as disorienting as I thought it was when we were watching the demo in class.

== Witton Chou - Oct 13, 2008 02:41:46 am ==

I have to say I'm not really a big fan of the excentric labels demonstrations. I found that the labeling system actually confused me more than it helped. Most of the time I was squinting to try to pinpoint where some of the labels were pointing to. I think part of the confusion can be attributed to the mouse cursor covering up a great deal of space when the data points are so small with a thin line pointing to the points. Although there are some benefits to the excentric labels demonstrations, but there is still a lot of fine tuning to be done and more features to consider. One thing that may help would be to add another frame that would magnify the region and somehow encode pointers or shapes to help the user associate the points with the labels better to resolve the problem of having to squint. At the point that the user has to spend more time trying to associate points with labels, the benefits of the visualization are lost.

== Chris - Oct 13, 2008 07:44:57 am ==

Regarding, Dynamic Space Management for User Interfaces, one area of future work which I'd be interested in would be adding data about the "working set" of windows which are being used.  The application does a good job of maximizing visibility, but sometimes I create way too much clutter to be arranged effectively.  Often this work has a few "working sets" which I really want to have visible at the same time (e.g, mail, address book, and calendar go together, but are independent of the another group, group debugger and source editor).  An interesting are of future research would be to
* try to identify, based on the user's behavior, what sets of windows are expected to be visible at the same time
* feed that data into the space management algorithm
The first point is the difficult one, and will require some heuristics, which the user may end up fighting.  The second one could be pretty simple, maybe one could just add another dimension of free space and migrate windows between points in that dimension based on which group they belong to.

== Calvin Ardi - Oct 13, 2008 05:52:30 am ==

@[[Spatial_Layout#Ketrina_Yim_-_Oct_06.2C_2008_08:00:25_pm|Ketrina]] I didn't expect to find AI techniques to have such direct application to layouts, either. As I'm taking the AI class ([http://inst.eecs.berkeley.edu/~cs188 CS188]) at the same time, it will be interesting to see some of the overlap and how some of the techniques mentioned (A* search, simulated annealing) will apply to layout generation. Coming up with penalty functions is something I look forward to learning about in the next lecture (it seems a bit easier to do in a game, for example).

@[[Spatial_Layout#NickDoty_-_Oct_06.2C_2008_02:30:02_pm|Nick]] I didn't really find the office map demo to be all that useful. After zooming in to a certain point, the clustering of the labels make it easy to see who is in which office, but I agree regarding not having control over the size/shape of the lens. It seems like it could be more useful for a map with a large amount of data points with heavy clustering (food places on a map, or a [http://www.wikisky.org/ skymap]).

The London underground metro map example presented in class, as an example of heavy cartographic distortion, brought up some interesting points from other students. For one, the map is easy to follow, but the distances between stops are rather misleading (e.g., you wouldn't be able to walk between two stops). What would be more helpful, especially for a tourist, is if there was something that had the two side by side in some manner. The NYC metro, for example, is relatively straight-forward to follow, as it just so happens that the way the city and the stations are laid out happen to be in a grid-based format (with the exception of the outer areas).

== Nicholas Kong - Oct 13, 2008 01:18:22 pm ==

As Calvin and others mentioned, I did find the points raised about subway maps in class quite interesting. I'd never thought of using a subway map to judge distances, but perhaps this is because most maps of this type are not designed for that task. Usually upon entering a station a traveler has a final stop in mind; for determining the best way to get from station A to station B topological maps do well. The map distortion is also less of a problem because once underground a sense of direction is difficult to maintain and perhaps unnecessary.

Just thought I'd throw this out: on my Japan sojourn last summer I spent an awful lot of time looking at this particular [http://www.tokyometro.jp/rosen/rosenzu/pdf/network2.pdf map]. I like how it's easy to match labels to stations even though it's very data-dense, and I also like how by pictorially depicting the stations you can get a rough idea of how large a station is and even a rough idea of how far you need to walk within a station to transfer from line to line. It's also roughly geographically mapped, so it's possible to use it as a rough guide in determining how feasible it is to walk between stations.

== Sarah Van Wart - Oct 13, 2008 11:59:56 pm ==

@Nick:  Yes, I agree that in the excentric labels demo, using the lens of 'arbitrary size and shape' isn't really all that helpful.  That being said, I have encountered a number of cases where using a circular buffer to query or highlight has been useful.  In specialized mapping applications, people often identify a source point and a possible 'spread trajectory' for things like disease outbreaks, chemical contamination spreads, and even explosion analyses.  So perhaps one useful application of the excentric labels would be to (1) center the cursor at the point where a particular activity / incident has occurred, (2) set the radius of the lens (say, 1/2 a mile), and (3) bring to the forefront all of the labels associated with the points that fall within this lens.  I agree with you that fisheye zoom would probably accomplish the same task.

Also, a quick comment about the lecture:  I really enjoyed the part of the lecture where we went through the actual labeling algorithm
I found it very interesting to review the pseudocode used to enforce a labeling optimization algorithm, and also having the algorithm explained in class.  Without reading / learning about the penalty-reward algorithm, I never would have even thought about how much thought goes into label placement optimization!  It was also interesting to see how many iterations the logic actually went though to assign final label placement.

==[[User:Yuta Morimoto|Yuta Morimoto]]==
Applying simulated annealing to label of pie graph is very interesting.
I have little learnt exploration algorithms, but have bit idea of application using of them.
I have a interest of the software showing about how to manage stable outcome.
Since, simulated annealing is depending on how to schedule lowering temperature.
To obtain unique output, how to make schedule is the most crucial, but I remembered that schedule is strongly depending on the problem. I think, in specific problem, there is an answer of how to schedule. But, I do not know exact scheduling about the pie graph demo shown in class.

== Dmason - Oct 13, 2008 02:12:55 pm ==

I noticed a lot of griping regarding the excentric labeling, and I for one was quite partial to it. Like any tool, it is good for some things and not so good for others. For a particular situation anyone can optimize a visualization that would be better, but who can improve upon its sheer simplicity and generality? If I were exploring data for the first time, I'd be thrilled to have this at my fingertips 

I can relate the problem of excentric labeling to my own research regarding eigenvalues. These are a finite set of numbers that we overlay on a spectrum which may contain other information in the continuum. We often want to know how closely spaced they are, and the spacing can take on extreme values (i.e., a hundred eigenvalues in the span of a few eigenvalues elsewhere in the spectrum). We can even have degenerate eigenvalues, and knowing how many data occupy the same point is extremely important, and most of the visualization techniques are pretty poor. (People generally just avoid it). In these cases, a variant on excentric labeling would be invaluable.

== James Hamlin - Oct 15, 2008 03:43:27 am ==

@Dmason: I agree with you about the excentric bashing. It should be kept in mind that the task of a visualization is paramount, and the right visualization tool depends on what one is doing with the data. The selective labelling it allows could certainly find a use, and there's no reason zooming couldn't be used alongside this technique.

Getting back to the optimization techniques, something note-worthy is just that one can construct this model of the human-perceptual quality of the layout space that we can use for optimization. Just as in the Banking to 45 Degrees paper, we see clearly the point at which algorithmic and numerical techniques gain traction with results from psychophysics.

== Razvan Carbunescu - Oct 18, 2008 12:44:53 pm ==

I really didn't see the general use of the Excentric labeling for information visualization because it seemed like the problem of then selecting a point or even viewing something else close was terribly difficult and that the lines that were drawn to the labels were taking up part of the space which could have been used for labeling. I believe that in this case the best solution would be applying a fisheye lens to the graph in the region that the mouse is over and magnifying until it is possible to run the labeling algorithm we saw before applied in the map case to each point. This would eliminate I believe most of the problems with labeling very cluttered points.