On Wednesday 16 July 2003 10:50 pm, Zlatin Balevsky wrote: > Possible improvements over using a fixed number of reference points and > straight lines between them would be : > > I. Non-linear estimators: instead of straight lines, user some sort of > interpolation to create the graph : > a. If the number of points is fixed around 10, we could use newton > interpolation or chebyshev polynomials. > b. For larger number of more dynamic reference points we could use cubic > or quadric splines - these have the benefit that when one reference > point moves only its immediate neighbors need to be re-calculated which > spares us some cpu time while providing even better interpolation than > the polynomials. > c. If after some experimental data we notice that the reference points > tend to form periods, we could even use FFT for the very best of the > interpolating world ;). > > these are only the interpolations that I could remember from a Numerical > Methods course I took last year; when the textbook finds itself I'll > probably come up with more information. Each of the above methods beats > using straight lines by far though. > > > AND/OR > > II Dynamic number of reference points based on specific events: > a. adding new reference point for every new sample (yeah right)
Well, I once tried to make a liner time function to derive the formula using an Nth degree polynomial. At the time is was just an exercise, so I gave up after the math became too much of a bitch. (I think I could do it.) This would in theory yield the best possible interpolation, if one assumes that the cache distribution follows a polynomial curve. (and you could just add new data points to the set and change your weights without recalculating the whole thing.) Although I'm not sure it would lead to any real benefit, as if we cached biased any consistant formula, say a quadratic (fixed time) function biased on the data we currently have in our store, then using that same formula might work just as well. I proposed this a while back under the name Node Stereotyping, and I assume something similar will be done with NGrouting. However if it would produce more accurate results, with an N-degree polynomial, and be worth while I could hash out some pseudo code. Vote yay/nay. Ether way, you can do quadratic with N points in fixed time and no recalculation when you add a new point. So I see no reason to stay with linear. _______________________________________________ devl mailing list [EMAIL PROTECTED] http://hawk.freenetproject.org:8080/cgi-bin/mailman/listinfo/devl
