{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T02:04:29Z","timestamp":1772676269670,"version":"3.50.1"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T00:00:00Z","timestamp":1649376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Key-Area Research and Development Program of Guangdong Province","award":["2021B0101190003"],"award-info":[{"award-number":["2021B0101190003"]}]},{"name":"Science and Technology Program of Guangzhou, China","award":["201804020053"],"award-info":[{"award-number":["201804020053"]}]},{"name":"Natural Science Foundation of Guangdong Province, China","award":["No.2022A1515010831"],"award-info":[{"award-number":["No.2022A1515010831"]}]},{"name":"US National Science Foundation","award":["DMS-1912958"],"award-info":[{"award-number":["DMS-1912958"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Sample entropy, an approximation of the Kolmogorov entropy, was proposed to characterize complexity of a time series, which is essentially defined as \u2212log(B\/A), where B denotes the number of matched template pairs with length m and A denotes the number of matched template pairs with m+1, for a predetermined positive integer m. It has been widely used to analyze physiological signals. As computing sample entropy is time consuming, the box-assisted, bucket-assisted, x-sort, assisted sliding box, and kd-tree-based algorithms were proposed to accelerate its computation. These algorithms require O(N2) or O(N2\u22121m+1) computational complexity, where N is the length of the time series analyzed. When N is big, the computational costs of these algorithms are large. We propose a super fast algorithm to estimate sample entropy based on Monte Carlo, with computational costs independent of N (the length of the time series) and the estimation converging to the exact sample entropy as the number of repeating experiments becomes large. The convergence rate of the algorithm is also established. Numerical experiments are performed for electrocardiogram time series, electroencephalogram time series, cardiac inter-beat time series, mechanical vibration signals (MVS), meteorological data (MD), and 1\/f noise. Numerical results show that the proposed algorithm can gain 100\u20131000 times speedup compared to the kd-tree and assisted sliding box algorithms while providing satisfactory approximate accuracy.<\/jats:p>","DOI":"10.3390\/e24040524","type":"journal-article","created":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T12:11:14Z","timestamp":1649419874000},"page":"524","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Super Fast Algorithm for Estimating Sample Entropy"],"prefix":"10.3390","volume":"24","author":[{"given":"Weifeng","family":"Liu","sequence":"first","affiliation":[{"name":"Guangdong Province Key Laboratory of Computational Science, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Jiang","sequence":"additional","affiliation":[{"name":"Guangdong Province Key Laboratory of Computational Science, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuesheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Old Dominion University, Norfolk, VA 23529, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2297","DOI":"10.1073\/pnas.88.6.2297","article-title":"Approximate entropy as a measure of system complexity","volume":"88","author":"Pincus","year":"1991","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1152\/ajpheart.2000.278.6.H2039","article-title":"Physiological time-series analysis using approximate entropy and sample entropy","volume":"278","author":"Richman","year":"2000","journal-title":"Am. J. Physiol. Heart Circ. Physiol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"068102","DOI":"10.1103\/PhysRevLett.89.068102","article-title":"Multiscale entropy analysis of complex physiologic time series","volume":"89","author":"Costa","year":"2002","journal-title":"Phys. Rev. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1016\/j.cam.2011.06.007","article-title":"Hierarchical entropy analysis for biological signals","volume":"236","author":"Jiang","year":"2011","journal-title":"J. Comp. Appl. Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/j.ymssp.2017.12.008","article-title":"A fault diagnosis scheme for planetary gearboxes using adaptive multi-scale morphology filter and modified hierarchical permutation entropy","volume":"105","author":"Li","year":"2017","journal-title":"Mech. Syst. Signal Proc."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"107182","DOI":"10.1016\/j.ymssp.2020.107182","article-title":"Hierarchical multiscale permutation entropy-based feature extraction and fuzzy support tensor machine with pinball loss for bearing fault identification","volume":"149","author":"Yang","year":"2021","journal-title":"Mech. Syst. Signal Proc."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Li, W., Shen, X., and Li, Y. (2019). A comparative study of multiscale sample entropy and hierarchical entropy and its application in feature extraction for ship-radiated noise. Entropy, 21.","DOI":"10.3390\/e21080793"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1142\/S1793536911000775","article-title":"A fast algorithm for computing sample entropy","volume":"3","author":"Jiang","year":"2011","journal-title":"Adv. Adapt. Data Anal."},{"key":"ref_9","unstructured":"Mao, D. (2008). Biological Time Series Classification via Reproducing Kernels and Sample Entropy. [Ph.D. Dissertation, Syracuse University]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0375-9601(90)90577-B","article-title":"An optimized box-assisted algorithm for fractal dimensions","volume":"148","author":"Grassberger","year":"1990","journal-title":"Phys. Lett. A"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"4456","DOI":"10.1103\/PhysRevA.36.4456","article-title":"Efficient algorithm for estimating the correlation dimension from a set of discrete points","volume":"36","author":"Theiler","year":"1987","journal-title":"Phys. Rev. A Gen. Phys."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.cmpb.2008.02.008","article-title":"Fast computation of approximate entropy","volume":"91","author":"Manis","year":"2008","journal-title":"Comput. Meth. Prog. Biomed."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Manis, G., Aktaruzzaman, M., and Sassi, R. (2018). Low computational cost for sample entropy. Entropy, 20.","DOI":"10.3390\/e20010061"},{"key":"ref_14","first-page":"9312616","article-title":"A low-cost implementation of sample entropy in wearable embedded systems: An example of online analysis for sleep eeg","volume":"70","author":"Wang","year":"2021","journal-title":"IEEE Trans. Instrum. Meas."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tom\u010dala, J. (2020). New fast ApEn and SampEn entropy algorithms implementation and their application to supercomputer power consumption. Entropy, 22.","DOI":"10.3390\/e22080863"},{"key":"ref_16","unstructured":"Shekelyan, M., and Cormode, G. (2021, January 13\u201315). Sequential Random Sampling Revisited: Hidden Shuffle Method. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Virtually Held."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Karr, A.F. (1993). Probability, Springer.","DOI":"10.1007\/978-1-4612-0891-4"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1017\/S0004972718000059","article-title":"A simple proof of the strong law of large numbers with rates","volume":"97","author":"Luzia","year":"2018","journal-title":"Bull. Aust. Math. Soc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1161\/01.CIR.101.23.e215","article-title":"Physiobank, physiotoolkit, and physionet: Components of a new research resource for complex physiologic signals","volume":"101","author":"Goldberger","year":"2000","journal-title":"Circulation"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2446","DOI":"10.1109\/TII.2018.2864759","article-title":"Highly accurate machine fault diagnosis using deep transfer learning","volume":"15","author":"Shao","year":"2019","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_21","unstructured":"(2022, March 27). Case Western Reserve University Bearing Data Center. Available online: https:\/\/engineering.case.edu\/bearingdatacenter."},{"key":"ref_22","unstructured":"(2022, March 27). Royal Netherlands Meteorological Institute. Available online: https:\/\/www.knmi.nl\/nederland-nu\/klimatologie\/uurgegevens."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1093\/europace\/eum096","article-title":"Abrupt changes in fibrillatory wave characteristics at the termination of paroxysmal atrial fibrillation in humans","volume":"9","author":"Petrutiu","year":"2007","journal-title":"Europace"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/BF02344885","article-title":"Long-term st database: A reference for the development and evaluation of automated ischaemia detectors and for the study of the dynamics of myocardial ischaemia","volume":"41","author":"Jager","year":"2003","journal-title":"Med. Biol. Eng. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1016\/S0735-1097(86)80478-8","article-title":"Survival of patients with severe congestive heart failure treated with oral milrinone","volume":"7","author":"Baim","year":"1986","journal-title":"J. Am. Coll. Cardiol."},{"key":"ref_26","first-page":"96","article-title":"The massachusetts general hospital-marquette foundation hemodynamic and electrocardiographic database\u2013comprehensive collection of critical care waveforms","volume":"7","author":"Welch","year":"1991","journal-title":"Clin. Monit."},{"key":"ref_27","unstructured":"Shoeb, A.H. (2009). Application of Machine Learning to Epileptic Seizure Onset Detection and Treatment. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"045002","DOI":"10.1088\/2057-1976\/2\/4\/045002","article-title":"Two-dimensional sample entropy: Assessing image texture through irregularity","volume":"2","author":"Silva","year":"2016","journal-title":"Biomed. Phys. Eng. Expr."},{"key":"ref_29","unstructured":"DeGroot, M.H., and Schervish, M.J. (2012). Probability and Statistics, Person Education. [4th ed.]."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/4\/524\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:50:26Z","timestamp":1760136626000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/4\/524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,8]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["e24040524"],"URL":"https:\/\/doi.org\/10.3390\/e24040524","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,8]]}}}