International Journal of Computational Linguistics Research

DLINE Journals portal

Home

New Journals

Browse Journals

Journal Prices

For Authors

Print ISSN: 0976-416X
Online ISSN: 0976-4178

About IJCLR
	DLINE Portal Home Home Aims & Scope Editorial Board Current Issue Next Issue Previous Issue Sample Issue Upcoming Conferences Self-archiving policy Alert Services Be a Reviewer Publisher Paper Submission Subscription Contact us

How To Order
	Order Online Price Information Request for Complimentary Print Copy

For Authors
	Guidelines for Contributors Online Submission Call for Papers Author Rights

RELATED JOURNALS

Journal of Digital Information Management (JDIM)

Journal of Multimedia Processing and Technologies (JMPT)

International Journal of Web Application (IJWA)

International Journal of Computational Linguistics Research

RELATE: Preference-aware Correlation-based Query Refinement

Abdullah Albarrak
Al Imam Mohammad Ibn Saud Islamic University Saudi Arabia

Abstract: Data exploration techniques aim to efficiently and effectively guide users towards interesting data within massive, complex data. Being one of those techniques, query refinement goal is to automatically refine a userÃ¢â‚¬â„¢s query so that its result satisfies a certain constraint. In this paper, we focus on time series correlation as a constraint for refinement such that the result of a query is a pair of two subsequence time series. Differently than most existing works, we make use of the deviation from a correlation constraint as an objective to minimize in our problem. Moreover, we include users preferences as an objective to maximize in proportion to users input queries. The combination of these two objectives are prevalent in applications where users seek time series subsequences that exhibit a certain correlation value range and are close from their initial queries. Towards finding the optimal query satisfying these objectives, we propose an efficient computationalcentric algorithm and an innovative I/O-centric algorithm as well. We experimentally validate the efficiency and effectiveness of our proposed algorithms using real and synthetic data compared to recently proposed correlation-based subsequence search algorithms.

Keywords: Time Series, Correlation, Query Refinement RELATE: Preference-aware Correlation-based Query Refinement

DOI:https://doi.org/10.6025/jcl/2019/10/4/108-124

Full_Text PDF 3.5 MB Download: 323 times

References:

[1] Albarrak, A. M., Sharaf, M. A. (2017). Efficient schemes for similarity-aware refinement of aggregation queries. World Wide Web, 20 (6) 237-1267, 2017.
[2] Bikakis, N., Sellis, T. K. (2016). Exploration and visualization in the web of big linked data: A survey of the state of the art. In: Proceedings of the Workshops of the EDBT/ICDT 2016 Joint Conference, 2016.
[3] Bruno, N., Chaudhuri, S., Thomas, D. (2006). Generating queries with cardinality constraints for DBMS testing. IEEE Trans. Knowl. Data Eng., 18 (12) 1721-1725.
[4] Buoncristiano, M., Mecca, G., Quintarelli, E., Roveri, M., Santoro, D., Tanca, L. (2015). Database challenges for exploratory computing. SIGMOD Record, 44 (2) 17{22, 2015.
[5] Guo, T., Sathe, S., Aberer, K. (2015). Fast distributed correlation discovery over streaming time-series data. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM 2015, Melbourne, VIC, Australia, October 19 - 23, 2015, p. 1161-1170, 2015.
[6] Idreos, S., Papaemmanouil, O., Chaudhuri, S. (2015). Overview of data exploration techniques. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, p. 277-281, 2015.
[7] Jiang, L., Nandi, A. (2015). Snaptoquery: Providing interactive feedback during exploratory query specification. PVLDB, 8(11) 1250-1261, 2015.
[8] Kadlag, A., Wanjari, A. V., Freire, J., Haritsa, J. R. (2004). Supporting exploratory queries in databases. In: DASFAA, p. 594- 605, 2004.
[9] Kersten, M. L., Idreos, S., Manegold, S., Liarou, E. (2011). The researcher’s guide to the data deluge: Querying a scientific database in just a few seconds. PVLDB, 4(12)1474-1477, 2011.
[10] Li, Y., L., Yiu, H. U, M. L., Gong, Z. (2013). Discovering longest-lasting correlation in sequence databases. PVLDB, 6 (14) 1666-1677, 2013.
[11] Mishra, C., Koudas, N. (2009). Interactive query refinement. In: EDBT 2009, 12th International Conference on Extending Database Technology, Saint Petersburg, Russia, March 24-26, 2009, Proceedings, p. 862-873, 2009.
[12] Mishra, C., Koudas, N., Zuzarte, C. (2008). Generating targeted queries for database testing. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, p. 499-510, 2008.
[13] Mottin, D., Marascu, A., Roy, S. B., Das, G., Palpanas, T., Velegrakis,Y. (2014). IQR: an interactive query relaxation system for the empty-answer problem. In: International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, p. 1095-1098, 2014.
[14] Mueen, A., Hamooni, H., Estrada, T. (2014). Time series join on subsequence correlation. In: 2014 IEEE International Conference on Data Mining, ICDM 2014, Shenzhen, China, December 14-17, 2014, p. 450{459, 2014.
[15] Mueen, A., Nath, S., Liu, J. (2010). Fast approximate correlation for massive time-series data. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, p. 171-182, 2010.
[16] Muslea, I. (2004). Machine learning for online query relaxation. In KDD, p. 246-255, 2004.
[17] Sakurai, Y., Papadimitriou, S., Faloutsos, C. (2005). BRAID: stream mining through group lag correlations. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005, p. 599-610, 2005.
[18] Tran, Q. T., Chan, C. (2010). How to conquer why-not questions. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, p. 15-26, 2010.
[19] Vartak, M., Raghavan, V., Rudensteiner, E., Madden, S. (2016). Refinement driven processing of aggregation constrained queries. In Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016, Bordeaux, France, March 15-16, 2016, Bordeaux, France, March 15-16, 2016., p. 101-112, 2016.
[20] Vartak, M.,Raghavan, V., Rundensteiner, E. A. (2010). Qrelx: generating meaningful queries that provide cardinality assurance. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, p. 1215-1218, 2010.
[21] Zhu, Y., and Shasha, D. (2002). Statstream: Statistical monitoring of thousands of data streams in real time. In: VLDB 2002, Proceedings of 28th International Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong, China, p. 358-369, 2002.

DLINE Journals portal