Effective monitoring by efficient fingerprint matching using a forest of NAQ-trees

摘要

Sensor devices have been widely used in many applications, e.g., security, wildlife monitoring, critical health cases, etc. The sensors constantly capture information about the monitored case and encode the information into feature vectors, called fingerprints, which are sent to a central server for further analysis; the process is generally semi-automated. To ease the on-line analysis, the central server should maintain a reference database containing standard fingerprints representing the status of known conditions. The key operation is to find the matchings (i.e., nearest neighbors) for each fingerprint arriving from the remote sensor devices; thus the current status of each sensor device can be automatically determined. As the fingerprints are usually characterized by hundreds of dimensions and quick response is mostly the top priority in sensor based monitoring applications, the existing index structures for nearest neighbor search fail to properly satisfy such applications. In this paper, we propose a method that allows for fully automated monitoring by efficiently reporting the matchings for most fingerprints sent by the sensor devices. The proposed method consists of two steps; the first step clusters the reference database into r-separable clusters and one fingerprint (i.e., the centroid) is selected to represent each cluster. The second step builds indexes for the representative fingerprints using a set of NAQ-trees residing on multiple nodes of a parallel machine. In the query processing phase, the built indexes are queried in parallel and from each tree only a very small number of index nodes are searched to report the partial results, which are combined into the final result. Taking advantage of the “randomization” property and compact partitioning of the NAQ-tree construction, the union of the partial results is anticipated to cover most of the matchings; this has been demonstrated in the experiments that have been conducted to emphasize the applicability and effectiveness of the proposed approach.