Abstract
Many modern applications produce massive amounts of data series that need to be analyzed, requiring efficient similarity search operations. However, the state-of-the-art data series indexes that are used for this purpose do not scale well for massive datasets in terms of performance, or storage costs. We pinpoint the problem to the fact that existing summarizations of data series used for indexing cannot be sorted while keeping similar data series close to each other in the sorted order. This leads to two design problems. First, traditional bulk-loading algorithms based on sorting cannot be used. Instead, index construction takes place through slow top-down insertions, which create a non-contiguous index that results in many random I/Os. Second, data series cannot be sorted and split across nodes evenly based on their median value; thus, most leaf nodes are in practice nearly empty. This further slows down query speed and amplifies storage costs. To address these problems, we present Coconut. The first innovation in Coconut is an inverted, sortable data series summarization that organizes data series based on a z-order curve, keeping similar series close to each other in the sorted order. As a result, Coconut is able to use bulk-loading techniques that rely on sorting to quickly build a contiguous index using large sequential disk I/Os. We then explore prefix-based and median-based splitting policies for bottom-up bulk-loading, showing that median-based splitting outperforms the state of the art, ensuring that all nodes are densely populated. Overall, we show analytically and empirically that Coconut dominates the state-of-the-art data series indexes in terms of construction speed, query speed, and storage costs.
- Incorporated Research Institutions for Seismology - Seismic Data Access. http://ds.iris.edu/data/access/, 2016.Google Scholar
- Adhd-200. http://fcon_1000.projects.nitrc.org/indi/adhd200/, 2017.Google Scholar
- Sloan digital sky survey. https://www.sdss3.org/dr10/data_access/volume.php, 2017.Google Scholar
- A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Commun. ACM, 31(9):1116--1127, 1988. Google ScholarDigital Library
- R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient similarity search in sequence databases. In FODO, pages 69--84, 1993. Google ScholarDigital Library
- I. Assent, R. Krieger, F. Afschari, and T. Seidl. The ts-tree: efficient time series search and retrieval. In EDBT, pages 252--263, 2008. Google ScholarDigital Library
- A. Camerra, T. Palpanas, J. Shieh, and E. J. Keogh. isax 2.0: Indexing and mining one billion time series. In ICDM, pages 58--67, 2010. Google ScholarDigital Library
- A. Camerra, J. Shieh, T. Palpanas, T. Rakthanmanon, and E. Keogh. Beyond One Billion Time Series: Indexing and Mining Very Large Time Series Collections with iSAX2+. KAIS, 39(1):123--151, 2014.Google ScholarDigital Library
- K. Chakrabarti, E. J. Keogh, S. Mehrotra, and M. J. Pazzani. Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst., 27(2):188--228, 2002. Google ScholarDigital Library
- V. Chandola, A. Banerjee, and V. Kumar. Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3):15, 2009. Google ScholarDigital Library
- N. Dayan, M. Athanassoulis, and S. Idreos. Monkey: Optimal navigable key-value store. In SIGMOD, pages 79--94, 2017. Google ScholarDigital Library
- C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In SIGMOD, pages 419--429, 1994. Google ScholarDigital Library
- J. Grabocka, N. Schilling, and L. Schmidt-Thieme. Latent time-series motifs. TKDD, 11(1):6:1--6:20, 2016. Google ScholarDigital Library
- A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984. Google ScholarDigital Library
- P. Huijse, P. A. Estévez, P. Protopapas, J. C. Principe, and P. Zegers. Computational intelligence challenges and applications on large-scale astronomical time series databases. IEEE CIM, 9(3):27--39, 2014. Google ScholarDigital Library
- S. Idreos, M. L. Kersten, and S. Manegold. Database cracking. In CIDR 2007, pages 68--78, 2007.Google Scholar
- K. Kashino, G. Smith, and H. Murase. Time-series active search for quick retrieval of audio and video. In ICASSP, pages 2993--2996, 1999. Google ScholarDigital Library
- S. Kashyap and P. Karras. Scalable knn search on vertically stored time series. In SIGKDD, pages 1334--1342, 2011. Google ScholarDigital Library
- R. J. Kate. Using dynamic time warping distances as features for improved time series classification. Data Min. Knowl. Discov., 30(2):283--312, 2016. Google ScholarDigital Library
- E. J. Keogh. Fast similarity search in the presence of longitudinal scaling in time series databases. In ICTAI, pages 578--584, 1997. Google ScholarDigital Library
- E. J. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. KAIS, 3(3):263--286, 2001.Google ScholarCross Ref
- E. J. Keogh and M. J. Pazzani. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In KDD, pages 239--243, 1998. Google ScholarDigital Library
- F. Korn, H. V. Jagadish, and C. Faloutsos. Efficiently supporting ad hoc queries in large datasets of time sequences. In SIGMOD, pages 289--300, 1997. Google ScholarDigital Library
- S. T. Leutenegger, J. M. Edgington, and M. A. López. STR: A simple and efficient algorithm for r-tree packing. In ICDE, pages 497--506, 1997. Google ScholarDigital Library
- C. Li, P. S. Yu, and V. Castelli. Hierarchyscan: A hierarchical similarity search algorithm for databases of long sequences. In ICDE, pages 546--553, 1996. Google ScholarDigital Library
- T. W. Liao. Clustering of time series data - a survey. Pattern Recognition, 38(11):1857--1874, 2005. Google ScholarDigital Library
- J. Lin, E. J. Keogh, and W. Truppel. Clustering of streaming time series is meaningless. In DMKD, pages 56--65, 2003. Google ScholarDigital Library
- M. Linardi and T. Palpanas. ULISSE: ULtra compact Index for Variable-Length Similarity SEarch in Data Series. In ICDE, 2018.Google ScholarCross Ref
- M. Linardi, Y. Zhu, T. Palpanas, and E. J. Keogh. Matrix profile X: Valmod - scalable discovery of variable-length motifs in data series. In SIGMOD, 2018.Google ScholarDigital Library
- K. Mirylenka, V. Christophides, T. Palpanas, I. Pefkianakis, and M. May. Characterizing home device usage from wireless traffic time series. In EDBT, pages 551--562, 2016.Google Scholar
- G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Ottawa, International Business Machines Company, 1966.Google Scholar
- A. Mueen, H. Hamooni, and T. Estrada. Time series join on subsequence correlation. In ICDM, pages 450--459, 2014. Google ScholarDigital Library
- A. Mueen, E. J. Keogh, Q. Zhu, S. Cash, M. B. Westover, and N. B. Shamlo. A disk-aware algorithm for time series motif discovery. DAMI, 22(1-2):73--105, 2011. Google ScholarDigital Library
- A. Mueen, S. Nath, and J. Liu. Fast approximate correlation for massive time-series data. In SIGMOD, pages 171--182, 2010. Google ScholarDigital Library
- P. E. O'Neil, E. Cheng, D. Gawlick, and E. J. O'Neil. The log-structured merge-tree (lsm-tree). Acta Inf., 33(4):351--385, 1996. Google ScholarDigital Library
- T. Palpanas. Data series management: The road to big sequence analytics. SIGMOD Record, 44(2):47--52, 2015. Google ScholarDigital Library
- T. Palpanas. Big sequence management: A glimpse of the past, the present, and the future. In SOFSEM, pages 63--80, 2016. Google ScholarDigital Library
- T. Palpanas. The parallel and distributed future of data series mining. In HPCS, pages 916--920, 2017.Google ScholarCross Ref
- P. Paraskevopoulos, T.-C. Dinh, Z. Dashdorj, T. Palpanas, and L. Serafini. Identification and characterization of human behavior patterns from mobile phone data. In D4D Challenge session, NetMob, 2013.Google Scholar
- T. Pelkonen, S. Franklin, P. Cavallaro, Q. Huang, J. Meza, J. Teller, and K. Veeraraghavan. Gorilla: A fast, scalable, in-memory time series database. PVLDB, 8(12):1816--1827, 2015. Google ScholarDigital Library
- K. pong Chan and A. W. Fu. Efficient time series matching by wavelets. In ICDE, pages 126--133, 1999. Google ScholarDigital Library
- D. Rafiei. On similarity-based queries for time series data. In ICDE, pages 410--417, 1999. Google ScholarDigital Library
- D. Rafiei and A. O. Mendelzon. Similarity-based queries for time series data. In SIGMOD, pages 13--25, 1997. Google ScholarDigital Library
- T. Rakthanmanon, B. J. L. Campana, A. Mueen, G. E. A. P. A. Batista, M. B. Westover, Q. Zhu, J. Zakaria, and E. J. Keogh. Searching and mining trillions of time series subsequences under dynamic time warping. In SIGKDD, pages 262--270, 2012. Google ScholarDigital Library
- T. Rakthanmanon, E. J. Keogh, S. Lonardi, and S. Evans. Time series epenthesis: Clustering time series streams requires ignoring some data. In ICDM, pages 547--556, 2011. Google ScholarDigital Library
- R. Ramakrishnan and J. Gehrke. Database management systems (3. ed.). McGraw-Hill, 2003. Google ScholarDigital Library
- J. Rao and K. A. Ross. Making b+-trees cache conscious in main memory. In SIGMOD, pages 475--486, 2000. Google ScholarDigital Library
- C. A. Ratanamahatana and E. J. Keogh. Three myths about dynamic time warping data mining. In SIAM, pages 506--510, 2005.Google Scholar
- K. V. Ravi Kanth, D. Agrawal, and A. Singh. Dimensionality reduction for similarity searching in dynamic databases. In SIGMOD, pages 166--176, 1998. Google ScholarDigital Library
- U. Raza, A. Camerra, A. L. Murphy, T. Palpanas, and G. P. Picco. Practical data prediction for real-world wireless sensor networks. IEEE Trans. Knowl. Data Eng., 27(8):2231--2244, 2015.Google ScholarDigital Library
- P. P. Rodrigues, J. Gama, and J. P. Pedroso. Hierarchical clustering of time-series data streams. IEEE Trans. Knowl. Data Eng., 20(5):615--627, 2008. Google ScholarDigital Library
- D. Shasha. Tuning time series queries in finance: Case studies and recommendations. IEEE Data Eng. Bull., 22(2):40--46, 1999.Google Scholar
- J. Shieh and E. Keogh. iSAX: disk-aware mining and indexing of massive time series datasets. Data Mining and Knowledge Discovery, 19(1):24--57, 2009. Google ScholarDigital Library
- J. Shieh and E. J. Keogh. isax: indexing and mining terabyte sized time series. In ACM SIGKDD, pages 623--631, 2008. Google ScholarDigital Library
- S. Soldi, V. Beckmann, W. Baumgartner, G. Ponti, C. Shrader, P. Lubinski, H. Krimm, F. Mattana, and J. Tueller. Long-term variability of agn at hard x-rays. Astronomy & Astrophysics, 563:A57, 2014.Google ScholarCross Ref
- Y. Wang, P. Wang, J. Pei, W. Wang, and S. Huang. A data-adaptive and dynamic segmentation index for whole matching on time series. PVLDB, 6(10):793--804, 2013. Google ScholarDigital Library
- X. Xi, E. J. Keogh, C. R. Shelton, L. Wei, and C. A. Ratanamahatana. Fast time series classification using numerosity reduction. In ICML, pages 1033--1040, 2006. Google ScholarDigital Library
- D. E. Yagoubi, R. Akbarinia, F. Masseglia, and T. Palpanas. Dpisax: Massively distributed partitioned isax. In ICDM, pages 1135--1140, 2017.Google ScholarCross Ref
- L. Ye and E. J. Keogh. Time series shapelets: a new primitive for data mining. In ACM SIGKDD, pages 947--956, 2009. Google ScholarDigital Library
- K. Zoumpatianos, S. Idreos, and T. Palpanas. Indexing for interactive exploration of big data series. In SIGMOD, pages 1555--1566, 2014. Google ScholarDigital Library
- K. Zoumpatianos, S. Idreos, and T. Palpanas. RINSE: interactive data series exploration with ADS+. PVLDB, 8(12):1912--1915, 2015. Google ScholarDigital Library
- K. Zoumpatianos, S. Idreos, and T. Palpanas. ADS: the adaptive data series index. VLDB J., 25(6):843--866, 2016. Google ScholarDigital Library
- K. Zoumpatianos, Y. Lou, T. Palpanas, and J. Gehrke. Query workloads for data series indexes. In ACM SIGKDD, pages 1603--1612, 2015. Google ScholarDigital Library
- K. Zoumpatianos and T. Palpanas. Data series management: Fulfilling the need for big sequence analytics. In ICDE, 2018.Google Scholar
Index Terms
- Coconut: a scalable bottom-up approach for building data series indexes
Recommendations
Coconut: a scalable bottom-up approach for building data series indexes
Many modern applications produce massive amounts of data series that need to be analyzed, requiring efficient similarity search operations. However, the state-of-the-art data series indexes that are used for this purpose do not scale well for massive ...
Coconut: a scalable bottom-up approach for building data series indexes
Many modern applications produce massive amounts of data series that need to be analyzed, requiring efficient similarity search operations. However, the state-of-the-art data series indexes that are used for this purpose do not scale well for massive ...
Coconut Palm: Static and Streaming Data Series Exploration Now in your Palm
SIGMOD '19: Proceedings of the 2019 International Conference on Management of DataMany modern applications produce massive streams of data series and maintain them in indexes to be able to explore them through nearest neighbor search. Existing data series indexes, however, are expensive to operate as they issue many random I/Os to ...
Comments