Monday, June 29, 2009

A Sensor-Based Framework for Kinetic Data

I leave in about a week for Greece, where I'll be presenting a paper at AlgoSensors, a workshop associated with ICALP. The paper is entitled "Compressing Kinetic Data From Sensor Networks" and is joint work with my advisor, David Mount. You can see the camera ready version here. Slides will be posted on my website once they exist.

While the main result of the paper is a compression algorithm, the point of the paper is broader than that. When reasoning about kinetic data (the data generated by a set of moving points), the current accepted model is the kinetic data structures model that assumes that points are given flight plans in the form of algebraic expressions. This works well when reasoning theoretically (assume the points follow predetermined algebraic curves...), when modeling physical properties, or possibly when dealing with actual planes that really do need to give us their flight plans in advance. But what about if we want to do statistical analyses on collected data to determine what motion trends the objects follow? The cell phone users, migratory birds, enemy tanks, whatever you like to think about, aren't going to tell us how and when and where they're going to move. Many of these observations are collected using a sensor network, so it makes sense to design algorithms that work over these networks using the possible minimal amount of information available - the number of objects each sensor sees at each time instant. The framework we introduce assumes nothing about the motion of the objects or our advance knowledge of their plans. Instead, we analyze our results with respect to the entropy of this information. The ultimate goal, then, is that algorithms designed over this framework would perform better on "neat" motion, say all the birds following a straight line from Canada to Mexico, while algorithms on "messy" data would take longer. This paper takes the first step in that direction, giving a compression algorithm that compresses the sensor observations to within a constant factor of the optimal joint entropy bound.

For those interested in more precision, the abstract is included below:

We introduce a framework for storing and processing kinetic data observed by sensor networks. These sensor networks generate vast quantities of data, which motivates a significant need for data compression. We are given a set of sensors, each of which continuously monitors some region of space. We are interested in the kinetic data generated by a finite set of objects moving through space, as observed by these sensors. Our model relies purely on sensor observations; it allows points to move freely and requires no advance notification of motion plans. Sensor outputs are represented as random processes, where nearby sensors may be statistically dependent. We model the local nature of sensor networks by assuming that two sensor outputs are statistically dependent only if the two sensors are among the k nearest neighbors of each other. We present an algorithm for the lossless compression of the data produced by the network. We show that, under the statistical dependence and locality assumptions of our framework, asymptotically this compression algorithm encodes the data to within a constant factor of the information-theoretic lower bound optimum dictated by the joint entropy of the system.

Also, a reminder - the SODA abstract deadline is today at 4:59pm EDT.

Friday, June 19, 2009

At The Lake

It's the middle of my yearly pilgrimage to Minnesota lake country. It's beautiful here, and while I'm spending much of my time working, at least I'm looking at the lake while doing it.

I'm also reading an excellent book: How the States Got Their Shapes by Mark Stein. While I'm always skeptical about books on somewhat academic subjects written by non-academics (I think he's a playwright), it's a thoroughly enjoyable book that gives a brief overview of the history, geography, and geometry of state boundaries. As I like all three of those things, I'm totally hooked. It turns out that many of the decisions about state boundaries were made based on two main ideas - water rights and state equality. For example, why does Minnesota have the northeastern corner, known as the arrowhead, in which I am currently looking at a lake? Why isn't that Wisconsin or possibly Canada? It's all about access to the Great Lakes and through them the Atlantic Ocean - the Minnesota arrowhead was shaped precisely so that Canada, Wisconsin, and Minnesota all have access to Lake Superior. On the other hand, why that specific boundary taking a southeast course from the Lake of the Woods to Superior? The book just says that it follows the boundaries of a set of lakes, but up here there are a whole lot of lakes. I have to wonder whether the boundary was really chosen to be where it is today, or whether no-one noticed or cared since the area was, and is, mostly uninhabited. The region is now part of an international/national park - the Boundary Waters Canoe Area Wilderness. The only way in is by canoe. I'll hopefully make a day trip in sometime next week.

Monday, June 8, 2009

Life Is Unfair - Sue

I've been meaning to post this information for awhile - it was distributed (with right to forward) on the Systers email list in response to a question about what to do if you believe that you've been denied tenure due to discrimination.

One resource to recommend is the AAUW Legal Advocacy Fund.

LAF has a long history of fighting sex discrimination in higher education, and in 2004 published a summary of several cases in "Tenure Denied." Download the full report.

In the last couple of years, LAF has stopped providing support for individual plaintiffs, but it does maintain a network of attorneys who are experienced in such cases and willing to discuss options with potential plaintiffs.

See these resources for more information on tenure issues.

For those of you in a position to be more proactive, check out LAF's campus outreach program to bring a gender-equity focused program to your campus.

If you're female and you're not already on the Systers email list, I recommend it (though only in digest form... it gets a lot of traffic).

Wednesday, June 3, 2009

The Cost of Being a Woman in CS

A paper of mine was accepted at AlgoSensors, which will be held in conjunction with ICALP this July. I'll post a summary and copy once the camera-ready version is finished. Right now, I'm working on the logistics of getting to and staying in Rhodes, Greece, an exciting but expensive location. The problem with staying at this conference, as with any conference, is that as a woman in computer science it's hard to find a roommate. The chance that another woman from your school is going is extremely small, since the chance that you're not the only woman in theory in your department is small to begin with. Perhaps this is why all the female students I talked to at STOC were staying with people they knew in the local area, while most of the male students were sharing hotel rooms. Were female students without local connections unable to afford to come? Knowing women from other schools due to the women in computer science conferences helps, but certainly doesn't solve, this problem. And so going to conferences costs (my advisor) more money than it should - more money than it would if I were male.

There is a simple solution to this problem. And, as in the case with many changes I advocate with women in mind, it would help men too (in addition to our advisors' budgets). CRA or ACM could put up an online conference roommate finding board. If one exists, I couldn't find it. Perhaps one of you has the ear of the right person...

In the meantime, if any of you know (or are) a woman going to ICALP and looking for a roommate for the nights of July 8th - 11th, please send her my way.

Tuesday, June 2, 2009


Other folks already have some nice STOC summaries up (Bill/Lance, Michael), so I won't repeat them except to say that not only was Shafi Goldwasser's Athena Lecture excellent, her jokes were intelligent too (if you missed it, it looks like there might be a video posted here some day). Truly a talk worth seeing.

Another talk that's gotten less attention, but that I thought was exciting, was the paper "Homology flows, cohomology cuts" by Erin Chambers, Jeff Erickson, and Amir Nayyeri. There's no point paraphrasing when they say it so well themselves:

We describe the first algorithms to compute Maximum flows in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a maximum (s,t)-flow in in O(g7 n log2n log2C) time for integer capacities that sum to C, or in (g log n)O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

Check out their full paper from Jeff's site, where I also stole the nice graphic and abstract from.

I was volunteering for the conference (Maryland was the local host) and spent some of my time working the registration desk, which gave me a nice chance to see people as they entered. It was nice to meet some of you in person. Even though the business meeting was a bit tame (perhaps Chazelle should be given best paper awards at every conference to add entertainment value...), it seems to have been a successful conference. Congrats and thanks to all the organizers/speakers/PC members/etc.