Wednesday, October 28, 2009

Clustering Over Space and Time

(This is partially in response to Suresh's wonderful series on clustering.)

Recently, my advisor (Dave Mount) and I have been kicking around the idea of how to define the problem of clustering over time. Imagine birds traveling in a flock from Canada to Mexico, and suppose that you are able to perfectly observe their locations over time (of course, for any practical use we'd need to come up with a better model, but for now...). Given all these locations, you'd like to be able to identify the flock as a cluster. If this flock crosses another flock (say, stupidly traveling from California to Maryland), you'd like to be able to identify these as two separate flocks, even if the "current" time is the one at which they're all in the same place.

Now, what about if the birds' pattern is a bit more complicated... Suppose that instead of staying nicely within the same approximate radius as they fly, the radius of the cluster varies drastically. Perhaps all the birds fly away from each other for some amount of time, then converge back to a central point, then fly away again, etc. Or perhaps there are many flocks all flying from Canada to Mexico that follow parallel linear paths, but spaced many miles apart. Are these clusters that we want to identify?

These are certainly questions that biologists are interested in (understanding infections over time), as well as folks in data mining and statistical modeling (general ideas about changing data over time). I've seen algorithmic approaches about clustering data streams (Cormode, Muthukrishnan, and Zhuang) or kinetic data structures models that maintain a clustering snapshot (Gao, Guibas, and Nguyen, and my own work) and database papers about essentially this question (Kalnis, Mamoulis, and Bakiras), but haven't seen algorithmic approaches to this question. So, I ask the internet, are there any papers I should know about? Anything else I should be thinking about?

Monday, October 26, 2009

National Computer Science Education Week

Last week, Congress (trying to push off health care reform for as long as possible) passed house resolution 558 to create national computer science education week, the week of December 7th. Why the week of December 7th? Grace Hopper's birthday was December 9th!

If these statistics (from the ACM) are still accurate, then we're badly in need of more computer science education. Talking with a friend about this recently, I found myself defending the position that computer science is not so hard that many more people can't learn it. Though originally a devil's advocate position, I talked myself into believing it. While it's unreasonable to expect that many people could get Ph.D.s in computer science, it does seem reasonable to expect many people to be able to understand basic algorithms and master basic programming skills. And that needs to happen. As money leads, so people will follow. Or, people will follow if the government leads. The government's encouragement is nice, but not actually transformative unless they put muscle behind it - perhaps a mandate for computer science education in high schools, or at least less focus on NCLB testing so that schools can teach subjects other than math and English. Meanwhile, we can all do our best to lure unsuspecting freshman to our classes with robots, videos, and other shiny things.

Wednesday, October 21, 2009

Conference Roommate Finding Forum

Announcing a conference roommate finding board:

The hope is that this will help students (and others) to find roommates to share hotel rooms with at conferences, thus decreasing cost and increasing the possibility of attendance. Ideally, I think this is something that should be hosted by CRA or ACM, but until they take over, it seems better to have something than nothing. Similarly, I don't intend this to be limited to theoretical computer science.

Please spread the word so that it will actually be useful!

Monday, October 19, 2009

On the Job Market

Having just sent off a bunch of applications, it seems fair to say that I'm officially on the job market. I'm planning to graduate this coming summer. Given the current market, I'm applying to all sorts of jobs - academia, labs, industry, permanent, 2-year, etc. I'd love to end up somewhere with exciting colleagues, interesting research possibilities, engaged students, and amazing things to do on the weekends... but I'm cursed with a certain dose of realism. Still, if you know how to achieve all my dreams, I'd love to hear the advice. Or, of course, if you have job tips...

(For more about who I am and what I do, see my more professional site.)

Friday, October 9, 2009

SoCG 2010 Call for Papers

The call for papers for SoCG 2010 just went out. It's in Utah, and Suresh is one of the local organizers. Plus, last I heard I'll be helping out with a student-only get to meet each other event. So you have just under two months to solve a problem and write a paper! Since it looks like the call hasn't appeared on the website yet, I'm including the basic details below:

26th Annual Symposium on Computational Geometry (SoCG 2010)
June 13-16, 2010
Snowbird, Utah, USA
In cooperation with ACM SIGACT and SIGGRAPH

The Twenty-sixth Annual Symposium on Computational Geometry will be held at Snowbird, Utah. We invite submissions of high-quality papers, videos, and multimedia presentations describing original research addressing computational problems in a geometric setting, in particular their algorithmic solutions, implementation issues, applications, and mathematical foundations.

The topics of the Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:
* design, analysis, and implementation of geometric algorithms and data structures; lower bounds on the computational complexity of geometric problems;
* mathematical, numerical, and algebraic issues arising in the formulation, analysis, implementation, and experimental evaluation of geometric algorithms and heuristics; discrete and combinatorial geometry; computational topology;
* novel algorithmic applications of geometry in computer graphics, geometric modeling, computer-aided design and manufacturing, scientific computing, geographic information systems, database systems, robotics, computational biology, machine learning, sensor networks, medical imaging, combinatorial optimization, statistical analysis, discrete differential geometry, theoretical computer science, graph drawing, pure mathematics, and other fields.

----- Important Dates -----

* November 23, 2009: Paper titles and (short) abstracts due
* December 02, 2009: Full submissions due (23:59, Honolulu time)
* February 15, 2010: Notification of acceptance/rejection of papers
* February, 19, 2010: Video and multimedia submissions due
* March 01, 2010: Notification of acceptance or rejection of video/multimedia submissions
* March 15, 2010: Camera-ready papers and video/multimedia abstracts due
* April 20, 2010: Final versions of video/multimedia presentations due
* June 13-16, 2010: Symposium at Snowbird, Utah

----- Local Arrangements Co-Chairs ------

* Valerio Pascucci (University of Utah)
* Suresh Venkatasubramanian (University of Utah)


We invite submissions of high-quality papers describing original research on geometric algorithms and data structures, their mathematical foundations and correctness, their implementation, and their applications.

The program committee explicitly encourages the submission of video or multimedia in support of submitted papers. Authors may wish to consider making a separate submission to the video/multimedia track (see the guidelines below). Papers and video/multimedia submissions will be reviewed separately; acceptance or rejection of one will not influence acceptance or rejection of the other.

Final versions of accepted papers will be published by ACM in the symposium proceedings. Proceedings will be distributed to symposium participants and will also be available from ACM for purchase or through the digital library. An author of each accepted paper will be expected to attend the Symposium and give a presentation (approximately 20 minutes) of the paper. Authors of a selection of papers from the conference will be invited to submit extended versions of their papers to a special issue of one or more journals.

Tuesday, October 6, 2009

Grace Hopper 2009

I just got back from Grace Hopper in Tucson! Some highlights:

  • The keynote by Megan Smith, VP of New Business Development and General Manager of, was excellent. She showed us a map of the world highlighted based on the number of search queries from the region (I wish I could find the map, it was definitely worth seeing). Africa was mostly empty of queries in comparison to the rest of the world. One of the things I really appreciated about her description of ways to change that was her acknowledgement that the people of Africa are highly intelligent and will "bring the internet to themselves."

  • I went to a talk about feminism and technology. The highlight was a Skype'd in call from a woman in Pakistan. She discussed how technology is increasing women's freedom to work, even if they aren't allowed to leave their homes. It was amazing to see her, and the room was packed.
  • The Best Practices in Introductory Computer Science Classes talk had some excellent and exciting ideas. My favorite suggestion (or really, theme) was the idea of taking projects that local community organizations need done, and giving them as class or group projects to the students. This motivates the students to do their best, since people are actually relying on what they get done, and also helps local organizations that frequently need small programs written but don't have the money to hire a programmer. While this might not work in an algorithms class, it seems like a good fit for a second or third programming focussed class.
  • I stayed for the weekend after Grace Hopper to go hiking and get to see more of Tucson than just the hotel. I went with a friend who I met at the CRA-W Grad Cohort my first year of grad school. We're still friends and both still in grad school, so for a sample size of two Grad Cohort has been effective. We spent Saturday hiking in the desert, and Sunday exploring the surrounding mountains. Saturday evening we went to watch the sunset in a location suggested by one of the rangers, and were treated to a beautiful sunset, full moon, and group of people singing the sun to sleep. Apparently Tucson doesn't frequently have clouds, but that certainly wasn't my experience.

  • Of course, no trip to Tucson is complete without cacti.

All in all, an excellent trip.