JuliaDynamics / JuliaDynamics/RecurrenceAnalysis.jl

Lazy RecurrenceMatrix to compute certain rqa metrics

Open
#166 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Julia
Stars
50
Forks
16
PR merge metrics
No merged PRs in 30d

Description

Describe the feature you'd like to have
We are using RecurrenceAnalysis.jl for computing the RQA Trend to detect changes in satellite time series.
When we upscaled this to larger areas ( meaning more time series) we found that a lot of time was spent in garbage collection and that a lot of the allocations are coming from the construction of the sparse recurrence matrix.
When we switched the algorithm to compute the tau_recurrence directly from our input time series we got a huge improvement in the number of allocations and thereby also in the timing of the RQA Trend computation.
This is the performance and memory consumption from saving the RecurrenceMatrix and then computing the Trend versus computing the tau_recurrence in one sweep and then computing the trend from there.
These are the compared functions:

"""
rqatrend(xin, xout, thresh)

Compute the RQA trend metric for the non-missing time steps of xin, and save it to xout. 
`thresh` specifies the epsilon threshold of the Recurrence Plot computation
"""
function rqatrend(pix_trend, pix, thresh=2)
    #replace!(pix, -9999 => missing)
    ts = collect(skipmissing(pix))
    #@show length(ts)
    tau_pix = tau_recurrence(ts, thresh)
    pix_trend .= RA._trend(tau_pix)
end

function rqatrend_matrix(pix_trend, pix, thresh=2)
    #replace!(pix, -9999 => missing)
    ts = collect(skipmissing(pix))
    rm = RecurrenceMatrix(ts, thresh)
    pix_trend .= RA.trend(rm)
end

rqa_single_pixel_perf

And this is the number of allocations:

rqa_single_pixel_perf_allocs

If possible, sketch out an implementation strategy

This is our implementation of the tau_recurrence function:

function tau_recurrence(ts::AbstractVector, thresh, metric=Euclidean())
    n = length(ts)
    rr_τ = zeros(n)
    for col in 1:n
        for row in 1:(col-1)
            d = evaluate(metric, ts[col], ts[row])
            #@show row, col, d
            rr_τ[col-row+1] += d <= thresh
        end
    end
    rr_τ[1] = n
    rr_τ ./ (n:-1:1)
    #rr_τ
end

I am envisioning to have a LazyRecurrenceMatrix type which would just keep the input vector and the arguments for the RecurrenceMatrix computation but where the actual matrix would not be immidiately computed but where the tau_recurrence would be computed like above.

I would be happy to provide a PR if you think this would be a useful addition to RecurrenceAnalysis.jl

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by tracing the existing RecurrenceMatrix, tau_recurrence, and trend entry points in RecurrenceAnalysis.jl. Compare the proposed lazy type with the shown rqatrend and rqatrend_matrix flows, then define completion by preserving the relevant RQA results while avoiding eager sparse-matrix construction and validating the allocation improvement.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.