this is my first post to stackexchange, I have read many solutions, especially to programming questions in R and have appreciated their helpfulness.

Currently I find myself stuck with a time series analysis problem. I am an aspiring dendrochronologist, measuring the annual tree-rings from a particularly difficult tropical tree. I have $n=37$ stem cross-sections, that I will soon finish measuring the area of, and form time series that estimate tree growth per year. Each of these stems have between 60 and 80 years in their series, but have unknown dates for each tree-ring (many died in unknown years). I need to cross-correlate all the tree samples together and adjust each series to the best lags, before averaging all the series into an estimated annual forest growth for the population. I would like to trend away from traditional methodology, of plotting each time series on a graph and visually cross-dating, and prefer to use a robust function in R, python, c++, or matlab.

Currently I have written two algorithms in R, that both rely on the cross-correlation function ccf() acf{stats} package which can return the pairwise euclidean distance between all samples. These pairwise correlations are used for forming correlation matrices between all samples, with a predicted lag for each tree growth series. When looking at a high $\text{lag.max}=40$, you cannot test every possible permutation of even $n=20$ samples because this becomes: $$(2*\text{max.lag}+1)^{(n-1)} = \text{ states; or }(2*40+1)^{(20-1)}=1.8\text{e}36 \text{ states}$$ which is not testable in a reasonable amount of time. I circumvented testing all possibilities by binning samples into groups of four, and solving all possibilities within these bins, then cross-correlating these bins to each other and adjust the series in the bins accordingly. This becomes slow as you add more samples, even though its only testing a small subset of all possibilities, which potentially sacrifices the optimal solution.

I am wondering if there is a good algorithm that can find the optimal cross-correlation between all time series that can avoid testing all 1.8e36 possibilities. I have made some attempts to use machine learning algorithms inside of Weka, but am unsure how they could be easily applied to this problem.

Thank you for reading,


  • $\begingroup$ This is synonymous to dynamic time warping. The linked wikipedia page has a list of implementations, including an R package dtw. $\endgroup$ – Andy W May 15 '14 at 13:17
  • $\begingroup$ Thank you Andy, I will look more into dynamic time warping, I was thinking about applying it to my false ring problem, where some of the years make two rings instead of one, but maybe I can apply it to my current problem. $\endgroup$ – user45525 May 15 '14 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.