Weitere Artikel dieser Ausgabe durch Wischen aufrufen
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.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Agarwal, M., Sain, K., Singh, D., & Goyal, S. P. (2006). Monitoring habitat characteristics using GIS and remote sensing: A case study for mitigating human-leopard conflict in Pauri Garhwal, India. In Proceedings of carnivores 2006, habitats, challenges and opportunities. St. Petersburg, FL.
Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999). Optics: Ordering points to identify the clustering structure. In Proceedings of ACM SIGMOD conference on management of data (pp. 49–60).
Beckmann, N., Kriegel, H., Schneider, R., & Seeger, B. (1990). The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of ACM SIGMOD international conference on management of data (pp. 322–331).
Berchtold, S., Keim, D., & Kriegel, H. P. (1996). The X-tree: An index structure for high-dimensional data. In: Proceedings of the international conference on very large databases.
Bondmass, M., Bolger, N., Castro, G., & Avitall, B. (1999). The effect of physiologic home monitoring and telemanagement of chronic heart failure outcomes. The Internet Journal of Asthma, Allergy and Immunology, 3(2). ISSN:1523-6064.
Bozkaya, T., & Ozsoyoglu, M. (1997). Distance-based indexing for high-dimensional metric spaces. In Proceedings of ACM SIGMOD international conference on management of data (pp. 357–368).
Chakrabarti, K., & Mehrotra, S. (2000). Local dimensionality reduction: A new approach to indexing high dimensional spaces. In Proceedings of the conference on very large databases, Cairo, Egypt (pp. 89–100).
Ciaccia, P., Patella, M., & Zezula, P. (1997). M-Tree: An efficient access method for similarity search in metric spaces. In Proceedings of the international conference on very large databases, Athens, Greece (pp. 426–435).
Egecioglu, O., & Ferhatosmanoglu, H. (2000). Dimensionality reduction and similarity distance computation by inner product approximations. In Proceedings of ACM international conference on information and knowledge management (pp. 219–226).
Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of ACM international conference on knowledge discovery and data mining, Portland, OR (pp. 226–231).
Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994). Fast subsequence matching in time-series databases. ACM SIGMOD Records, 23(2), 419–429. CrossRef
Filho, R. F. S., Traina, A. J. M., Traina, C., & Faloutsos, C. (2001). Similarity search without tears: The OMNI family of all-purpose access methods. In Proceedings of IEEE international conference on data engineering (pp. 623–630).
Girgin, S., Polat, F., & Alhajj, R. (2007). Positive impact of state similarity on reinforcement learning performance. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 37(5), 1256–1270. CrossRef
Guha, S., Rastogi, R., & Shim, K. (1998). Cure: An efficient clustering algorithm for large databases. In Proceedings of ACM SIGMOD conference on management of data (pp. 73–84).
Guo, Z., Zhou, M. C., & Jiang, G. (2007). Adaptive sensor placement and boundary estimation for monitoring mass objects. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 38(1), 222–232. CrossRef
Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. In Proceedings of ACM SIGMOD international conference on management of data (pp. 47–57).
Hartigan, J. (1975). Clustering algorithms. Wiley, New York. MATH
Home and Community Care Digest (2007). Internet-based monitoring provides peace of mind for parents of children with asthma. Home and Community Care Digest, 6(4), 2007.
Jagadish, H. V., Ooi, B. C., Tan, K. L., Yu, C., & Zhang, R. (2005). iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Transactions on Database Systems, 30(2), 364–397. CrossRef
Katakis, I., Tsoumakas, G., Banos, E., Bassiliades, N., & Vlahavas, I. (2009). An adaptive personalized news dissemination system. Journal of Intelligent Information Systems, 32(2), 191–212. CrossRef
Katamaya, N., & Satoh, S. (1997). The SR-tree: An index structure for high-dimensional nearest neighbor queries. Proceedings of ACM SIGMOD international conference on management of data (pp. 369–380).
Keogh, E. J., Chu, S., & Pazzani, M. J. (2001). Ensemble-index: A new approach to indexing large databases. In Proceedings of ACM international conference on knowledge discovery and data mining (pp. 117–125).
Likas, A., Vlassis, N., & Verbeek, J. (2003). The global k-means clustering algorithm. Pattern Recognition, 36(2), 451–461. CrossRef
Locke, S. L., Cline, M. D., Wetzel, D. L., Pittman, M. T., Brewer, C. E., & Harveson, L. A. (2005). A web-based digital camera for monitoring remote wildlife. Wildlife Society Bulletin, 33(2), 761–765. CrossRef
Lukowski, T. I., Power, D., Yue, B., Randall, C. J., Youden, J., & Howell, C. (2004). Pipeline encroachment monitoring using polarimetric SAR imagery. In Proceedings of IEEE international symposium on geoscience and remote sensing (pp. 66–68).
Priede, I. G., & Swift, S. M. (1992). Wildlife telemetry: Remote monitoring and tracking of animals. Ellis Horwood.
Robinson, J. T. (1981). The K-D-B tree: A search structure for large multi-dimensional dynamic indexes. In Proceedings of ACM SIGMOD international conference on management of data (pp. 0– 18).
Seligman, L., Lehner, P., Smith, K., Elsaesser, C., & Mattox, D. (2000). Decision-centric information monitoring. Journal of Intelligent Information Systems, 14(1), 29–50. CrossRef
Shaft, U., & Ramakrishnan, R. (2005). When is nearest neighbors indexable? In Proceedings of the international conference on database theory (pp. 158–172).
Shah, N., Der, E., Ruggerio C., Heidenreich, P., & Massie, B. (1998). Prevention of hospitalizations for heart failure with an interactive home monitoring program. American Heart Journal, 135(2), 373–378. CrossRef
Talukder, A., Morookian, J., Monacos, S., Lam, R., LeBaw, C., & Lambert, J. L. (2005). Eye-tracking architecture for biometrics and remote monitoring. Applied Optics, 44, 693–700. CrossRef
Traina, C., Traina, A. J. M., Seeger, B., & Faloutsos, C. (2000). Slim-trees: Height performance metric trees minimizing overlap between nodes. In Proceedings of the international conference on extended database technology (pp. 51–65).
Vieira, M. R., Traina, C., Chino, F. J. T., & Traina, A. J. M. (2004). DBM-tree: A dynamic metric access method sensitive to local density data. In Proceedings of the Brazilian symposium on databases (pp. 163–177).
Wang, H., & Kasagami, F. (2008). A patient transfer apparatus between bed and stretcher. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 38(1), 60–67. CrossRef
Weber, R., Schek, H. J., & Blott, S. (1998). A quantitative analysis and performance study for similarity-search methods in high-dimensional space. In Proceedings of the international conference on very large databases (pp. 194–205).
White, D. A., & Jain, R. (1996). Similarity indexing with the ss-tree. In Proceedings of IEEE international conference on data engineering (pp. 516–523).
Yasuda, M., & Kawakami, K. (2002). New method of monitoring remote wildlife via the internet. Ecological Research, 17(1), 119–124. CrossRef
Yianilos, P. (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. In Proc. of ACM-SIAM symposium on discrete algorithms (pp. 311–321).
Zhang, M., & Alhajj, R. (2008). Novel approach for nearest neighbor search in high dimensional space. In Proceedings of IEEE international conference on intelligent systems, Bulgaria (pp. 26–31).
- Effective monitoring by efficient fingerprint matching using a forest of NAQ-trees
- Springer US
Neuer Inhalt/© ITandMEDIA