What is the terminology for reducing inputs to only distinct elements to speed computation?

user_2962956 0
Viewed 41

Is there a term for leveraging the fact that data is comprised of a few much-repeated values to speed computation?

As an example when trying to compute Sample Entropy on a long discrete sequence (Length=64.000.000.000, Distinct elements = 11, Length of substring=3) I was finding the running time too long (over 10 minutes). I realised that I should be able to make use of the relatively few distinct elements to speed up computation but was unable to find any literature relating to doing this (I suspect because I don't know what to Google).

The algorithm for Sample Entropy involves counting the pairs of substrings that are within a certain tolerance. This was the computationally expensive aspect of the algorithm O(n^2). By taking only the distinct substrings (of which there were at most 1331) I was able to find the pairs of distinct substrings within the tolerance, I then used the counts of each distinct substring to find the total number of pairs of (non-distinct) substrings that are within a certain tolerance. This method substantially sped up my computation.

Do algorithms that make use of the property of relatively few, much-repeated elements have a specific terminology.

def sampen(L, m, r):
    N = len(L)
    B = 0.0
    A = 0.0

    # Split time series and save all templates of length m
    xmi = np.array([L[i : i + m] for i in range(N - m)])
    xmj = np.array([L[i : i + m] for i in range(N - m + 1)])

    # Save all matches minus the self-match, compute B
    B = np.sum([np.sum(np.abs(xmii - xmj).max(axis=1) <= r) - 1 for xmii in xmi])

    # Similar for computing A
    m += 1
    xm = np.array([L[i : i + m] for i in range(N - m + 1)])

    A = np.sum([np.sum(np.abs(xmi - xm).max(axis=1) <= r) - 1 for xmi in xm])

    # Return SampEn
    return -np.log(A / B)

def sampen2(L, m, r):
    N = L.shape[0]

    # Split time series and save all templates of length m
    xmi = np.array([L[i : i + m] for i in range(N - m)])
    xmj = np.array([L[i : i + m] for i in range(N - m + 1)])

    # Find the unique subsequences and their counts
    uni_xmi, uni_xmi_counts = np.unique(xmi, axis=0, return_counts = True)
    uni_xmj, uni_xmj_counts = np.unique(xmj, axis=0, return_counts = True)

    # Save all matches minus the self-match, compute B
    B = np.sum(np.array([np.sum((np.abs(unii - uni_xmi).max(axis=1) <= r)*uni_xmj_counts)-1 for unii in uni_xmi])*uni_xmi_counts)

    # Similar for computing A
    m +=1
    xm = np.array([L[i: i + m] for i in range(N - m + 1)])

    uni_xm, uni_xm_counts= np.unique(xm, axis=0, return_counts = True)
    A = np.sum(np.array([np.sum((np.abs(unii - uni_xm).max(axis=1) <= r)*uni_xm_counts)-1 for unii in uni_xm])*uni_xm_counts)

    return -np.log(A / B)
distinct-values algorithm terminology
1 Answers

It's a broad concept with several related terms.

A common, closely related term is Memoization, wherein the results of computing a subproblem for different inputs are stored, and reused when a previously-seen input is re-encountered. That's slightly different from what you're doing here, since memoization is a form of lazy evaluation where values are recognized opportunistically rather than the code performing an up-front exhaustive enumeration of the inputs which will be processed.

Materialization is also worth mentioning. It's encountered in the context of databases, and refers to the results of a query (a.k.a. tabular processing including possible filtering and/or reduction) being stored for reuse. The active concerns with materialization are largely around long-term considerations like dynamic updates, so it's not a perfect match for a run-and-forget algorithm.

Speaking of 'dynamic', one could also maybe describe this as a form of dynamic programming, with a problem solved by exhaustively enumerating and solving a sequence of subproblems. In dynamic programming, though, one expects those subproblems to have a more regular and inductive form, so I think that one's a stretch.

I would describe the precise strategy here as a sort of "eager memoization", to contrast with the lazy-evaluation assumption normally inherent with memoization.

user_7874800
Related