On Sunday 03 August 2008 00:58, you wrote: > On August 2, 2008, Matthew Toseland wrote: > > On Saturday 02 August 2008 02:41, Ed Tomlinson wrote: > > > On August 1, 2008, Michael Rogers wrote: > > > > Daniel Cheng wrote: > > > > > in a circular space, we can get infinite number of "average" by changing > > > > > point of reference. --- choose the point of reference with the smallest > > > > > standard deviation. > > > > > > > > From an infinite number of alternatives? Sounds like it might take a > > > > while. ;-) I think we can get away with just trying each location as the > > > > reference point, but that's still O(n^2) running time. > > > > > > > > How about this: the average of two locations is the location midway > > > > along the shortest line between them. So to estimate the average of a > > > > set of locations, choose two locations at random from the set and > > > > replace them with their average, and repeat until there's only one > > > > location in the set. > > > > > > > > It's alchemy but at least it runs in linear time. :-) > > > > > > Another idea that should run in linear time. Consider each key a point on > > the edge > > > of a circle (with a radius of 1). Convert each key (0=0 degress, 1=360) to > > an x, y cord and > > > average these numbers. Once all keys are averaged convert the (x, y) back > > into a key to > > > get the average. > > > > > > eg x = sin (key * 360), y = cos(key * 360) assuming the angle is > > > in > > degrees not radians. > > > where a key is a number between 0 and 1 > > > > You miss the point. We already have what is effectively an angle, it's just in > > 0 to 1 instead of 0 to 360 deg / 2*pi rads. The problem is the circular > > keyspace. > > No I have _not_ missed the point. If you map each key onto the rim of a circle and > average resulting the x and y coords of all the keys you get an average in a circular > keyspace. Try it. > > If fact radius of the averaged x, y will also be a measure of just how specialized your > store is... (eg r = sqrt(average(x cords)^2+average(y cords)^2)
Cool! So the principle is that the closer the mid-point is to being actually on the circle, the more specialised the store? Somebody should implement this... We don't need to keep the actual samples, we can just keep a running average of x and y, right? What about sensitivity, can we reuse the bootstrapping-decaying-running-average code? Aka klein filter with sensitivity reducing over time so that for the first N samples it's effectively a simple running average and after that it's a klein filter with sensitivity equal to that at the end of the first phase? Or would we need to use a running average and reset it periodically? > > Ed -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 189 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20080805/c70fd10e/attachment.pgp>
