text:
\section{Introduction}

	In the last few decades, a significant amount of research has been invested in studying the curse of dimensionality of a distance measure. We have now a good understanding of the curse in terms of (i) concentration of measure \citep{Talagrand} and its consequence of being unable to find the nearest neighbor \citep{Beyer:1999}, and (ii) hubness \citep{HubsInSpace-JMLR-2010}.

	Despite this advancement, breaking the curse is still elusive. The central question remains open:   \textit{is it possible to find the single nearest neighbor of a query in high dimensions?}

	The answer to this question is negative, based on the current analyses on distance \citep{Beyer:1999,Density-based-Indexing-KDD1999,Pestov}. Rather than finding the single nearest neighbor of a query, the issue has been diverted to finding all data points belonging to the same cluster as the query, in a distribution with well-separated clusters \citep{Beyer:1999,Density-based-Indexing-KDD1999}. These nearest neighbors are `meaningful' for the purpose of separating different clusters in a dataset. But the (single) nearest neighbor, in the true sense of the term, cannot be obtained using a distance measure, even in the special distribution of well-separated clusters described above \citep{Beyer:1999}.

	Unlike many existing measures, a recently introduced Isolation Kernel \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019} is derived directly from a finite dataset without learning and has no closed-form expression.
	We show here that Isolation Kernel is not affected by the concentration effect, and it works well in high dimensions; and it does not need to use low intrinsic dimensions to explain why it works well in high dimensions.

	Our theoretical analysis focuses on \textit{the ability of a feature map produced by kernel evaluation using a finite dataset to distinguish two distinct points  in high dimensions} (\textbf{distinguishability} or \textbf{indistinguishability} hereafter). A kernel is said to have indistinguishability if its feature map is unable to distinguish two distinct points. This is manifested as being unable to find the single nearest neighbor of a query because there are many nearest neighbors which cannot be distinguished from each other, especially in high dimensions.

	Our contributions are:
	\vspace{-1mm}
	\renewcommand{\labelenumi}{\Roman{enumi}}
	\begin{enumerate}[itemsep=1ex, leftmargin=5mm]
		\item  Revealing that Isolation Kernel (IK) is the only measure that is provably free from the curse of dimensionality,
		compared with existing metric-based Lipschitz continuous kernels.

		\item Determining three key factors in IK that lead to breaking the curse of dimensionality.

		(a) Space partitioning using an isolation mechanism is the key ingredient in measuring similarity between two points in IK.
		(b) The probability of a point falling into a partition

		is independent of data distribution, the distance measure used to create the partitions and the data dimensions.
		(c) The unique feature map of IK has its dimensionality linked to a concatenation of these partitionings.

		\item Proving that IK's unique feature map produced by a finite dataset has distinguishability,

		independent of the number of data dimensions and data distribution.

		Our theorem suggests that increasing the number of partitionings (i.e., the dimensionality of the feature map) leads to increased distinguishability.

		\item Verifying that IK
		breaks the curse of dimensionality in two sets of experiments. First, IK finds the single nearest neighbor in high dimensions; while many existing measures fail under the same condition. Second, IK enables consistently effective indexing, spectral \& density peaks clustering, SVM classification and t-SNE visualization in both low and high dimensions.

		\item Showing that Euclidean distance, Gaussian and linear kernels have a mixed bag of poor and good results in high dimensions, reflecting the current understanding of existing measures.
	\end{enumerate}

	\section{Related work}

	\subsection{The curse of dimensionality}
	\label{sec_curse}
	One of the early investigations of the curse of dimensionality is in terms of concentration of measure \cite{Mil_man_1972,Talagrand}. \citet{Talagrand} summarises the intuition behind the concentration of measure

	as follows: ``a random variable that depends (in a `smooth' way) on the influence of many independent
	random variables (but not too much on any of them) is essentially constant.''

	Translating this statement in the context of a high dimensional space, a distance measure which depends on many independent dimensions (but not too much on any of them) is essentially constant.

	\citet{Beyer:1999} analyze the conditions under which nearest neighbor is `meaningful' when a distance measure is employed

	in high dimensions.
	A brief summary of the conditions in high dimensions is given as follows:
	\renewcommand{\labelenumi}{\alph{enumi})}
	\begin{enumerate}
		\item Finding the (single) nearest neighbor of a query is not meaningful because every point from the same cluster in the database has approximately the same distance to the query. In other words, the variance of distance distribution within a cluster approaches zero as the number of dimensions increases to infinity.
		\item Despite this fact, finding the exact match is still meaningful.
		\item The task of retrieving all points belonging to the same cluster as the query is meaningful because although variance of distances of all points within the cluster is zero, the distances of this cluster to the query are different from those of another cluster---making a distinction between clusters possible.
		\item The task of retrieving the nearest neighbor of a query, which does not belong to any of the clusters in the database, is not meaningful for the same reason given in (a).
	\end{enumerate}
	\citet{Beyer:1999} reveal that finding (non-exact match) nearest neighbors is `meaningful' only if the dataset has clusters (or structure), where the nearest neighbors refer to any/all points in a cluster rather than a specific point which is the nearest among all points in the dataset. In short, a distance measure cannot produce the `nearest neighbor' in high dimensions, in the true sense of the term. Hereafter the term `nearest neighbor' is referred to the single nearest neighbor in a dataset, not many nearest neighbors in a cluster.

	\citet{Beyer:1999} describe the notion of instability of a distance measure as follows: ``{\em A nearest neighbor query is unstable for a given $\epsilon$ if the distance from the query point to most data points is less than (1 + $\epsilon$) times the distance from the query point to its nearest neighbor.}''

	Current analyses on the curse of dimensionality focus on distance measures \citep{Beyer:1999,NN-HighDim-VLDB-2000,Aggarwal-2001,HubsInSpace-JMLR-2010}. While random projection preserves structure in the data, it still suffers the concentration effect \citep{Ata-Kaban-2011}.
	Current methods dealing with high dimensions are: dimension reduction \citep{PCA-Book2002,Hinton2008Visualizing}; suggestions to use non-metric distances, e.g., fractional distances \citep{Aggarwal-2001}; and angle-based measures, e.g., \citep{Angle-BasedAD-KDD2008}. None has been shown to break the curse.

	Yet, the influence of the concentration effect in practice is less severe than suggested mathematically \citep{Concentration-Fractionaldistances}. For example,  k-nearest neighbor (kNN) classifier still yields reasonable high accuracy in high dimensions \citep{Aryal2017}; while the concentration effect would have rendered kNN producing random prediction. One possible explanation of this phenomenon is that the high dimensional datasets employed have low intrinsic dimensions (e.g., \citep{Concentration-Fractionaldistances,LID-NIPS2011}.)

	In a nutshell, existing works center around reducing the effect of concentration of measures,

	knowing that the  nearest neighbor could not be obtained in high dimensions.
	A saving grace is that many high dimensional datasets used in practice have low intrinsic dimensions---leading to a significantly reduced concentration effect.

	Our work shows that the concentration effect can be eliminated to get the  nearest neighbor in high dimensions using a recently introduced measure called Isolation Kernel \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019}, without the need to rely on low intrinsic dimensions. While three existing measures have a mixed bag of poor and good results in high dimensions, Isolation Kernel defined by a finite dataset yields consistently good results in both low and high dimensions.

	\subsection{Isolation Kernel}

	Unlike commonly used distance or kernels, Isolation Kernel \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019} has no closed-form expression, and it is derived directly from a given dataset without learning; and the similarity between two points is computed based on the partitions created in data space.

	The key requirement of Isolation Kernel (IK) is a space partitioning mechanism which isolates a point from the rest of the points in a sample set. This can be achieved in several ways, e.g., isolation forest \citep{liu2008isolation,ting2018IsolationKernel}, Voronoi Diagram \citep{IsolationKernel-AAAI2019} and isolating hyperspheres \citep{IDK-KDD2020}.
	Isolation Kernel \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019} is defined as follows.

	Let $\mathbb{H}_\psi(D)$ denote the set of all admissible partitionings $H$ derived from a given finite dataset $D$, where each $H$ is derived from $\mathcal{D} \subset D$; and each point in $\mathcal{D}$ has the equal probability of being selected from $D$; and $|\mathcal{D}|=\psi$.

	Each partition $\theta[{\bf z}] \in H$ isolates a point ${\bf z} \in \mathcal{D}$ from the rest of the points in $\mathcal{D}$. The union of all  partitions of each partitioning $H$ covers the entire space.

	\begin{definition}
		Isolation Kernel of any two points ${\bf x},{\bf y} \in \mathbb{R}^d$ is defined to be
		the expectation taken over the probability distribution on all partitionings $H \in \mathds{H}_\psi(D)$ that both ${\bf x}$ and ${\bf y}$  fall into the same isolating partition $\theta[{\bf z}] \in H$, where ${\bf z} \in \mathcal{D} \subset D$, $\psi=|\mathcal{D}|$:
		\begin{eqnarray}
			K_\psi({\bf x},{\bf y}\ |\ D)  =  {\mathbb E}_{\mathds{H}_\psi(D)} [\mathds{1}({\bf x},{\bf y} \in \theta[{\bf z}]\ | \ \theta[{\bf z}] \in H)],

			\label{eqn_kernel}
		\end{eqnarray}
	\end{definition}
	\noindent
	where $\mathds{1}(\cdot)$ is an indicator function.

	In practice, Isolation Kernel $K_\psi$ is constructed using a finite number of partitionings $H_i, i=1,\dots,t$, where each $H_i$ is created using randomly subsampled $\mathcal{D}_i \subset D$; and $\theta$ is a shorthand for $\theta[{\bf z}]$:
	\begin{eqnarray}
		K_\psi({\bf x},{\bf y}\ |\ D)   & \simeq &  \frac{1}{t} \sum_{i=1}^t   \mathds{1}({\bf x},{\bf y} \in \theta\ | \ \theta \in H_i) \nonumber\\
		& = &   \frac{1}{t} \sum_{i=1}^t \sum_{\theta \in H_i}   \mathds{1}({\bf x}\in \theta)\mathds{1}({\bf y}\in \theta).
		\label{Eqn_IK}
	\end{eqnarray}
	This gives a good approximation of $K_\psi({\bf x},{\bf y}\ |\ D)$ when $|D|$ and $t$ are sufficiently large to ensure that the ensemble is obtained from a sufficient number of mutually independent $\mathcal{D}_i, i=1,\dots,t$.

	Given $H_i$, let $\Phi_i({\bf x})$ be a $\psi$-dimensional binary column (one-hot) vector representing all $\theta_j \in H_i$, $j=1,\dots,\psi$; where ${\bf x}$ must fall into only one of the $\psi$ partitions.

	The $j$-component of the vector is:
	$\Phi_{ij}({\bf x})=\mathds{1}({\bf x}\in \theta_j\ |\ \theta_j\in H_i)$. Given $t$ partitionings, $\Phi({\bf x})$ is the concatenation of $\Phi_1({\bf x}),\dots,\Phi_t({\bf x})$.

	\begin{prop}
		\label{prop:featureMap}
		\textbf{Feature map of Isolation Kernel.}
		The feature mapping $\Phi: {\bf x}\rightarrow \mathbb \{0,1\}^{t\times \psi}$ of $K_\psi$, for point ${\bf x} \in \mathbb{R}^d$, is a vector that represents the partitions in all the partitionings $H_i\in \mathds{H}_\psi(D)$, $i=1,\dots,t$ that contain ${\bf x}$; where ${\bf x}$ falls into only one of the $\psi$ partitions in each partitioning $H_i$. Then, $\parallel {\Phi}({\bf x}) \parallel\ = \sqrt{t}$ holds, and Isolation Kernel always computes its similarity using its feature map as:
		\[
		K_\psi({\bf x},{\bf y}\ |\ D)   \simeq  \frac{1}{t} \left< {\Phi}({\bf x}|D), {\Phi}({\bf y}|D) \right>.
		\]

	\end{prop}

	Let $\mathbbmtt{1}$ be a shorthand of $\Phi_i({\bf x})$ such that $\Phi_{ij}({\bf x})=1$ and $\Phi_{ik}({\bf x})=0, \forall k \neq j$ of any $j \in [1,\psi]$.

	The feature map
	${\Phi}({\bf x})$ is sparse because it has exactly $t$ out of $t \psi$ elements having 1 and the rest are zeros. This gives $\parallel {\Phi}({\bf x}) \parallel\ = \sqrt{t}$.
	Note that  while every point has $\parallel {\Phi}({\bf x}) \parallel\ = \sqrt{t}$ and $\Phi_i({\bf x}) = \mathbbmtt{1}$ for all $i \in [1,t]$, they are not all the same point.

	Note that Isolation Kernel is a positive definite kernel with probability 1 in the limit of $t \rightarrow \infty$ because its Gram matrix  is full rank as $\Phi(x)$ for all points $x \in D$ are mutually independent (see \cite{IDK-KDD2020} for details.) In other words, the feature map coincides with a reproducing kernel Hilbert space (RKHS) associated with the Isolation Kernel.

	This finite-dimensional feature map has been shown to be the key in leading to fast runtime in kernel-based anomaly detectors \citep{IDK-KDD2020} and enabling the use of fast linear SVM \citep{IsolationSetKernel,IK-XFactor-2019}.

	IK has been shown to be better than Gaussian and Laplacian kernels in SVM classification \citep{ting2018IsolationKernel}, better than Euclidean distance in density-based clustering \citep{IsolationKernel-AAAI2019}, and better than Gaussian kernel in kernel-based anomaly detection \citep{IDK-KDD2020}.

	IK's superiority has been attributed to its data dependent similarity, given in the following lemma.

	Let $D \subset \mathcal{X}_D \subseteq {\mathbb R}^d$ be a dataset sampled from an unknown distribution $\mathcal{P}_D$ where $\mathcal{X}_D$ is the support of $\mathcal{P}_D$
	on ${\mathbb R}^d$; and
	let $\rho_D({\bf x})$ denote the density of $\mathcal{P}_D$ at point ${\bf x} \in \mathcal{X}_D$, and $\ell_p$ be the $\ell_p$-norm.
	The unique characteristic of Isolation Kernel \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019} is:

	\begin{lem}\label{lem_characteristic}
		Isolation Kernel $K_\psi$ has the data dependent characteristic:
		\vspace{-2mm}
		\begin{equation}
			K_\psi( {\bf x},{\bf y}\ |\ D) > K_\psi( {\bf x}',{\bf y}'\ |\ D)\nonumber
		\end{equation}
		for $\ell_p({\bf x}-{\bf y})\ =\-\ell_p({\bf x}'-{\bf y}')$,
		$\forall {\bf x},{\bf y} \in \mathcal{X}_\mathsf{S}$ and $\forall {\bf x}',{\bf y}' \in  \mathcal{X}_\mathsf{T}$

		subject to $\forall {\bf z}\in \mathcal{X}_\mathsf{S}, {\bf z}'\in \mathcal{X}_\mathsf{T}, \ \rho_D({\bf z})<\rho_D({\bf z}')$.
	\end{lem}

	As a result, $K_\psi( {\bf x},{\bf y}\ |\ D)$ is not translation invariant, unlike the data independent Gaussian and Laplacian kernels.

	We show in Section \ref{sec_distinguishability} that this feature map is instrumental in making IK the only measure that breaks the curse,  compared with existing metric-based Lipschitz continuous kernels.

	\section{Analyzing the curse of dimensionality in terms of (in)distinguishability}
	\label{sec_break-curse}
	In this section, we theoretically show that IK does not suffer from the concentration effect in any high dimensional data space;

	while metric-based Lipschitz continuous kernels, including  Gaussian and Laplacian kernels, do.

	We introduce the notion of indistinguishability of two distinct points in a feature space $\mathcal{H}$ produced by kernel evaluation
	using a finite dataset

	to analyze the curse of dimensionality. Let $\Omega \subset \mathbb{R}^d$ be a data space, $D \subset \Omega$ be a finite dataset, and $\mathcal{P}_D$ be the probability distribution that generates $D$. The support of $\mathcal{P}_D$, denoted as $\mathcal{X}_D$, is an example of $\Omega$.

	Given two
	distinct points ${\bf x}_a,{\bf x}_b \in \Omega$ and their feature vectors
	$\phi({\bf x}_a), \phi({\bf x}_b) \in \mathcal{H}_\kappa$ produced by a kernel $\kappa$ and a finite dataset $D = \{{\bf x}_i \in \mathbb{R}^d \; | \; i=1, \dots, n\}$ as $\phi({\bf x}_a) = [\kappa({\bf x}_a,{\bf x}_1),\dots,\kappa({\bf x}_a,{\bf x}_n)]^\top$ and
	$\phi({\bf x}_b) = [\kappa({\bf x}_b,{\bf x}_1),\dots,\kappa({\bf x}_b,{\bf x}_n)]^\top$.

	\begin{definition}
		$\mathcal{H}_\kappa$ has \textbf{indistinguishability} if
		there exists some $\delta_L \in (0,1)$ such that
		the probability of $\phi({\bf x}_a) = \phi({\bf x}_b)$ is lower bounded by $\delta_L$ as follows:
		\begin{equation}
			P(\phi({\bf x}_a) = \phi({\bf x}_b)) \geq \delta_L. \label{indist}
		\end{equation}
	\end{definition}

	On the other hand, given two

	feature vectors
	$\Phi({\bf x}_a), \Phi({\bf x}_b) \in \mathcal{H}_K$ produced by a kernel $K$ and a finite dataset $D$.

	\begin{definition}
		$\mathcal{H}_K$  has \textbf{distinguishability} if there exists some $\delta_U \in (0,1)$ such that $P(\Phi({\bf x}_a) = \Phi({\bf x}_b))$ is upper bounded by $\delta_U$ as follows:
		\begin{equation}
			P(\Phi({\bf x}_a) = \Phi({\bf x}_b)) \leq \delta_U. \label{eqn_distinguishability}
		\end{equation}
	\end{definition}
	Note that these definitions of indistinguishability and distinguishability are rather weak. In practice, $\delta_L$ should be close to 1 for strong indistinguishability, and $\delta_U$ should be far less than 1 for strong distinguishability.

	In the following, we first show in Section \ref{sec_indistinguishability} that a feature space $\mathcal{H}_\kappa$ produced by any metric-based Lipschitz
	continuous kernel $\kappa$ and a finite dataset $D$ has indistinguishability when the number of dimensions $d$ of the data space is very large.
	Then, in Section \ref{sec_distinguishability}, we show that a feature space $\mathcal{H}_K$ procudd by Isolation Kernel $K$ implemented using the Voronoi diagram \citep{IsolationKernel-AAAI2019}
	has distinguishability for any $d$.

	\subsection{$\mathcal{H}_\kappa$ of a metric-based Lipschitz
		continuous kernel $\kappa$ has indistinguishability}
	\label{sec_indistinguishability}

	Previous studies have analyzed the concentration
	effect in high dimensions~\citep{Pestov, Gromov, Ledoux}. Let a triplet
	$(\Omega, m, F)$ be a probability metric space where $m: \Omega \times \Omega \mapsto \mathbb{R}$
	is a metric, and
	$F: 2^\Omega \mapsto \mathbb{R}$ is a probability measure.  $\ell_p$-norm is an
	example of $m$. $\Omega$ is the support of $F$, and thus $F$ is assumed to have non-negligible probabilities over the entire $\Omega$, i.e., points drawn from $F$ are widely distributed over the entire data space.

	Further, let $f: \Omega \mapsto \mathbb{R}$ be a Lipschitz continuous function, i.e., $|f({\bf x}_a) - f({\bf x}_b)| \leq m({\bf x}_a,{\bf x}_b), \forall {\bf x}_a,{\bf x}_b \in \Omega$;
	and $M$ be a median of $f$ defined as:
	\begin{eqnarray}

		F(\{{\bf x} \in \Omega \; | \; f({\bf x}) \leq M\}) = F(\{{\bf x} \in \Omega \; | \; f({\bf x}) \geq M\}).\nonumber
	\end{eqnarray}
	Then, the following proposition holds~\citep{Pestov, Gromov}.
	\begin{prop}\label{prop1}
		$F(\{{\bf x} \in \Omega | f({\bf x}) \in [M-\epsilon,M+\epsilon]\}) \geq 1-2\alpha(\epsilon)$ holds for any $\epsilon>0$, where
		$\alpha(\epsilon) = C_1 e^{-C_2 \epsilon^2 d}$ with two constants $0 < C_1 \leq \frac{1}{2}$ and $C_2 > 0$.
	\end{prop}

	For our analysis on the indistinguishability of a feature space $\mathcal{H}_\kappa$ associated with any metric-based Lipschitz continuous kernel, we reformulate this proposition
	by replacing $f({\bf x})$ and $M$ with $m({\bf x},{\bf y})$ and $M({\bf y})$, respectively, for
	a given ${\bf y} \in \Omega$. That is:
	\begin{eqnarray}
		&&\hspace*{-5mm} |m({\bf x}_a,{\bf y}) - m({\bf x}_b,{\bf y})| \leq m({\bf x}_a,{\bf x}_b), \forall {\bf x}_a,{\bf x}_b \in \Omega, \mbox{ and}\nonumber\\
		&&\hspace*{-5mm}F(\{{\bf x} \in \Omega \; | \; m({\bf x},{\bf y}) \leq M({\bf y})\}) = F(\{{\bf x} \in \Omega \; | \; m({\bf x},{\bf y}) \geq M({\bf y})\}).\nonumber
	\end{eqnarray}
	The inequality in the first formulae always holds because of the triangular inequality of $m$.
	Then, we obtain the following corollary:
	\begin{col}\label{col1}
		Under the same condition in Proposition~\ref{prop1}, the inequality $F(A_\epsilon({\bf y})) \geq 1- 2\alpha(\epsilon)$ holds for any ${\bf y} \in \Omega$
		and any $\epsilon > 0$, where
		$A_\epsilon({\bf y}) = \{{\bf x} \in \Omega \; | \; m({\bf x},{\bf y}) \in [M({\bf y})-\epsilon, M({\bf y})+\epsilon]\}$.
	\end{col}

	This corollary represents the  concentration effect where almost all
	probabilities of the data are concentrated in the limited area $A_\epsilon({\bf y})$.
	It provides an important fact on the indistinguishability of two distinct points using
	a class of metric-based Lipschitz continuous kernels such as Gaussian kernel:
	\begin{equation}
		\kappa({\bf x},{\bf y}) = f_\kappa(m({\bf x},{\bf y})),\nonumber
	\end{equation}
	where $f_\kappa$ is Lipschitz continuous and monotonically decreasing for $m({\bf x},{\bf y})$.
	\begin{lem}\label{lem1}
		Given two distinct points ${\bf x}_a$, ${\bf x}_b$ i.i.d. drawn from $F$ on $\Omega$
		and a data set $D = \{{\bf x}_i \in \mathbb{R}^d \; | \; i=1, \dots, n\} \sim G^n$
		where every ${\bf x}_i$ is i.i.d drawn from any probability distribution $G$ on
		$\Omega$, let the feature vectors of ${\bf x}_a$ and ${\bf x}_b$ be
		$\phi({\bf x}_a) = [\kappa({\bf x}_a,{\bf x}_1),\dots,\kappa({\bf x}_a,{\bf x}_n)]^\top$ and
		$\phi({\bf x}_b) = [\kappa({\bf x}_b,{\bf x}_1),\dots,\kappa({\bf x}_b,{\bf x}_n)]^\top$ in a feature space $\mathcal{H}_\kappa$.  The following holds:

		\begin{equation}
			P\left(\ell_p(\phi({\bf x}_a)-\phi({\bf x}_b)) \leq 2L\epsilon n^{1/p} \right) \geq (1-2\alpha(\epsilon))^{2n}, \nonumber
		\end{equation}
		for any $\epsilon > 0$, where $\ell_p$ is an $\ell_p$-norm on $\mathcal{H}_\kappa$, and
		$L$ is the Lipschitz constant of $f_\kappa$.

	\end{lem}

	\begin{thm}\label{thm1}
		Under the same condition as Lemma~\ref{lem1}, the feature space $\mathcal{H}_\kappa$
		has indistinguishability in the limit of $d \rightarrow \infty$.

	\end{thm}

	This result implies that the feature space $\mathcal{H}_\kappa$ produced by any finite dataset and any metric-based
	Lipschitz continuous kernels such as Gaussian and Laplacian kernels have indistinguishability
	when the data space has a high number of dimensions $d$. In other words, these kernels suffer
	from the concentration effect.

	\subsection{$\mathcal{H}_K$ of Isolation Kernel $K$ has distinguishability}
	\label{sec_distinguishability}
	We show that the feature map of Isolation Kernel implemented using Voronoi diagram \citep{IsolationKernel-AAAI2019}, which is not a metric-based
	Lipschitz continuous kernel, has distinguishability.

	We derive Lemma \ref{lem2} from the
	fact given in \cite{Fukunaga}, before providing our theorem.
	\begin{lem}\label{lem2}
		Given ${\bf x} \in \Omega$ and a data set
		$\mathcal D = \{ {\bf z}_1, \dots, {\bf z}_\psi \} \sim G^\psi$ where
		every ${\bf z}_j$ is i.i.d. drawn from any probability distribution $G$ on
		$\Omega$ and forms its Voronoi partition $\theta_j \subset \Omega$, the probability that ${\bf z}_j$ is the nearest neighbor
		of ${\bf x}$ in $\mathcal D$ is given as: $P({\bf x} \in \theta_j) = 1/\psi$, for every $j=1,\dots,\psi$.

	\end{lem}
	This lemma points to a simple but nontrivial result that
	$P({\bf x} \in \theta_j)$
	is independent of $G$, $m({\bf x},{\bf y})$ and data dimension $d$.

	\begin{thm}\label{thm2}
		Given two distinct points ${\bf x}_a$, ${\bf x}_b$ i.i.d. drawn from $F$ on $\Omega$
		and ${\mathcal D}_i = \{ {\bf z}_1, \dots, {\bf z}_\psi \} \sim G^\psi$ defined in
		Lemma~\ref{lem2}, let the feature vectors of ${\bf x}_a$ and ${\bf x}_b$ be $\Phi({\bf x}_a)$ and $\Phi({\bf x}_b)$

		in a feature space $\mathcal{H}_K$ associated with Isolation Kernel $K$, implemented using Voronoi diagram, as given in Proposition \ref{prop:featureMap}.

		Then the following holds:
		\[
		P(\Phi({\bf x}_a)=\Phi({\bf x}_b)) \leq \cfrac{1}{\psi^t},
		\]
		and $\mathcal{H}_K$  always has strong distinguishability for large $\psi$ and $t$.

	\end{thm}

	Proofs of Lemmas \ref{lem1} \& \ref{lem2} and Theorems \ref{thm1} \& \ref{thm2} are given in Appendix \ref{sec_A_Proofs}.

	In summary, \textbf{the IK  implemented using Voronoi diagram is free from the curse of dimensionality for any probability distribution}.

	\subsection{The roles of  $\psi$ \& $t$ and the time complexity of Isolation Kernel}
	The sample size (or the number of partitions in one partitioning) $\psi$ in IK has a function similar to the bandwidth parameter in Gaussian kernel, i.e., the higher $\psi$ is, the sharper the IK distribution \citep{ting2018IsolationKernel} (the small the bandwidth, the sharper the Gaussian kernel distribution.) In other words, $\psi$ needs to be tuned for a specific dataset to produce a good task-specific performance.

	The number of partitionings $t$ has three roles. First, the higher  $t$ is, the better Eq \ref{Eqn_IK} is in estimating the expectation described in Eq \ref{eqn_kernel}. High $t$ also leads to low variance of the estimation. Second, with its feature map, $t$ can be viewed as IK's  user-definable effective number of dimensions in Hilbert space. Third, Theorem~\ref{thm2} reveals that  increasing $t$ leads to increased distinguishability. The first two roles were uncovered in the previous studies \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019,IDK-KDD2020}. We reveal the last role here in Theorem \ref{thm2}. These effects can be seen in the experiment reported in Appendix \ref{sec_partitiongs}.

	In summary, \textbf{IK's feature map, which has its dimensionality linked to distinguishability, is unique among existing measures}. In contrast, Gaussian kernel (and many existing metric-based kernels) have a feature map with intractable dimensionality; yet, they have indistinguishability.

	\textbf{Time complexity}:
	IK, implemented using the Voronoi diagram, has time complexity $O(ndt\psi)$ to convert $n$  points in data space to $n$ vectors in its feature space. Note that each $\mathcal{D}$ implemented using one-nearest-neighbor produces a Voronoi diagram implicitly, no additional computation is required to build the Voronoi diagram explicitly (see \citet{IsolationKernel-AAAI2019} for details.) In addition, as this implementation is amenable to acceleration using parallel computing, it can be reduced by a factor of $w$ parallelizations to $O(\frac{n}{w}dt\psi)$.
	The readily available finite-dimensional feature map of IK enables a fast linear SVM to be used. In contrast, Gaussian kernel (GK) must use a slow nonlinear SVM. Even adding the IK's feature mapping time, SVM with IK still runs up to two orders of magnitude faster than SVM with GK. See Section \ref{sec_traditional_tasks}  for details.

	\section{Empirical verification}
	\label{sec_experiments}
	We verify that IK breaks the curse of dimensionality by conducting two experiments.
	In Section~\ref{sec_instability}, we verify the theoretical results in terms of instability of a measure, as used in a previous study of the concentration effect \citep{Beyer:1999}. This examines the (in)distinguishability of linear, Gaussian and Isolation kernels.
	In the second experiment in Section \ref{sec_traditional_tasks}, we explore the impact of IK having distinguishability in three tasks:  ball tree indexing \citep{omohundro1989five}, SVM classification \citep{CC01a} and t-SNE visualization \citep{Hinton2008Visualizing}.

	\begin{figure*}[t]
		\centering

		\begin{subfigure}[b]{0.245\textwidth}
			\centering
			\includegraphics[width=1.5in]{cluster1.png}
			\caption{Dataset used}
		\end{subfigure}

		\begin{subfigure}[b]{0.245\textwidth}
			\centering
			\includegraphics[width=1.6in]{GKIKvdmcen1.png}
			\caption{Concentration effect}
		\end{subfigure}
		\begin{subfigure}[b]{0.245\textwidth}
			\centering
			\includegraphics[width=1.6in]{GKIKLKb.png}
			\caption{${\bf q}_i$: between 2 clusters}
		\end{subfigure}
		\begin{subfigure}[b]{0.245\textwidth}
			\centering
			\includegraphics[width=1.6in]{GKIKLKcen.png}
			\caption{${\bf q}_c$: sparse cluster center}
		\end{subfigure}

		\caption{The instability of a measure $\kappa$: Gaussian kernel (GK) and Linear kernel (LK) versus IK. The dataset used has 1,000 data points per cluster: the number of dimensions is increased from 10 to 10,000.

			Query ${\bf q}_c$ is used in subfigure (b).

			$\epsilon=0.005$ is used in  subfigures (c) \& (d).

		}
		\label{fig_std-mean}
	\end{figure*}

	\begin{table*}[t]
		\caption{The instability of a measure.

			The dataset shown in Figure \ref{fig_std-mean}(a) is used here. $\epsilon=0.005$.}
		\label{tbl_SNN_AG_IK}
		\centering
		\begin{tabular}{cc|cc}
			\hline
			\multicolumn{2}{c|}{SNN, AG and IK} & \multicolumn{2}{c}{$\ell_p$-norm for $p=0.1,0.5$ \& $2$ } \\ \hline
			${\bf q}_i$: between 2 clusters & ${\bf q}_c$: sparse cluster center & ${\bf q}_i$: between 2 clusters & ${\bf q}_c$: sparse cluster center\\ \hline
			\includegraphics[width=1.3in]{IKSNN2AGcen005.png} &
			\includegraphics[width=1.3in]{IKSNN2AGspa005.png} &
			\includegraphics[width=1.3in]{lpcen.png} &    \includegraphics[width=1.3in]{lpspa.png}

			\\\hline

		\end{tabular}
	\end{table*}

	\subsection{Instability of a measure}
	\label{sec_instability}
	The concentration effect is assessed in terms of the variance of measure distribution $F_{m,d}$  wrt the mean of the measure, i.e., $var \left( \frac{F_{m,d}}{\mathbb{E}[F_{m,d}]} \right)$, as the number of dimensions $d$ increases,

	based on a measure $m({\bf x},{\bf y}) = 1 - \kappa({\bf x},{\bf y})$.
	A measure is said to have the concentration effect if the variance of the measure distribution in dataset $D$ approaches zero as $d \rightarrow \infty$.

	Following \cite{Beyer:1999}, we use the same notion of instability of a measure, as a result of a nearest neighbor query, to show the concentration effect. Let $m({\bf q}|D) = \min_{{\bf y} \in D} 1- \kappa({\bf q},{\bf y})$ be the distance as measured by $\kappa$ from query ${\bf q}$ to its nearest neighbor in dataset $D$; and $N_\epsilon$ be the number of points in $D$ having distances wrt ${\bf q}$ less than $(1+\epsilon)m({\bf q}|D)$.

	When there are many close nearest neighbors for any small $\epsilon>0$, i.e., $N_\epsilon$ is large, then the nearest neighbor query is said to be unstable. An unstable query is a direct consequence of the concentration effect.
	Here we use $N_\epsilon$ as a proxy for indistinguishability: for small $\epsilon$, high $N_\epsilon$ signifies indistinguishability; and $N_\epsilon=1$ or close to 1 denotes distinguishability.

	Figure \ref{fig_std-mean} shows the verification outcomes using the dataset shown in Figure \ref{fig_std-mean}(a).
	Figure \ref{fig_std-mean}(b) shows the concentration effect, that is, $var \left( \frac{F_{m,d}}{\mathbb{E}[F_{m,d}]} \right) \rightarrow 0$ as $d \rightarrow \infty$ for Gaussian kernel (GK). Yet, using Isolation Kernel (IK), the variance approaches a non-zero constant under the same condition.

	Figures \ref{fig_std-mean}(c) \& \ref{fig_std-mean}(d) show that $N_\epsilon$ increases as $d$ increases for GK for two different queries; and LK is unstable in one query. Yet, IK has almost always maintained a constant $N_\epsilon$ ($=1$) as $d$ increases.

	\textbf{SNN, AG, Linear kernel and fractional distances}:
	Here we examine the stability of Shared Nearest Neighbor (SNN) \citep{SNN,SNN-Defeat-Curse?}, Adaptive Gaussian kernel (AG) \citep{zelnik2005self} and fractional distances \cite{Aggarwal-2001}.

	Our experiment using SNN has shown that it has query stability if the query is within a cluster; but it has the worst query instability when the query is outside any clusters when $k$ is set less than the cluster size (1000 in this case), even in low dimensions!
	This result is shown in the first two subfigures in Table~\ref{tbl_SNN_AG_IK}. AG ($k=200$) has a similar behaviour as SNN that uses $k>1000$.

	The last two subfigures in Table \ref{tbl_SNN_AG_IK} show a comparison between Euclidean distance and fractional distances ($\ell_p, p=0.1,0.5$). It is true that the fractional distances are better than Euclidean distance in delaying the concentration effect up to $d=1000$; but they could not resist the concentration effect for higher dimensions.

	\textbf{Summary}. Many existing measures have indistinguishability in high dimensions that have prevented them from finding the  nearest neighbor if the query is outside of any clusters.

	\textbf{Only IK has distinguishability}. Note that IK uses distance to determine the (Voronoi) partition into which a point falls; but IK's similarity does not directly rely on distance. IK has a unique $t$-dimensional feature map that has increased distinguishability as $t$ increases, described in Section~\ref{sec_distinguishability}. No existing metric-based Lipschitz continuous kernels have a feature map with this property.

	\subsection{The impact of (in)distinguishability on four traditional tasks}
	\label{sec_traditional_tasks}

	We use the same ten datasets in the following four tasks. All have been used in previous studies (see Appendix \ref{ap1}), except two synthetic datasets: Gaussians and $w$-Gaussians. The former has two well-separated Gaussians, both on the same 10000 dimensions; and the latter has two $w$-dimensional Gaussians which overlap at the origin only, as shown in Figure \ref{fig_SC}. Notice below that algorithms which employ distance or Gaussian kernel have problems with the $w$-Gaussians dataset in all four tasks; but they have no problems with the Gaussians dataset.

	\begin{table*}[t]
		\centering
		\caption{Runtimes of exact 5-nearest-neighbors search.  Brute force vs Ball tree index. Boldface indicates faster runtime between brute force and index; or better precision.  The experimental details are in Appendix~\ref{ap1}. The Gaussians dataset is as used in Figure \ref{fig_std-mean}; $w$-Gaussians (where $w=5,000$) is as shown in Table \ref{fig:t-SNE}. The last two columns show the retrieval precision of 5 nearest neighbours. Every point in a dataset is used as a query; and the reported result is an average over all queries in the dataset.}
		\begin{tabular}{|c|rrr|rr|rr|r|rr||rr|}
			\hline
			Dataset & $\#points$ & $\#dimen.$ & \#class & \multicolumn{2}{c|}{Distance} & \multicolumn{3}{c|}{IK} & \multicolumn{2}{c||}{LK} & \multicolumn{2}{c|}{Precision@5} \\\cline{5-13}
			& & & & Brute  & Balltr & Brute  & Balltr & Map &  Brute  & Balltr & Distance & IK\\
			\hline
			Url & 3,000 & 3,231,961 & 2 & \textbf{38,702} &  41,508  & 112  & \textbf{109}  &  9 & \textbf{39,220} & 43,620 & .88  & \textbf{.95}\\

			News20 & 10,000 & 1,355,191 & 2

			& \textbf{101,243} & 113,445 & 3,475 & \textbf{2,257}  & 16 & \textbf{84,986} & 93,173 & .63  & \textbf{.88}\\

			Rcv1 & 10,000	& 47,236 & 2 & \textbf{3,615} & 4,037 & 739 & \textbf{578} & 11 & \textbf{5,699} & 6,272 & .90 & \textbf{.94}\\
			Real-sim &	10,000	&	20,958  & 2 &  \textbf{2,541}  & 2,863  & 4,824  &	\textbf{4,558}  & 21 & \textbf{2,533} & 2853 & .50 & \textbf{.63}\\

			Gaussians & 2,000 & 10,000 & 2 &  46  & \textbf{41} &  229 & \textbf{213} & 46 & \textbf{45} & 54 & \textbf{1.00} & \textbf{1.00} \\

			$w$-Gaussians & 2,000 & 10,000 & 2 &  \textbf{53} &  77 &    210  &  \textbf{205}  & 45  & \textbf{56}   &   73  & .90 & \textbf{1.00} \\
			Cifar-10 &	10,000	&	3,072 & 10 &  \textbf{340} & 398 &  7,538 &	\textbf{7,169} & 67 & \textbf{367} & 439 & .25 & \textbf{.27}\\

			Mnist	&	10,000	&	780 & 10 & \textbf{58}   &  72   & 1,742 & \textbf{1,731} & 2 & \textbf{87} & 106 & \textbf{.93} & \textbf{.93} \\
			A9a	&	10,000	&	122 & 2 & \textbf{10}    &	13 & 5,707 & \textbf{5,549} & 1 & \textbf{12} & 16 & \textbf{.79} & \textbf{.79} \\

			Ijcnn1 & 10,000 & 22 & 2 & 2.3 & \textbf{1.3} & 706  &	\textbf{654} & 1 & 2.2 & \textbf{1.8} & \textbf{.97} & .96\\

			\hline
			\multicolumn{11}{|r}{\textit{Average}}     & .77  & \textbf{.84}  \\
			\hline
		\end{tabular}%
		\label{tbl_indexing}%
	\end{table*}%

	\subsubsection{Exact nearest neighbor search using ball tree indexing}
	\label{sec_ballTree}

	Existing indexing techniques are sensitive to dimensionality, data size and structure of the dataset \citep{NN-indexibility-TODS2006,ExactNNSearch-PKDD2007}. They only work in low dimensional datasets of a moderate size where a dataset has clusters.

	Table \ref{tbl_indexing} shows the comparison between the brute force search and an indexed search based on ball tree \citep{omohundro1989five}, in terms of runtime, using Euclidean distance, IK and linear kernel (LK).
	Using LK, the ball tree index is always worse than the brute force search in all datasets, except the lowest dimensional dataset. Using Euclidean distance, we have a surprising result that the ball tree index ran faster than the brute force in one high dimensional dataset. However, this result cannot be `explained away' by using the argument that they may have low intrinsic dimensions (IDs) because the Gaussians dataset has 10,000 (theoretically true) IDs; while the indexed search ran slower in  all other real-world high dimensional datasets where each has the median ID less than 25, as estimated using a recent local ID estimator \citep{LID-SIAM19} (see the full result in Appendix \ref{sec_ID}.)

	Yet, with an appropriate value of $\psi$, IK yielded a faster search using the ball tree index than the brute force search in all datasets, without exception. Note that the comparison using IK is independent of the feature mapping time of IK because both the brute force and the ball tree indexing require the same feature mapping time (shown in the `Map' column in  Table \ref{tbl_indexing}.)

	It is interesting to note that the feature map of IK uses an effective number of dimensions of $t=200$ in all experiments. While one may tend to view this as a dimension reduction method, it is a side effect of the kernel, not by design. The key to IK's success in enabling  efficient indexing is the kernel characteristic in high dimensions (in Hilbert space.) IK is not designed for dimension reduction.

	Note that IK works not because it has used a low-dimensional feature map. Our result in Table \ref{tbl_indexing} is consistent with the previous evaluation (up to 80 dimensions only \citep{ExactNNSearch-PKDD2007}), i.e.,  indexing methods ran slower than brute-force when the number of dimensions is more than 16. If the IK's result is due to low dimensional feature map, it must be about 20 dimensions or less for IK to work. But all IK results in Table \ref{tbl_indexing} have used $t=200$.

	Nevertheless, the use of $t=200$ effective dimensions has an impact on the absolute runtime. Notice that, when using the brute force method, the actual runtime of IK  was one to two orders of magnitude shorter than that of distance in $d>40,000$; and the reverse is true in $d<40,000$.
	We thus recommend using IK in high dimensional ($d>40,000$) datasets, not only because its indexing runs faster than the brute force, but IK runs significantly faster than distance too. In $d\le 40,000$ dimensional datasets, distance is preferred over IK because the former runs faster.

	The last two columns in Table \ref{tbl_indexing} show the retrieval result in terms of precision of 5 nearest neighbors. It is interesting to note that IK has better retrieval outcomes than distance in all cases, where large differences can be found in News20, Realsim and $w$-Gaussians. The only exception is Ijcnn1 which has the lowest number of dimensions, and the difference in precision is small.

	This shows that the concentration effect influences not only the indexing runtime but also the precision of retrieval outcomes.

	\subsubsection{Clustering}
	\label{sec_SC}

	In this section, we examine the effect of IK versus GK/distance using a scalable spectral clustering algorithm (SC) \citep{chen2010parallel}  and Density-Peak clustering (DP) \citep{DP2014clustering}.

	We report the average clustering performance in terms of AMI (Adjusted Mutual Information) \citep{vinh2010information} of SC over 10 trials on each dataset because SC is a randomized algorithm; but only a single trial is required for DP, which is a deterministic algorithm.

	\begin{table}[h]
		\centering
		\caption{Best AMI scores of Desity-Peak clustering (DP) and Spectral Clustering (SC) using Distance/Gaussian kernel (GK), Adaptive Gaussian kernel (AG) and IK. Note that every cluster in Cifar10 and Ijcnn1 has mixed classes. That is why all clustering algorithms have very low AMI.}
		\begin{tabular}{|c|ccc|ccc|}
			\hline
			Dataset &   \multicolumn{3}{c|}{DP} & \multicolumn{3}{c|}{SC} \\
			\cline{2-7}
			& Distance & AG    & IK    & GK & AG    & IK \\
			\hline
			Url   & .07  & \textbf{.19}  & .16 & .04  & .04  & \textbf{.07}\\
			News20  & .02  & .05  & \textbf{.27} & .16  & .15  & \textbf{.21} \\
			Rcv1  & .18  & .19  & \textbf{.32} & \textbf{.19} & \textbf{.19} & \textbf{.19} \\
			Real-sim & .02  & .03  & \textbf{.04} & .04  & .02  & \textbf{.05} \\
			Gaussians & \textbf{1.00} & \textbf{1.00} & \textbf{1.00} & \textbf{1.00} & \textbf{1.00} & \textbf{1.00} \\
			$w$-Gaussians & .01  & .01  & \textbf{.68} & .24  & .25  & \textbf{1.00} \\
			Cifar-10 & .08  & .09  & \textbf{.10} & \textbf{.11} & \textbf{.11} & .10 \\
			Mnist & .42  & \textbf{.73} & .69  & .49  & .50  & \textbf{.69} \\
			A9a   & .08  & .17  & \textbf{.18} & .15  & .14  & \textbf{.17} \\
			Ijcnn1 & .00  & .00  & \textbf{.07} & \textbf{.00} & \textbf{.00} & \textbf{.00} \\
			\hline
			\textit{Average} & .19  & .25  & \textbf{.35}  & .24  & .24  & \textbf{.35}\\
			\hline
		\end{tabular}%
		\label{tbl_SC2}%
	\end{table}%

	\begin{table*}[t]
		\centering
		\caption{SVM classification accuracy \& runtime (CPU seconds). Gaussian kernel (GK), IK and Linear kernel (LK). $nnz\% = \#nonzero\_values / ((\#train+\#test) \times \#dimensions) \times 100$.

			IK ran five trials to produce [mean]{\tiny $\pm$}[standard error]. The runtime of SVM with IK includes the IK mapping time. The separate runtimes of IK mapping and SVM are shown in Appendix \ref{sec_IK_mapping_time}.
			\label{tbl:SVM-accuracy} }

		\begin{tabular}{|c|rrrr|rrr||rrr|}\hline
			Dataset		& $\#train$     & $\#test$ & $\#dimen.$ & $nnz\%$ & \multicolumn{3}{c||}{Accuracy} & \multicolumn{3}{c|}{Runtime}\\
			& & & & 	& LK & \multicolumn{1}{c}{IK} & GK & LK & IK & GK\\
			\hline
			Url &     2,000 & 1,000 & 3,231,961 & .0036 & \textbf{.98} & \textbf{.98}{\tiny $\pm$.001} & \textbf{.98} & 2 & 3 & 14 \\

			News20 & 15,997 & 3,999 & 1,355,191 & .03
			& .85 & \textbf{.92}{\tiny $\pm$.007} & .84  & 38 & 60 & 528 \\
			Rcv1 & 20,242 & 677,399 & 47,236 & .16
			& .96  & .96{\tiny $\pm$.013} & \textbf{.97} & 111 & 420 & 673\\
			Real-sim & 57,848 & 14,461 & 20,958 & .24
			& \textbf{.98} & \textbf{.98}{\tiny $\pm$.010} & \textbf{.98} & 49 & 57 & 2114\\

			Gaussians & 1,000 & 1,000 & 10,000 & 100.0 &  \textbf{1.00} & \textbf{1.00}{\tiny $\pm$.000} & \textbf{1.00} & 14 & 9 & 78\\
			$w$-Gaussians & 1,000 & 1,000 & 10,000 & 100.0  & .49 & \textbf{1.00}{\tiny $\pm$.000} & .62 & 20 & 8 & 79  \\
			Cifar-10 & 50,000 & 10,000 & 3,072 & 99.8
			& .37 & \textbf{.56}{\tiny $\pm$.022} & .54 & 3,808 & 1087 & 29,322\\

			Mnist & 60,000 & 10,000 & 780 & 19.3
			& .92 & .96{\tiny $\pm$.006} & \textbf{.98} & 122 &  48  & 598\\
			A9a & 32,561 & 16,281 & 123 & 11.3
			& \textbf{.85} & \textbf{.85}{\tiny $\pm$.012} & \textbf{.85} & 1 & 31 & 100\\

			Ijcnn1 & 49,990 & 91,701 & 22 & 59.1
			& .92 & .96{\tiny $\pm$.006} & \textbf{.98} & 5 & 66 & 95\\
			\hline
		\end{tabular}
	\end{table*}

	Table \ref{tbl_SC2} shows the result.
	With SC, IK improves over GK or AG \citep{zelnik2005self} in almost all datasets. Large improvements are found on $w$-Gaussians and Mnist. The only dataset in which distance and GK did well is the Gaussians dataset that has two well-separate clusters.

	AG was previously proposed to `correct' the bias of GK \citep{zelnik2005self}. However, our result shows that AG is not better than GK in almost all datasets we have used. There are two reasons. First, we found that previous evaluations have searched for a small range of $\sigma$ of GK (e.g., \citep{chen2010parallel}.) Especially in high dimensional datasets, $\sigma$ shall be searched in a wide range (see Table \ref{tbl_SC_parameters} in Appendix \ref{ap1}.) Second, spectral clustering is weak in some data distribution even in low dimensional datasets. In this case, neither GK nor AG makes a difference. This is shown in the following example using $w$-Gaussians, where $w=1$, which contains two 1-dimensional Gaussian clusters which only overlap at the origin in the 2-dimensional space.

	Figure \ref{fig_SC} shows the best spectral clustering results with IK and AG.
	When the two Gaussians in the $w$-Gaussians dataset have the same variance, spectral clustering with AG (or GK) fails to separate the two clusters; but spectral clustering with IK succeeds.

	\begin{figure}[h]
		\centering
		\begin{subfigure}[b]{0.22\textwidth}
			\centering
			\includegraphics[width=1.4in]{IK.png}
			\caption{SC with IK (AMI=0.91)}
		\end{subfigure}
		\begin{subfigure}[b]{0.22\textwidth}
			\centering
			\includegraphics[width=1.4in]{AG2.png}
			\caption{SC with AG (AMI=0.29)}
		\end{subfigure}
		\caption{The spectral clustering results with IK and AG on the $w$-Gaussians dataset (where $w=1$) that contains two 1-dimensional subspace clusters. Each cluster has 500 points, sampled from a $1$-dimensional Gaussian distribution $\mathcal{N}(0, 1)$. The density distribution of each cluster is shown in (a) wrt the corresponding 1-dimensional subspace. }
		\label{fig_SC}
	\end{figure}

	When the variances of the two subspace clusters are substantially different,  spectral clustering with AG yields a comparable good result to that with IK. Note that spectral clustering with GK cannot separate the two subspace clusters regardless. This is the specific condition, as used previously \citep{zelnik2005self} to show that AG is better than GK in spectral clustering.

	In a nutshell, in general, IK performs better than GK and AG on spectral clustering in both low and high dimensional datasets.

	This clustering result is consistent with the previous result \citep{IsolationKernel-AAAI2019} conducted using DBSCAN \citep{ester1996density} in both low and high dimensional datasets comparing between distance and IK.

	Similar relative results with DP \cite{DP2014clustering} are shown in Table \ref{fig_SC}, where large differences in AMI in favor of IK over distance/AG can be found in News20 and $w$-Gaussians.

	\begin{table*}[t]

		\caption{t-SNE: Gaussian Kernel versus Isolation Kernel on the $w$-Gaussians datasets having two $w$-dimensional subspace clusters (shown in the first column.)  Both clusters are generated using $\mathcal{N}(0, 1)$.  ``$\times$'' is the origin---the only place in which the two clusters overlap in the data space. }
		\label{fig:t-SNE}
		\centering
		\begin{tabular}{c|ccccc}
			\hline
			$w=1$ dataset  &  &  t-SNE(GK)   & t-SNE(IK)  &  FIt-SNE  & q-SNE\\
			\hline
			\includegraphics[width=1.2in]{w1.png} &       \begin{turn}{90} \quad   $w=2$   \end{turn}&
			\includegraphics[width=1.2in]{GK250.png}                     &
			\includegraphics[width=1.2in]{2IK5.png}  &
			\includegraphics[width=1.2in]{FitSNE1.png}  &
			\includegraphics[width=1.2in]{qsne1.png}\\
			&   \begin{turn}{90} \quad  $w=5000$ \end{turn}&
			\includegraphics[width=1.2in]{GK5k.png}                           &
			\includegraphics[width=1.2in]{IK5k.png}  &
			\includegraphics[width=1.2in]{f5k.png} &
			\includegraphics[width=1.2in]{q5k.png} \\
			\hline
		\end{tabular}
	\end{table*}

	\begin{table*} [t]
		\caption{t-SNE: GK versus IK on $w$-Gaussians datasets having two $w$-dimensional subspace clusters (different variances.)  The red and blue clusters are generated using $\mathcal{N}(0, 1)$ and $\mathcal{N}(0, 32)$, respectively.
			``$\times$'' is the origin---the only place in which the two clusters overlap in the data space.  }
		\label{fig:t-SNE-different-variance}
		\centering
		\begin{tabular}{c|ccccc}
			\hline
			$w=1$ dataset  &  &  t-SNE(GK)   & t-SNE(IK)  &  FIt-SNE  & q-SNE\\
			\hline
			\includegraphics[width=1.2in]{w2.png} &       \begin{turn}{90} \quad   $w=2$   \end{turn}&
			\includegraphics[width=1.2in]{GK_2_500_552.png}                     &
			\includegraphics[width=1.2in]{IK_2_5_451.png}      &
			\includegraphics[width=1.2in]{f2.png} &
			\includegraphics[width=1.2in]{q2.png} \\
			&     \begin{turn}{90}    \quad  $w=100$ \end{turn}&
			\includegraphics[width=1.2in]{GK_100_500_004.png}                           &
			\includegraphics[width=1.2in]{750.png}     &
			\includegraphics[width=1.2in]{f100.png}  &
			\includegraphics[width=1.2in]{q100.png} \\
			\hline
		\end{tabular}

	\end{table*}

	\subsubsection{SVM classification}
	\label{sec_SVM-classification}

	Table \ref{tbl:SVM-accuracy} shows the comparison between linear kernel, IK and Gaussian kernel using an SVM classifier in terms of accuracy and runtime. The experimental details are in Appendix~\ref{ap1}.

	It is interesting to note that IK produced consistently high (or the highest) accuracy in all datasets. In contrast, both linear and Gaussian kernels have a mixed bag of low and high accuracies. For example, they both perform substantially poorer than IK on News20 and $w$-Gaussians (where $w=5,000$.) Each $w$-Gaussians dataset has two $w$-dimensional subspace clusters. The $w=1$ version of the dataset is shown in the first column in Table \ref{fig:t-SNE}.

	The runtime result shows that,  SVM using IK runs either comparably or faster than SVM using Linear Kernel, i.e., they are in the same order, especially in high dimensions. Because of employing LIBLINEAR \citep{fan2008liblinear}, both are up to two orders of magnitude faster  in large datasets than SVM with GK which must employ the slower nonlinear LIBSVM \citep{CC01a}.

	\subsubsection{Visualization using t-SNE}
	\label{sec_visualization_experiment}

	Studies in visualization \citep{MDS-wickelmaier2003introduction,Hinton2008Visualizing} often ignore the curse of dimensionality issue which raises doubt about the assumption made by visualization methods. For example, t-SNE \citep{Hinton2008Visualizing} employs Gaussian kernel as a means to measure similarity in the high dimensional data space. No studies have examined the effect of its use in the presence of the curse of dimensionality, as far as we know.
	Here we show one example misrepresentation from t-SNE, due to the use of GK to measure similarity in the high dimensional data space on the $w$-Gaussians datasets.

	The t-SNE visualization results comparing Gaussian kernel and Isolation Kernel are shown in the middle two columns in Table \ref{fig:t-SNE}. While t-SNE using GK has preserved the structure in low dimensional  ($w=2$) data space, it fails completely to separate the two clusters  in high dimensional ($w=5,000$) data space.

	In contrast, t-SNE with IK correctly separates the two clusters in both low and high dimensional data spaces.

	Recent improvements on t-SNE, e.g., FIt-SNE \citep{linderman2019fast} and q-SNE \citep{hakkinen2020qsne}, explore  better local structure resolution or efficient approximation. As they employ Gaussian kernel, they also produce misrepresented structures, as shown in Table \ref{fig:t-SNE}.

	Table \ref{fig:t-SNE-different-variance} shows the results on a variant $w$-Gaussians dataset where the two clusters have different variances. Here t-SNE using GK produces misrepresented structure in both low and high dimensions. It has misrepresented the origin in the data space as belonging to the red cluster only, i.e., no connection between the two clusters. Note that all points in the red cluster are concentrated at the origin in $w=100$ for GK. There is no such issue with IK.

	In low dimensional data space, this misrepresentation is due solely to the use of a data independent kernel. To make GK adaptive to local density in t-SNE, the bandwidth is learned locally for each point. As a result, the only overlap between the two subspace clusters, i.e., the origin,  is assigned to the dense cluster only.
	The advantage of IK in low dimensional data space is due to the data dependency stated in Lemma \ref{lem_characteristic}. This advantage in various tasks has been studied previously \citep{ting2018IsolationKernel,IsolationKernel-AAAI2019,IsolationSetKernel,IDK-KDD2020}.

	In high dimensional data space, the effect due to the curse of dimensionality obscures the similarity measurements made. Both this effect and the data independent effect collude in high dimensional data space when distance-based measures are used, leading to poor result in the transformed space.

	\vspace{-1mm}
	\subsubsection{Further investigation using the low dimensional $w$-Gaussians ($w=2$)}
	It is interesting to note that (i) in SVM classification, both GK and IK could yield 100\% accuracy while LK still performed poorly at 51\% accuracy; and (ii) all three measures enable faster indexed search than brute force search and have equally high precision on this low dimensional dataset. But only IK can do well in the high dimensional $w$-Gaussians ($w=5,000$) in all four tasks, as shown in Tables \ref{tbl_indexing} to \ref{fig:t-SNE-different-variance}.

	The $w$-Gaussians datasets provide an example condition in which GK/distance performed well in low dimensions but poorly in high dimensions in indexed search, SVM classification and t-SNE visualization.
	This is a manifestation that the GK/distance used in these algorithms has indistinguishability in high dimensions.

	\noindent
	\textbf{Summary}:

	\begin{itemize}[itemsep=0ex, leftmargin=5mm]
		\item IK is the only measure that consistently (a) enabled faster indexed search than brute force search, (b) provided good clustering outcomes with SC and DP,  (c) produced  high accuracy in SVM classification, and (d) yielded matching structures in t-SNE visualization in both low and high dimensional datasets.
		\item Euclidean distance or GK performed poorly in most high dimensional datasets in all tasks except SVM classification. We show one condition, using the artificial $w$-Gaussians datasets, in which they did well in low dimensions but performed poorly in high dimensions in all four tasks. The Gaussians dataset is one condition in which Euclidean distance or GK can do well in high dimensions.
		\item Though low intrinsic dimensions may explain why GK/LK can do well in some high dimensional datasets in SVM classification, the explanation failed completely for all the slower indexed searches in high dimensions, and for the only faster indexed search on the Gaussians dataset as it has high intrinsic dimensions.

	\end{itemize}

	\section{Discussion}
	\label{sec_discussion}

	We have limited our discussion on the curse of dimensionality based on nearest neighbors, i.e., their (in)distinguishability. But the effect of the curse is broader than this. For example, it has effects on the consistency of estimators, an aspect not discussed in this article.

	In addition to the concentration effect \citep{Talagrand,Beyer:1999}, the curse of dimensionality has also been studied under different phenomena, e.g., the correlation between attributes \citep{WhenNNisMeaningful-2009} and hubness \citep{HubsInSpace-JMLR-2010}.

	It is interesting to analyze whether IK can deal with these issues, other than the concentration effect, effectively in high dimensions.

	Our results in Tables \ref{tbl_indexing} to \ref{tbl:SVM-accuracy} show that some existing measures may perform well in high dimensions under special conditions. However, we are not aware of analyses that examine whether any existing measures can break the curse of dimensionality.

	Previous work on intrinsic dimensionality (e.g., \cite{LID-NIPS2011}) has shown that nonparametric distance-based regressors could escape the curse of dimensionality if a high dimensional dataset has low intrinsic dimensions. This is consistent with the finding that the concentration effect depends more on the intrinsic dimensions $I_d$ than on the input dimensions $d > I_d$ \citep{Concentration-Fractionaldistances}. Our result in Table \ref{tbl_indexing} on the Gaussians dataset adds another element that needs an explanation for existing measures, i.e., why does distance perform well on datasets with high intrinsic dimensions?

	Because our analysis on IK's distinguishability is independent of dimensionality and data distribution, IK does not rely on low intrinsic dimensions to perform well, as shown in the artificial datasets: both Gaussians and $w$-Gaussians have high ($\ge 5,000$ true) intrinsic dimensions in Tables \ref{tbl_indexing} to \ref{fig:t-SNE-different-variance}.

	Our applications in ball tree indexing, two clustering algorithms, SVM classification and t-SNE here, and previously in DBSCAN clustering \citep{IsolationKernel-AAAI2019}  and multi-instance learning \cite{IsolationSetKernel}, suggest that many existing algorithms can get performance improvement by simply replacing distance/kernel with IK. However, a caveat is in order: not all existing algorithms can achieve that. For example, OCSVM \citep{OCSVM2001} and OCSMM \citep{OCSMM2013} have been shown to work poorly with IK \citep{ting2020-IDK-GroupAnomalyDetection}. This is because the learning in these two algorithms is designed to have a certain geometry in Hilbert space in mind; and IK does not have such a geometry (see details in \cite{ting2020-IDK-GroupAnomalyDetection}.)

	The isolating mechanism used has a direct influence on IK's distinguishability.

	Note that the

	proofs of Lemma \ref{lem2} and Theorem \ref{thm2} rely on the isolating partitions being the Voronoi diagram.  It remains an open question whether IK with a different implementation could be proven to have distinguishability.

	Kernel functional approximation is an influential approach to obtain an approximate finite-dimensional feature map from an infinite-dimensional feature map of a kernel such as Gaussian kernel. Its representative methods are Nystr\"{o}m \citep{Nystrom_NIPS2000} and random features \citep{RandomFeatures2007,OrthonogalRandomFeatures2016}. The former is often dubbed data dependent and the latter data independent. These terms refer to the use (or no use) of data samples to derive the approximate feature map. In either case, the kernel employed is data independent and translation invariant, unlike the data dependent IK in which the similarity depends local data distribution and it is not translation invariant.

	VP-SVM \citep{VP-SVM-2016} employs Voronoi diagram to split the input space and then learns a local SVM with a local bandwidth of Gaussian kernel in each Voronoi cell. It aims to reduce the training time of SVM only, and do not address the curse of dimensionality at all.

	A recent work \citep{IK-SNE-2021} has already shown that IK improves the effectiveness and efficiency of t-SNE, by simply replacing Gaussian kernel. However, it did not address the issue of curse of dimensionality, which is the focus of this paper.

	The result of an additional investigation on the hubness effect \cite{HubsInSpace-JMLR-2010}  can be found in Appendix  \ref{App_hubness}.

	\section{Conclusions}

	We show for the first time that the curse of dimensionality can be broken using Isolation Kernel (IK). It is possible because (a) IK measures the similarity between two points based on the space partitionings produced from an isolation mechanism;

	(b)  the probability of a point falling into a partition in the isolation partitioning of Voronoi diagram is independent of data distribution, the distance measure used to create the Voronoi partitions and the data dimensions, implied in Lemma \ref{lem2}; and (c) IK's unique feature map has its dimensionality linked to a concatenation of these partitionings.
	Theorem~\ref{thm2} suggests that increasing the number of partitionings $t$ (i.e., the dimensionality of the feature map) leads to increased distinguishability, independent of the number of dimensions and distribution in data space.

	Isolation Kernel, with its feature map having the distinguishability stated in Theorem \ref{thm2}, is the key to  consistently producing (i) faster indexed search than brute force search, and high retrieval precision, (ii) good clustering outcomes with SC and DP,  (iii) high accuracy of SVM classification, and (iv) matching structures in t-SNE visualization in both low and high dimensional data spaces.

	Euclidean distance, Gaussian and linear kernels  have a mixed bag of poor and good results in high dimensions in our experiments. This is not a surprising outcome of the curse of dimensionality, echoing the current state of understanding of these measures, with or without the aid of intrinsic dimensions.

	\newpage

redpajama_set_name: RedPajamaArXiv


text:
Thunder Gulch (May 23, 1992 – March 19, 2018)  was a Champion American Thoroughbred racehorse best known for his wins in the Kentucky Derby and the Belmont Stakes in 1995, which earned him the title of U.S. Champion 3-Yr-Old Colt.

Background
Bred by Peter Brant and owned by Michael Tabor, Thunder Gulch was a son of Gulch out of Line Of Thunder.

Racing career
Thunder Gulch won the Remsen Stakes as a two-year-old in 1994. In the spring of 1995, he won the Fountain of Youth Stakes and the Florida Derby.

At Churchill Downs, he left the starting gate at 25-1 odds in 1995 and won the Kentucky Derby in 2:01.2 from post 16. He was ridden by jockey Gary Stevens. D. Wayne Lukas, his trainer, entered three horses for the 121st "Run for the Roses".

Following his win in Louisville, Thunder Gulch finished  third to his stablemate Timber Country in the Preakness Stakes. In the Belmont Stakes, Thunder Gulch was made 3/2 favourite after Timber Country was withdrawn from the race with a fever. He won by two lengths from Star Standard, giving Lukas the first individual Triple Crown, his fifth consecutive win in the series. Thunder Gulch also won in the Travers Stakes, in which he overcame a bad start to record a four and a half length victory over Pyramid Peak. With the Travers Stakes win, he became only the fourth horse to win the Kentucky Derby, Belmont Stakes, and Travers (Twenty Grand, Whirlaway and Shut Out were the others). Other victories in 1995 included the Swaps Stakes, and the Kentucky Cup Classic Handicap.

Thunder Gulch was retired in the fall of his three-year-old campaign after finishing fifth to  American Horse of the Year  Cigar in a "much-anticipated showdown" for the Jockey Club Gold Cup.  After the race, it was discovered that he had fractured his left front cannon bone.

Stud record
In 2012, the chestnut stallion was standing at Ashford Stud, the American branch of the giant Irish breeder Coolmore Stud, near Versailles, Kentucky, for a fee of $10,000 live foal.

Among the many horses Thunder Gulch has sired are the graded stakes race winners Spain, Balance, Point Given, and Circular Quay.  Point Given was 2001 3 year old Horse of the Year after winning the Preakness Stakes and Belmont Stakes that year.  Circular Quay was among trainer Todd Pletcher's many Kentucky Derby entries of 2007, but ran a disappointing sixth in that race and  fifth in the Preakness. He also sired Alittlebitearly, whose December birth date made it impossible for her to be raced, but has had a successful breeding career, as she was dam to Bayern, a Breeders' Cup Classic winner.  4-time winning bay gelding Sir Mowgli XVII, is now a leading Hunter competing throughout the Southwest, having recently relocated to Durango Farms in Coto de Caza, CA.

In 2015, Thunder Gulch was pensioned from stud duties at Ashford Stud and lived out the rest of his days at the farm. He was selected as the "babysitter of sorts" to be a neighboring pasture companion and calming influence to the newly retired Triple Crown champion, American Pharoah.

Thunder Gulch was euthanized on March 19, 2018, due to the infirmities of old age at Coolmore America's Ashford Stud. Technically age 25, based upon standardized rules declaring all Thoroughbreds a year older each January 1, he was officially age 26.

Pedigree

References

1992 racehorse births
2018 racehorse deaths
Racehorses bred in Kentucky
Racehorses trained in the United States
Kentucky Derby winners
Belmont Stakes winners
Eclipse Award winners
United States Champion Thoroughbred Sires
Thoroughbred family 11-d

redpajama_set_name: RedPajamaWikipedia


text:
Home/Health/Scientists have said what pet plants are hazardous to health
Scientists have said what pet plants are hazardous to health
Singapore NewsDesk November 16, 2018 13:43
Do not forget that cacti are not harmless.Often, it can be said that working on a computer is useful to keep it in the cactus.
But it turned out that the usual cacti on the domestic cacti require special attention and treatment, writes Chronicle.info with reference to the 24-course.
Head of Botanical Garden Institute RAS, a member of RAS Pavel Krestov, warns that cacti are not harmless. According to the crosses, the juice of these plants contains an impressively large list of various alkaloids, more than 120 species. These chemicals can sometimes have a very strong effect on the nervous system of people and pets and do not improve the condition.
The source of dangerous alkaloids is not just a cactus. The expert said that alkaloids contain rubber plants and poinsettias (also known as the Christmas star).
Starting in the spring of social networks, it's becoming fashionable to make a photo from a bouquet. Paul Crosses talked about what brings a wonderful bouquet into the house, it can cause serious health problems.
But, for example, a dangerous bunch of lilac? According to the expert, the rich scent of lilac is dangerous due to its volatile substances that contribute to the development of hydrocyanic acid, which has toxic potential.
It can damage the health of bouquets of lilies, cherries or lilac. These plants can cause headache, migraine and as close as possible to narcotic poisoning, he said.
In addition, you must be careful when handling the plants of the Solanaceae family. They can have a strong toxin solanin.
If there is subsurface water across Mars, where is it safe to avoid contamination?
New Nokia Budget Handset Spotted on TENAA Website: Details Here | Newspapers
A zeal pays off in 'spectacular success': as the leading coronavirus vaccines reach the finish line – The Washington Post
22 people were taken to hospital after accident between bus and car on Jurong Island highway
Britain's Queen Elizabeth to receive Covid-19 vaccine 'in weeks': Reports, Europe News & Top Stories
Lufthansa will have shed 29,000 staff by the end of the year: Bild am Sonntag
By Singapore NewsDesk

redpajama_set_name: RedPajamaCommonCrawl


Life as the Mrs.: TGIF.
I woke up this morning with Katy Perry's "TGIF" in my head. A sign of a good day, perhaps?
I'm seeing "The Help" tomorrow and am seriously looking forward to it. Brandon's playing a little golf and we're just planning to relax.


text:
Luxury switzerland jail
🔎 Are there prisons in switzerland?
Are there prisons in switzerland?
Asked By: Eusebio Stroman
Date created: Tue, Jul 13, 2021 2:47 PM
Date updated: Sun, Jan 16, 2022 3:35 PM
Categories: Luxury switzerland jail
Video answer: Top 10 most luxurious prisons in the world
Top best answers to the question «Are there prisons in switzerland»
FAQ. Those who are looking for an answer to the question «Are there prisons in switzerland?» often ask the following questions
Video answer: 10 most luxurious prisons in the world
Answered by Jarrod Dibbert on Wed, Jul 14, 2021 7:37 PM
Prisons in Switzerland are operated by the Swiss cantons, which are responsible for law enforcement in Switzerland. Swiss prisons have a capacity of up to 6,736 detainees total (amounting to 89 detention places per 100,000 inhabitants), including up to 477 women and 105 minors…
Answered by Bessie Ryan on Sat, Jul 17, 2021 10:29 AM
Who is responsible for private prisons in Switzerland?
Prisons in Switzerland are operated by the Swiss cantons, which are responsible for law enforcement in Switzerland.
Those who are looking for an answer to the question «Are there prisons in switzerland?» often ask the following questions:
🔎 How many prisons are there in switzerland?
As of 2008, Switzerland has 124 prisons according to the Catalogue of Correctional Institutions (Katalog der Einrichtungen des Freiheitsentzuges) compiled by the Federal Statistical Office; other statistics, which account for various institutions being administratively associated with each other, report 117 prisons.
Does switzerland have jails and prisons?
Where are the prisons in switzerland?
How many swiss prisons are there?
🔎 Are there male and female prisons in switzerland?
How many people are in jail in Switzerland?
Out of the total prison population of 6,863 people in 2017, 49.3% were legal residents (Swiss and non-Swiss), 9.6% were asylum seekers and 41.1% were classified "other foreigners (including foreigners of unknown status)".
How many people are detained in swiss prisons?
Switzerland there is metrobank?
🔎 How many prisons in switzerland?
Prison population total (including pre-trial detainees / remand prisoners)
6 316 at 31.1.2021 (Swiss Federal Statistical Office)
Number of establishments / institutions 92 (2021)
Official capacity of prison system 7 397 (31.1.2021)
Occupancy level (based on official capacity) 85.4% (31.1.2021)
Are there beaches in switzerland?
Are there bears in switzerland?
Are there casinos in switzerland?
Video answer: 5 nicest prisons in the world!
We've handpicked 24 related questions for you, similar to «Are there prisons in switzerland?» so you can surely find the answer!
Are there deserts in switzerland?
Like the rest of Europe, there are no deserts in Switzerland
Are there dolphins in switzerland?
No. Dolphins live in the sea, and Switzerland is a land-locked country.
Are there germans in switzerland?
They constitute 22.6% of the total Swiss population. Of these, 279, 672 are German, an increase of 11,500 from the previous year. They are the second largest immigrant group in Switzerland after the Italians (291,000). In addition there are about 50,000 German cross border workers.
Are there ghettos in switzerland?
There are no slums or ghettos existing in Switzerland. Even communities often have houses and offer cheaper rental fees for people with low income. There are also sleep-ins for urgencies.
Are there goats in switzerland?
Are there homeless in switzerland?
Homelessness in Switzerland is a known social issue, however, there are few estimates as to the number of Swiss people affected. Homelessness is less visible in Switzerland than in many other Western countries… One Swiss study found that 1.6 percent of all patients admitted to psychiatric wards were homeless.
Are there hummingbirds in switzerland?
are hummingbirds in switzerland
Video answer: Prison inmate: we get puppies, ice cream and flowers
Are there jungles in switzerland?
No. Switzerland has a temperate climate, not a tropical one.
Are there lottery in switzerland?
In Switzerland, all large-scale lotteries are run exclusively by two major operators – Swisslos for the German- and Italian-speaking territories, and Loterie Romande in the French-speaking territories. These two organizations are licensed and regulated by Comlot, a supervisory body tasked with overseeing gambling activities in Switzerland.
Are there mennonites in switzerland? There are believed to be around 600,000 descendants of Swiss Anabaptists living in North America. The Mennonite community in Switzerland today has 2,500 members belonging to 14 congregations.There are believed to be around 600,000 descendants of Swiss Anabaptists
Anabaptism includes Amish, Hutterite, Mennonite, Bruderhof, and Church of the Brethren denominations. Some individual congregations, church buildings, or communities are individually notable, such as by being listed as historic sites.
https://en.wikipedia.org › wiki › List_of_Anabaptist_churches
List of Anabaptist churches - Wikipedia
living in North America. The Mennonite community in Switzerland today has 2,500 members belonging to 14 congregations.
Video answer: Most luxurious prison cells | world's most luxurious prisons (luxury tube)
Are there mosquitoes in switzerland?
In Switzerland, tiger mosquitoes have already been spotted in Graubünden in the east, Ticino in the south and Basel in the north. In Europe, they have had a strong presence in Italy since the early 1990s.
Are there police in switzerland?
The Swiss Police Forces comprise about 23,000 members. This includes federal, cantonal communal police forces as well as the Swiss Border Guards.
Are there provinces in switzerland?
No. Instead of provinces, Switzerland has cantons.
Are there republicans in switzerland?
Switzerland is a republic. By definition there are republicans in Switzerland.
Are there seas in switzerland?
What are the names of the lakes in Switzerland?
List of lakes of Switzerland. Lakes, large and small, can be found in almost all cantons and provide an important source of water as well as leisure opportunities. The two most extensive, Lake Geneva and Lake Constance, are amongst the largest in Europe and mark the border of the Swiss Plateau, along with the Alps and the Jura Mountains.
Are there spiders in switzerland?
In Switzerland, the number of spider species theoretically able to bite humans amounts to a few dozen among the nearly 1,000 species found in this country [1]. Despite mostly minor clinical symptoms, the general population may frequently overestimate the danger of spider bites.
Are there summers in switzerland?
Summer in Switzerland. Summer in Swiss valleys is rather humid season. Average temperature of northern and central regions is between 19 and 24°C (66-75°F). Southern regions are hotter with up to 32°C (89°F). But even the highest temperature is relatively comfort. Evening chill eases noon heat.
Are there tolls in switzerland?
The price of the Swiss motorway vignette is CHF 40, excluding shipping. It's basically a prepaid toll for an entire year. Separate tolls for specific routes are very rare in Switzerland. The vignette allows you to drive on 99.9% of all roads.
Video answer: Prisons closed in the netherlands | postmortem by gazi sakib
Is there amazon in switzerland?
With Amazon Prime, consumers in Switzerland would be able to access Amazon's complete online offering, which includes 229 million products.
Is there disneyland in switzerland?
How many countries does Disney have in Europe?
Jan oversaw the successful rollout of Disney+ to 16 countries in 2020, bringing the total number of European countries with Disney+ to 17. In his role, Jan is responsible for overseeing Disney's portfolio across a diverse collection of countries with teams operating in 59 markets across 29 countries.
Video answer: 12 prisons so luxurious that will shock you!!!


PO's are accepted from schools and other government agencies.
Click here if you want to use a PO to register.
*Our classes are taught in English (unless noted differently) and the exams are bilingual (English and Spanish). If you require the exam in a language other than English or Spanish, please notify us at least 14 business days prior to the exam date. The exam is also available in Korean, Chinese, and Vietnamese.
*Nuestras clases se enseñan en inglés (a menos que se indique de manera diferente) y los exámenes son bilingües (inglés y español).


text:
Q: How to update state for function that relies on if statement from state? I have an array called values:
values = RAW_VALUES.map((data) => {
  return {
    id: data.id,
    name: data.name,
    value: financials[data.id],
    add: false,
    subtract: false,
    change: "",
    newValue: "",
  };
});

and a function:
  updateValues(val, index) {
    let { values } = this.state;

    if (!isNaN(val)) {
      values[index].change = parseFloat(val);
      if(values[index].add){ //this checks if add property is true
        values[index].newValue = values[index].value + values[index].change
      }
      this.setState({
        values,
      });
    }
  }

I have a button called 'Add' which toggles the add field of each index in values.
To update values[index].newValue, the user currently needs to set add to true first and then type in the updated value.
How can I ensure that the value is also updated if the user first types in the value, and then sets add to true ?
This is how updateValues is called in render:
                  <MetricInput
                    value={values[index]?.change}
                    onChange={(e) =>
                      this.updateValues(e.target.value, index) //function
                    }
                  />

Edit: There are two buttons, add and subtract. if add is set to true then I'd want to do values[index].newValue = values[index].value + values[index].change
Else, if subtract is set to true, I'd do values[index].newValue = values[index].value - values[index].change

A: Not withstanding there are better ways to update an array of objects, can you not consider ignoring the if(values[index].add) condition and just set values[index].add = true ?
updateValues(val, index) {
    let { values } = this.state;

    if (!isNaN(val)) {
      values[index].change = parseFloat(val);
        values[index].newValue = values[index].value + values[index].change
        values[index].add = true
      this.setState({
        values,
      });
    }
  }

Update - Keep the above, and consider making numbers Positive or Negative depending on Add/Subtract
const onAdd = (index) => {
let values = this.state.values;
values[index].newValue = Math.abs(values[index].newValue)
this.setState({ values })
}
const onSubtract = (index) => {
let values = this.state.values;
values[index].newValue = -Math.abs(values[index].newValue)
this.setState({ values })
}

redpajama_set_name: RedPajamaStackExchange


Apple products prices in Colombo compared to other countries.
Colombo is very bad for buying Apple products, because the prices are very high here.
The blue line shows the average price for 3 star hotel rooms in Colombo in the current month.
The green line shows the minimal hotel room price in Colombo in the given month.


The following examples show how to use the YouTube Data API (v3) to perform functions related to captions.
To retrieve a list of caption tracks that are available for a specific video, call the captions.list method. Set the videoId parameter value to the YouTube video ID that uniquely identifies the video for which you are retrieving captions. Your request must be authorized using OAuth 2.0.
See the captions.list method's documentation for code samples.
This query cannot be tested using the APIs Explorer because the APIs Explorer does not support the ability to upload files, which is a requirement for this method.
snippet.videoId - This identifies the video to which the caption track is being added.
snippet.language - The language of the caption track.
snippet.name - The name of the caption track.
If you set the sync parameter to true, YouTube will disregard any time codes that are in the uploaded caption file and generate new time codes for the captions.
You should set the sync parameter to true if you are uploading a transcript, which has no time codes, or if you suspect the time codes in your file are incorrect and want YouTube to try to fix them.
If you set the caption resource's snippet.isDraft property to true, the track will not be publicly visible.
See the captions.insert method's documentation for code samples.
This query cannot be tested using the APIs Explorer because the APIs Explorer does not support the ability to download files.
To download a specific caption track, call the captions.download method. Set the id parameter value to the YouTube caption track ID that uniquely identifies the caption track that you are downloading. Your request must be authorized using OAuth 2.0.
To specify that a caption track should be returned in a specific format, set the tfmt parameter value to identify the desired format. The parameter definition lists supported values.
To retrieve a translation of a caption track, set the tlang parameter value to an ISO 639-1 two-letter language code that identifies the desired caption language. The translation is generated by using machine translation, such as Google Translate.
See the captions.download method's documentation for code samples.
The API supports the ability to change a caption track's draft status, upload a new caption track for a file, or both.
You can use the APIs Explorer to test the ability to change a track's draft status. However, you cannot use the APIs Explorer to update the actual caption track because tool does not support the ability to upload files.
The request updates the draft status of a caption track to true, which means the track will not be publicly visible. To complete the request in the APIs Explorer, you need to set the id property's value to identify a caption track.
See the captions.update method's documentation for code samples.
Follow the steps above to retrieve a list of caption tracks for a video. The list could be used to display a list of caption tracks, using each track's ID as a key.
Call the captions.delete method to delete a specific video. In the request, the id parameter specifies the caption track ID of the track that you are deleting. The request must be authorized using OAuth 2.0. If you are testing this query in the APIs Explorer, you will need to substitute a valid caption track ID for the id parameter value.


text:
Q: Dynamic Event Handling Here's a random question.
I have an object called Monkey, and an object called Banana. The Banana exposed an event called Ripens which the Monkey object subscribes to. When the Ripens event is triggered, the Monkey calls its Consume() function, which in turn destroys the Banana Object.
Example:
//And yes, I know this isnt real C# code. Just trying to get my point across and
//not necessarily be syntatically correct with this exmaple.
public class Banana
{
    public event Ripens;
}

public class Monkey
{
    public Monkey()
    {
        List<Banana> tree = new List<Banana>();
        for (int i = 0; i < 8; i ++)
        {
             tree.Add(new Banana());
             tree[i].Ripens += this.Consume;
        }
    }

    public void Consume(Banana b)
    {
         tree.Remove(b);
         b.Destroy();
    }
}

So my question then is: Does the Monkey bleed memory for each banana that is destroyed without first unsubscribing from its events. Or do the event handlers in Monkey get destroyed along with the banana?

A: When monkey subscribes to banana it's the banana that now has a reference to the monkey and monkey does not have one to banana. In your example when bananas risen they are now subject for garbage collection. So no - monkey doesn't leak memory.

A: "Memory leaks" from events actually occur in the other direction. If the monkey goes out of scope, the banana event still has a reference to the event delegate on the monkey, so the Monkey will not get Garbage Collected.
To address your "each" question, yes - the event handlers are per-object. So multiple subscribers going out of scope would still have references to them via the event publisher, causing them to not be garbage collected.


text:
Home » News » Throne Records Is Back! Brand New Releases From NOOTHGRUSH, CORRUPTED & JARBOE
Throne Records Is Back! Brand New Releases From NOOTHGRUSH, CORRUPTED & JARBOE
18 months ago the doors to Throne Records were shut, with what we thought was forever, but now, Uge has announced it's return with not 1, or 2 but 3 reissues and issued the following statement:
"Hell, it's been a year and a half… Many personal changes and situations occured in the meantime, too many to mention, and probably too boring for you to read… What really matters is that Throne Records is flying high again, stronger than ever.Thank you all for supporting independent, Do-It-Yourself, true alternative bands and labels. You keep all this alive, and you know it."
Now read on to see what the label has in store over the next few months:
NOOTHGRUSH 'Erode The Person – Anthology 1997-1998'
A re-mastered collection of NOOTHGRUSH's mid 90's best recordings. Includes the very rare and limited split vinyls with Gasp, Suppression, Carol Ann, Wellington and Corrupted. Plus a good bunch of re-arranged and unreleased stuff.
Comes packed in a very neat inside-out printed piece of deluxe digipack with envelope containing a 12 pages comprehensive booklet. This is a reissue of the 2006 Throne Records original jewel case CD release, which includes unreleased artwork and updated info.
Limited to 460 copies, per-orders for the CD are available HERE, while an ultra-limited collectors bundle of 40 units which includes the CD with a 'Hatred For The Species' T-Shirt is available HERE.
CORRUPTED 'Nadie' 12″
Originally released by Throne in 2008, it was about time for a repress. This is the Japanese Sludge cult band CORRUPTED's official debut. The audio has been remastered from the original tapes. Whole artwork (including a fold-out A2 size poster) is exclusively arranged using a war-reporter's unique exclusive pictures shot at Palestina.
Pressed at 45 rpm for maximum performance. This is a sought-after CORRUPTED release. Initial pressing of 1000 copies back in 2008 sold-out within weeks, now a highly priced collectable release. Without bands like CORRUPTED, successful modern bands of the genre would not sound the same, as CORRUPTED are an avant-garde band which expanded both sound/tuning and timing to the extreme. Often imitated, few times matched.
Limited to just 75 hand number copies on black splattered grey vinyl and per-orders are available HERE.
JARBOE 'Mahakali' 2xLP
This nice piece of vinyl was supposed to be the last Throne release ever (hence its reference throne 11), which eventually never happened. Now that the label is back on track, this highly anticipated vinyl edition of the majestic JARBOE's album is available in a very limited one and only edition of 500 copies worldwide, split into 3 different vinyl colors.
For the first time in vinyl format, this full length is claimed to be one of JARBOE's best releases. The group chosen for Mahakali includes all three members of DYSRHYTMIA as well as JOSH GRAHAM (Red Sparrowes, A Storm Of Light, Neurosis). It also includes the perfomance of PHIL ANSELMO (Pantera, Down) ATTILA CSIHAR (Mayhem, Gravetemple), and KRIS FORCE (Amber Asylum).
JARBOE is considered a true independent artist of the 21st century experimental music. She has released 18 solo albums in addition to working on more than 20 SWANS albums and more than 60 collaborative projects with visual and sound artists all over the world.
This release press-run is divided into three different vinyl colors:
· 100 copies pressed on 180 gr. Yellow-splattered Orange vinyl
· 100 copies pressed on 180 gr. Brown-splattered Clear vinyl
· 300 copies pressed on 180 gr. Black vinyl
Pre-order Mahakali right HERE.
http://thronerecs.com
http://www.facebook.com/thronerecordsofficial
http://thronerecords.bandcamp.com
http://twitter.com/thronerecs
Published on 4th August 2014 at 7:51 pm and has the following tags:
Corrupted, Erode The Person, Jarboe, Mahakali, Nadie, New Vinyl Details, News, Noothgrush, Throne Records
If you liked this, you may also want to read these...
Triptykon Returns To Roadburn Festival 2014
EYEHATEGOD To Kick Off 25 Years Of Dysfunctional Family Abuse Tour 2014 This Friday
Damnation 2015: Final Bands Announced Join AT THE GATES, HIGH ON FIRE, MONO & More!