text:
\section{Appendix}

\begin{table*}[t]
  \centering
  { \scriptsize
  \begin{tabular}{lrrrrrr}
  \toprule
    Dataset & eurlex-4k & amazoncat-13k & wiki10-31k & wiki-500k & amazon-670k & amazon-3m\\ \midrule
    Dimension ($d$) & 5K & 204K & 102K & 2M & 136K & 337K \\
    Labels ($L$) & 4K & 13K & 31K & 501K & 670K & 3M \\
    Train Data Size & 16K & 1M & 14K & 2M & 490K & 2M \\
    Test Data Size & 4K & 307K & 7K & 784K & 153K & 743K \\ \bottomrule
    \end{tabular}
    }
  \caption{Size statistics for all datasets in our experiments}
  \label{tab:data_stats}

\end{table*}

\begin{table*}[t]
    \centering
    \begin{tabular}{ccc}
    \toprule
        Iteration Method & Per-Query Time Complexity & Extra Memory Overhead \\
        \midrule
        Marching Pointers & $O(\text{nnz}_x + \text{nnz}_K)$ & None \\
        Binary Search & $O(\min(\text{nnz}_x, \text{nnz}_K) \cdot \log(\max(\text{nnz}_x, \text{nnz}_K))$ & None  \\
        Hash-map & $O(h \cdot \text{nnz}_x)$ & $O(c \cdot \text{nnz}_K)$ \\
        Dense Lookup & $O(\text{nnz}_x + \text{nnz}_K / n)$ & $O(d)$
        \\ \bottomrule
    \end{tabular}
    \caption{A chart of the per-query time complexity and memory overhead of all the different iteration methods provided in this section. Here $h$ denotes the time it takes to perform a hash lookup, $c$ denotes the number of chunks, $\text{nnz}_x = |\nzlist{\vc{x}}|$ and $\text{nnz}_K = |\nzlist{\mat{K}}|$.}
    \label{tab:complexity}
\end{table*}

\begin{algorithm}[H]
   \caption{Sparse Vector Inner Product}
   \label{alg:sparsevectorinnerprod}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} Sparse vectors $\vc{x} \in \Rn{d}$ and $\vc{y} \in \Rn{d}$
   \STATE {\bfseries Output:} The value of $\vc{x} \cdot \vc{y}$
   \STATE Initialize result variable: $z \gets 0$.
   \STATE Initialize nonzero entry indices: $i_x \gets 0$ and $i_y \gets 0$
   \STATE \emph{Note}: For vector $\star$, $\nzlist{\star}$ denotes the array of indices of nonzeros in $\star$
   \STATE \emph{Note}: The $\text{LowerBound}(L, i)$ function finds the index of the first element in list $L$ that is not less than $i$.
   \REPEAT
   \STATE Get index of $i_x$-th nonzero in $\vc{x}$: $j_x \gets \nzlist{\vc{x}}[i_x]$
   \STATE Get index of $i_y$-th nonzero in $\vc{y}$: $j_y \gets \nzlist{\vc{y}}[i_y]$
   \IF{Collision check: $j_x = j_y$}
   \STATE $z \gets z + x_{j_x} \vc{y}_{j_y}$
   \STATE Increment $i_x$ and $i_y$.
   \ELSIF{$j_x < j_y$}
   \STATE Advance $i_x$: $i_x \gets \text{LowerBound}(\nzlist{\vc{x}}, j_y)$
   \ELSIF{$j_y < j_x$}
   \STATE Advance $i_y$: $i_y \gets \text{LowerBound}(\nzlist{\vc{y}}, j_x)$
   \ENDIF
   \UNTIL{$i_x = \text{Length}(\nzlist{\vc{x}})$ and $i_y = \text{Length}(\nzlist{\vc{y}})$}
   \STATE {\bfseries return} $z$
\end{algorithmic}
\end{algorithm}

\subsection{Selecting an Iteration Method} \label{sec:selectingmethod}

Using the results of the performance benchmark, as well as the contents of \Cref{tab:complexity}, we briefly provide a guide to choosing a version of the MSCM technique that performs well in a given setting. We always recommend using MSCM, and we suggest that the user consider their choice of iteration scheme in the following order:

\begin{enumerate}
  \item \textbf{Dense Lookup MSCM}: Use this when batch sizes are sufficiently large and storing a dense vector of feature dimension $d$ is not an issue. Conversely, when the batch size is small (i.e., online settings), we don't recommend using dense lookup.
  \item \textbf{Hash-map MSCM}: We recommend using this technique when the queries are significantly sparser than the MSCM chunks. However, this technique typically requires some memory overhead (in our implementation around 40\% additional memory), because a hash-map of nonzero rows must be stored for every chunk.
  \item \textbf{Binary Search MSCM}: We recommend using this if the extra memory requirements of hash-map MSCM are too demanding, as this seems to be a good alternative to hash-maps with only a slight loss in performance, according to our benchmarks. Also, we recommend using this if the weight matrices are significantly sparser than the queries.
  \item \textbf{Marching Pointers MSCM}: We have not found any situations in our data where this outperforms the above two. However, there may be hypothetical cases where marching pointers can perform better than hash-maps or binary search. For example, if queries and chunks are equally sparse, then marching pointers could have the best complexity.
\end{enumerate}

\section{Conclusion} \label{sec:conclusion}

In this paper, we have presented the MSCM technique for accelerating inference for sparse XMR tree models. MSCM leverages the structure of the inference sparsity pattern to mitigate unnecessary traversal and improve memory locality. MSCM also comes \textbf{free-of-charge} as it exactly preserves inference results, and only requires modest changes to an existing inference pipeline. Moreover, we have examined different variations of the MSCM technique to compile guidelines for extracting the optimal performance. We believe that this technique will allow practitioners to save a substantial amount of compute resources in their inference pipelines, in both online and offline prediction settings. We have already implemented it into our production pipeline and have been very pleased with the low latency our method enables, as demonstrated in \cref{sec:enterprise}.

For future work, another avenue for optimization comes from the observation that a substantial part of our performance boost comes from sorting vector times chunk products by chunk id --- thus better localizing our computation in memory space. It is possible reordering the queries in order to achieve a similar effect. We briefly investigated this, but were unable to obtain a performance boost in our exploration. Further, our exploration of MSCM techniques is not exhaustive, there may be additional ways to iterate through the intersection of query and chunk supports.

As for limitations of the work presented herein, we note that our technique explicitly requires that the XMR tree is composed of linear rankers --- which means our method is not directly applicable to models that use nonlinear based rankers, such as neural networks. However, since most neural network architectures are repeated compositions of linear transformations and activation functions, our technique may be applicable in sparse settings. Also, we note that our technique as presented here is designed to run on the CPU, and one might gain additional performance by investigating GPU-based implementations.
\section{Benchmarks} \label{sec:eval}

To evaluate the extent to which the MSCM technique improves performance, we put all of the above variations of MSCM through a series of benchmarks on a set of models that we trained on six publicly available datasets \cite{Bhatia16}. We ran all benchmarks in this paper on both a reserved \textbf{r5.4xlarge} AWS instance and a reserved \textbf{m5.8xlarge} AWS instance. Results were consistent across both instance types, so in the interest of space, we will present only the \textbf{r5.4xlarge} results here, \textbf{m5.8xlarge} are provided in our benchmark repository.\footnote{https://github.com/UniqueUpToPermutation/pecos/tree/benchmark} The following subsection discusses single-threaded results, while \Cref{sec:parallel} discusses multi-threaded results.

For each dataset, we trained multiple models with a term frequency-inverse document frequency (TFIDF) word embedding and positive instance feature aggregation (PIFA) for label representations (see \cite{anonymous} for more details). In our results we present benchmarks for models constructed with tree branching factors of 2, 8, and 32 to cover a broad swath of performance under different model meta-parameter choices. Furthermore, we ran each of our methods in both the batch setting, where we pass all the queries to the model at the same time as a single matrix, as well as the online setting, where we pass the queries to the model individually one-by-one for evaluation. Both of these settings represent different use cases in industry and we believe it is important for our technique to work well in both settings.
For each choice of model branching factor, setting, dataset, and iteration method (i.e., marching pointers, binary search, hash, dense lookup), we run the inference computation \emph{with MSCM} and \emph{without MSCM} and record the wall-times and the relative speedup that MSCM provides.

For each iteration method, we present the wall-time ratio between an MSCM implementation using that iteration method and a baseline vector-dot-product implementation using that same iteration method. In the vector-dot-product baseline, all entries of the required masked matrix product are computed by taking the inner product between respective rows and columns in the two matrices that form the product.

The results of our benchmarks can be seen in tabular form in \Cref{tab:time_split2}, \Cref{tab:time_split8}, and \Cref{tab:time_split32}. We also provide a visual graph of the inference times relative to our baseline in \Cref{fig:inftime2} and \Cref{fig:inftime3}.

\iffalse
\subsection{Performance Against  \textsc{Parabel}} \label{sec:parabelcomp}

To provide an apples-to-apples comparison of our inference method against already existing inference methods, we converted a \textsc{Parabel} \cite{prabhu2018parabel} model into our framework so that we could directly compare the performance of our code against that of Parabel. The results

\begin{table*}
  \centering
  \begin{tabular}{lllllll}
    \toprule
     & eurlex-4k & amazoncat-13k & wiki10-31k & wiki-500k & amazon-670k & amazon-3m \\
    \midrule
    \midrule
    \textsc{Parabel} \cite{prabhu2018parabel} & 0.761 ms & 0.388 ms & 1.40 ms & 1.90 ms &  0.471 ms & 0.411 ms \\
    \midrule
    \textsc{\textsc{PECOS}}  \textsc{Parabel} & 0.815 ms & 0.469 ms & 1.52 ms & 2.36 ms & 0.681 ms & 0.633 ms \\
    \textsc{\textsc{PECOS}}  \textsc{Parabel} + MCSM & 0.349 ms  & 0.283 ms & 0.982 ms & 2.85 ms & 0.358 ms & 0.363 ms \\
    \bottomrule
  \end{tabular}
  \caption{Inference time per query in both the batch and online settings. The performance results were run on models trained with a branching factor of 32. (*) denotes that the benchmark did not terminate running within four days and therefore had to be terminated early. \todo{Change this description. Make clear that this }}
  \label{tab:parabelcomparison}
\end{table*}
\fi

\begin{table*}[p]
  \centering
  { \scriptsize
  \begin{tabular}{lrrrrrr}
    \toprule
      Branching Factor: 2 & amazon-3m & amazon-670k & amazoncat-13k & eurlex-4k & wiki-500k & wiki10-31k \\
    \midrule
    \midrule
    \textbf{Batch} & & & & & & \\ \hdashline
    Binary Search MSCM      & 0.83 \text{ ms} & 0.69 \text{ ms} & 0.45 \text{ ms} & 0.55 \text{ ms} & 3.46 \text{ ms} & 2.69 \text{ ms} \\
    Binary Search           & 2.83 \text{ ms} & 2.02 \text{ ms} & 2.24 \text{ ms} & 2.55 \text{ ms} & 8.75  \text{ ms} & 7.79 \text{ ms} \\ \hdashline
    Dense Lookup MSCM       & 0.43 \text{ ms} & 0.20 \text{ ms} & 0.14 \text{ ms} & 0.18 \text{ ms} & 1.34 \text{ ms} & 0.62 \text{ ms} \\
    Dense Lookup            & 0.82 \text{ ms} & 0.36 \text{ ms} & 0.28 \text{ ms} & 0.49 \text{ ms} & 1.44 \text{ ms} & 1.18 \text{ ms} \\ \hdashline
    Hash MSCM               & 0.49 \text{ ms} & 0.29 \text{ ms} & 0.19 \text{ ms} & 0.25 \text{ ms} & 1.41 \text{ ms} & 0.99 \text{ ms} \\
    Hash                    & 1.26 \text{ ms} & 0.83 \text{ ms} & 0.60 \text{ ms} & 1.34 \text{ ms} & 3.15 \text{ ms} & 3.44 \text{ ms} \\ \hdashline
    Marching Pointers MSCM  & 7.78 \text{ ms} & 2.62 \text{ ms} & 2.88 \text{ ms} & 0.49 \text{ ms} & 16.00 \text{ ms} & 2.13 \text{ ms} \\
    Marching Pointers       & 13.20 \text{ ms} & 4.65 \text{ ms} & 6.31 \text{ ms} & 1.85 \text{ ms} & 24.40 \text{ ms} & 5.40 \text{ ms} \\
    \midrule
    \textbf{Online} & & & & & & \\ \hdashline
Binary Search MSCM      & 1.91 \text{ ms} & 1.33 \text{ ms} & 0.95 \text{ ms} & 0.64 \text{ ms} & 7.07 \text{ ms} & 3.27 \text{ ms} \\
Binary Search           & 4.62 \text{ ms} & 2.72 \text{ ms} & 3.16 \text{ ms} & 2.62 \text{ ms} & 12.90 \text{ ms} & 8.06 \text{ ms} \\  \hdashline
Dense Lookup MSCM       & 17.10 \text{ ms} & 4.45 \text{ ms} & 4.87 \text{ ms} & 0.77 \text{ ms} & 74.70 \text{ ms} & 3.04 \text{ ms} \\
Dense Lookup            & 9.10 \text{ ms} & 6.26 \text{ ms} & 10.10 \text{ ms} & 1.37 \text{ ms} & 112.00 \text{ ms} & 4.13 \text{ ms} \\  \hdashline
Hash MSCM               & 1.81 \text{ ms} & 1.32 \text{ ms} & 0.88 \text{ ms} & 0.42 \text{ ms} & 6.20 \text{ ms} & 2.57 \text{ ms} \\
Hash                    & 2.44 \text{ ms} & 1.82 \text{ ms} & 1.62 \text{ ms} & 1.73 \text{ ms} & 7.12 \text{ ms} & 5.43 \text{ ms} \\  \hdashline
Marching Pointers MSCM  & 9.10 \text{ ms} & 3.54 \text{ ms} & 3.52 \text{ ms} & 0.58 \text{ ms} & 20.40 \text{ ms} & 3.12 \text{ ms} \\
Marching Pointers       & 14.80 \text{ ms} & 5.48 \text{ ms} & 7.37 \text{ ms} & 1.88 \text{ ms} & 28.20 \text{ ms} & 5.67 \text{ ms} \\
    \bottomrule
  \end{tabular}
  }
  \caption{Inference time per query in both the batch and online settings. The performance results were run on an \textbf{r5.4xlarge} AWS instance, on models trained with a branching factor of 2. For the online results, we test only a random subset of the test data of size 10,000.}
  \label{tab:time_split2}
\end{table*}

\begin{table*}[p]
   \centering
   { \scriptsize
   \begin{tabular}{lrrrrrr}
     \toprule
       Branching Factor: 8 & amazon-3m & amazon-670k & amazoncat-13k & eurlex-4k & wiki-500k & wiki10-31k \\
     \midrule
    \midrule
    \textbf{Batch} & & & & & & \\ \hdashline
   Binary Search MSCM      & 0.43 \text{ ms} & 0.34 \text{ ms} & 0.23 \text{ ms} & 0.29 \text{ ms} & 1.67 \text{ ms} & 1.23 \text{ ms} \\
Binary Search           & 3.01 \text{ ms} & 2.20 \text{ ms} & 2.22 \text{ ms} & 2.52 \text{ ms} & 9.73 \text{ ms} & 8.16 \text{ ms} \\ \hdashline
Dense Lookup MSCM       & 0.32 \text{ ms} & 0.16 \text{ ms} & 0.11 \text{ ms} & 0.13 \text{ ms} & 0.83 \text{ ms} & 0.41 \text{ ms} \\
Dense Lookup            & 0.84 \text{ ms} & 0.38 \text{ ms} & 0.28 \text{ ms} & 0.48 \text{ ms} & 1.54 \text{ ms} & 1.21 \text{ ms} \\ \hdashline
Hash MSCM               & 0.33 \text{ ms} & 0.19 \text{ ms} & 0.13 \text{ ms} & 0.16 \text{ ms} & 0.87 \text{ ms} & 0.60 \text{ ms} \\
Hash                    & 1.31 \text{ ms} & 0.87 \text{ ms} & 0.60 \text{ ms} & 1.33 \text{ ms} & 3.36 \text{ ms} & 3.57 \text{ ms} \\ \hdashline
Marching Pointers MSCM  & 3.41 \text{ ms} & 1.34 \text{ ms} & 1.48 \text{ ms} & 0.28 \text{ ms} & 10.10 \text{ ms} & 1.24 \text{ ms} \\
Marching Pointers       & 15.50 \text{ ms} & 5.14 \text{ ms} & 6.35 \text{ ms} & 1.84 \text{ ms} & 26.20 \text{ ms} & 5.79 \text{ ms} \\
    \midrule
    \textbf{Online} & & & & & & \\ \hdashline
Binary Search MSCM      & 0.83 \text{ ms} & 0.59 \text{ ms} & 0.43 \text{ ms} & 0.33 \text{ ms} & 3.25 \text{ ms} & 1.49 \text{ ms} \\
Binary Search           & 4.71 \text{ ms} & 2.76 \text{ ms} & 3.03 \text{ ms} & 2.57 \text{ ms} & 14.00 \text{ ms} & 8.31 \text{ ms} \\ \hdashline
Dense Lookup MSCM       & 6.23 \text{ ms} & 2.04 \text{ ms} & 2.18 \text{ ms} & 0.43 \text{ ms} & 33.60 \text{ ms} & 1.68 \text{ ms} \\
Dense Lookup            & 32.70 \text{ ms} & 6.57 \text{ ms} & 9.32 \text{ ms} & 1.27 \text{ ms} & 109.00 \text{ ms} & 4.28 \text{ ms} \\ \hdashline
Hash MSCM               & 0.79 \text{ ms} & 0.60 \text{ ms} & 0.40 \text{ ms} & 0.24 \text{ ms} & 2.88 \text{ ms} & 1.27 \text{ ms} \\
Hash                    & 2.55 \text{ ms} & 1.89 \text{ ms} & 1.58 \text{ ms} & 1.68 \text{ ms} & 7.77 \text{ ms} & 5.48 \text{ ms} \\ \hdashline
Marching Pointers MSCM  & 3.81 \text{ ms} & 1.69 \text{ ms} & 1.71 \text{ ms} & 0.32 \text{ ms} & 11.90 \text{ ms} & 1.70 \text{ ms} \\
Marching Pointers       & 17.30 \text{ ms} & 5.93 \text{ ms} & 7.35 \text{ ms} & 1.84 \text{ ms} & 30.30 \text{ ms} & 5.96 \text{ ms} \\
    \bottomrule
   \end{tabular}
   }
   \caption{Inference time per query in both the batch and online settings. The performance results were run on an \textbf{r5.4xlarge} AWS instance, on models trained with a branching factor of 8. For the online results, we test only a random subset of the test data of size 10,000.}
   \label{tab:time_split8}
 \end{table*}

 \begin{table*}[p]
   \centering
   { \scriptsize
   \begin{tabular}{lrrrrrr}
     \toprule
       Branching Factor: 32 & amazon-3m & amazon-670k & amazoncat-13k & eurlex-4k & wiki-500k & wiki10-31k \\
     \midrule
    \midrule
    \textbf{Batch} & & & & & & \\ \hdashline
   Binary Search MSCM      & 0.38 \text{ ms} & 0.29 \text{ ms} & 0.21 \text{ ms} & 0.21 \text{ ms} & 1.44 \text{ ms} & 0.95 \text{ ms} \\
Binary Search           & 4.28 \text{ ms} & 3.60 \text{ ms} & 2.88 \text{ ms} & 2.45 \text{ ms} & 16.40 \text{ ms} & 11.60 \text{ ms} \\ \hdashline
Dense Lookup MSCM       & 0.32 \text{ ms} & 0.18 \text{ ms} & 0.12 \text{ ms} & 0.11 \text{ ms} & 0.77 \text{ ms} & 0.37 \text{ ms} \\
Dense Lookup            & 0.93 \text{ ms} & 0.54 \text{ ms} & 0.36 \text{ ms} & 0.47 \text{ ms} & 2.34 \text{ ms} & 1.69 \text{ ms} \\ \hdashline
Hash MSCM               & 0.33 \text{ ms} & 0.20 \text{ ms} & 0.14 \text{ ms} & 0.13 \text{ ms} & 0.84 \text{ ms} & 0.53 \text{ ms} \\
Hash                    & 1.64 \text{ ms} & 1.19 \text{ ms} & 0.76 \text{ ms} & 1.32 \text{ ms} & 5.04 \text{ ms} & 4.41 \text{ ms} \\ \hdashline
Marching Pointers MSCM  & 2.07 \text{ ms} & 1.06 \text{ ms} & 1.25 \text{ ms} & 0.21 \text{ ms} & 8.78 \text{ ms} & 1.01 \text{ ms} \\
Marching Pointers       & 20.00 \text{ ms} & 8.03 \text{ ms} & 8.44 \text{ ms} & 1.78 \text{ ms} & 36.80 \text{ ms} & 7.42 \text{ ms} \\
    \midrule
    \textbf{Online} & & & & & & \\ \hdashline
    Binary Search MSCM      & 0.69 \text{ ms} & 0.51 \text{ ms} & 0.37 \text{ ms} & 0.25 \text{ ms} & 2.70 \text{ ms} & 1.18 \text{ ms} \\
Binary Search           & 7.06 \text{ ms} & 4.40 \text{ ms} & 3.81 \text{ ms} & 2.51 \text{ ms} & 23.10 \text{ ms} & 11.70 \text{ ms} \\ \hdashline
Dense Lookup MSCM       & 3.57 \text{ ms} & 1.55 \text{ ms} & 1.84 \text{ ms} & 0.33 \text{ ms} & 23.50 \text{ ms} & 1.35 \text{ ms} \\
Dense Lookup            & 44.60 \text{ ms} & 10.70 \text{ ms} & 17.00 \text{ ms} & 1.20 \text{ ms} & 175.00 \text{ ms} & 5.77 \text{ ms} \\ \hdashline
Hash MSCM               & 0.61 \text{ ms} & 0.48 \text{ ms} & 0.33 \text{ ms} & 0.20 \text{ ms} & 2.26 \text{ ms} & 1.06 \text{ ms} \\
Hash                    & 3.59 \text{ ms} & 2.80 \text{ ms} & 1.93 \text{ ms} & 1.63 \text{ ms} & 12.60 \text{ ms} & 7.10 \text{ ms} \\ \hdashline
Marching Pointers MSCM  & 2.30 \text{ ms} & 1.28 \text{ ms} & 1.41 \text{ ms} & 0.25 \text{ ms} & 9.98 \text{ ms} & 1.30 \text{ ms} \\
Marching Pointers       & 22.60 \text{ ms} & 9.23 \text{ ms} & 9.66 \text{ ms} & 1.78 \text{ ms} & 43.50 \text{ ms} & 7.61 \text{ ms} \\
    \bottomrule
   \end{tabular}
   }
   \caption{Inference time per query in both the batch and online settings. The performance results were run on an \textbf{r5.4xlarge} AWS instance, on models trained with a branching factor of 32. For the online results, we test only a random subset of the test data of size 10,000.}
   \label{tab:time_split32}
 \end{table*}

\subsection{Discussion}

It is evident from the results in Tables~\ref{tab:time_split2}, \ref{tab:time_split8}, \ref{tab:time_split32} and Figures~\ref{fig:inftime2} and \ref{fig:inftime3} that the MSCM technique provides a substantial acceleration to any baseline inference technique. Moreover, in the batch setting with a single thread, we observe that chunked matrices with dense lookup always perform faster than every other technique, regardless of dataset or tree topology. Moreover, this speed boost grows more substantial as the branching factor of the model grows. This matches our expectations, because larger branching factors allow the chunked methods to shave off more of the unnecessary traversal costs and cache misses of the unchunked methods.

In online mode, there is no longer always a clear winner in the performance benchmarks, but it seems that hash-map chunked matrices usually provide optimal or near-optimal performance among the algorithms that we have tested here, although there is more individual variation among the results than in the batch setting. We note that the dense lookup methods tend to perform worse in this setting because the cost of loading a hash-map into a dense vector is no longer amortized across a large number of queries. Furthermore, we also note that, as one would expect, larger branching factors give a more substantial performance increase. These performance gains persist in multi-threaded environments, see \cref{sec:parallel} for details about multi-threaded performance.

From these results, we can conclude that it is \emph{always} beneficial to use a chunked MSCM matrix format over a column-by-column (e.g., CSC) format for the weight matrix.

\subsection{Performance Comparison versus NapkinXC}

To help compare the performance of our code-base with MSCM implemented against other state of the art code-bases, we have implemented a direct comparison with NapkinX \cite{jasinska2020probabilistic}. We built a script that converts models in our format to models in NapkinXC's format, allowing us to do an apples-to-apples comparison with an external implementation. We can see in \cref{fig:napkinxc} that we substantially outperform NapkinXC by a margin of $\sim10 \times$ on every dataset. Our conversion script is accessible at \url{https://github.com/UniqueUpToPermutation/PECOStoNapkinXC}.

\begin{figure}
    \centering
    \includegraphics[width=2.5in]{images/charts/NapkinXC.pdf}
    \caption{A direct performance comparison between our inference code's performance (with MSCM) to a reference implementation (NapkinXC \cite{jasinska2020probabilistic}). Both implementation use the hash iteration scheme. We see that MSCM enables a nearly $10\times$ performance gain over NapkinXC.}
    \label{fig:napkinxc}
\end{figure}

\section{ Enterprise-Scale Performance} \label{sec:enterprise}

\begin{table*}[t]
  \centering
  { \small
  \begin{tabular}{l c c c}
    \toprule
      Iteration Method & Average Time (ms/query) & P95 Time (ms/query) & P99 Time (ms/query) \\
      \midrule
      \textit{Beam Size: 10} & \\
      \hdashline
      Binary Search MSCM & 0.88 &	1.20 &	1.42 \\
      Hash-map MSCM & 0.96	& 1.38	& 1.62 \\
      Binary Search & 7.28	& 10.56	& 12.78 \\
       \midrule
      \textit{Beam Size: 20} &  \\
      \hdashline
      Binary Search MSCM & 1.63	& 2.23	& 2.63	\\
      Hash-map MSCM & 1.80 &	2.60 &	3.06	\\
      Binary Search & 14.32 &	20.68 &	24.81	\\
       \bottomrule \\
  \end{tabular}
  }
  \caption{Performance results on an enterprise-scale semantic search model with 100 million labels in batch mode using a single thread on an \textbf{X1} AWS instance. The model's branching factor is 32. Dense lookup is not compared due to out of memory issue.} \label{tab:enterprise}
\end{table*}

To end our discussion of the performance benefits of MSCM, we deploy our MSCM method on an enterprise-scale semantic search model with $L=100$ million labels (products) and a feature dimension of $d=4$ million. We see that with beam size $10$, both binary search and hash-map MSCM deliver sub-millisecond latency per query on this exceedingly large search problem on 100 million products --- a more than $8\times$ reduction in average and P95/P99 inference times compared to vanilla binary search algorithms. In particular, binary search MSCM with beam size 10 has average inference time of 0.884 ms while binary search without MSCM needs 7.282 ms. In terms of P99 latency, binary search MSCM gains more over binary search without MSCM --- 1.416 ms vs 12.781 ms. More performance results are provided in \Cref{tab:enterprise} in the Appendix.

\subsection{Multi-Threaded MSCM}\label{sec:parallel}

\begin{figure*}
    \centering
    \includegraphics[width=2.1in]{images/charts/r5-multi-amazon-3m.pdf}
    \includegraphics[width=2.1in]{images/charts/r5-multi-amazon-670k.pdf}
    \includegraphics[width=2.1in]{images/charts/r5-multi-wiki-500k.pdf}
    \caption{A figure demonstrating the easy parallelization of MSCM. We see that the relative speed-up across different numbers of threads is consistent.}
    \label{fig:multithread}
\end{figure*}

One of the benefits of binary search and hash-map MSCM techniques is that batch processing is embarrassingly parallelizable. Indeed, for binary search and hash-map MSCM, one can simply distribute all of the row-chunk operations in line (7) of \Cref{alg:sparsevectorchunkprod} across many different threads with a library like OpenMP, and no substantial additional work or synchronization is required. Dense lookup (both the baseline and MSCM variants) is harder to parallelize because each thread requires its own dense lookup; moreover, we observe that the performance of dense lookup and its MSCM variant are not competitive when parallelized, due to these subtleties that arise in implementation. Since there are no alternative parallel dense lookup tree-based XMR methods available at time of writing (\textsc{Parabel} and \textsc{Bonsai} do not offer parallelization at this level of granularity), we leave this as possible future work and focus on binary search and hash-map MSCM.

We present the results of parallelizing MSCM in \Cref{fig:multithread}, which clearly shows the performance benefits of MSCM clearly extend into the multi-threaded regime. In each of our three tests on \textsc{wiki-500k}, \textsc{amazon-670k}, and \textsc{amazon-3m}, both binary search and hash-map MSCM are significantly faster than their non-MSCM counterparts.
\section{Introduction}
\label{sec:intro}

Tree-based models are the workhorse of many modern search engines and recommender systems \cite{jasinska2020probabilistic, pecos2020,prabhu2018parabel,khandagale2020bonsai, wydmuch2018no, you2019attentionxml, pecos_semantic_kdd_2021}. Nonetheless, performing inference with these models on the scale demanded by modern applications quickly becomes intractable, requiring an unacceptable amount of compute time and memory to generate useful results. It is no surprise, then, that engineers devote a considerable amount of energy to optimizing their tree-based inference pipelines.

In the interest of pursuing tractable computation for practical applications, we dedicate this paper to examining how to make eXtreme Multi-label Ranking (XMR) and eXtreme Multi-label Classification (XMC)\footnotemark[1]\footnotetext[1]{We consider XMC as a subset of XMR. Everything in this paper regarding XMR applies equally well to XMC.} more time and memory efficient. In particular, we propose herein a set of optimizations for sparse XMR tree models that can drastically accelerate inference speed.

Most XMR tree models use a form of beam search to make inference tractable; the core idea of our optimizations is to take full advantage of the sparsity structure of this beam search to improve performance. This key idea manifests in our principal contribution, \emph{Masked Sparse Chunk Multiplication} (MSCM). MSCM is a new matrix data structure and accompanying multiplication algorithm that uses the aforementioned structured sparsity to drastically reduce unnecessary traversal and cache misses in the underlying memory. We observe that this technique can improve inference time usually anywhere from 2 to 20 times over vanilla inference.

The data structures and algorithms presented herein generalize to many different types of linear XMR tree models. In our performance benchmarks, we present an in-depth exploration of many variations of this technique implemented on top of our generic linear XMR tree implementation.

We now quickly outline this paper: in \Cref{sec:rel_work}, we describe previous related work in the literature. In \Cref{sec:pecos}, we give an overview of a generic XMR tree model. \Cref{sec:ourmethod} includes all the details of our contribution to the literature. We present our performance benchmarks and evaluation in \Cref{sec:eval}. In our benchmarks, we compare the results of our methods to a baseline implementation without MSCM --- and demonstrate substantial improvements across a massive range of different settings, i.e., tree topologies, datasets, thread count, etc. We give advice on maximizing performance gain from MSCM in \Cref{sec:selectingmethod}. To demonstrate the usefulness of our method in an industrial setting, in \Cref{sec:enterprise} we apply our methods to an enterprise-scale semantic product search problem with 100 million products and use MSCM to achieve a sub-millisecond latency of 0.83 ms per query on a single thread --- an 8x improvement over the baseline. Finally, we conclude our study in \Cref{sec:conclusion}.

\section{XMR Tree Models}\label{sec:pecos}

In this section, we present a generic formulation of the tree model for eXtreme Multi-label Ranking (XMR) problems. To provide the necessary context, we will give a brief overview of the inference algorithm. We omit training details because they are not directly relevant to the techniques in this paper once a model is trained; but we recommend that readers see any of the aforementioned XMR tree model papers e.g. \cite{prabhu2018parabel, khandagale2020bonsai, pecos2020} for an overview of training.

\subsection{Overview} \label{sec:pecos_overview}

An XMR problem can be characterized as follows: given a query $\vc{x}$ from some embedding $\Rn{d}$ and a set of labels $\mathcal{Y}$, produce a model that gives an (implicit) ranking of the relevance of the labels in $\mathcal{Y}$ to query $\vc{x}$. In addition, for any query $\vc{x} \in \mathcal{X}$, one must be able to efficiently retrieve the top $k$ most relevant labels in $\mathcal{Y}$ according to the model --- noting that $d$ is typically very large and $\vc{x}$ very sparse.

\begin{figure}
\begin{center}
\includegraphics[scale=0.25]{images/pecos/bisection-clustering.pdf}
\caption{A diagram of the structure of an XMR tree model. \cite{pecos2020}} \label{fig:pecosstruct}
\end{center}
\end{figure}

\begin{algorithm}
{ \scriptsize
   \caption{Linear XMR Tree Inference}
   \label{alg:batchinference}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} Query matrix $\mat{X} \in \Rn{n \times d}$.
   \STATE {\bfseries Output:} Beamed predictions $\tilde{\mat{P}} \in \Rn{n \times L}$.
   \STATE Initialize $1$st layer predictions to $1$: $\beamedpredmatrixat{1} = \mat{1} \in \Rn{n \times 1}$.
  \FOR{$l \in \{2, 3, ..., \text{depth} \}$}
  \STATE Copy previous layer predictions:
  $\beamedpredmatrixat{l} \gets \beamedpredmatrixat{l - 1} {\clusterindat{l - 1}}^T\,.$
  \STATE Get computation mask: $\maskmatrixat{l} \gets \text{bool}(\beamedpredmatrixat{l} \neq 0)$.
    \STATE Conditional prediction step: $\condpredmatrixat{l} \gets \sigma(\maskmatrixat{l} \odot (\mat{X} \weightmatrixat{l}))$.
  \STATE Combine with prev. layers: $\beamedpredmatrixat{l} \gets \condpredmatrixat{l} \odot \beamedpredmatrixat{l - 1}$.
  \STATE Beam search by selecting top $b$ entries of each row:
  $\beamedpredmatrixat{l} \gets \text{SelectTop}_b(\beamedpredmatrixat{l}) \,.$
  \ENDFOR
   \STATE {\bfseries return} $\tilde{\mat{P}} = \beamedpredmatrixat{\text{depth}}$
\end{algorithmic}
}
\end{algorithm}

A linear XMR tree model is a hierarchical linear model that constructs a hierarchical clustering of the labels $\mathcal{Y}$, forming a tree structure. These clusters are denoted $\cluster{l}{i}$, where $l$ denotes the depth (i.e., layer) of $\cluster{l}{i}$ in the model tree and $i$ denotes the index of $\cluster{l}{i}$ in that layer, see \Cref{fig:pecosstruct}. The leaves of the tree are the individual labels of $\mathcal{Y}$.

Every layer of the model has a ranker model that scores the relevance of a cluster $\cluster{l}{i}$ to a query $\vc{x} \in \mathcal{X}$. This ranker model may take on different forms, but for this paper we assume that the model is logistic-like. This means that, at the second layer, for example, the relevance of a cluster $\cluster{2}{i}$ is given by
\begin{equation}
f(\vc{x}, \cluster{2}{i}) = \sigma\left({\weightfull{2}{i}} \cdot \vc{x} \right) \,,
\end{equation}
where $\sigma$ denotes an activation function (e.g., sigmoid) and $\weightfull{2}{i} \in \Rn{d}$ denotes a very sparse vector of weight parameters.

At subsequent layers, rankers are composed with those of previous layers, mimicking the notion of conditional probability; hence the score of a cluster $\tilde{\mathcal{Y}} \subset \mathcal{Y}$ is defined by the model as
\begin{equation} \label{eq:defmodel}
f(\vc{x}, \tilde{\mathcal{Y}}) = \prod_{\vc{w} \in \mathcal{A}(\tilde{\mathcal{Y}})} \sigma \left( \vc{w} \cdot \vc{x} \right) \,,
\end{equation}
where $\mathcal{A}(\tilde{\mathcal{Y}}) = \{ \weightfull{l}{i} \mid \tilde{\mathcal{Y}} \subset \cluster{l}{i}, l \neq 1 \}$ denotes all tree nodes on the path from $\tilde{\mathcal{Y}}$ to the root $\mathcal{Y}$ (including $\tilde{\mathcal{Y}}$ and excluding $\mathcal{Y}$). Naturally, this definition extends all the way to the individual labels $\ell \in \mathcal{Y}$ at the bottom of the tree. We assume here for simplicity that the leaves of the tree all occur on the same layer, but the techniques described in this paper can be extended to the general case.

As a practical aside, the column weight vectors $\weightfull{l}{i}$ for each layer $l$ are stored in a $d \times L_l$ weight matrix
\begin{equation}
\weightmatrixat{l} = \left[\begin{array}{cccc} \weightfull{l}{1} & \weightfull{l}{2} & ... & \weightfull{l}{L_l} \end{array}\right] \,,
\end{equation}
where $L_l$ denotes the number of clusters in layer $l$. The tree topology at layer $l$ is usually represented using a cluster indicator matrix $\clusterindat{l}$. $\clusterindat{l} \in \{0, 1\}^{L_{l + 1} \times L_{l}}$ is defined as
\begin{equation}
\clusterindat{l}_{ij} = \text{bool}(\cluster{l+1}{i} \subset \cluster{l}{j})\,,
\end{equation}
i.e., it is one when $\cluster{l+1}{i}$ is a child of $\cluster{l}{j}$ in the tree. Here, $\text{bool}(\cdot)$ is $1$ when the condition $\cdot$ is true and $0$ otherwise.

\subsection{Inference} \label{sec:batchinference}

Throughout this paper, we will assume two inference settings:

\begin{enumerate}
   \item \emph{Batch Inference}: inference is performed for a batch of $n$ queries represented by a sparse matrix $\mat{X} \in \Rn{n \times d}$ where every row of $\mat{X}$ is an individual query $\vc{x}_i$.
   \item \emph{Online Inference}: a subset of the batch setting where there is only one query, e.g., the matrix $\mat{X}$ has only one row.
\end{enumerate}

When performing inference, the XMR model $f$ prescribes a score to all query-cluster pairs $(\vc{x}_i, \cluster{l}{j})$. Hence, in the batch setting, one can define the prediction matrices,
\begin{equation}
\predmatrixat{l}_{ij} = f(\vc{x}_i, \cluster{l}{j}) = \prod_{\vc{w} \in \mathcal{A}(\cluster{l}{j})} \sigma \left( \vc{w} \cdot \vc{x}_i \right)  \,.
\end{equation}
The act of batch inference entails collecting the top $k$ most relevant labels (leaves) for each query $\vc{x}_i$ and returning their respective prediction scores $\predmatrixat{l}_{ij}$.

However, the act of exact inference is typically intractable, as it requires searching the entire model tree. To sidestep this issue, models usually use a greedy beam search of the tree as an approximation. For a query $\vc{x}$, this approach discards any clusters on a given level that do not fall into the top $b \geq k$ most relevant clusters examined at that level. Hence, instead of $\predmatrixat{l}$, we compute {\em beamed} prediction matrices $\beamedpredmatrixat{l}$, where each row has only $b$ nonzero entries whose values are equal to their respective counterparts in $\predmatrixat{l}$. Pseudo-code for the inference algorithm is given for reference in \Cref{alg:batchinference}, where $\odot$ denotes entry-wise multiplication.

\section{Our Method} \label{sec:ourmethod}
Our contribution is a method of evaluating masked sparse matrix multiplication that leverages the unique sparsity structure of the beam search to reduce unnecessary traversal, optimize memory locality, and minimize cache misses. The core prediction step of linear XMR tree models is the evaluation of a masked matrix product, i.e.,
\begin{equation} \label{eq:maskedprediction}
\actmatrixat{l} = \maskmatrixat{l} \odot (\mat{X} \weightmatrixat{l}) \,,
\end{equation}

where $\actmatrixat{l} \in \Rn{n \times L_l}$ denotes ranker activations at layer $l$, $\maskmatrixat{l} \in \{0, 1\}^{n \times L_l}$ denotes a dynamic mask matrix determined by beam search, $\mat{X} \in \Rn{n \times d}$ is a sparse matrix whose rows correspond to queries in the embedding space, $\weightmatrixat{l} \in \Rn{d \times L_l}$ is the sparse weight matrix of our tree model at layer $l$, and $\odot$ denotes entry-wise multiplication. Note the mask matrix $\maskmatrixat{l}$ is only known at the time of reaching the $l$-th layer. We leave out the application of $\sigma$ because it can be applied as a post processing step. We have observed that this masked matrix multiplication takes up the vast majority of inference time  on various data sets --- between $90\%$ and $98\%$ depending on model sparsity --- and hence is ripe for optimization.

\textbf{For readability, we will suppress the $(l)$ superscript for the rest of the section.} Recall that both $\mat{W}$ and $\mat{X}$ are highly sparse. One typically implements the above computation by storing the weight matrix $\mat{W}$ in compressed sparse column (CSC) format and the query matrix $\mat{X}$ in compressed sparse row (CSR) format\footnote{For details of the well-known CSR and CSC formats, see \cite{davis2006direct}.}, facilitating efficient access to columns of $\mat{W}$ and rows of $\mat{X}$, respectively. Then, to perform the operation in \Cref{eq:maskedprediction}, one iterates through all the nonzero entries $\mathcal{M}_{ij} \neq 0$, extracts the $i$-th query $\vc{x}_i$ and the ranker weights $\vc{w}_j$ for cluster $j$, and computes the inner product $\mat{A}_{ij} = \vc{x}_i \cdot \vc{w}_j$ via a sparse vector dot product routine. One method is to use a progressive binary search in both $\vc{x}_i$ and $\vc{w}_j$ to find all simultaneous nonzeros. We give pseudo-code for binary search in \Cref{alg:sparsevectorinnerprod}. However, there are other iteration methods, we will describe below -- such as marching pointers, hash-maps, and dense lookups. Any iteration method can be combined with MSCM to give a significant performance boost.

While for general sparse matrix multiplication, this is a reasonable method of computation, there are a few special properties about the matrices $\mathcal{M}$ and $\mat{W}$ that this method ignores, namely:

\begin{enumerate}
\item The sparsity pattern of the mask matrix $\mathcal{M}$ is determined by prolongating the search beam from layer $l - 1$ to layer $l$. That is, if cluster $\cluster{l}{j}$ in layer $l$ is a child of a cluster in the search beam of query $i$, then $\mathcal{M}_{ij} \neq 0$. This means that, if the nodes on a layer are grouped by their respective parents, the nonzero entries of $\mathcal{M}$ come in contiguous single row blocks corresponding to siblings in the model tree. See \Cref{fig:explanation}, bottom, for an illustration. \textbf{This suggests that one may improve performance by evaluating all siblings simultaneously.} \label{it:sparsityofmask}
\item Columns in $\mat{W}$ corresponding to siblings in the model tree often tend to have \emph{similar sparsity patterns}. We give an illustration of this fact in \Cref{fig:explanation}, top. Together with the previous observation, \textbf{this suggests storing the matrix $\mat{W}$ in such a way that entries of $\mat{W}$ are contiguous in memory if they both lie on the same row and belong to siblings in the model tree.} \label{it:similarsupport}
\end{enumerate}

\begin{figure}
\centering
  \includegraphics[width=0.475\textwidth]{images/pecos/chunked.pdf}
  \hspace{0.1in}
  \includegraphics[width=0.475\textwidth]{images/pecos/chunkmultiplication.pdf}
  \caption{\textbf{Top}: A simplified pictorial representation of the property discussed in \Cref{it:similarsupport}. The darkened region indicate non-zeros and the light regions indicate zeros. \textbf{Bottom}: A visual representation of the chunked matrix multiplication routine. The colored blocks of $\mat{A}$ represent possible nonzeros. For each colored block in the output, MSCM evaluates the entire block simultaneously. Blocks are evaluated in order of their color.} \label{fig:explanation}
\end{figure}

These considerations lead us naturally to the \textbf{column chunked matrix} data structure for the weight matrix $\mat{W}$. In this data structure, we store the matrix $\mat{W} \in \Rn{d \times L_l}$ as a horizontal array of \emph{matrix chunks} $\weightmatrixchunk{i}$,
\begin{equation} \label{eq:weightchunked}
    \mat{W}^{(l)} = \left[\begin{array}{cccc} \weightmatrixchunk{1} & \weightmatrixchunk{2} & ... & \weightmatrixchunk{L_{l - 1}} \end{array} \right] \,,
\end{equation}
where each chunk $\weightmatrixchunk{i}\in \Rn{d\times B}$ ($B$ is the branching factor, i.e. number of children of the parent node) and is stored as a vertical sparse array of some sparse horizontal vectors $\vc{v}^{(j,i)}$,
\begin{equation}
\weightmatrixchunk{i} = \left[\begin{array}{ccccccc} \vc{0} & \hdots & (\vc{v}^{(r_1, i)})^T & \hdots & (\vc{v}^{(r_{s_i}, i)})^T & \hdots & \vc{0} \end{array}\right]^T \,.
\end{equation}
We identify each chunk $\weightmatrixchunk{i}$ with a parent node in layer $l- 1$ of the model tree, and the columns of the chunk $\weightmatrixchunk{i}$ with the set of siblings in layer $l$ of the model tree that share the aforementioned parent node in layer $l - 1$. As we will see, this data structure therefore makes use of both ideas \Cref{it:sparsityofmask} and \Cref{it:similarsupport} simultaneously.

To see why this data structure can accelerate the masked matrix multiplication, consider that one can think of the mask matrix $\mathcal{M}$ as being composed of blocks,
\begin{equation}
\mathcal{M} = \left[\begin{array}{cccc} \mathcal{M}^{(1, 1)} & \mathcal{M}^{(1, 2)} & ... & \mathcal{M}^{(1, L_{l - 1})} \\ \vdots & \vdots & \ddots & \vdots \\ \mathcal{M}^{(L_{l}, 1)} & \mathcal{M}^{(L_{l}, 2)} & ... & \mathcal{M}^{(L_{l}, L_{l - 1})} \end{array}\right] \,,
\end{equation}
where the block column partition is the same as that in \Cref{eq:weightchunked}, and every block has one row and corresponds to a single query. As per the observation in \Cref{it:sparsityofmask} above, every block $\mathcal{M}^{(j, i)}$ must either be composed entirely of zeros or entirely of ones.

Therefore, since $\mat{A}$ and $\mathcal{M}$ share the same sparsity pattern, the ranker activation matrix $\mat{A}$ is also composed of the same block partition as $\mathcal{M}$,
\begin{equation}
\begin{split}
\mat{A} &= \left[\begin{array}{cccc} \mat{A}^{(1, 1)} & \mat{A}^{(1, 2)} & ... & \mat{A}^{(1, L_{l - 1})} \\ \vdots & \vdots & \ddots & \vdots \\ \mat{A}^{(L_{l}, 1)} & \mat{A}^{(L_{l}, 2)} & ... & \mat{A}^{(L_{l}, L_{l - 1})} \end{array}\right] \,, \\
\mat{A}^{(j, i)} &= \mathcal{M}^{(j, i)} \odot (\vc{x}_j \weightmatrixchunk{i}) \,.
\end{split}
\end{equation}
Hence, for all mask blocks $\mathcal{M}^{(j, i)}$ that are $1$, we have
\begin{equation} \label{eq:expforblock}
\mat{A}^{(j, i)} = \vc{x}_j \weightmatrixchunk{i} = \sum_{k \in S(\vc{x}_j) \cap S(\weightmatrixchunk{i})} x_{jk} \vc{v}^{(k, i)} \,,
\end{equation}
where $S(\vc{x}_j)$ and $S(\weightmatrixchunk{i})$ denote the indices of the nonzero entries of $\vc{x}_j$ and the nonzero rows of $\weightmatrixchunk{i}$ respectively. The above equation says that for all entries of $\mat{A}$ in the same block, the intersection $k \in S(\vc{x}_j) \cap S(\weightmatrixchunk{i})$ only needs to be iterated through \emph{once per chunk}, as opposed to \emph{once per column} as is done in a vanilla implementation. Of course, it is theoretically possible that $S(\vc{x}_j) \cap S(\weightmatrixchunk{i})$ is substantially larger than the intersections $S(\vc{x}_j) \cap S(\vc{w}_i)$ in our baseline, but this tends not to be the case in practice because of the observation in \Cref{it:similarsupport} that the columns of $\weightmatrixchunk{i}$ tend to have similar support. Moreover, the actual memory locations of the values actively participating in the product \Cref{eq:expforblock} are physically closer in memory than they are when $\weightmatrixchunk{i}$ is stored in CSC format. This helps contribute to better memory locality.

\begin{comment}
\begin{figure}
  \centering
  \includegraphics[scale=0.33]{images/pecos/chunkmultiplication.pdf}
  \caption{A visual representation of the chunked matrix multiplication routine. The colored blocks of $\mat{A}$ represent possible nonzeros. For each colored block, MSCM evaluates the entire block simultaneously. Blocks are evaluated in order of their color.} \label{fig:chunkmult}
\end{figure}
\end{comment}

We take a moment to pause and remark that the only task remaining to fully specify our algorithm is to determine how to efficiently iterate over the nonzero entries $x_{jk}$ and nonzero rows $\weightmatrixchunk{k, i}$ for $k \in \nzlist{\vc{x}_j} \cap \nzlist{\weightmatrixchunk{i}}$. This is essential for computing the vector-chunk product $\vc{x}_j \weightmatrixchunk{i}$ efficiently. There are number of ways to do this, each with potential benefits and drawbacks:

\begin{enumerate}
    \item \textbf{Marching Pointers}: The easiest method is to use a marching pointer scheme to iterate over $x_{jk}$ and $\weightmatrixchunk{k,i}$ for $k \in \nzlist{\vc{x}_j} \cap \nzlist{\weightmatrixchunk{i}}$. In this scheme, we maintain both $\nzlist{\vc{x}_j}$ and $\nzlist{\weightmatrixchunk{i}}$ as sorted arrays. To iterate, we maintain an index $k_x$ in $\nzlist{\vc{x}_j}$ and an index $k_K$ in $\nzlist{\weightmatrixchunk{i}}$. At any given time, we either have $k_x = k_K$, in which case, we emit $x_{jk}$ and $\weightmatrixchunk{k,i}$; if $k_x < k_K$, we increment $k_x$; and if $k_x > k_K$, we increment $k_x$. \label{enum:march}
    \item \textbf{Binary Search}: Since $\vc{x}$ can be highly sparse, the second possibility is to do marching pointers, but instead of incrementing pointers one-by-one to find all intersections, we use binary search to quickly find the next intersection. This mirrors the implementation of our baseline \Cref{alg:sparsevectorinnerprod}. We maintain an index $k_x$ in $\nzlist{\vc{x}_j}$ and an index $k_K$ in $\nzlist{\weightmatrixchunk{i}}$. At any given time, we either have $k_x = k_K$, in which case, we emit $x_{jk}$ and $\weightmatrixchunk{k,i}$; if $k_x < k_K$, we use a binary search to find the index $k_K'$ in $\nzlist{\weightmatrixchunk{i}}$ where $\nzlist{\vc{x}_j}[k_x]$ would be inserted into $\nzlist{\weightmatrixchunk{i}}$ and set $k_K \gets k_K'$; and we handle $k_x > k_K$ similarly. \label{enum:binsearch
    \item \textbf{Hash-map}: The third possibility is to enable fast random access to the rows of $\weightmatrixchunk{i}$ via a hash-map. The hash-map maps indices $i$ to nonzero rows of $\weightmatrixchunk{i}$. One can iterate over $x_{jk}$ for $k \in \nzlist{\vc{x}_j}$ and perform a hash-map lookup for each $k$ to retrieve $\weightmatrixchunk{k,i}$ if nonzero. This method is implemented by \textsc{NapkinXC} \cite{jasinska2020probabilistic} for online inference. However, in \textsc{NapkinXC}, it is implemented on a per-column basis, which introduces a massive memory overhead. Matrix chunking significantly reduces this memory overhead. \label{enum:hash}
    \item \textbf{Dense Lookup}: The last possibility is to accelerate the above hash-map access by copying the contents of the hash-map into a dense array of length $d$. Then, a random access to a row of $\weightmatrixchunk{i}$ is done by an array lookup. This dense array is recycled across the entire program, so afterwards, the dense array must be cleared. This is the method implemented by \textsc{Parabel} \cite{prabhu2018parabel} and \textsc{Bonsai} \cite{khandagale2020bonsai}. \label{enum:dense}
\end{enumerate}

\begin{algorithm}
   \caption{Sparse Vector Chunk Product}
   \label{alg:sparsevectorchunkprod}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} Sparse row vector $\vc{x} \in \Rn{d}$ and chunk $\mat{K} \in \Rn{d \times s}$
   \STATE {\bfseries Output:} The dense product $\vc{x} \mat{K} \in \Rn{s}$
   \STATE Initialize dense result vector: $\vc{z} \gets \vc{0} \in \Rn{s}$
   \STATE \emph{Note}: in the following loop, use one of the iterators as described in items 1 through 4.
   \STATE \emph{Note}: For vector $\star$, $\nzlist{\star}$ denotes the array of indices of nonzeros in $\star$
   \STATE \emph{Note}: For chunk $\ast$, $\nzlist{\ast}$ denotes the array of indices of nonzero rows in $\ast$
   \FOR{scalar $x_i$, row $\mat{K}_i$, where $i \in \nzlist{\vc{x}} \cap \nzlist{\mat{K}}$}
     \FOR{All nonzeros in chunk row: $k \in \nzlist{\mat{K}_{i}}$}
   \STATE $\vc{z}_k \gets \vc{z}_k + x_{i} K_{i, k}$
   \ENDFOR
   \ENDFOR
   \STATE {\bfseries return} $\vc{z}$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
   \caption{Evaluating Masked Matrix Products}
   \label{alg:maskedmatrixprod}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} Mask matrix $\mathcal{M} \in \{0, 1\}^{n \times L_l}$ in CSR format, query matrix $\mat{X} \in \Rn{n \times d}$ in CSR format, and weight matrix $\mat{W} \in \Rn{d \times L_l}$ in chunked format.
   \STATE {\bfseries Output:} Ranker activation matrix $\mat{A} \in \Rn{n \times L_l}$ in CSR format.
   \STATE Allocate memory for $\mat{A}$ using the sparsity pattern of $\mathcal{M}$
   \STATE Initialize $\mat{A} \gets \mat{0}$.
   \STATE Collect nonzero blocks: $A \gets \{(i, j) \mid \mathcal{M}^{(i, j)} \neq \mat{0}\}$
   \IF{$n > 1$}
   \STATE Sort nonzero blocks $(i, j) \in A$ by chunk index $j$
   \ENDIF
   \FOR{$(i, j) \in A$}
   \STATE Compute $\mat{A}^{(i, j)} \gets \vc{x}_i \weightmatrixchunk{j}$ via \Cref{alg:sparsevectorchunkprod}
   \ENDFOR
      \STATE {\bfseries return} $\mat{A}$.
\end{algorithmic}
\end{algorithm}

There is one final optimization that we have found particularly helpful in reducing inference time --- and that is evaluating the nonzero blocks $\mat{A}^{(j, i)}$ in order of column chunk $i$. Doing this ensures that a single chunk $\weightmatrixchunk{i}$ ideally only has to enter the cache once for all the nonzero blocks $\mat{A}^{(j, i)}$ whose values depend on $\weightmatrixchunk{i}$.

With these optimizations in place, we have found in our performance benchmarks that the hash-map iteration scheme tends to perform best on small to medium sized batches. On large batch sizes, dense lookup performs the best --- this is because we incur the cost of copying the hash-map contents into a dense array only once per chunk if we perform evaluations in chunk order. This cost is then amortized by the increase in the speed of random accesses to the rows of $\weightmatrixchunk{i}$.

To help readers decide which implementation would suit them best, we present a rule of thumb to deciding which iterator to use in \Cref{sec:selectingmethod}. A more detailed examination of time complexity and memory overhead is given in \Cref{tab:complexity}.

With all of this taken into account, we present \Cref{alg:maskedmatrixprod}, the final version of our algorithm for performing the masked sparse matrix multiplication in \Cref{eq:maskedprediction}. As one can see in our benchmarks in Figures~\ref{fig:inftime2} and \ref{fig:inftime3}, we have found that the optimizations above produce substantial speedups over the baseline implementation in Alg.~\ref{alg:sparsevectorinnerprod}. We will discuss this in \Cref{sec:eval}. Generally, the larger the branching factor of the model tree, the more significant the performance boost due to the fact that our method aggregates computation over entire chunks. Moreover, we note that the {\bf performance boost of this technique is essentially free} in that it gives exactly the same inference result as the baseline method, but runs significantly faster.

\begin{figure*}
\centering
\includegraphics[width=2.1in]{images/charts/r5-batch2.pdf}
\includegraphics[width=2.1in]{images/charts/r5-batch8.pdf}
\includegraphics[width=2.1in]{images/charts/r5-batch32.pdf}
\begin{comment}
\caption{A comparison of batch inference times on different datasets and different model branching factors between the baseline naive algorithm described in \Cref{alg:sparsevectorinnerprod} (blue), an unchunked version of dense lookup (the algorithm used by \textsc{Parabel} \cite{prabhu2018parabel}) (orange), chunked matrices with binary search iteration (yellow), chunked matrices with hash-map iteration (grey), and chunked matrices with dense lookup iteration (green). We omit the remaining methods in the result tables because they are not competitive. Note that chunked matrices provide a substantial performance boost over the baseline and that the dense lookup chunked matrix technique consistently outperforms everything else. } \label{fig:inftime2}
\end{comment}
\caption{A comparison of the speedup provided by an MSCM implementation over a non-MSCM reference implementation for different iteration methods and different tree branching factors in the batch setting. Measured on a \textbf{r5.4xlarge} AWS instance.} \label{fig:inftime2}
\end{figure*}

\begin{figure*}
\centering
\includegraphics[width=2.1in]{images/charts/r5-realtime2.pdf}
\includegraphics[width=2.1in]{images/charts/r5-realtime8.pdf}
\includegraphics[width=2.1in]{images/charts/r5-realtime32.pdf}
\caption{A comparison of the speedup provided by an MSCM implementation over a non-MSCM reference implementation for different iteration methods and different tree branching factors in the online setting (i.e., batch size 1). Measured on a \textbf{r5.4xlarge} AWS instance.} \label{fig:inftime3}
\end{figure*}

\section{Related Work}\label{sec:rel_work}

XMR tree models are widely used throughout the literature --- though a comprehensive terminology surrounding these related techniques has yet to fully emerge. In short, we define an XMR tree model as a tree where every node is associated with a ranker function, every label corresponds to a leaf of the tree, and the ranking for any given label is obtained by combining all ranker functions on the path from the label leaf to the root of the tree.

This definition captures several prior works --- for example, the probabilistic label tree (PLT) that originates from \cite{jasinska2016extreme}. This model in turn takes inspiration from previous work on label trees \cite{beygelzimer2009error, bengio2010label}, and there has since been a large body of follow-up work, spawning many state-of-the-art XMR models such as \textsc{Parabel} \cite{prabhu2018parabel}, \textsc{Bonsai} \cite{khandagale2020bonsai}, \textsc{ExtremeText} \cite{wydmuch2018no}, \textsc{AttentionXML} \cite{you2019attentionxml}, \textsc{NapkinXC} \cite{jasinska2020probabilistic}, and \textsc{PECOS} \cite{pecos2020}.  Note that \textsc{ExtremeText} and \textsc{AttentionXML} are designed only for dense features. The remaining models support sparse features and thereby require masked sparse matrix times sparse vector multiplication routines (see \cref{eq:maskedprediction}). We present MSCM as a way to accelerate these routines.

We turn now from the models themselves to existing optimizations for sparse inference. Unlike dense matrix multiplication, the random nature of memory access in sparse matrix algebra can be harder to optimize. Despite that, computational science researchers have devoted considerable energy to optimizing sparse matrix times vector products. Notable sparse matrix techniques relevant to this paper include \emph{cache blocking}, where the internal data of a matrix is reorganized into blocks to encourage memory locality. Many sparse kernel libraries make use of this idea to better tailor sparse matrix calculations to the underlying hardware. Notable examples include the SPARSITY framework \citep{im2004sparsity}, a framework that can automate the optimization of sparse kernels -- making use of both register and cache level optimizations. Other examples include work by \citep{williams2007optimization} specifically targeting multi-core platforms, and \citep{nishtala2007cache}, who develop an analytic model to better help predict optimal sparse kernel reorganization. Unfortunately, these techniques all target sparse matrix times dense vector calculations, as these are most common in computational science.

In comparison, sparse matrix times sparse vector (SpMSpV) multiplication is an under-served area. However, there are a number of emerging techniques for sparse matrix operations with underlying graph structure, including \cite{sundaram2015graphmat, azad2017work, yang2015fast}. Unfortunately, none of these methods are tailored to XMR tree inference, where beam search induces a very well-structured mask over matrix outputs. They are also significantly more heavy-weight than the method we present. The scale of XMR problems therefore necessitates the development of new masked sparse matrix methods specifically tailored to XMR trees.

redpajama_set_name: RedPajamaArXiv


We are a Service Elite Specialist and Platinum Channel Partner, which are Motorola Solutions highest rankings. We have our own factory trained staff of experienced service professionals who are totally committed to keeping your system performing at peak efficiency. Our technicians are ETA certified, which essentially means they meet the industry's highest caliber of standards. We maintain on call technicians for 24 hour emergency service. We utilize the latest test equipment that is calibrated annually as a quality control measure and maintain an extensive inventory of factory original parts. The technical department maintains a screen room that is 100% RF clean and a "staging room" to set up systems as in the field for burn-in and customer inspection.
You can expect fast turnaround and equipment fixed right the first time at Commtronics!


text:
Please click on the map above for travel directions to our campground.
The casino has more than 380 gaming tables for blackjack, craps, roulette, and poker and has more than 4,700 slot machines. There are several restaurants within the casino, among them a Hard Rock Cafe. Foxwoods has 2,266 hotel rooms and a two-story arcade for children and teens. It is now the largest casino in the United States.
Mohegan Sun Casino
It features the 12,000-seat capacity Mohegan Sun Arena, home of the New England Black Wolves of the National Lacrosse League and the Women's National Basketball Association's Connecticut Sun. It houses a 350-seat Cabaret Theatre, the 300-seat Wolf Den, and contains slot machines, poker, blackjack, craps, roulette, Caribbean stud poker, keno and baccarat. The race book offers live horse or greyhound racing from around the U.S. as well as from Australia and England.
Mystic Seaport
The Museum of America and the Sea in Mystic, Connecticut is the largest maritime museum in the world. It is notable for its collection of sailing ships and boats, and for the re-creation of the crafts and fabric of an entire 19th-century seafaring village. It consists of more than 60 original historic buildings, most of them rare commercial structures moved to the 19-acre site and meticulously restored.
Mystic Marine life Aquarium
The Aquarium is one of three U.S. facilities holding Steller sea lions and it has one of the largest outdoor Beluga whale exhibits in the United States. Special exhibits include a ray and shark touch pool, an African penguin exhibit, and a jelly gallery.
The United States Navy Submarine Force Library and Museum, located on the Thames River near Groton, Connecticut is the only submarine museum managed exclusively by the Naval History & Heritage Command division of the U.S. Navy, which makes it a repository for many special submarine items of national significance, including USS Nautilus (SSN-571).
Ocean Beach Park
Located at the foot of Ocean Avenue in Mystic Country, New London's premier recreational facility provides excellent public access to the Atlantic Ocean from a beautiful white, sugar sand beach, complimented by an olympic-size freshwater pool, lockers, and event staging. The 50-acre Park also boasts a beautifully landscaped 18-hole miniature golf course and various attractions.
Thames Science Center
Housed in five storefronts along the waterfront of Newport, the Thames Science Center gives visitors of all ages a chance to learn about robots, computers, and much more. The center acts as a pioneer in developing and testing unique, interactive science and pre-engineering learning programs, including Watershed Worlds, RobotACTS, Shoot for the Moon!, Mentors for Explainers, and others.
Connecticut River Ferry (Chester)
The Chester Ferry is a seasonal ferry crossing the Connecticut River between the town of Chester, Connecticut and the village of Hadlyme (in the town of Lyme, Connecticut). It is the second oldest continuously operating ferry service in the state of Connecticut and is a designated state historical landmark. The ferry is part of the scenic portion of Route 148 and provides a convenient link between two of Connecticut's tourist attractions: Gillette Castle State Park in Hadlyme and the Essex Steam Train.
Connecticut River cruises (Haddam)
From February - October Riverquest is on the river with many fun and relaxing cruises to enjoy. From daytime and sunset Cruises, birding (Tree Swallow, Osprey), kid's, wine/food, music and more, there is a cruise for everyone, making RiverQuest a must visit.
Olde Mistick Village
Stroll the beautiful lanes and enjoy shopping in distinctive buildings designed to represent a New England Village of about 1720. The village features picturesque settings of flowers, trees & duck ponds that surround you as you relax and unwind. Shopkeepers pride themselves on offering you some of the most interesting and unique items from around the world. Feeling hungry? Olde Mistick Village is home to some of Mystic's best restaurants. They also feature a multi-theatre arts & movie cinema for your enjoyment.
Essex Steam Train
The Valley Railroad Company, operating the Essex Steam Train & Riverboat, has been serving the lower Connecticut River Valley since 1971. The company's mission is to keep alive the rich mechanical, industrial, and transportation heritage of the state through the ongoing operation of vintage steam and diesel locomotives, passenger coaches, and the facilities and infrastructure to support these.
Gillette Castle
Gillette Castle State Park straddles the towns of East Haddam and Lyme, Connecticut. Sitting high above the Connecticut River, the castle was originally a private residence commissioned and designed by William Gillette, an American actor who is most famous for his portrayal of Sherlock Holmes on stage.
Goodspeed Opera House
Come hear the story of how an enterprising family, a picturesque landmark, an insightful restoration, and brilliant execution evolved into one of the most important institutions in American theater: Goodspeed Musicals. You can go behind the scenes of a musical at the Goodspeed Opera House. Explore places such as backstage and the actors' dressing rooms while learning about the vibrant history of the Opera House.
Fort Griswold
Fort Griswold is a former American military base in Groton, Connecticut. Named after then Deputy Governor Matthew Griswold, the fort played a key role in the early stages of the American Revolutionary War. In tandem with Fort Trumbull on the opposite side of the harbor, Griswold served to defend the port of New London, a supply center for the new Continental Army and a friendly port for Connecticut-sanctioned privateers who preyed on British ships.
Devil's Hopyard
Devil's Hopyard State Park is a state park located in the town of East Haddam, Connecticut at scenic Chapman Falls on the Eightmile River. The 1,000-acre park is used for hiking, stream fishing, bird watching, bicycling, picnicking, camping, and youth group camping.
Nehantic State Forest
The forest offers opportunities for hiking, hunting, picnicking, swimming, and boating. The Lyme portion of the forest provides access to 69-acre Uncas Pond and 30-acre Norwich Pond. Boat launches are located on each pond. The ponds and their connecting stream, Falls Brook, sit at the western edge of Becket Hill State Park Reserve. No roads or trails pass from the state forest into the undeveloped and otherwise inaccessible 260-acre state park reserve.
Eugene O'Neill Theater & Workshop
The O'Neill is the recipient of two Tony Awards: the 1979 Special Award and the 2010 Regional Theatre Award. The O'Neill is a multi-disciplinary institution that has had a transformative effect on American theater. The O'Neill pioneered play development and stage readings as a tool for new plays and musicals, and is also home to the National Theater Institute, an intensive study-away semester for undergraduates.
Ocean Beaches
Connecticut's shoreline, along Long Island Sound, offers a good selection of salt water beaches for all tastes. Among the best of these is Ocean Beach in New London, with white sugar sand and lots of entertainment to include a swimming pool, miniature golf, and game rooms. Come swim, tan, and enjoy the great beaches Connecticut has to offer.
Mansions are synonymous with Newport and Bristol Counties. During the Gilded Age, America's wealthiest families flocked to the "City-by-the-Sea" and its surrounding areas, including Bristol, making the area their summertime playground. Today, more than a dozen prestigious properties have been preserved by dedicated organizations committed to protecting our past for both you and generations to come.
Mystic Argia Schooner Cruise
Explore the surrounding islands of Mystic, CT from the spacious wooden deck of the sailing ship, ARGIA. Relax as you sail by scenic coastlines and lighthouses or help the crew hoist and trim the sails aboard this elegant schooner. Each cruise includes complimentary snacks and lemonade. You may also bring your own beverages and food – coolers and cups are available.
Connecticut offers some of the best saltwater fishing that few places can rival. With over 100 species of fish found in Long Island Sound, anglers can enjoy some of the very best striped bass, bluefish, summer flounder, scup, hickory shad, black sea bass and tautog fishing along the entire coast. The State of Connecticut offers anglers many fishing opportunities with excellent boat launches along the coast and great shore fishing locations at coastal state and city parks, and convenient party and charter boat fishing.
Clinton Crossing Premium Outlets®, located along the Connecticut Shoreline, is a charming outdoor village center conveniently located on I-95 en route to Boston or New York. Enjoy savings of 25% to 65% off every day prices featuring more than 70 designer and name brand outlet stores.
The Connecticut Antiques Trail
On the Connecticut Antiques Trail, you can uncover 1700s Americana, mid-century modern furniture and vintage collectibles from every generation. With auction houses and small town antique shops, flea markets and antique shows — even historic inns filled with treasures from another age — the CT Antiques Trail winds through historic and scenic Connecticut revealing antiques of varying styles, periods and price ranges to satisfy enthusiasts and collectors alike.
Ocean ferries to Block Island, Orient Point & Martha's Vineyard
There is so much to visit, we are conveniently located to quickly get to local jems such as Block Island, Orient Point, & Martha's Vineyard.

redpajama_set_name: RedPajamaCommonCrawl


After talking to people on the Wanhao Duplicator i3/Monoprice Maker Select (Prusia i3 clone) Facebook group, I decided to install Cura 2.3.1. However, I am stuck at the print head settings. Do I simply need to take some measurements or have others already figured out the settings?
If you are not going to print one at a time, you can ignore the print head size settings.


The patient is a 57-year-old female, who was the restrained driver of a vehicle involved in a motor vehicle accident on June 28, 2013. She presents today for further evaluation and treatment of her injuries. Specifically, she reports pain to the low back predominantly on the right side. She does report sharp pains at times, but denies pain, weakness or numbness shooting to her extremities. She does have a history of low back pain, which occurred from a prior motor vehicle accident. However, she reports that low back pain had completely resolved and she was pain-free prior to this new accident. She has been receiving therapies and is seeing a chiropractic physician. She has undergone some trigger point injections, which she reports did provide some relief. She has had an MRI scan of the lumbar spine. This was performed on August 21, 2013. It did reveal a herniated disc at L5-S1.
4. Myofascial pain secondary to all the above.
The patient and I did have nice talk today regarding her pain and overall plan of care. She does have patches which were prescribed by Dr. and we will continue to use these for pain relief. She will continue with therapy as well as home exercise. She will use ice 20 minutes at least twice daily. We did discuss other treatment options including additional trigger point injections. She did well from Dr. . We will therefore request pre-certification from her insurance carrier for additional injections. She will call me with any questions or concerns prior to this.


Dawn Richards and Machinedrum entwine one of 2016's most adventurous R&B albums in Redemption, unpackaging the promise of their Not Above That anthem across a suite of idiosyncratic vocal twists and flighty, vibrant production.
Looking like the starchild of Sun Ra on the front cover, D∆WN really sets to work defining her sound in freestyling opposition to the rest of the scene, embracing a palette of giddy tweaks and unexpected pivots that make the former member of girl group, Danity Kane, stand out a mile on her own terms.
The Redemption LP is literally and conceptually cleft in two parts that correspond to the yin and yang of D∆WN's chimeric aesthetic. On the one hand, you have the lushly spacious and vertiginous A-side, freewheeling from ascendent new age plumes to teetering dance-pop zingers in Love Under Lights and the brassy bedspring bounce of Renegades, via the ecstatic Black Crimes and weightless thizz of Voices with its spiralling ululations. Allow the guitars on LA, tho.
However, on the flipside, she appear to temper those experimental urges into a subtler run of rugged and bittersweet songs, tipping in with the bleep-gilded swang of Lazarus before tucking the vibe deeper with the RiRi-esque Tyrants and the chiming downstroke of Vines in duet with PJ Morton, prior to really dimming the lights for the pitch-bent rhodes of Sands and fading to close in symphonic style with the aching R&B folk essence of The Louvre.


text:
American wrestlers, Commentators, 1969 births,
1994 debuts
2005 retirements
Total Nonstop Action Wrestling alumni
Mortimer Plumtree
Ring names
Aloysius Hayes
6 ft 1 in (1.85 m)
Billed from
Lenny Lane
JB Trask
Jerry Lynn
Mortimer Plumtree (born David Webber) was an American manager, road agent, commentator, and sometimes wrestler. He has best known for his work in Total Nonstop Action Wrestling in 2002.
Webber's early career largely centered around the upper Midwest region of the United States where he managed and teamed with Lenny Lane. In 1996, Webber had his television debut appearing on American Wrestling Federation programming. His gimmick was that of a nephew of Lord Alfred Hayes called Aloysius Hayes.
In 1997, Webber tried out for WCW, but was ejected from the locker room by then-President Eric Bischoff after a misunderstanding. Webber nearly retired, but instead focused his energy as a manager in Steel Domain Wrestling. He managed was known as the "Chicago Group" (Ace Steele, Danny Dominion, and Brad Bradley).
Total Nonstop Action (2002)
In 2002, Webber signed for first national contract. Jeremy Borash was familiar with Webber's work and brought him to the attention of TNA founders Jeff Jarrett, Jerry Jarrett, and Bob Ryder.
Webber appeared on the first NWA-TNA Weekly PPV as Mortimer Plumtree, a weaselly nerd who managed the masked Johnson Brothers (Richard & Rod) who notoriously resembled a pair of penises. The Johnsons soon after broke with Plumtree and left TNA.
Webber appeared infrequently on-screen as Plumtree for a few months. Instead he concentrated on being a backstage staff member. In October, he started managing Ace Steele but that ended after only a few shows after Steele was released.
Managing success was finally found with A.J. Styles. Over a few months, he helped the rising Styles in feuds against Sean Waltman and Jerry Lynn.
In January 2003, TNA booker Vince Russo allegedly wrote the Plumtree character out of all future TNA programming due to his feeling that Webber was aligned with Jerry Jarrett in office politics. He remained on staff full-time until June, when he moved back to Minnesota. He would appear only a handful of times after that, both for the failed Force 1 Wrestling promotion he assisted with booking and with another short-lived group, the American Wrestling League.
Wrestlers Managed
Ace Steele
Adrian Lynch
Brad Bradley
Danny Dominion
Retrieved from "https://prowrestling.fandom.com/wiki/Mortimer_Plumtree?oldid=1551379"
American wrestlers


text:
Home Asia/Pacific Afghanistan BREAKING NEWS: Afghanistan Releases Christian Convert Assadullah (Update)
BREAKING NEWS: Afghanistan Releases Christian Convert Assadullah (Update)
>Christian faced death sentence
>Assadullah remains confined to home
>Security concerns remain
By Stefan J. Bos, Chief International Correspondent BosNewsLife
Christian converts can face the death penalty in Afghanistan.
KABUL, AFGHANISTAN (BosNewsLife)– An Afghan man who faced the death penalty for converting from Islam to Christianity has been released on bail after international pressure, but concerns remain about his safety, his friends confirmed to BosNewsLife Friday, April 8.
Shoaib Assadullah, 23, was reportedly detained October 21 in the city of Mazar-e-Sharif for giving the Bible's New Testament to a man who later reported him to local authorities. While jailed, Assadullah said in letters seen by BosNewsLife that he was physically abused and receiving death threats from fellow inmates.
Afghan officials did not comment on his release.
Friends said they still fear for his safety as Muslims planned new protests Friday, April 8, against last month's burning of a Koran at a church in the U.S. state of Florida. Several other demonstrations against the torching of what Muslims regard as a holy book left at least 24 dead, including seven United Nations employees.
There were fears Friday, April 8, the protests could put additional pressure on Assadullah and other Christian converts in Afghanistan.
BosNewsLife News Agency said Friday, April 8, it had temporarily pulled a photo of Assadullah after friends expressed concerns he may be recognized by angry crowds. The news agency did not yet release names of sources that contacted BosNewsLife citing security concerns.
NEW TRIAL?
It was not immediately clear when and if Assadullah would face a new trial. He did not address media directly yet, apparently amid fears for his safety.
Authorities have confined Assadullah to an area in northern Afghanistan where last Friday, April 1, a dozen people were killed in an attack on the U.N. compound in Mazar-e-Sharif, the capital of Balkh province, BosNewsLife learned.
Despite the difficulties, Assadullah reportedly said he wants to "continue to live and serve God in Afghanistan."
Assadullah is the second Christian to be released from prison after Said Musa, another convert,who was quietly granted asylum in Europe in February after what he called an "abusive" nine month detention.
CONVERTS BAPTIZED
Christian Musa was detained in May when a local television network aired footage of Afghans being baptized and participating in prayer gatherings.
The broadcast led to a nationwide crackdown against Muslim converts to Christianity, several rights groups said.
While Afghanistan's constitution upholds freedom of religion, "apostasy", or abandoning Islam, is tried under Islamic law and punishable by death, according to experts.
There were indications Friday, April 8, that the release of the Christians followed Western diplomatic pressure and publicity.
Among those pressuring the Afghan government was the Netherlands where Dutch Prime Minister Mark Rutte pledged he would do everything in his power to prevent executions of Christian converts, BosNewsLife learned.
His cabinet also announced an expert would join a police force to investigate possible religious rights violations in Afghanistan.
The opposition ChristenUnie (ChristianUnion) party had said it would only back a planned Dutch police mission in Afghanistan if the government pressured the country to release Christian converts and improve religious rights.
While its contribution is relatively small, the Netherlands is viewed as a key ally of the United States in rebuilding the country and the fight against militant Taliban and al-Qaida groups.
In latest statements, United States President Barack Obama and Afghan President Hamid Karzai have also condemned an explosion of Islamic violence in Afghanistan, following the torching of a Koran, although they did not directly address the reported persecution of Christian converts in the country.
There may be as many as 10,000 Christian converts in heavily Islamic Afghanistan, according to Christian rights activists.
Detained Afghan Christian Fears Execution
Mazar-e-Sharif
Shoaib Assadullah
Previous articleNepal Christians Protest Closure Cemetery; Demand More Rights
Next articleNEWS WATCH: EU Ministers Warn Portugal Over Massive Bailout
West Papua Churches Urge UN To Halt Attacks
M. Veldman 8th April 2011 At 8:35 pm
Thank to the Lord for Schoaib from Afghanistan is free.
M. Veldman
Rani 24th July 2011 At 9:11 pm
God bless you Asadullah. Remember that Mullah Asadullah is in heaven as he was in Taliban, but later converted to christianity after he met Jesus Christ.


text:
No Sacrifice, No Victory is the seventh studio album by Swedish heavy metal band HammerFall, released 20 February 2009. It was partly recorded at PAMA Studios, Torsås and partly at  Andy La Rocque's Sonic Train Studios in Varberg. This is the first album featuring the band's new lead guitarist Pontus Norgren,  the return of bassist Fredrik Larsson who played bass from 1994 to 1997, as well as the first to have the band tuning all of their guitars in all songs to D tuning as opposed to the E-flat tuning seen on most songs from all previous albums.

Track listing

Personnel
 Joacim Cans - lead vocals
 Oscar Dronjak - guitars, backing vocals
 Pontus Norgren - guitars, backing vocals
 Anders Johansson - drums
 Fredrik Larsson - bass, backing vocals
 Jens Johansson - keyboard solo on "Something for the Ages" and church organ on "Between Two Worlds"
 Stefan Elmgren - additional guitar solo on "Bring the Hammer Down"
 Samwise Didier - cover art

Chart positions

Song description
Drummer Anders Johansson knew No Sacrifice, No Victory was an important record as it was the first since their debut Glory to the Brave (1997) without the guitarist Stefan Elmgren. But Johansson is confident and explains every song in his own words:

References

External links
Official HammerFall website
Album information
Lyrics at Darklyrics

2009 albums
HammerFall albums
Nuclear Blast albums
Albums produced by Charlie Bauerfeind

redpajama_set_name: RedPajamaWikipedia


text:
Red Hat Expands Free Enterprise Linux RHEL Terms of Use
Red Hat announced that it is expanding the terms of free access to its enterprise Linux distribution, Red Hat Enterprise Linux (RHEL).
Red Hat announced the completion of the development of CentOS Linux, which was widely used as a server, in December 2020. It was a decision to match the development of Linux to the growth of the IT industry, but there was a strong backlash against the announcement that could lose the free RHEL-compatible Linux, and CentOS alternative operating systems such as AlmaLinux and Rocky Linux appeared. done.
In the context of these Red Hat-based Linux distributions, Red Hat announced that it is expanding the conditions for free use of RHEL in the Red Hat Developer Program. Until now, the free use condition was limited to one per user and only for software development purposes, but in the future, it will be available in up to 16 production environments.
In order to use RHEL free of charge, you must register for the Individual Developer Subscription starting on February 1, 2021, so there is no registration fee and there is no sales activity at Red Hat. According to this program, the use of RHEL is self-supporting, but you can upgrade to full support as needed.
It also announced that the scope of the Red Hat developer program, which had been limited to personal development until now, will be extended to development by teams. To provide RHEL subscription customers with free access to RHEL through that subscription when developing products. In addition, it will be possible to easily deploy RHEL to cloud services such as AWS, Microsoft Azure and GCP using Red Hat Cloud Access in customer subscriptions.
This relaxation of free terms and conditions does not cover all use cases using CentOS. Red Hat is working on a variety of barriers to make RHEL easier to use, and plans to announce a new program in February 2020. Related information can be found here .
U.S. government purchases smartphone location data without warrant
MSI Gaming PC with OLED Knob


A MURDER OF MYSTERIES – 20 Novels – Only $2.99! $70 off!
The second of our series of holiday bundles, A Murder of Mysteries features twenty novels of mystery and suspense by various award-winning and bestselling authors. For $2.99, you're getting twenty novels, each the first book in a continuing series, containing almost 1.5 million words in total, and a savings of more than $70 if each title was purchased separately. This bundle is only available for a limited time, so purchase your copy before it's gone.


text:
Smol wonder: A Honda CT125 inspired by Mad Max
April 12, 2021 by Chris Hunter
There's something irresistible about tiny motorcycles. According to scientists, we're drawn to objects that are smaller than usual because they pose less danger, they remind us of toys, and they give us a feeling of control.
That would explain the cultural appeal of mini marvels like Japanese Kei trucks, and the Honda Grom. And classics like the Piaggio Ape three-wheeler, originally adapted from the Vespa scooter. Plus the Super Cub, the Australian CT110 'Postie Bike' … and this Honda CT125 from Motolord in Thailand.
Motolord is run by Chayakrit 'Win' Kaewwongwan, who designs and fabricates aftermarket parts for popular local models such as the Honda Rebel. He also occasionally customizes bikes, and this CT125 'MadMax' is his latest project.
"The design concept was to customize parts while keeping the original structure," he tells us. "We replaced components without harming the frame, so the bike can go back to its original state at any time."
It's a clever transformation that made us smile the instant we first saw it. Honda calls the color 'Matte Fresco Brown' and that's what got Chayakrit thinking.
"When I saw the new CT125 for the first time in this desert color, it reminded me of the movie Mad Max," he says. "I like the style of those vehicles, and used some of them as inspiration."
The CT125 would be at home in the Australian outback: like its CT110 predecessor, it's a simple but capable workhorse. It's related to the iconic Super Cub and the specs are basic, with a 125cc single-cylinder engine and a four-speed semi-automatic 'box. But you also get modern fripperies like electric start, ABS, LED lighting and digital instumentation.
Chayakrit has added dual LED headlights mounted in a robust bracket that's effectively a bolt-on replacement part for the stock single bowl. The bracket assembly is big enough to do double duty as a small rack, and it's flanked by daytime running lights mounted to custom bars.
The tough look is mostly cosmetic at the front, but there are now crash bars to provide more practical protection. The engine gets ribbed covers, and there's a stylish custom air filter cover right under the seat, giving the CT a bit of a 'tactical' vibe.
The central spine of the underbone frame gets a matching cover too, which acts as a mounting point for luggage.
Luggage is the focus here, so there's a huge custom rack at the back, which can also act as a mounting point for a box, and there's a side rack on the left for a soft bag.
It may seem like overloading, but the CT125 is a pretty sturdy for such a compact machine: it weighs just under 260 pounds wet in the showroom, but has a 522-pound GVWR.
If the rider has stayed off the cheeseburgers, that leaves enough spare capacity for a decent camping trip. And just to be sure, Chayakrit has upgraded the rear shock to a 'Diablo' unit from K-Speed.
'MadMax' isn't going to win any drag races, but it's unlikely to leave you stranded in the middle of nowhere, either. Or break your leg if you fall off it. It's small but mighty, with go-anywhere capabilities that would shame many conventional ADV bikes.
If you're inspired by Chayakrit's approach and live in the US, grab yourself a Honda Trail 125 and get creative. It'll cost just $3,900 to ride one off the showroom floor, so you might have a little left in the bank for a light custom job …
Motolord web shop
Honda Super Cub customs


Prof. Dinesh Singh, Vice Chancellor of Delhi University visited the Royal Institute of Management in Thimphu on 24 September 2013 to discuss the role of higher education in the 21st Century. The session explored two fundamental ideas: the importance of education in instilling morality and the changing education landscape due to technology. His visit was facilitated by The Thimphu Seminars.
The importance of education in instilling morality was illustrated with various examples of how various financial crises around the world could be traced to individuals or a group of individuals who broke the moral code. Several countries took advantage of existing loopholes in the law to benefit their companies financially, without paying heed to the consequences. It is imperative that one of the primary aims of education should be instilling an inner moral compass in its students, developing in them the ability to understand the larger impact their actions may have on the world around.
The advent of technology is a precursor to traditional methods of imparting and receiving knowledge becoming obsolete. It implies more flexibility, specifically with respect to time and space. School campuses may soon be replaced by spaces such as cafes, neighbourhood parks, and individual bedrooms. Technology enables individuals to store, share, and create information within a matter of seconds. Prof. Dinesh Singh urged countries of Asia and especially Bhutan to realize this trend and reasoned how crucial future policies regarding education should be suited to this trend.


At the heart of simple living is staying home. This is so hard for most of us, because our homes are often a combination of boring, stressful, and depressing. The best way to stay at home without feeling trapped is to love being at home . This does not mean being satisfied with all your decor. It means having an emotional connection to Your home. There is no way to buy it, but here are some ideas to create it.
Make sure you own at least ten books that you love to read and are easily accessible to you in your living room. Not classics that you think you should be reading, but books that you truly love, whether they be novels or home decor books. Group them together on a shelf in the room you are most frequently in. Try to get in the habit of settling down to read instead of watching TV. It feels more productive and not so gross.
Nothing is more damaging to the budget than going out to eat for dinner all the time. The most difficult and most important part of getting dinner on the table is having a plan. Even if it is frozen pizza and carrot sticks, have that plan either written down or firmly planted in your mind. You won't feel anxious all afternoon because you have no idea what to serve for dinner, and won't be forced to waste time and money going out to get something at the last minute. Knowing what's for dinner for the whole week is very peaceful, but just having one day planned is good too.
Work as hard as you can all morning, to the point that you are maybe a little overworked. I like to set up a weekly schedule with specific things to focus on each day, but it's not necessary if it doesn't interest you. Make your bed and clean the bedrooms every morning. Do a bunch of laundry, clean the house, arrange your bookshelves. Stay busy. Then when afternoon comes, you can take a break but you won't be bored. Boredom is the enemy staying home. Getting everything done in the morning allows you to focus on dinner in the afternoon. You can turn on the radio and have a drink while you cook. You start feeling that maybe being home is fun.
Anything. A big garden, a small garden, herbs in containers, a house plant. The more things that are at your house that require care, the stronger your connection to your home. The stronger the connection to your home, the less you will want to get out all the time. Plants can be beautiful, they can be useful, but the most important thing about them is the care they take and the emotional response that creates. Maybe this sounds a bit wacky to you. Try it anyway.
Having a bunch of machines running the show does not make you feel like you want to be at home. It makes you feel like you are not really that important and might as well be out shopping. I love many of my machines: the dishwasher, vacuum, bread maker, and deep fryer are all my friends. But don't neglect the human element of your home. Everything you can do by hand at home strengthens your bond to it. Sweeping by hand, hanging your laundry, or heating water in a kettle instead of the microwave will all affect your sense of home satisfaction. Just a few things done by hand will make a difference.
Not cooking, cleaning, gardening, or laundry. Something else. I am not artistic but I am capable of creating things, and that is what I mean by creative. You can create a pretty photograph, a napkin you've sewn, or a new gallery wall. It doesn't have to mean retreating to your art studio or composing a song. Obviously completing one project a day is not realistic, but working on one every day is usually doable, even if it's just for a few minutes. Keeping up this takes you out of the consumerist mindset that tells you your main function is to buy things.
Not decorating. I don't know how to do that. I just mean taking your everyday practical spaces, and make them appealing to you. For me, this means natural materials, warm neutrals, and visual calm. For you this might mean bright colors, lots of modern art, and lots of energy. In my shower and by my sink I've switched everything to wooden brushes and clear bottles, and now those practical spaces are uplifting instead of soul crushing. Try making your cabinets and fridge pretty when you open them. It is depressing to pull a drawer open and see a jumbled mess. This is hard for me and I have to make a conscious effort at this. But when I open a door and find everything looking pretty and organized, it's like a little gift to myself.
What do you see when you look out your windows? Your old deck furniture and some cracking planters? The back of someone else's house? A bunch of outdoor toys sitting around? Perhaps the curtains are always closed? Change it, as much as you can, to something you'll enjoy. This might mean putting some flowerpots out. It might mean making your kids put their outdoor toys away every time they are done. Maybe a bird feeder would help, or even just bird seed scattered on the ground every morning. Looking out the window should be a happy thing.
This is the different between a home and a prison. Open the curtains unless it is night. Open the windows whenever you can. Its very nice to air out your bedrooms early in the morning. If it's cold out, shut the bedroom door so cold air doesn't rush through the house. Find the sunniest corner of your house and put a chair there. Spend the mornings in places that face east and the afternoons in places that face west. It's good for you.
Rearrange your furniture to make a conversation grouping instead of facing the TV. (I'm super guilt of this) Style your bookshelves by mixing in some picture frames and vases that you already have. There is plenty you can do to mix things around the house without spending any money. Simply rearranging throw pillows, blankets, frames, and fresh flowers makes a big impact. Keep in mind many small things can look like clutter, but a few bigger ones make more of a statement.
When you take care of your house it will take care of you. Of course everyone needs to get out every now and then, but hopefully these idea will make you feel connected to your home and make you want to be there more.
This is a great post, and it is so true! Love these tips – going to absolutely work on implementing them! Thanks for the inspiration!
I'm definitely a change things up kind of gal, but it stresses my husband… go figure. I love being at home and I think that's because I follow most of what you have above. The morning chores is a game changer though!
Love these ideas! We are new empty nesters and after our twin grandsons are gone, we are ready to chill! We keep them 5 days-8hours a day! We now enjoy just being home too!
You have motivated me to start that herb garden! I completely failed with my first one. I'm going to bo it again!
Yes!! This is such a great topic! I read a blog many many years ago about a woman who made her home into a respite from the world. She didn't have a lot of money but she was determined to make it cozy and beautiful regardless. It inspires me so much and that's what I've tried to do as well. Now I have the opposite problem, I never want to leave! Lol!
Haha, yes! If I didn't have kids in activities I would truly never go anywhere. Homebodies unite!
A lovely read, and it reminded me to take something out of the freezer for dinner tonight! Now that I am home all the time I am trying to find a god schedule for myself and this was a good start.
Great thoughts! I've spent many years making our home a cozy haven away from the world. I believe home should be place you don't need to take a vacation from. So each room becomes it's own welcoming space. It's always a work in progress because our needs and tastes change over time. Thank you for all the interesting ideas. I love bright airy spaces that invite a person to kick off their shoes and get comfy!
I truly love to be home. I have had the "make your home your favorite vacation spot" mentality for years. I also want my home to be a destination spot for my adult children. We are well on our way to always being on vacation!
Love that kym. I definitely struggle with this because sometimes I just want to get out! But I think part of that is having young children.


Like all other businesses and particularly other on-line businesses School Style gets targeted by those looking to defraud us using stolen credit/ debit card details.
This costs us money and in order to minimise these costs and to keep our prices to genuine customers as low as possible we have introduced a ZERO TOLERANCE approach to fraud.
During the check-out process you will be asked to enter your card details. This is a secure process and School Style never see these details. Instead they are communicated securely and directly to an independent payment provider who validates the details yuo provide with your bank/ card provider.
We then receive a report providing information regarding the validity of the transaction and the card holder including a RISK SCORE.
Any transaction that receives a high RISK SCORE will be subject to further checks before any goods are sent out. If we do not receive reassurance on the validity of the payment then the order will be cancelled.
Any phone number, address, email address or card that is regarded as high risk in the banking system will return a HIGH RISK score.


Hello Vamerites! Welcome to the #VamersChristmas Nintendo hamper competition page.
Nintendo Distributor South Africa have been generous enough to sponsor over R7500 in prizes for our very first #VamersChristmas. We are incredibly grateful for their support and cannot thank them enough for helping make our first #VamersChristmas a reality!
1 x Nintendo Super Mario hat.
BONUS: One randomly selected Nintendo hamper winner will also receive 1 x Super Mario Odyssey for Nintendo Switch.
In order to enter our #VamersChristmas Nintendo hamper competition, you need to watch the video above and then follow either Option A or B to enter.
Click here to go to the Vamers Facebook page.
Like the Vamers Facebook page.
Record a video of yourself doing your best "It's me, Mario" impression (watch the video above for an example). Please also include your favourite Nintendo memory in the video.
Send the video you have made to us via our Facebook Page. Simply hit the "Message" button at the top of the page.
If you are not comfortable with recording or submitting a video, then we have a second way to enter this competition. With that said, please note that video entries will be weighted higher/given preference in this competition.
Who bops Hans in the head with the Yellow Arma boxing glove?
If you know the answer, simply fill in the form below to enter the competition.
Bonus: If you like, share this post on social media to spread the Vamers love (the more you share, the better our competitions become)!
The #VamersChristmas Nintendo competition will be open for entry from 4 – 18 December 2017. This way, we will hopefully be able to get the prizes to the winning Vamerites just in time for Christmas.
Once again, a big thank you to Nintendo Distributor South Africa, they have been absolutely stellar, and a special thank you to you, our readers, viewers and fans.


The St. Benedict the Moor Fraternity of the Secular Franciscans invites everyone to acelebration of the Feast of Divine Mercy next Sunday, April 23, from 2:45 to 4:30 PM atthe lower church.
The celebration will start with the recitation of the concluding Novena prayer. At 3:00 PM, the modern musical version of the Chaplet will be played.
You can then attend the regular Sunday Mass in the upper church at 5:00 or 6:15 PM.
For inquiries,please call Vicky Vinuya at 347-653-8133.