Clustering and indexing methods for high dimensional data and moving objects

The clustering problem concerns the discovery of homogeneous groups of data according to a certain similarity measure. It is not meaningful to look for clusters in high dimensional spaces as the average density of points anywhere in input space is likely to be low. We introduce the Locally Adaptive Clustering (LAC) algorithm, which discovers clusters in subspaces spanned by different combinations of dimensions via local weightings of features. Our method associates to each cluster a weight vector, whose values capture the relevance of features within the corresponding cluster. We formally prove that the algorithm converges, and experimentally demonstrate the gain in performance our method achieves, using both synthetic and real data sets. Furthermore, we present an SQL implementation of LAC.; We propose methods to index moving objects in order to efficiently answer range queries about their current and future positions. We address the problem in external memory and present dynamic solutions, both for the one-dimensional, as well as the two-dimensional cases. Our approach transforms the problem into a dual-space that is easier to index. An experimental evaluation with the TPR-tree shows that the dual transformation approach provides comparable query performance but has much faster update processing. Moreover, unlike the TPR-tree, the dual method does not require establishing a predefined query horizon.; One of the main applications of sensor networks is to detect and monitor transient events of interest, or objects as they move or spread through an area. To track such objects efficiently, and accurately we need distributed mechanisms that allow the cooperation of many sensors and the exchange of real-time data. We propose a new distributed mechanism for tracking moving objects that addresses these desiderata. Our mechanism provides efficient setup and cooperation of the sensors within the network, while providing fault tolerant characteristics through replication. We also provide an algorithm for predicting, with high probability, the future location of an object based on the past observations of many sensors. We empirically evaluate the performance of our approach and our simulations demonstrate its efficiency and accuracy.