Archive for Tue, 24 May 2005

For almost the entire year until now, I had been writing a paper about an algorithm that Mark and I came up with. The algorithm was pretty complicated, so a few weeks ago I decided to step back and see if I could make it simpler. The result was good -- we shaved off a log n factor from the time and space complexity. However, the paper that I had been working on for months is now obsolete, never to be published. I could salvage a large part of it for the new paper that I am now working on, but it was still a bit discouraging.

I recently had an idea for something similar to evdb. It is a web application that lets you search based on a location, a name of something like a sports team or a band and it tells you what events are coming up that are related to these things.

The current implementation clearly needs a bit of work (there is a Blue Jays game listed as being in "Toronto, United States") and more data (there is only one page about things related to the Netherlands) but it has definite potential. What really needs to happen is for a service like this to gain critical mass. That way, promoters of events have a simple way to publicize the events and event-goers can be more confident that the events that they are interested in will be listed.

Of course, there is a slight computational geometry angle that could be explored here: I would really like a way to find events that happen within 100 km of my town. This would correspond to a range-searching query with a circle as the range. This can be accomplished using O(n^2) space and O(k) query time. If that is too much space, there is apparently a data structure that uses O(n log n) space and has O(sqrt(n log n) + k) query time. This is a pretty bad result, and one would guess that a more practical solution would be to use a rectangular query area where there are data structures that use O(n log^2 n) space and O(log^n + k) query time.