How do you fit six million miles of street data on one CD? How do you quickly search through one million place names to find the one the user was looking for? How do you draw maps of a curved globe on a flat screen? How do you draw a map quickly enough so the user doesn't have to wait - no matter what part of the globe she is looking at? How do you find one thousand addresses on the map fast enough to keep the user from getting bored?
In my work with mapping software at Microsoft, my team has encountered all of these problems. All require deep mathematical understanding of the problem above and beyond a typical computer science course. As program manager, I have to understand what features I would like to build into our products are actually feasible, and what problems we are likely to encounter when trying to implement them.
A great example is the first one, fitting the entire United States on a CD. Users don't want to have to switch CDs to look at the east half or the west half of the country - they'd rather have one CD that contains everything. But "everything" is a moving target - we always want to add more restaurants, more schools, more things to see and do, as well as make sure we have every street and every highway in the country. This was one of the first problems I faced when I joined Microsoft's geography product unit in January 97.
We were writing sophisticated compression algorithms that would squeeze our data as small as possible, but they wouldn't tell us how big our map is until we had all the data and our program was finished. At that point, it would be too late to throw away information to fit on a CD - and much too late give up and split the product over two CDs.
So we took sample drops of part of the United States and ran tests on them. We estimated items like the number of restaurants, number of schools, and so on. We estimated compression ratios by running small pieces of data through the code we had, and thought about the likely impact of optimizations we would be able to make in the future. Once we had a model that will tell us how large our map is likely to be we adjusted parameters until we fit on a CD. Some things we adjusted were the number of places on the map, the amount of time we spend improving our code, and the detail of the rivers and streams.
We fit Expedia Streets 98 on one CD with only about 1% of the CD to spare, despite including much more information than the previous version of the product. And we shipped the product on time - although with only minutes to spare. Check it out at your local computer store now - and watch for us to do even more in the future!
My background in mathematics, from math contests, school classes, and independent reading, gave me skill with numeric problems that helped me solve the problem above and many others. The mathematics used was pretty simple but assembling all the concepts into a mathematical description of the problem and figuring out how to solve it required experience in solving complex numerical problems. Concepts from geometry helped with our estimations of how much space the actual lines on the map would take. Statistical concepts helped understand how error would propagate through my model - if I was a few percentage points off on some estimates, we could have been in big trouble. We knew those were the areas to watch and to revise our data accordingly.
My first big chance to work on these kinds of problems was the National Mathematics Contest in Modeling. This college-level contest has teams of three people work on a single real-world problem for an entire weekend and submit their solution in written form. I was lucky enough to be one of the first NCSSM students on an MCM team and we worked hard enough to be awarded an Outstanding ranking (the top ranking).
Even if you can't compete in the modeling contest until college, there are plenty of other real-world problems out there to be solved. Go to the library and find books of math puzzles and problems. Compete in contests in both pure and applied math. Or even find local companies interested in some free math consulting.
Above all, figure out how other interests you have relate to mathematics. The ties between mathematics and geography are deep, and exploring those ties have helped me find a job in which I can use both sets of skills and interests. Every branch of science is based on a mathematical foundation, while most non-scientific fields are desperate for people with mathematical backgrounds. There are so many great problems that need to be solved - you just have to keep your eyes open for them.
Return to Alumni columns.