help mata blncdtree

Title

blncdtree() -- Balanced search tree functions used by somersd

Syntax

real matrix
blncdtree(nnode)

void
_blncdtree(tree,
imin,
imax)

tidot =
tidottree(x,
y [ ,
weight [ ,
xcen [ ,
ycen ] ] ] )

tidot =
tidot(x,
y [ ,
weight [ ,
xcen [ ,
ycen ] ] ] )

where

nnode: real scalar
tree: real matrix
imin: real scalar
imax: real scalar
tidot: real colvector
x: real colvector
y: real colvector
weight: real colvector
xcen: real colvector
ycen: real colvector

Description

These functions are used by the somersd package to create balanced
binary search trees and to calculate tidot vectors as defined below
under Remarks. Applications of these functions are discussed in the
file somersd.pdf, which is distributed with the somersd package.

blncdtree(nnode) returns a balanced binary search tree
matrix, representing a balanced binary search tree whose nodes are the
positive integer indices from 1 to nnode. The result is defined as an
nnode x 2 matrix, whose ith row contains, in column 1, the left
daughter index of the index i (or zero if i has no left daughter)
and contains, in column 2, the right daughter index of the index i (or
zero if i has no right daughter). A balanced binary search tree has the
feature that, for any index i, the numbers of indices in the left and
right subtrees of i differ by no more than one. The root node of the
returned balanced binary search tree matrix is the index given by the Mata
expresstion trunc((1+nnode)/2).

_blncdtree(tree, imin, imax) inputs an
existing matrix in tree and reassigns columns 1 and 2 of rows imin
to imax of tree, so that these rows define a balanced binary search
tree whose nodes are the row indices i such that imin <= i <=
imax. The root node of this search tree is the index given by the Mata
expression trunc((imin+imax)/2).
blncdtree() works by calling _blncdtree(), which works by
assigning daughter indices to the root node and then calling itself
recursively to produce left and right subtrees for the root node.
_blncdtree() is a fast program that performs no conformability or
consistency checks, although it will abort if the matrix tree has fewer
than two columns.

tidottree(x, y, weight,
xcen, ycen) inputs a vector of X values in x
and a parallel vector of Y values in y, and, optionally, other
parallel vectors in weight, xcen, and ycen, containing,
respectively, the weights, the censorship indicators for x, and the
censorship indicators for y. A censorship indicator value is interpreted
as implying left-censorship if negative, right-censorship if positive, and
noncensorship if zero. tidottree() assumes that weight is a vector
of ones and that xcen and ycen are vectors of zeros, if these
arguments are not provided by the user. tidottree() returns, as output,
a new vector tidot, parallel to the input vectors, which will contain the
weighted sums of concordance-discordance differences corresponding to the
input vectors, assuming that the data matrix defined by these input vectors is
sorted in ascending order of x. tidottree() performs no
checks that the input data matrix is indeed sorted by x. However,
tidottree() uses a search tree algorithm, which calculates the
tidot values in a time proportional to N*log(N). It
creates the search tree by calling blncdtree().

tidot(x, y, weight, xcen,
ycen) inputs the same vectors as tidottree() and returns the
same output vector tidot, which in this case contains
concordance-discordance totals whether or not the input data matrix is sorted.
However, tidot() does not use the search tree algorithm and therefore
requires a time proportional to the square of N. tidot() is
therefore less efficient than tidottree() for large datasets, even after
accounting for the time taken to sort the dataset before calling
tidottree().

Remarks

The vector tidot calculated by tidottree and tidot is defined
as follows. For scalars u, p, v, and q, define the
function

csign(u,p,v,q)

as 1 if u>v and p>=0>=q, -1 if u<v and
p<=0<=q, and 0 otherwise. For row indices i and j, define

T_ij = csign(x_i,xcen_i,x_j,xcen_j) * csign(y_i,ycen_i,y_j,ycen_j)

as the concordance-discordance difference between rows i and j of the input data vectors.
Then the vector tidot, returned by tidottree or tidot, is defined by

N
tidot_i = Sum weight_j * T_ij
j=1

for each index i. The function tidot() calculates tidot by
calculating all the T_ij and summing them, taking a time
asymptotically proportional to the square of N. The function
tidottree() uses a search tree algorithm to calculate tidot in a
time asymptotically proportional to N*log(N). The
algorithm used by tidottree() is a more advanced version of the one
presented in Newson (2006) and assumes that the input data vectors are sorted
in ascending order of the values of x. tidottree() calls
blncdtree() to create a search tree with one row for each value of
y and uses this search tree to calculate tidot without calculating
the individual T_ij.

Applications of these functions are discussed in the manual somersd.pdf,
which is distributed with the somersd package as an ancillary file.
Balanced binary search trees are discussed in Wirth (1976).

Conformability

blncdtree(nnode):
nnode: 1 x 1

_blncdtree(tree, imin, imax):
tree: M x K where K >= 2
imin: 1 x 1
imax: 1 x 1

tidottree(x, y, weight, xcen, ycen):
x: N x 1
y: N x 1
weight: N x 1
xcen: N x 1
ycen: N x 1

tidot(x, y, weight, xcen, ycen):
x: N x 1
y: N x 1
weight: N x 1
xcen: N x 1
ycen: N x 1

Diagnostics

blncdtree(nnode) aborts with error if nnode < 0.

_blncdtree(tree, imin, imax) aborts with error if cols(tree) < 2.

blncdtree(0) can return a 0 x 2 result.

Source code

blncdtree.mata,
_blncdtree.mata,
tidottree.mata,
tidot.mata

Author

Roger Newson, Imperial College London, UK.

Email: r.newson@imperial.ac.uk

References

Newson, R. 2006.
Efficient calculation of jackknife confidence intervals for rank statistics.
Journal of Statistical Software 15: 1-10.
Download from
the Journal of Statistical Software website.

Wirth, N. 1976.
Algorithms + Data Structures = Programs.
Englewood Cliffs, NJ: Prentice-Hall.

Also see

Manual: [M-0] intro

Online: mata,

somersd (if installed)