Hi Denis Very warm welcome and thank you for wanting to help!
On Wed, Sep 24, 2025 at 9:07 AM Denis Shchepakin <[email protected]> wrote: > Good day, > > My name is Denis Shchepakin. I have a background in mathematics and > software development, and I currently work as an Applied Scientist at > Amazon. The Otava project caught my attention, and this thread in > particular looks like a good opportunity for me to contribute. > > To better understand the request, I reviewed a few relevant papers > (notably Matteson & James 2013 and Fleming et al. 2023). Based on that, I’d > like to propose the following plan in two phases: > > 1. Phase 1 - Core reimplementation. > Re-implement the core e-divisive solution from Matteson & James (2013) > directly within Otava. This would effectively remove the dependency on the > signal_processing_algorithms repository without requiring changes to > existing code, apart from imports. > > Yes. I think it's enough to implement equations 5 and 6, but I could be missing something. But the general approach of just swapping out the dependency and not do any other changes is one I agree with. > 2. Phase 2 - Incremental optimizations. > Once the baseline implementation is in place, extend Otava with > optimizations. For example, the current EDivisive class computes pairwise > distances in O(n^2). When a new (n+1)’th point arrives, we can avoid > reconstructing the entire structure for O((n+1)^2) by only computing the > O(n) new distances involving that point. > Otava should already have that optimization: https://arxiv.org/abs/2505.06758 Note that it's better than N: As The Fleming & Kozlakowski paper describes, Otava has modified e-divisive to only consider a window of W surrounding points. Thus when appending a new point n+1 (or anywhere, actually, not just appending) the new point only interacts with W points backwards. W is typically 50 or less, in any case it is a constant!. Hence, an algorithm that originally was N^3, is now constant time in the common case! That said, you should be able to implement the N+1 (I called it incremental e-divisive) much more elegantly once you can touch the core algorithm as well. Also, note that I only implemented append. henrik -- *nyrkio.com <http://nyrkio.com/>* ~ *git blame for performance* Henrik Ingo, CEO [email protected] LinkedIn: www.linkedin.com/in/heingo +358 40 569 7354 Twitter: twitter.com/h_ingo
