Your data comes from an unknown distribution $f:\mathbb{Z}_+^d \rightarrow \mathbb{R}$ where d>1000. If you cannot assume anything about this distribution then there is no way to detect outliers.
One weak and relatively standard assumption you can make is that the distribution has bounded finite differences. i.e. if $|\bf x_1 - \bf x_2|$ is small then $|f({\bf x_1}) - f({\bf x_2})|$ must be small.
In that case, it is possible in principle to use nonparametric density estimation such as Kernel Density Estimation to estimate the density at each new data point (given all the previously recorded points) and give an outlier alert if this density lies below a threshold. This approach is easy to implement and needs only a reasonable choice of distance metric, kernel function and kernel width. The width can be estimated via cross-validation and the choice of kernel usually does not matter too much.
For a much simpler procedure, you can just compute the distance to the nearest sample. If this distance is large then you have an outlier.
However, given that the dimension is high, you probably won't get good results using both of these methods due to the curse of dimensionality - accurate nonparametric density estimation requires a number of samples exponential in the dimension.
I can think of several solutions to this problem:
- Use nonparametric density estimation on each key separately. Create an outlier alert if one of the keys is an outlier.
- Use nonparametric density estimation on each key separately. Estimate the density using the product of marginal densities and alert if this result is low. (i.e. take the product of estimated densities for all keys)
- Apply a dimension reduction algorithm such as PCA to go down to 2-3 dimensions and use nonparametric density estimation in that space.
