{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:25:20Z","timestamp":1740122720679,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T00:00:00Z","timestamp":1628035200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T00:00:00Z","timestamp":1628035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 del Salento"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present <jats:sc>afqn<\/jats:sc> (Approximate Fast <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>), a novel algorithm for approximate computation of the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> scale estimator in a streaming setting, in the sliding window model. It is well-known that computing the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> estimator exactly may be too costly for some applications, and the problem is a fortiori exacerbated in the streaming setting, in which the time available to process incoming data stream items is short. In this paper we show how to efficiently and accurately approximate the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> estimator. As an application, we show the use of <jats:sc>afqn<\/jats:sc> for fast detection of outliers in data streams. In particular, the outliers are detected in the sliding window model, with a simple check based on the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> scale estimator. Extensive experimental results on synthetic and real datasets confirm the validity of our approach by showing up to three times faster updates per second. Our contributions are the following ones: (i) to the best of our knowledge, we present the first approximation algorithm for online computation of the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> scale estimator in a streaming setting and in the sliding window model; (ii) we show how to take advantage of our <jats:sc>UDDSketch<\/jats:sc> algorithm for quantile estimation in order to quickly compute the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> scale estimator; (iii) as an example of a possible application of the <jats:italic>Q<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> scale estimator, we discuss how to detect outliers in an input data stream.<\/jats:p>","DOI":"10.1007\/s10489-021-02614-w","type":"journal-article","created":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T20:02:50Z","timestamp":1628107370000},"page":"5082-5099","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["AFQN: approximate Qn estimation in data streams"],"prefix":"10.1007","volume":"52","author":[{"given":"Italo","family":"Epicoco","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catiuscia","family":"Melle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1118-7109","authenticated-orcid":false,"given":"Massimo","family":"Cafaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Pulimeno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,4]]},"reference":[{"issue":"4","key":"2614_CR1","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum M, Floyd RW, Pratt VR, Rivest RL, Tarjan RE (1973) Time bounds for selection. J. Comput. Syst. Sci. 7(4):448\u2013461","journal-title":"J. Comput. Syst. Sci."},{"key":"2614_CR2","doi-asserted-by":"publisher","unstructured":"Cafaro M, Melle C, Pulimeno M, Epicoco I (2021) Fast online computation of the qn estimator with applications to the detection of outliers in data streams. Expert Syst Appl 164:113831. https:\/\/doi.org\/10.1016\/j.eswa.2020.113831. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0957417420306424","DOI":"10.1016\/j.eswa.2020.113831"},{"key":"2614_CR3","doi-asserted-by":"publisher","unstructured":"Chandola V, Banerjee A, Kumar V (2009) Anomaly detection: A survey (tr). ACM Comput Surv 41(3):1\u201358. https:\/\/doi.org\/10.1145\/1541880.1541882","DOI":"10.1145\/1541880.1541882"},{"key":"2614_CR4","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, Third Edition, 3rd edn. The MIT Press"},{"key":"2614_CR5","doi-asserted-by":"crossref","unstructured":"Croux C, Rousseeuw PJ (1992) Time-efficient algorithms for two highly robust estimators of scale. In: Dodge Y, Whittaker J (eds) Computational statistics. Physica-Verlag HD, Heidelberg, pp 411\u2013428","DOI":"10.1007\/978-3-662-26811-7_58"},{"key":"2614_CR6","unstructured":"Datar M, Gionis A, Indyk P, Motwani R (2002) Maintaining stream statistics over sliding windows: (extended abstract). In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201902. Society for Industrial and Applied Mathematics, Philadelphia, pp 635\u2013644"},{"key":"2614_CR7","doi-asserted-by":"publisher","unstructured":"Epicoco I, Melle C, Cafaro M, Pulimeno M, Morleo G (2020) Uddsketch: Accurate tracking of quantiles in data streams. IEEE Access 8:147604\u2013147617. https:\/\/doi.org\/10.1109\/ACCESS.2020.3015599","DOI":"10.1109\/ACCESS.2020.3015599"},{"issue":"3","key":"2614_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1145\/360680.360691","volume":"18","author":"RW Floyd","year":"1975","unstructured":"Floyd RW, Rivest RL (1975) Expected time bounds for selection. Commun ACM 18(3):165\u2013172","journal-title":"Commun ACM"},{"issue":"346","key":"2614_CR9","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1080\/01621459.1974.10482962","volume":"69","author":"FR Hampel","year":"1974","unstructured":"Hampel FR (1974) The influence curve and its role in robust estimation. J Am Stat Assoc 69 (346):383\u2013393. https:\/\/doi.org\/10.1080\/01621459.1974.10482962","journal-title":"J Am Stat Assoc"},{"issue":"7","key":"2614_CR10","first-page":"321","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare CAR (1961) Algorithm 65: find. Commun ACM 4(7):321\u2013322","journal-title":"Commun ACM"},{"key":"2614_CR11","doi-asserted-by":"publisher","unstructured":"Hodge V, Austin J (2004) A survey of outlier detection methodologies. Artif Intell Rev 22(2):85\u2013126. https:\/\/doi.org\/10.1023\/B:AIRE.0000045502.10941.a9","DOI":"10.1023\/B:AIRE.0000045502.10941.a9"},{"issue":"2","key":"2614_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1137\/0207013","volume":"7","author":"D Johnson","year":"1978","unstructured":"Johnson D, Mizoguchi T (1978) Selecting the k-th element in x + y and x_1 + x_2 + \u22ef + x_m. SIAM J Comput 7(2):147\u2013153. https:\/\/doi.org\/10.1137\/0207013","journal-title":"SIAM J Comput"},{"issue":"12","key":"2614_CR13","doi-asserted-by":"publisher","first-page":"2195","DOI":"10.14778\/3352063.3352135","volume":"12","author":"C Masson","year":"2019","unstructured":"Masson C, Rim JE, Lee HK (2019) Ddsketch: a fast and fully-mergeable quantile sketch with relative-error guarantees. Proc VLDB Endow 12(12):2195\u20132205. https:\/\/doi.org\/10.14778\/3352063.3352135","journal-title":"Proc VLDB Endow"},{"key":"2614_CR14","doi-asserted-by":"publisher","unstructured":"Mirzaian A, Arjomandi E (1985) Selection in x + y and matrices with sorted rows and columns. Inf Process Lett 20(1):13\u201317. https:\/\/doi.org\/10.1016\/0020-0190(85)90123-1. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0020019085901231","DOI":"10.1016\/0020-0190(85)90123-1"},{"issue":"2","key":"2614_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan S (2005) Data streams: Algorithms and applications. Found Trends\u00ae Theor Comput Sci 1(2):117\u2013236. https:\/\/doi.org\/10.1561\/0400000002","journal-title":"Found Trends\u00ae Theor Comput Sci"},{"key":"2614_CR16","doi-asserted-by":"crossref","unstructured":"Nunkesser R, Schettlinger K, Fried R (2008) Applying the qn estimator online. In: Preisach C, Burkhardt H, Schmidt-Thieme L, Decker R (eds) Data analysis, machine learning and applications. Springer, Berlin, pp 277\u2013284","DOI":"10.1007\/978-3-540-78246-9_33"},{"issue":"424","key":"2614_CR17","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1080\/01621459.1993.10476408","volume":"88","author":"PJ Rousseeuw","year":"1993","unstructured":"Rousseeuw PJ, Croux C (1993) Alternatives to the median absolute deviation. J Am Stat Assoc 88(424):1273\u20131283. https:\/\/doi.org\/10.1080\/01621459.1993.10476408","journal-title":"J Am Stat Assoc"},{"issue":"1","key":"2614_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/widm.2","volume":"1","author":"PJ Rousseeuw","year":"2011","unstructured":"Rousseeuw PJ, Hubert M (2011) Robust statistics for outlier detection. WIREs Data Min Knowl Discov 1(1):73\u201379. https:\/\/doi.org\/10.1002\/widm.2","journal-title":"WIREs Data Min Knowl Discov"},{"key":"2614_CR19","volume-title":"Economic control of quality of manufactured product","author":"WA Shewhart","year":"1931","unstructured":"Shewhart WA (1931) Economic control of quality of manufactured product. Macmillan And Co Ltd, London"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-021-02614-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10489-021-02614-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-021-02614-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T05:17:31Z","timestamp":1646457451000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10489-021-02614-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,4]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["2614"],"URL":"https:\/\/doi.org\/10.1007\/s10489-021-02614-w","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"type":"print","value":"0924-669X"},{"type":"electronic","value":"1573-7497"}],"subject":[],"published":{"date-parts":[[2021,8,4]]},"assertion":[{"value":"13 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}}]}}