-
Notifications
You must be signed in to change notification settings - Fork 0
/
mops.tex
168 lines (133 loc) · 10.9 KB
/
mops.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
\section{Analysis of Moving Object Processing System Performance \label{sec:mops}}
The linking of individual detections from difference images into plausible orbital tracks will be performed using
a special-purpose code referred to as the Moving Object Processing System (MOPS). There are several slightly modified
versions of MOPS in use by various projects; the original version was developed collaboratively by Pan-STARRS
and LSST, and is described in \cite{denneau13}. MOPS employs a two-step processing: first pairs of detections
from a given night are connected into {\it tracklets}, and then at least three tracklets are associated into a
candidate {\it track}. Realistic MOPS simulations show high linking efficiency ($>$99\%; \citealt{denneau13})
across all classes of Solar System objects. The core algorithmic components of MOPS are {\it findTracklets} and
{\it linkTracklets} kd-tree algorithms by \citet{kubica07}. {\it findTracklets} links \DIASources from a single
night to produce {\it tracklets}, and {\it linkTracklets} links tracklets from at least three nights to produce candidate
{\it tracks} (assuming quadratic motion in each coordinate; the LSST version also accounts for topocentric
corrections). Candidate tracks produced by MOPS are then filtered using initial orbital determination (IOD) step,
which is executed using a stand-alone code (e.g. OrbFit, \citealt{milani08}; OpenOrb, \citealt{OpenOrb2009}).
Given the empirically estimated false detection rates expected for LSST, discussed in the preceeding section,
in this section we show that MOPS performance is already adequate - MOPS requires significantly less
computing capacity than planned for other LSST data processing needs. In addition to reporting the results of
numerical experiments with MOPS, we also analyze them using analytic and semi-analytic results for the
rates of false tracklets and false tracks.
\subsection{A Summary of LSST tests of MOPS}
As a part of the Final Design Review preparations, the LSST team has developed an enhanced prototype
implementation of MOPS and analyzed its behavior. Here we summarize the main results of that work;
a detailed internal technical note has been made public in \cite{LDM-156}.
Simulated \DIASources were based on a Solar System model by \citet{Grav2011}.
The model includes about 11 million objects; about 9 million are main-belt asteroids. Observations span
30 days and were selected from a simulated baseline cadence (at that time, the baseline simulation was
OpSim3.61, which in this context is statistically the same as the current baseline cadence, {\it minion\_1016}).
The number of tracklets and tracks, the runtime, and the memory usage were studied as functions of
the false positive detection rate. The rate was varied from none to four times the asteroid detection rate
(100 deg$^{-2}$). The highest rate corresponds to the expected false positive detection rate for LSST
($\rho_{FP} = 400$ deg$^{-2}$).
Tests were run with 16 threads on single 16 CPU node on Gordon cluster at San Diego Supercomputing
Center (in 2011). Due to computational constraints, a $v < 0.5$ deg/day velocity limit for pairing detections
into tracklets was imposed. For similar reasons, the filters that were imposed on track fitting were not
optimized, artificially reducing the yield. As we now understand the algorithmic scalings much better
(see Appendix~\ref{sec:appMOPS}), it is clear that these unoptimized filters have no major impact on the
simulation results and derived conclusions.
As expected, the addition of false detections increases the number of tracklets and tracks,
the runtime, and the memory usage. For the 4:1 false:true detection rate ratio, compared to case with
no false detections, the number of tracklets increases by about
a factor of 10, the number of tracks by about 50\%, and runtime increases by about a factor of 3.
For the 4:1 false:true detection rate ratio, the runtime with 16 CPUs is 33 hours, with maximum memory
usage of about 80 GB.
\begin{figure}[t!]
\centering
\vskip -0.3in
%\includegraphics[width=0.49\textwidth]{figures/tracklet}
%\includegraphics[width=0.49\textwidth]{figures/tracks}
\includegraphics[width=0.95\textwidth]{figures/track_stats}
\caption{A summary of MOPS tests for the dependence of the number of tracklets (left)
and tracks (right) on the false detection rate. As the rate of false detections
increases from none to four times the asteroid detection rate, the number of tracklets
increases by about an order of magnitude. At the same time, the number of candidate
tracks increases by only about 50\%.
\label{fig:MOPStests}}
\end{figure}
\subsection{Understanding MOPS Performance}
The rather slow increase of the number of tracks with false positive detection rate (a 50\% increase
although the number of tracklets increased by a factor of 10) may seem surprising. We have
developed analytic and semi-analytic analysis to better understand the scaling of the number of
tracklets and tracks with false detection rate and other relevant parameters. Details of this
analysis are provided in Appendix~\ref{sec:appMOPS}. Here we briefly discuss the main results.
The increase of the number of tracklets with the false detection rate,
$\rho_{FP}$, shown in left panel in Figure~\ref{fig:MOPStests}, is well
described by eq.~\ref{eq:NttFalse}. In particular, the number of tracklets
approximately increases proportionally to $(C_1 + C_2\rho_{FP}^2)$, where $C_1$
and $C_2$ do not depend on $\rho_{FP}$. As both the full analytic result and the
simulations show, false tracklets quickly outnumber true tracklets even at low
false detection rates, resulting in the observed $\rho_{FP}^2$ behavior.
While the number of tracklets is dominated by the false detections, in the
baseline LSST cadence and the nominal noise assumptions under which the MOPS
simulations were run ($\rho_{FP} \leq 500\,\rm{deg}^{-2}$), the number of
tracks is not dominated by spurious detections---instead it is dominated by true
tracks and mislinkages between true objects. This is due to the fundamental
feature of MOPS: the 4-dimensional space of tracks (two coordinates and two
velocity vector components) is sparse at up to moderate levels of contamination,
and at the tested noise levels false tracklets are effectively filtered out. This
behavior accounts for the slow growth in tracks in the right panel of
Figure~\ref{fig:MOPStests}.
As we evaluate the impact of different survey parameters, we can assess the
number of tracks that would be generated (and thus require IOD processing) using
the analytic results developed in Appendix~\ref{sec:appMOPS}. For a given window
width and false detection density, the number of false tracks per search window
that would arise from false detections is given by
\begin{equation}
\label{eq:falsetracks2}
N^{falsetracks} = 4.5 \times 10^6 \, \left( {N_w \over 30 \, {\rm day} } \right)^{8} \left( {\rho_{FP} \over 400 \, {\rm deg}^{-2} }\right)^{3.7}.
\end{equation}
This expression is valid around fiducial values and assumes $\rho_{ast}=100$ deg$^{-2}$.
The number of true tracks is of the order 10$^6$; therefore, with the baseline
window $N_W=15$ the contribution of false detections is small, while in the
enhanced NEO cadences with $N_W=30$ the contribution is only a factor of a few
times the number of true tracks.
\subsection{Required Computing Resources for MOPS and IOD Processing}
Given the modest computing resources used in MOPS tests described above, the runtime and memory
usage results bode well for LSST processing. Assuming a 1000-core machine dedicated to LSST moving
object processing (corresponding to about 1\% of the anticipated total LSST compute power), MOPS runtime for producing
candidate tracks should not exceed an hour, assuming sufficient parallelization can be achieved.
The IOD step can also be handled with anticipated resources and is trivially parallelizable. The number
of available IOD computations for a compute system with $N_{core}$ cores and allocated runtime $T_{runtime}$
can be expressed as
\begin{equation}
N_{IOD} = 3.6\times10^8 \left({ 0.1\,{\rm sec} \over T_{IOD}}\right) \,
\left({ T_{runtime} \over 10\,{\rm hr} }\right) \,
\left({ N_{core} \over 1000}\right).
\end{equation}
where $T_{IOD}$ is the time it takes to perform one IOD computation on a single core.
To get a handle on a realistic estimate of $T_{IOD}$, we benchmark an implementation provided
by the \FindOrb code\footnote{\FindOrb source code can be found at \url{https://github.com/Bill-Gray/find_orb/}} by Bill Gray.
\FindOrb is an open source orbit determination software written in C++.
It implements several IOD methods (Gauss, Herget, and V\"{a}is\"{a}l\"{a}),
whose precision are representative of other analogous packages in the field.
For benchmarking purposes, we used \FindOrb to fit an orbit of an
$a = 2.46, e = 0.57$ asteroid given six observations (a pair each night)
spanning a 16-day arc. The measurement is performed on a single 3.1 GHz core.
We find that the IOD using the Gauss method takes only 0.3ms to compute, a negligible fraction of
our 100ms computational budget. Running an afterburner with Herget's method
to obtain further differential improvements takes 26ms, still comfortably
within our computational budget.
These numbers leave a significant margin relative to the fiducial value of 100ms adopted here.
They are consistent with anecdotal estimates of JPL's NEO group (not more than 50ms; S. Chesley, priv. comm.). Given that the expected number of candidate tracks to filter using
IOD is well below $10^7$, it should therefore be possible to accomplish the IOD step in well under an hour.
Alternatively, it is plausible that a 100-core machine might be sufficient for LSST moving object
processing (assuming no engineering safety margin).
\subsection{Comparison to \cite{VeresChesley2017mops}\label{sec:mopsVeresChesleyComparison}}
In parallel to the work presented here, \cite{VeresChesley2017mops} have conducted a coordinated but independent evaluation of the linking capabilities using the Pan-STARRS1 variant of MOPS \citep{denneau13}. They perform linking on a three month long simulated LSST dataset and achieve:
\begin{itemize}
\item 93.6\% NEO linking efficiency for $H < 22$,
\item 96\% correct linkages in the derived NEO catalog, with
\item the large majority of false linkages stemming from main belt confusion (that would not arise given a longer simulation), and
\item less than 0.1\% of orbits due to false detections.
\end{itemize}
\cite{VeresChesley2017mops} findings are fully consistent with the results obtained here using the LSST implementation of MOPS. They show that the linking method underlying both implementations is valid and robust. Furthermore, they confirm that IOD is a sufficient filter for admissible tracks.
Adding our empirical measurement of the performance of LSST image differencing pipelines and the performance of LSST's implementation of MOPS, the two studies demonstrate that LSST's approach to asteroid discovery is on firm footing.