Finding Match Sets

Author:: Serge Monkewitz

	Contents
	Lane Subdivision Determining the number of lanes per band Mapping positions (apparitions) to lanes Finding lane windows Finding a match set Lane Walks Finding matches from a single lane Final match set finding algorithm

Lane Subdivision

The problem of finding a match set $M_R(i)$

for an apparition $a_i$

is made efficient by limiting the number of apparitions which are tested for membership.

The specific approach taken by the WAX software is to assign apparitions to small lanes (spatial bins corresponding to a range of declinations and right ascensions), and then determining, given a lane $L_p$ , which other lanes contain apparitions that potentially belong to match sets of apparitions in $L_p$ . For any single apparition, only a tiny area of the sky is examined to find a match set. This is the key to obtaining good performance in the swiss cheese algorithm.

Specifically, each band $B_x$ is split into lanes $L_i$ where $i \in \aleph$ , $0 \leq i < 2^{n}$ and $n \in \aleph$ , $0 \leq n \leq 21$ . Each lane covers a range of right ascensions :

covers right ascensions in the range $[0,\; \delta_r)$
covers right ascensions in the range $[\delta_r,\; 2\delta_r)$
...
$L_{2^n - 1}$ covers right ascensions in the range $[(2^n-1)\delta_r,\; 2^n\delta_r)$

where $\delta_r$ is equal to $2^{1-n}\pi$ radians.

Determining the number of lanes per band

The actual number of lanes in a band is determined by picking a minimum lane width $l$

, defined to be the smallest distance between a position $p_1 \in L_{i-1}$ and $p_2 \in L_{i+1}$ .

Without loss of generality, let $i = 0$ (the angle between unit vectors is invariant under rotation). Furthermore, define $d_m = \max{(|d_x|,|d_{x+1}|)}$ . This minimum distance occurs between the positions $p_1 = (0, d_m)$ and $p_2 = (\delta_r, d_m)$ , expressed in polar coordinates (unless $n = 0, 1$ , in which case this minimum distance is either undefined or zero).

When expressed as vectors in $\Re^3$ , $p_1 = (\cos{d_m}, 0, \sin{d_m})$ and $p_2 = (\cos{d_m}\cos{\delta_r}, \cos{d_m}\sin{\delta_r}, \sin{d_m})$ . Using the relation $l = \arccos{(p_1 \cdot p_2)}$ , the following formula is obtained :

$\cos{l} = \cos^2{d_m}\cos{\delta_r} + \sin^2{d_m}$

To find the number of lanes in a band the actual lane width for each possible value of $\delta_r$ is computed. The number of lanes is determined from the largest $n$ resulting in a lane width greater than the requested minimum, or $0$ if this is impossible. For example, bands containing a pole have a lane width of zero regardless of $n$ and will therefore contain just a single lane. Since this directly effects the efficiency of the match set finding algorithm, the pole bands should be as skinny as possible.

The WAX application uses a minimum lane width of $1$ arcsecond when the -o option is specified, and $10$ arcseconds otherwise.

Mapping positions (apparitions) to lanes

Positions are trivially mapped to lanes: given a right ascension $x$

for a position, the enclosing lane $L_i$

is determined as follows :

$i = \lfloor x\delta_r^{-1} \rfloor$

Once all apparitions in a band have been retrieved and assigned to the appropriate lanes, the apparitions in each lane are sorted in order of increasing declination.

Finding lane windows

Given an arbitrary apparition $a_k \in L_i$ , define the lane window $w_R$

to be the number of lanes $L_{j\bmod{2^n}},\; i < j \leq i + w_R$ which can contain an apparition falling into the match set $M_R(k)$

. Due to rotational symmetry, $w_R$

will be identical for all lanes in a band.

Using the relations derived above, the lane window is the smallest integer $w_R \in [1, 2^{n-1})$ satisfying

$\cos{R} > \cos^2{d_m}\cos{w_R\delta_r} + \sin^2{d_m}$

or $2^{n-1}$ if the relation cannot be satisfied.

Finding a match set

To find a match set for an apparition $a_s$

with position $p_s$

, given a lane window $w_R$

and a search radius $R$

, first find the lane $L_i$

enclosing

. To find all apparitions in the match set $M_R(s)$

, it is sufficient to consider apparitions in lanes $L_{j\bmod{2^n}}$ where $i - w_R \leq j \leq i + w_R$ if $2w_R + 1 < 2^n$

, or $0 \leq j < 2^n$ otherwise.

Furthermore, if the position $p_s$ has a declination $\psi_s$ , then apparitions in the match set $M_R(s)$ will have declinations in the range $[\psi_s - R,\; \psi_s + R]$ . For each $L_j$ being searched, the apparitions in this range can be found using a simple binary search (since apparitions within a lane are declination sorted). Each such apparition $a_k$ is then tested against $p_s$ , and included in $M_R(s)$ if and only if

$\cos{R} \leq p_s \cdot p_k$

Lane Walks

The density pass and swiss cheese pass of the swiss cheese algorithm involve computing match sets for almost all retrieved apparitions and allow freedom in the order in which match sets are found.

Number the apparitions based on their enclosing lane and position within that lane as follows :

$L_i = \{ a_{i0}, a_{i1}, a_{i2}, \ldots \}$

where $a_{ij}$ has declination $\psi_{ij}$ . Since the apparitions in a lane are declination sorted,

$v > u \Leftrightarrow \psi_{iv} \geq \psi_{iu}$

By "walking" up the apparitions within a single lane $L_i$ , finding match sets for $a_{i0}$ , then $a_{i1}$ , etc... the match set finding process can be made even more efficient :

The lanes containing potential members of a match set for $a_{is} \in L_i$ need only be computed once $\forall a_{is} \in L_i$ .
The range of apparitions $[a_{ku}, \ldots, a_{kv}),\; v \geq u$ within declination of $a_{is}$ can be used as a starting point for finding the range of apparitions within declination of $a_{i(s+1)}$ .

This leads to the lane walking algorithm described below.

Finding matches from a single lane

Let

be the lane containing apparitions for which match sets are desired. Let $L_k$

be one of the lanes potentially containing matches for these apparitions.

Consider the first apparition $a_{i0} \in L_i$ . Find the smallest non-negative integer $s$ such that $a_{ks} \in L_k$ has declination $\psi_{ks} \geq \psi_{i0} - R$ (using a binary or linear search).

Now, let $t = s$ . While $\psi_{kt} \leq \psi_{i0} + R$ :

add $a_{kt}$ to the match set for $a_{i0}$ if and only if $\cos{R} \leq p_{i0} \cdot p_{kt}$
increment

At this point, all apparitions in $L_k$ belonging to the match set for $a_{i0}$ have been found, so the next apparition in $L_i$ , $a_{i1}$ is considered. To find the first apparition in $L_k$ possibly belonging to the match set for $a_{i1}$ , increment $s$ until $\psi_{ks} \geq \psi_{i1} - R$ . Then repeat the steps above, finding all apparitions in $L_k$ belonging to the match set for $a_{i1}$ .

Continue in similar fashion until all apparitions in $L_i$ have been considered.

Final match set finding algorithm

The final algorithm for match set finding simply repeats the steps detailed above for each lane potentially containing matches for apparitions in $L_i$

(these are determined using the lane window $w_R$

By walking each lane $L_0, L_1, \ldots$ in this manner, match sets for every apparition in $B_x$ are found.

Generated on Thu Oct 21 13:19:38 2004 for WAX Version 2.1 by

1.3.8