SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 2 Vol 1

CELL MATCH

Name:
    CELL MATCH (LET)
Type:
    Let Subcommand
Purpose:
    Return the index in an array where the array value matches a scalar value.
Description:
    Given a scalar value, VAL, and an array, X, sort the values in X and then find the index, IVAL, such that

      \( X_{i} \le \mbox{VAL} < X_{i+1} \)

    If \( \mbox{VAL} < X_{1} \), set IVAL to 0. If \( \mbox{VAL} > X_{N} \), set IVAL to N+1.

    The CELL MATCH command will do this for an array of values.

    This command was motivated in the implementation of the P-square algorithm for one-pass estimation of percentiles.

Syntax:
    LET <index> = CELL MATCH <x> <value>
                            <SUBSET/EXCEPT/FOR qualification>
    where <y> is a response variable;
                <xseq> is a variable that defines the sequence number for the response variable;
                <x1> ... <x6> is a list of one to six group-id variables;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional and rarely used in this context.

    Neither the <x> nor the <value> variables need to be pre-sorted. The output variable <index> will be the same length as <value>.

Examples:
    LET IINDX = CELL MATCH X VAL
Default:
    None
Synonyms:
    None
Related Commands:
    MATCH = Match a column of values to another column of numbers and return the index of the matching value.
    SORT = Sort the elements of a variable.
    CODE = Generate a coded variable.
    SEQUENCE = Generate a sequence of numbers.
References:
    Jain and Chlamtac (1985), "The P^2 Algorithm for Dynamic Calculation of Quantiles and Histograms without Storing Observations," Communications of the ACM, 28, No. 10, pp. 1076-1085.

    Raatikanien (1987), "Simultaneous Estimation of Several Percentiles," Simulation, pp. 159-164.

Applications:
    Data Management
Implementation Date:
    2018/08
Program:
     
    . Purpose:  Demonstrate P-square algorithm for one-pass
    .           estimation of percentiles.
    .
    dimension 40 columns
    read y
     0.02
     0.5
     0.74
     3.39
     0.83
    22.37
    10.15
    15.43
    38.62
    15.92
    34.60
    10.28
     1.47
     0.40
     0.05
    11.39
     0.27
     0.42
     0.09
    11.37
    end of data
    let ny = size y
    .
    . Step 2:   Initializations based on first 2*m + 3 data points.
    .
    let p = data 0.1 0.5 0.9
    let m = size p
    let ninit = 2*m + 3
    let q = y
    retain q for i = 1 1 ninit
    let q = sort q
    let n = sequence 1 1 ninit
    let f = 0 for i = 1 1 ninit
    let f(ninit) = 1
    loop for k = 1 1 m
        let iindx = 2*k + 1
        let f(iindx) = p(k)
    end of loop
    let mp1 = m + 1
    loop for k = 1 1 mp1
        let iindx1 = 2*k - 1
        let iindx2 = 2*k + 1
        let iindx3 = 2*k
        let aval1 = f(iindx1)
        let aval2 = f(iindx2)
        let aval3 = (aval1 + aval2)/2
        let f(iindx3) = aval3
    end of loop
    let d = 1 + 2*(m+1)*f
    .
    . Step 3:   Now loop through remaining points
    .
    let nstrt = ninit + 1
    delete k
    .
    loop for k = nstrt 1 ny
        let ynew = y(k)
        let qmin = q(1)
        let qmax = q(ninit)
        if ynew < q1
           let ak = 1
           let q(1) = ynew
        else if ynew > qmax
           let ak = ninit
           let q(ninit) = qmax
        else
           let val = combine ynew
           let iindx = cell match q val
           let ak = iindx(1)
           delete val iindx
        end of if
        .
        let start = ak + 1
        let n = n + 1 for i = start 1 ninit
        let d = d + f
        .
        let mstop = 2*m + 2
        loop for l = 2 1 mstop
            let lm1 = l - 1
            let lp1 = l + 1
            .
            let aval1  = d(l)
            let aval2  = n(l)
            let di = aval1 - aval2
            .
            let aval1  = n(lp1)
            let dp = aval1 - aval2
            .
            let aval1  = n(lm1)
            let dm = aval1 - aval2
            .
            let aval1 = q(lp1)
            let aval2 = q(l)
            let qp = (aval1 - aval2)/dp
            .
            let aval1 = q(lm1)
            let qm = (aval1 - aval2)/dm
            .
            let nl   = n(l)
            let ql   = q(l)
            let qlm1 = q(lm1)
            let qlp1 = q(lp1)
            .
            if di >= 1 and dp > 1
               let qt = ql + ((1 - dm)*qp + (dp -1)*qm)/(dp-dm)
               if qlm1 < qt and qt < qlp1 then
                  let q(l) = qt
               else
                  let q(l) = ql + qp
               end of if
               let n(l) = nl + 1
            else if di <= 1 and dm < -1
               let qt = ql - ((1 + dp)*qm - (dm +1)*qp)/(dp-dm)
               if qlm1 < qt and qt < qlp1 then
                  let q(l) = qt
               else
                  let q(l) = ql - qm
               end of if
               let n(l) = nl - 1
            end of if
            .
        end of loop
        .
    end of loop
    .
    set write decimals 4
    loop for k = 1 1 m
        let iindx1 = 1 + 2*k
        let aval = q(iindx1)
        let qsave(k) = aval
    end of loop
    print "Estimated 0.10, 0.50, 0.90 quantiles"
    print " "
    print qsave
        
    The following output is returned
     
    Estimated 0.10, 0.50, 0.90 quantiles
     
     
    ---------------
              QSAVE
    ---------------
             0.1324
             2.9317
            19.7914
        

Privacy Policy/Security Notice
Disclaimer | FOIA

NIST is an agency of the U.S. Commerce Department.

Date created: 11/08/2018
Last updated: 11/08/2018

Please email comments on this WWW page to alan.heckert@nist.gov.