GAMPS: compressing multi sensor data by grouping and amplitude scaling

ABSTRACT

We consider the problem of collectively approximating a set of sensor signals using the least amount of space so that any individual signal can be efficiently reconstructed within a given maximum (L∞) error ε. The problem arises naturally in applications that need to collect large amounts of data from multiple concurrent sources, such as sensors, servers and network routers, and archive them over a long period of time for offline data mining. We present GAMPS, a general framework that addresses this problem by combining several novel techniques. First, it dynamically groups multiple signals together so that signals within each group are correlated and can be maximally compressed jointly. Second, it appropriately scales the amplitudes of different signals within a group and compresses them within the maximum allowed reconstruction error bound. Our schemes are polynomial time O(α, β approximation schemes, meaning that the maximum (L∞) error is at most α ε and it uses at most β times the optimal memory. Finally, GAMPS maintains an index so that various queries can be issued directly on compressed data. Our experiments on several real-world sensor datasets show that GAMPS significantly reduces space without compromising the quality of search and query.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: Balinksi, M. L. On finding integer solutions to linear programs.In IBM Scientific Computing Symposium on Combinatorial Problems (1966), IBM, pp.225--248.
• 3: Buragohain, C., Shrivastava, N., and Suri, S. Space efficient streaming algorithms for the maximum error histogram.In ICDE (2007).
• 4: Chan, K., and Fu, A. efficient time series matching by wavelets. In ICDE (1999).
• 5: Qiuxia Chen , Lei Chen , Xiang Lian , Yunhao Liu , Jeffrey Xu Yu, Indexable PLA for efficient similarity search, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 6: Kelvin Kam Wing Chu , Man Hon Wong, Fast time-series searching with scaling and shifting, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-248, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304000]
• 7: Dang, T., Bulusu, N., and chi Feng, W. RIDA:A robust information-driven data compression architecture for irregular wireless sensor networks. In EWSN (2007).
• 8: Mayur Datar , S. Muthukrishnan, Estimating Rarity and Similarity over Data Stream Windows, Proceedings of the 10th Annual European Symposium on Algorithms, p.323-334, September 17-21, 2002
• 9: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Compressing historical information in sensor networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007628]
• 10: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 11: Minos Garofalakis , Amit Kumar, Deterministic wavelet thresholding for maximum-error metrics, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055582]
• 12: Carlos Guestrin , Peter Bodik , Romain Thibaux , Mark Paskin , Samuel Madden, Distributed regression: an efficient framework for modeling sensor network data, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984624]
• 13: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 14: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 15: Eamonn J. Keogh , Michael J. Pazzani, A Simple Dimensionality Reduction Technique for Fast Similarity Search in Large Time Series Databases, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.122-133, April 18-20, 2000
• 16: Naoto Kimura , Shahram Latifi, A Survey on Data Compression in Wireless Sensor Networks, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II, p.8-13, April 04-06, 2005 [doi>10.1109/ITCC.2005.43]
• 17: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 18: Kuehn, A., and Hamburger, M. Aheuristic program for locating warehouses. Management Science 9 (1963), 643--666.
• 19: Lazaridis, I., and Mehrotra, S. Capturing sensor-generated time series with quality guarantees. In ICDE (2003).
• 20: Xiaolei Li , Jiawei Han, Mining approximate top-k subspace anomalies in multi-dimensional time-series data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 21: Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882086]
• 22: Lin, J., Vlachos, M., Keogh, E., and Gunopulos, D. Iterative incremental clustering of time series. In EDBT (2004).
• 23: Liu, J., Priyantha, B., Zhao, F., Liang, C. M., Wang, Q., and James, S. Towards discovering data center genome using sensor nets. In HotEmNets (2008).
• 24: Suman Nath , Phillip B. Gibbons, Online maintenance of very large random samples on flash storage, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453961]
• 25: Spiros Papadimitriou , Jimeng Sun , Christos Faloutsos, Streaming pattern discovery in multiple time-series, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 26: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 27: Davood Rafiei , Alberto Mendelzon, Similarity-based queries for time series data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.13-25, May 11-15, 1997, Tucson, Arizona, United States
• 28: Davood Rafiei , Alberto O. Mendelzon, Querying Time Series Data Based on Similarity, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.675-693, September 2000 [doi>10.1109/69.877502]
• 29: Sharadh Ramaswamy , Kenneth Rose, Shared Descriptions Fusion Coding for Storage and Selective Retrieval of Correlated Sources, Proceedings of the Data Compression Conference, p.262-271, March 25-27, 2008 [doi>10.1109/DCC.2008.56]
• 30: Rugh, W. J. Linear System Theory Prentice Hall, 1995.
• 31: Slepian, D., and Wolf, J. Noiseless coding of correlated information sources. IEEE Trans. on Info. Theory 19 (1973).
• 32: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing Multidimensional Time-Series, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.1, p.1-20, January 2006 [doi>10.1007/s00778-004-0144-2]
• 33: Xiong, Z., Liveris, A. D., and Cheng, S. Distributed source coding for sensor networks. IEEE Signal Processing Magazine 21 (2004).

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Composite structures**

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

General Terms:
Algorithms, Performance, Theory

Keywords:
clustering, multi-sensor data compression