{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T13:02:28Z","timestamp":1749646948697},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>Time series data is common in many settings including scientific and financial applications. In these applications, the amount of data is often very large. We seek to support prediction queries over time series data. Prediction relies on model building which can be too expensive to be practical if it is based on a large number of data points. We propose to use statistical tests of hypotheses to choose a proper subset of data points to use for a given prediction query interval. This involves two steps: choosing a proper history length and choosing the number of data points to use within this history. Further, we use an I\/O conscious skip list data structure to provide samples of the original data set. Based on the statistics collected for a query workload, which we model as a probability mass function (PMF) over query intervals, we devise a randomized algorithm that selects a set of pre-built models (PM's) to construct, subject to some maintenance cost constraint when there are updates. Given this set of PM's, we discuss interesting query processing strategies for not only point queries, but also range, aggregation, and JOIN queries. We conduct a comprehensive empirical study on real world datasets to verify the effectiveness of our approaches and algorithms.<\/jats:p>","DOI":"10.14778\/1453856.1453962","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"984-995","source":"Crossref","is-referenced-by-count":17,"title":["A skip-list approach for efficiently processing forecasting queries"],"prefix":"10.14778","volume":"1","author":[{"given":"Tingjian","family":"Ge","sequence":"first","affiliation":[{"name":"Brown University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stan","family":"Zdonik","sequence":"additional","affiliation":[{"name":"Brown University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_28"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-5398(99)00013-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011785"},{"key":"e_1_2_1_4_1","first-page":"384","volume-title":"Aspnes and Gauri Shah. Skip Graphs. In Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"James","year":"2002","unstructured":"James Aspnes and Gauri Shah. Skip Graphs. In Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 384 -- 393 , January 2002 . James Aspnes and Gauri Shah. Skip Graphs. In Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 384--393, January 2002."},{"key":"e_1_2_1_5_1","first-page":"237","article-title":"Formula for the Sums of Powers of the Integers","volume":"9","author":"Boyer C. B.","year":"1943","unstructured":"Boyer , C. B. Pascal's Formula for the Sums of Powers of the Integers . In Scripta Math. 9 , 237 -- 244 , 1943 . Boyer, C. B. Pascal's Formula for the Sums of Powers of the Integers. In Scripta Math. 9, 237--244, 1943.","journal-title":"Scripta Math."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1007\/b97391","volume-title":"Introduction to Time Series and Forecasting","author":"Brockwell P.","year":"2002","unstructured":"Brockwell , P. , and Davis , R . Introduction to Time Series and Forecasting . 2 nd Edition. Springer Texts in Statistics. 2002 . Brockwell, P., and Davis, R. Introduction to Time Series and Forecasting. 2nd Edition. Springer Texts in Statistics. 2002.","edition":"2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260801"},{"key":"e_1_2_1_8_1","article-title":"25 Years of IIF Time Series Forecasting","author":"De Gooijer R. J.","year":"2005","unstructured":"J. G. De Gooijer and R. J. Hyndman . 25 Years of IIF Time Series Forecasting : A Selective Review. June 2005 . Tinbergen Institute Discussion Papers No. TI 05--068\/4. J. G. De Gooijer and R. J. Hyndman. 25 Years of IIF Time Series Forecasting: A Selective Review. June 2005. Tinbergen Institute Discussion Papers No. TI 05--068\/4.","journal-title":"A Selective Review."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142483"},{"key":"e_1_2_1_10_1","volume-title":"VLDB","author":"Duan S.","year":"2007","unstructured":"Duan S. , and Babu , S . Processing Forecasting Queries . In VLDB , 2007 . Duan S., and Babu, S. Processing Forecasting Queries. In VLDB, 2007."},{"key":"e_1_2_1_11_1","volume-title":"A Kalman Filter Primer","author":"Eubank R. L.","year":"2006","unstructured":"Eubank , R. L. A Kalman Filter Primer . Chapman & amp; Hall\/CRC, 2006 . Eubank, R. L. A Kalman Filter Primer. Chapman &amp; Hall\/CRC, 2006."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647484.726176"},{"key":"e_1_2_1_14_1","volume-title":"Foresight, Issue","author":"Hyndman R. J.","year":"2007","unstructured":"Hyndman , R. J. , Kostenko , A. V. Minimum Sample Size Requirements for Seasonal Forecasting Models . In Foresight, Issue 6, Spring 2007 . Hyndman, R. J., Kostenko, A. V. Minimum Sample Size Requirements for Seasonal Forecasting Models. In Foresight, Issue 6, Spring 2007."},{"key":"e_1_2_1_15_1","volume-title":"Forecasting Methods and Applications","author":"Makridakis S.","year":"1998","unstructured":"Makridakis , S. , Wheelwright S. , and Hyndman , R . Forecasting Methods and Applications . Third Edition. John Wiley & amp; Sons, Inc. 1998 . Makridakis, S., Wheelwright S., and Hyndman, R. Forecasting Methods and Applications. Third Edition. John Wiley &amp; Sons, Inc. 1998."},{"key":"e_1_2_1_16_1","volume-title":"Statistics for Engineering and the Sciences","author":"Mendenhall W.","year":"1994","unstructured":"Mendenhall , W. , and Sincich , T . Statistics for Engineering and the Sciences . Fourth Edition. Prentice-Hall, Inc. 1994 . Mendenhall, W., and Sincich, T. Statistics for Engineering and the Sciences. Fourth Edition. Prentice-Hall, Inc. 1994."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/for.3980030104"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_19_1","first-page":"367","volume-title":"Robert Sedgewick. Deterministic Skip Lists. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92)","author":"Ian Munro","unstructured":"J. Ian Munro , Thomas Papadakis, and Robert Sedgewick. Deterministic Skip Lists. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92) . Orlando, Florida, United States. pp. 367 -- 375 . J. Ian Munro, Thomas Papadakis, and Robert Sedgewick. Deterministic Skip Lists. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, United States. pp. 367--375."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115804"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978140"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.99"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142545"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1980.11995070"},{"key":"e_1_2_1_26_1","volume-title":"Calculus: Concepts and Contexts","author":"Stewart","year":"2001","unstructured":"J. Stewart . Calculus: Concepts and Contexts ( 2 nd ed.). Thomson Learning, Inc. 2001 . J. Stewart. Calculus: Concepts and Contexts (2nd ed.). Thomson Learning, Inc. 2001.","edition":"2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11669463_5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375783"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-2070(95)00647-8"},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"Wolniewicz R.","year":"1993","unstructured":"Wolniewicz , R. , and Graefe , G . Algebraic Optimization of Computations over Scientific Databases . In VLDB , 1993 . Wolniewicz, R., and Graefe, G. Algebraic Optimization of Computations over Scientific Databases. In VLDB, 1993."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2000.839383"},{"key":"e_1_2_1_32_1","volume-title":"SIGMOD","author":"Zhu Y.","year":"2003","unstructured":"Zhu , Y. , and Shasha , D . Query by Humming: a Time Series Database Approach . In SIGMOD , 2003 . Zhu, Y., and Shasha, D. Query by Humming: a Time Series Database Approach. In SIGMOD, 2003."},{"key":"e_1_2_1_33_1","unstructured":"http:\/\/dekorte.com\/projects\/opensource\/SkipDB\/.  http:\/\/dekorte.com\/projects\/opensource\/SkipDB\/."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:04:11Z","timestamp":1672225451000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453962"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453962","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}