Despite their wide spread use, nearest neighbour density estimators have two fundamental limitations: O(n2) time complexity and O(n) space complexity. Both limitations constrain nearest neighbour density estimators to small data sets only. Recent progress using indexing schemes has improved to near linear time complexity only.We propose a new approach, called LiNearN for Linear time Nearest Neighbour algorithm, that yields the first nearest neighbour density estimator having O(n) time complexity and constant space complexity, as far as we know. This is achieved without using any indexing scheme because LiNearN uses a subsampling approach for which the subsample values are significantly less than the data size. Like existing density estimators, our asymptotic analysis reveals that the new density estimator has a parameter to trade off between bias and variance. We show that algorithms based on the new nearest neighbour density estimator can easily scale up to data sets with millions of instances in anomaly detection and clustering tasks. Highlights•Reject the premise that a NN algorithm must find the NN for every instance.•The first NN density estimator that has O(n) time complexity and O(1) space complexity.•These complexities are achieved without using any indexing scheme.•Our asymptotic analysis reveals that it trades off between bias and variance.•Easily scales up to large data sets in anomaly detection and clustering tasks.
Although simulated environments are improved by adding sensory information, temperature is one input that has rarely featured in them. Here we report findings from experiments that examine the efficacy of adding temperature information to the multimodal complex known to be of benefit in simulations. In the first experiment, Peltier tiles added thermal information to the kinesthetic feedback given by a hand-worn exoskeletal device and this increased ratings for 'presence' during interactions with simulated objects. In an experiment in which exploratory movements across surfaces of differing temperatures were either active or passive-guided, the degree of 'coldness' felt at the fingertip was reported as less intense when movement was active, suggesting that intentionality of movement plays a role in the attenuation of the thermal stimulus. Other work reported here suggests that the perception of temperature is not influenced by a simultaneously presented colour. For example, the perception of coldness is not enhanced when it is processed in conjunction with a blue colour. We discuss the potential value of thermal information within the context of the hypothesis that presence in simulated environments is enhanced by multisensory inputs that include redundant information.