Finding Representative Sampling Subsets in Sensor Graphs Using Time-series Similarities
Authors: 
Roshni Chakraborty, Josefine Holm, 
Torben Bach Pedersen, Petar PopovskiAuthors Info & Claims
Article No.: 89, Pages 1 - 32
Abstract
With the increasing use of Internet-of-Things–enabled sensors, it is important to have effective methods to query the sensors. For example, in a dense network of battery-driven temperature sensors, it is often possible to query (sample) only a subset of the sensors at any given time, since the values of the non-sampled sensors can be estimated from the sampled values. If we can divide the set of sensors into disjoint so-called representative sampling subsets, in which each represents all the other sensors sufficiently well, then we can alternate between the sampling subsets and, thus, increase the battery life significantly of the sensor network. In this article, we formulate the problem of finding representative sampling subsets as a graph problem on a so-called sensor graph with the sensors as nodes. Our proposed solution, SubGraphSample, consists of two phases. In Phase-I, we create edges in the similarity graph based on the similarities between the time-series of sensor values, analyzing six different techniques based on proven time-series similarity metrics. In Phase-II, we propose six different sampling techniques to find the maximum number of representative sampling subsets. Finally, we propose AutoSubGraphSample, which auto-selects the best technique for Phase-I and Phase-II for a given dataset. Our extensive experimental evaluation shows that AutoSubGraphSample can yield significant battery-life improvements within realistic error bounds.
References
[1]
Abubakar Abid and James Zou. 2018. Autowarp: Learning a warping distance from unlabeled time series using sequence autoencoders. Retrieved from https://arXiv:1810.10107.
[2]
Martin Aigner. 1999. A characterization of the Bell numbers. Discrete Math. 205, 1-3 (1999), 207–210.
[3]
Naomi S. Altman. 1992. An introduction to kernel and nearest-neighbor nonparametric regression. Amer. Stat. 46, 3 (1992), 175–185.
[4]
Shahzad Ashraf, Sehrish Saleem, and Tauqeer Ahmed. 2020. Sagacious communication link selection mechanism for underwater wireless sensors network. Int. J. Wirel. Microw. Technol. 10, 2 (2020), 12–25.
[5]
Yuanchao Bai, Fen Wang, Gene Cheung, Yuji Nakatsukasa, and Wen Gao. 2020. Fast graph sampling set selection using gershgorin disc alignment. IEEE Trans. Signal Process. 68 (2020), 2419–2434.
[6]
Donald J. Berndt and James Clifford. 1994. Using dynamic time warping to find patterns in time series. In Proceedings of the KDD Workshop. 359–370.
[7]
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. J. Stat. Mech.: Theory Exper. 2008, 10 (2008), P10008.
[8]
Jaime Carbonell and Jade Goldstein. 1998. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 335–336.
[9]
Luiz F. O. Chamon and Alejandro Ribeiro. 2017. Greedy sampling of graph signals. IEEE Trans. Signal Process. 66, 1 (2017), 34–47.
[10]
F. K.-P. Chan, A. W.-C. Fu, and Clement Yu. 2003. Haar wavelets for efficient similarity search of time-series: With and without time warping. IEEE Trans. Knowl. Data Eng. 15, 3 (2003), 686–705.
[11]
Lei Chen and Raymond Ng. 2004. On the marriage of lp-norms and edit distance. In Proceedings of the 30th International Conference on Very Large Data Bases-Volume 30. 792–803.
[12]
Lei Chen, M Tamer Özsu, and Vincent Oria. 2005. Robust and fast similarity search for moving object trajectories. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 491–502.
[13]
Siheng Chen, Rohan Varma, Aliaksei Sandryhaila, and Jelena Kovačević. 2015. Discrete signal processing on graphs: Sampling theory. IEEE Trans. Signal Process. 63, 24 (2015), 6510–6523.
[14]
Yueguo Chen, Mario A. Nascimento, Beng Chin Ooi, and Anthony K. H. Tung. 2007. Spade: On shape-based pattern detection in streaming time series. In Proceedings of the IEEE 23rd International Conference on Data Engineering. IEEE, 786–795.
[15]
Yan-Bin Chen, Ido Nevat, Pengfei Zhang, Sai Ganesh Nagarajan, and Hung-Yu Wei. 2018. Query-based sensors selection for collaborative wireless sensor networks with stochastic energy harvesting. IEEE Internet Things J. 6, 2 (2018), 3031–3043.
[16]
Alessandro Chiumento, Nicola Marchetti, and Irene Macaluso. 2019. Energy efficient WSN: A cross-layer graph signal processing solution to information redundancy. In Proceedings of the 16th International Symposium on Wireless Communication Systems (ISWCS). IEEE, 645–650.
[17]
Mario Coutino, Sundeep Prabhakar Chepuri, and Geert Leus. 2018. Subset selection for kernel-based signal reconstruction. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’18). IEEE, 4014–4018.
[18]
Padraig Cunningham and Sarah Jane Delany. 2021. K-nearest neighbour classifiers-a tutorial. ACM Comput. Surveys 54, 6 (2021), 1–25.
[19]
Marco Cuturi. 2011. Fast global alignment kernels. In Proceedings of the 28th International Conference on Machine Learning (ICML’11). 929–936.
[20]
Marco Cuturi and Mathieu Blondel. 2017. Soft-dtw: A differentiable loss function for time-series. In Proceedings of the International Conference on Machine Learning. PMLR, 894–903.
[21]
Kousik Das, Sovan Samanta, and Madhumangal Pal. 2018. Study on centrality measures in social networks: A survey. Soc. Netw. Anal. Min. 8, 1 (2018), 1–11.
[22]
Howard J. Diamond, Thomas R. Karl, Michael A. Palecki, C. Bruce Baker, Jesse E. Bell, Ronald D. Leeper, David R. Easterling, Jay H. Lawrimore, Tilden P. Meyers, Michael R. Helfert et al. 2013. U.S. climate reference network after one decade of operations: Status and assessment. Bull. Amer. Meteorol. Soc. 94, 4 (2013), 485–498.
[23]
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. 2015. Laplacian matrix learning for smooth graph signal representation. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’15). IEEE, 3736–3740.
[24]
Hilmi E. Egilmez, Eduardo Pavez, and Antonio Ortega. 2017. Graph learning from data under Laplacian and structural constraints. IEEE J. Select. Topics Signal Process. 11, 6 (2017), 825–841.
[25]
Christos Faloutsos, Mudumbai Ranganathan, and Yannis Manolopoulos. 1994. Fast subsequence matching in time-series databases. ACM SIGMOD Rec. 23, 2 (1994), 419–429.
[26]
Soheil Feizi, Daniel Marbach, Muriel Médard, and Manolis Kellis. 2013. Network deconvolution as a general method to distinguish direct dependencies in networks. Nature Biotechnol. 31, 8 (2013), 726–733.
[27]
Akshay Gadde, Aamir Anis, and Antonio Ortega. 2014. Active semi-supervised learning using sampling theory for graph signals. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 492–501.
[28]
Bugra Gedik, Ling Liu, and S. Yu Philip. 2007. ASAP: An adaptive sampling approach to data collection in sensor networks. IEEE Trans. Parallel Distrib. Syst. 18, 12 (2007), 1766–1783.
[29]
Zhichen Gong and Huanhuan Chen. 2018. Sequential data classification by dynamic state warping. Knowl. Info. Syst. 57, 3 (2018), 545–570.
[30]
Ram P. Gupta. 1968. Bounds on the Chromatic and Achromatic Numbers of Complimentary Graphs. Technical Report. Department of Statistics, North Carolina State University.
[31]
Sepideh Hassan-Moghaddam, Neil K. Dhingra, and Mihailo R. Jovanović. 2016. Topology identification of undirected consensus networks via sparse inverse covariance estimation. In Proceedings of the IEEE 55th Conference on Decision and Control (CDC’16). IEEE, 4624–4629.
[32]
Josefine Holm, Federico Chiariotti, Morten Nielsen, and Petar Popovski. 2021. Lifetime maximization of an internet of things (IoT) network based on graph signal processing. IEEE Communications Letters 25, 8 (2021), 2763–2767.
[33]
Tommi Jaakkola, Mark Diekhans, and David Haussler. 2000. A discriminative framework for detecting remote protein homologies. J. Comput. Biol. 7, 1-2 (2000), 95–114.
[34]
Weiwei Jiang. 2020. Time series classification: Nearest neighbor versus deep learning models. SN Appl. Sci. 2, 4 (2020), 1–17.
[35]
Vassilis Kalofolias. 2016. How to learn a graph from smooth signals. In Artificial Intelligence and Statistics. PMLR, 920–929.
[36]
Vassilis Kalofolias, Andreas Loukas, Dorina Thanou, and Pascal Frossard. 2017. Learning time varying graphs. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’17). IEEE, 2826–2830.
[37]
Fazle Karim, Somshubra Majumdar, Houshang Darabi, and Samuel Harford. 2019. Multivariate LSTM-FCNs for time series classification. Neural Netw. 116 (2019), 237–245.
[38]
Yoon Hak Kim. 2020. QR factorization-based sampling set selection for bandlimited graph signals. Signal Process. (2020), 107847.
[39]
Tim Van Der Lee, Georgios Exarchakos, and Sonia Heemstra De Groot. 2020. Distributed reliable and energy-efficient scheduling for lr-wpans. ACM Trans. Sensor Netw. 16, 4 (2020), 1–20.
[40]
Jure Leskovec, Kevin J. Lang, and Michael Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th International Conference on World Wide Web. 631–640.
[41]
Ian X. Y. Leung, Pan Hui, Pietro Lio, and Jon Crowcroft. 2009. Towards real-time community detection in large networks. Phys. Rev. E 79, 6 (2009), 066107.
[42]
Tianxing Liao, Wen-Qin Wang, Bang Huang, and Jian Xu. 2019. Learning Laplacian matrix for smooth signals on graph. In Proceedings of the IEEE International Conference on Signal, Information and Data Processing (ICSIDP). IEEE, 1–5.
[43]
Deyu Lin, Quan Wang, Weidong Min, Jianfeng Xu, and Zhiqiang Zhang. 2020. A survey on energy-efficient strategies in static wireless sensor networks. ACM Trans. Sensor Netw. 17, 1 (2020), 1–48.
[44]
Jason Lines and Anthony Bagnall. 2015. Time series classification with ensembles of elastic distance measures. Data Min. Knowl. Discov. 29, 3 (2015), 565–592.
[45]
Chong Liu, Kui Wu, and Jian Pei. 2007. An energy-efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation. IEEE Trans. Parallel Distrib. Syst. 18, 7 (2007), 1010–1023.
[46]
Jose A. Rosendo Macias and Antonio Gomez Exposito. 2005. Efficient computation of the running discrete Haar transform. IEEE Trans. Power Deliv. 21, 1 (2005), 504–505.
[47]
Lei Mao and Lisa Jackson. 2016. Selection of optimal sensors for predicting performance of polymer electrolyte membrane fuel cell. J. Power Sources 328 (2016), 151–160.
[48]
Gonzalo Mateos, Santiago Segarra, Antonio G. Marques, and Alejandro Ribeiro. 2019. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Process. Mag. 36, 3 (2019), 16–43.
[49]
Shinnosuke Matsuo, Xiaomeng Wu, Gantugs Atarsaikhan, Akisato Kimura, Kunio Kashino, Brian Kenji Iwana, and Seiichi Uchida. 2021. Attention to warp: Deep metric learning for multivariate time series. Retrieved from https://arXiv:2103.15074.
[50]
Michael D. Morse and Jignesh M. Patel. 2007. An efficient and accurate method for evaluating time series similarity. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 569–580.
[51]
Sunil K. Narang, Akshay Gadde, and Antonio Ortega. 2013. Signal processing techniques for interpolation in graph structured data. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE, 5445–5449.
[52]
Jyoti Narwariya, Pankaj Malhotra, Lovekesh Vig, Gautam Shroff, and T. V. Vishnu. 2020. Meta-learning for few-shot time series classification. In Proceedings of the 7th ACM IKDD CoDS and 25th COMAD. ACM, 28–36.
[53]
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José M. F. Moura, and Pierre Vandergheynst. 2018. Graph signal processing: Overview, challenges, and applications. Proc. IEEE 106, 5 (2018), 808–828.
[54]
Guillermo Ortiz-Jiménez, Mario Coutino, Sundeep Prabhakar Chepuri, and Geert Leus. 2018. Sampling and reconstruction of signals on product graphs. In Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP’18). IEEE, 713–717.
[55]
John Paparrizos, Chunwei Liu, Bruno Barbarioli, Johnny Hwang, Ikraduya Edian, Aaron J. Elmore, Michael J. Franklin, and Sanjay Krishnan. 2021. VergeDB: A database for IoT analytics on edge devices. In Proceedings of the Conference on Innovative Data Systems Research (CIDR’21).
[56]
Wenjie Pei, Hamdi Dibeklioğlu, David M. J. Tax, and Laurens van der Maaten. 2017. Multivariate time-series classification using the hidden-unit logistic model. IEEE Trans. Neural Netw. Learn. Syst. 29, 4 (2017), 920–931.
[57]
Rodrigo Pena. [n.d.]. Graph Learning. Retrieved from https://github.com/rodrigo-pena/graph-learning.
[58]
Nathanaël Perraudin, Johan Paratte, David Shuman, Lionel Martin, Vassilis Kalofolias, Pierre Vandergheynst, and David K. Hammond. 2014. GSPBOX: A toolbox for signal processing on graphs. Retrieved from https://arXiv:cs.IT/1408.5781.
[59]
Nathanael Perraudin, Benjamin Ricaud, David I. Shuman, and Pierre Vandergheynst. 2018. Global and local uncertainty principles for signals on graphs. APSIPA Trans. Signal Info. Process. 7 (2018).
[60]
Gilles Puy, Nicolas Tremblay, Rémi Gribonval, and Pierre Vandergheynst. 2018. Random sampling of bandlimited signals on graphs. Appl. Comput. Harmon. Anal. 44, 2 (2018), 446–475.
[61]
Lewis A. Rossman et al. 2000. EPANET 2: Users manual. http://personales.upv.es/piglesia/descarga/en2manual.pdf.
[62]
Britta Ruhnau. 2000. Eigenvector-centrality—A node-centrality? Social Netw. 22, 4 (2000), 357–365.
[63]
Akie Sakiyama, Yuichi Tanaka, Toshihisa Tanaka, and Antonio Ortega. 2019. Eigendecomposition-free sampling set selection for graph signals. IEEE Trans. Signal Process. 67, 10 (2019), 2679–2692.
[64]
Stan Salvador and Philip Chan. 2007. Toward accurate dynamic time warping in linear time and space. Intell. Data Anal. 11, 5 (2007), 561–580.
[65]
Alok Sharma, Kuldip K. Paliwal, Seiya Imoto, and Satoru Miyano. 2013. Principal component analysis using QR decomposition. Int. J. Mach. Learn. Cybernet. 4, 6 (2013), 679–683.
[66]
David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and P. Vanderghenyst. 2013. The emerging field of signal processing on graphs. IEEE Signal Process. Mag. (2013).
[67]
Vladimir Stojov, Nikola Koteli, Petre Lameski, and Eftim Zdravevski. 2018. Application of machine learning and time-series analysis for air pollution prediction. Proceedings of the 6th IASTED International Conference on Communications, Internet, and Information Technology (CIIT’18).
[68]
Nurgazy Sulaimanov and Heinz Koeppl. 2016. Graph reconstruction using covariance-based methods. EURASIP J. Bioinform. Syst. Biol. 2016, 1 (2016), 19.
[69]
Yuichi Tanaka, Yonina C. Eldar, Antonio Ortega, and Gene Cheung. 2020. Sampling signals on graphs: From theory to applications. IEEE Signal Process. Mag. 37, 6 (2020), 14–30.
[70]
V. A. Traag. 2015. Faster unfolding of communities: Speeding up the Louvain algorithm. Phys. Rev. E 92 (2015), 032801. Issue 3.
[71]
Mikhail Tsitsvero, Sergio Barbarossa, and Paolo Di Lorenzo. 2016. Signals on graphs: Uncertainty principle and sampling. IEEE Trans. Signal Process. 64, 18 (2016), 4845–4860.
[72]
Arun Venkitaraman, Saikat Chatterjee, and Peter Händel. 2019. Predicting graph signals using kernel regression where the input signal is agnostic to a graph. IEEE Trans. Signal Info. Process. Netw. 5, 4 (2019), 698–710.
[73]
Michail Vlachos, George Kollios, and Dimitrios Gunopulos. 2002. Discovering similar multidimensional trajectories. In Proceedings of the 18th International Conference on Data Engineering. IEEE, 673–684.
[74]
Xiaohan Wang, Pengfei Liu, and Yuantao Gu. 2015. Local-set-based graph signal reconstruction. IEEE Trans. Signal Process. 63, 9 (2015), 2432–2444.
[75]
Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann, and Eamonn Keogh. 2013. Experimental comparison of representation methods and distance measures for time series data. Data Min. Knowl. Discov. 26, 2 (2013), 275–309.
[76]
Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of “small-world” networks. Nature 393, 6684 (1998), 440–442.
[77]
Zhuangkun Wei, Bin Li, and Weisi Guo. 2019. Optimal sampling for dynamic complex networks with graph-bandlimited initialization. Retrieved from https://arXiv:1901.11405.
[78]
Robin Wilson and John J. Watkins. 2013. Combinatorics: Ancient & Modern. Oxford University Press, Oxford, UK.
[79]
Yi-Leh Wu, Divyakant Agrawal, and Amr El Abbadi. 2000. A comparison of DFT and DWT-based similarity search in time-series databases. In Proceedings of the 9th International Conference on Information and Knowledge Management. 488–495.
[80]
Zhengzheng Xing, Jian Pei, and Eamonn Keogh. 2010. A brief survey on sequence classification. ACM SIGKDD Explor. Newslett. 12, 1 (2010), 40–48.
[81]
Di Yao, Gao Cong, Chao Zhang, Xuying Meng, Rongchang Duan, and Jingping Bi. 2020. A linear time approach to computing time series similarity based on deep metric learning. IEEE Trans. Knowl. Data Eng. 34, 10 (2020), 4554–4571.
[82]
Byoung-Kee Yi and Christos Faloutsos. 2000. Fast time sequence indexing for arbitrary Lp norms. KiltHub.
[83]
Jiancheng Yin, Rixin Wang, Huailiang Zheng, Yuantao Yang, Yuqing Li, and Minqiang Xu. 2019. A new time series similarity measurement method based on the morphological pattern and symbolic aggregate approximation. IEEE Access 7 (2019), 109751–109762.
[84]
K.-B. Yu. 1991. Recursive updating the eigenvalue decomposition of a covariance matrix. IEEE Trans. Signal Process. 39, 5 (1991), 1136–1145.
[85]
Eftim Zdravevski, Petre Lameski, Riste Mingov, Andrea Kulakov, and Dejan Gjorgjevikj. 2015. Robust histogram-based feature engineering of time series data. In Proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, 381–388.
[86]
Eftim Zdravevski, Petre Lameski, Vladimir Trajkovik, Andrea Kulakov, Ivan Chorbev, Rossitza Goleva, Nuno Pombo, and Nuno Garcia. 2017. Improving activity recognition accuracy in ambient-assisted living systems by automated feature engineering. IEEE Access 5 (2017), 5262–5280.
Index Terms
- Finding Representative Sampling Subsets in Sensor Graphs Using Time-series Similarities
Recommendations
Metropolis Algorithms for Representative Subgraph Sampling
ICDM '08: Proceedings of the 2008 Eighth IEEE International Conference on Data MiningWhile data mining in chemoinformatics studied graph data with dozens of nodes, systems biology and the Internet are now generating graph data with thousands and millions of nodes. Hence data mining faces the algorithmic challenge of coping with this ...
Energy-balanced sampling workload allocation in wireless sensor networks
The quality of a wireless sensor network application is often measured by the number of samples collected in a period of time. Examples include debris flow monitoring systems, flood warning system and so on. In many situations, the number of collected ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
622 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 09 June 2023
Online AM: 11 May 2023
Accepted: 08 April 2023
Revised: 23 January 2023
Received: 29 June 2022
Published in TOSN Volume 19, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Danish Council for Independent Research
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 214Total Downloads
- Downloads (Last 12 months)73
- Downloads (Last 6 weeks)7
Reflects downloads up to 09 Feb 2025
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format