{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:14:18Z","timestamp":1760235258873,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"8","license":[{"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\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>Web search engines are built from components capable of processing large amounts of user queries per second in a distributed way. Among them, the index service computes the top-k documents that best match each incoming query by means of a document ranking operation. To achieve high performance, dynamic pruning techniques such as the WAND and BM-WAND algorithms are used to avoid fully processing all of the documents related to a query during the ranking operation. Additionally, the index service distributes the ranking operations among clusters of processors wherein in each processor multi-threading is applied to speed up query solution. In this scenario, a query running time prediction algorithm has practical applications in the efficient assignment of processors and threads to incoming queries. We propose a prediction algorithm for the WAND and BM-WAND algorithms. We experimentally show that our proposal is able to achieve accurate prediction results while significantly reducing execution time and memory consumption as compared against an alternative prediction algorithm. Our proposal applies the discrete Fourier transform (DFT) to represent key features affecting query running time whereas the resulting vectors are used to train a feed-forward neural network with back-propagation.<\/jats:p>","DOI":"10.3390\/fi13080204","type":"journal-article","created":{"date-parts":[[2021,8,4]],"date-time":"2021-08-04T03:57:41Z","timestamp":1628049461000},"page":"204","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A DFT-Based Running Time Prediction Algorithm for Web Queries"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7754-9996","authenticated-orcid":false,"given":"Oscar","family":"Rojas","sequence":"first","affiliation":[{"name":"CITIAPS, Universidad de Santiago, Santiago 9170020, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veronica","family":"Gil-Costa","sequence":"additional","affiliation":[{"name":"CONICET, Universidad Nacional de San Luis, San Luis 5700, Argentina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mauricio","family":"Marin","sequence":"additional","affiliation":[{"name":"CITIAPS, Universidad de Santiago, Santiago 9170020, Chile"},{"name":"CeBiB, Centre for Biotechnology and Bioengineering, Santiago 9170020, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Akdere, M., \u00c7etintemel, U., Riondato, M., Upfal, E., and Zdonik, S.B. (2012, January 1\u20135). Learning-based Query Performance Modeling and Prediction. Proceedings of the IEEE International Conference on Data Engineering, Arlington, VA, USA.","DOI":"10.1109\/ICDE.2012.64"},{"key":"ref_2","unstructured":"Ganapathi, A., Kuno, H., Dayal, U., Wiener, J.L., Fox, A., Jordan, M., and Patterson, D. (April, January 29). Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine Learning. Proceedings of the Conference on Data Engineering, Shanghai, China."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gupta, C., Mehta, A., and Dayal, U. (2008, January 2\u20136). PQR: Predicting Query Execution Times for Autonomous Workload Management. Proceedings of the Conference on Autonomic Computing, Chicago, IL, USA.","DOI":"10.1109\/ICAC.2008.12"},{"key":"ref_4","unstructured":"Kleerekoper, A., Navaridas, J., and Luj\u00e1n, M. (2019). Can the Optimizer Cost be Used to Predict Query Execution Times?. arXiv."},{"key":"ref_5","first-page":"1555","article-title":"Robust Estimation of Resource Consumption for SQL Queries Using Statistical Techniques","volume":"5","author":"Li","year":"2012","journal-title":"Very Large Data Base Endow."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Singhal, R., and Nambiar, M. (2016, January 11\u201313). Predicting SQL Query Execution Time for Large Data Volume. Proceedings of the International Database Engineering Applications Symposium, Montreal, QC, Canada.","DOI":"10.1145\/2938503.2938552"},{"key":"ref_7","unstructured":"Wu, W., Chi, Y., Zhu, S., Tatemura, J., Hacig\u00fcm\u00fcs, H., and Naughton, J.F. (2013, January 8\u201312). Predicting query execution time: Are optimizer cost models really unusable?. Proceedings of the International Conference on Data Engineering, Brisbane, QLD, Australia."},{"key":"ref_8","unstructured":"Baeza-Yates, R., and Ribeiro-Neto, B. (1999). Modern Information Retrieval, ACM Press\/Addison-Wesley."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1132956.1132959","article-title":"Inverted files for text search engines","volume":"38","author":"Zobel","year":"2006","journal-title":"ACM Comput. Surv."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Macdonald, C., Tonellotto, N., and Ounis, I. (2012, January 12\u201316). Learning to Predict Response Times for Online Query Scheduling. Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, Portland, OR, USA.","DOI":"10.1145\/2348283.2348367"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Rojas, O., Gil-Costa, V., and Marin, M. (2015, January 6\u20139). Running Time Prediction for Web Search Queries. Proceedings of the Parallel Processing and Applied Mathematics, Krakow, Poland.","DOI":"10.1007\/978-3-319-32152-3_20"},{"key":"ref_12","unstructured":"Badue, C.S., Almeida, J.M., Almeida, V., Baeza-Yates, R.A., Ribeiro-Neto, B.A., Ziviani, A., and Ziviani, N. (2010). Capacity Planning for Vertical Search Engines. arXiv."},{"key":"ref_13","unstructured":"Gil-Costa, V., Inostrosa-Psijas, A., Marin, M., and Feuestein, E. (March, January 27). Service Deployment Algorithms for Vertical Search Engines. Proceedings of the Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Belfast, UK."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MM.2003.1196112","article-title":"Web Search for a Planet: The Google Cluster Architecture","volume":"23","author":"Barroso","year":"2003","journal-title":"IEEE Micro"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Marin, M., Gil-Costa, V., and Gomez-Pantoja, C. (2010, January 21\u201325). New caching techniques for web search engines. Proceedings of the HPDC, Chicago, IL, USA.","DOI":"10.1145\/1851476.1851502"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/MCSE.2017.8","article-title":"Simulating Search Engines","volume":"19","author":"Marin","year":"2017","journal-title":"Comput. Sci. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Broder, A.Z., Carmel, D., Herscovici, M., Soffer, A., and Zien, J.Y. (2003, January 3\u20138). Efficient query evaluation using a two-level retrieval process. Proceedings of the Conference on Information and Knowledge Management, New Orleans, LA, USA.","DOI":"10.1145\/956863.956944"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ding, S., and Suel, T. (2011, January 24\u201328). Faster top-k document retrieval using block-max indexes. Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, Beijing, China.","DOI":"10.1145\/2009916.2010048"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chakrabarti, K., Chaudhuri, S., and Ganti, V. (2011, January 11\u201316). Interval-based pruning for top-k processing over compressed lists. Proceedings of the International Conference on Data Engineering, Hannover, Germany.","DOI":"10.1109\/ICDE.2011.5767855"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Tonellotto, N., Macdonald, C., and Ounis, I. (2011, January 28). Query Efficiency Prediction for Dynamic Pruning. Proceedings of the Large-Scale and Distributed Informational Retrieval, Glasgow, UK.","DOI":"10.1145\/2064730.2064734"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Freire, A., Macdonald, C., Tonellotto, N., Ounis, I., and Cacheda, F. (2012, January 12\u201316). Scheduling Queries Across Replicas. Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, Portland, OR, USA.","DOI":"10.1145\/2348283.2348508"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Cronen-Townsend, S., Zhou, Y., and Croft, W.B. (2002, January 11\u201315). Predicting Query Performance. Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, Tampere, Finland.","DOI":"10.1145\/564376.564429"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Peng, Z., and Plale, B. (2016, January 14). A Multi-tenant Fair Share Approach to Full-text Search Engine. Proceedings of the Data-Intensive Computing in the Cloud, Salt Lake City, UT, USA.","DOI":"10.1109\/DataCloud.2016.010"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3389795","article-title":"Using an Inverted Index Synopsis for Query Latency and Performance Prediction","volume":"38","author":"Tonellotto","year":"2020","journal-title":"ACM Trans. Inf. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Jeon, M., Kim, S., Hwang, S.W., He, Y., Elnikety, S., Cox, A.L., and Rixner, S. (2014, January 6\u201311). Predictive Parallelization: Taming Tail Latencies in Web Search. Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, Gold Coast, QLD, Australia.","DOI":"10.1145\/2600428.2609572"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kim, S., He, Y., Hwang, S.W., Elnikety, S., and Choi, S. (2015, January 2\u20136). Delayed-Dynamic-Selective (DDS) Prediction for Reducing Extreme Tail Latency in Web Search. Proceedings of the Conference on Web Search and Data Mining, Shanghai, China.","DOI":"10.1145\/2684822.2685289"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"19:1","DOI":"10.1145\/2943784","article-title":"Prediction and Predictability for Search Query Acceleration","volume":"10","author":"Hwang","year":"2016","journal-title":"ACM Trans. Web"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Tonellotto, N., Macdonald, C., and Ounis, I. (2013, January 4\u20138). Efficient and Effective Retrieval Using Selective Pruning. Proceedings of the ACM International Conference on Web Search and Data Mining, Rome, Italy.","DOI":"10.1145\/2433396.2433407"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Rojas, O., Gil-Costa, V., and Marin, M. (2013, January 26\u201330). Efficient Parallel Block-Max WAND Algorithm. Proceedings of the Euro-Par, Aachen, Germany.","DOI":"10.1007\/978-3-642-40047-6_41"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Bonacic, C., Bustos, D., Gil-Costa, V., Marin, M., and Sepulveda, V. (2015, January 23). Multithreaded Processing in Dynamic Inverted Indexes for Web Search Engines. Proceedings of the Large-Scale and Distributed Systems for IR, Melbourne, VIC, Australia.","DOI":"10.1145\/2809948.2809952"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Culpepper, J.S., Clarke, C.L.A., and Lin, J. (2016, January 5\u20137). Dynamic Cutoff Prediction in Multi-Stage Retrieval Systems. Proceedings of the Australasian Document Computing Symposium, Caulfield, VIC, Australia.","DOI":"10.1145\/3015022.3015026"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Wu, H., and Fang, H. (2014, January 3\u20137). Analytical Performance Modeling for Top-K Query Processing. Proceedings of the Information and Knowledge Management, Shanghai, China.","DOI":"10.1145\/2661829.2661931"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Rosset, C., Jose, D., Ghosh, G., Mitra, B., and Tiwary, S. (2018, January 8\u201312). Optimizing Query Evaluations Using Reinforcement Learning for Web Search. Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, Ann Arbor, MI, USA.","DOI":"10.1145\/3209978.3210127"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/j.ipm.2012.09.005","article-title":"Mining movies for song sequences with video based music genre identification system","volume":"49","author":"Doudpota","year":"2013","journal-title":"Inf. Process. Manag."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1857","DOI":"10.1016\/j.patcog.2005.01.025","article-title":"Clustering of Time Series Data-a Survey","volume":"38","year":"2005","journal-title":"Pattern Recogn."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"41823","DOI":"10.1109\/ACCESS.2019.2907929","article-title":"Exploring Popularity Predictability of Online Videos With Fourier Transform","volume":"7","author":"Zhou","year":"2019","journal-title":"IEEE Access"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1109\/TKDE.2004.1277815","article-title":"Fourier domain scoring: A novel document ranking method","volume":"16","author":"Park","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Zhang, H., Bie, S., and Luo, B. (2014, January 6\u201311). Classifying web documents using term spectral transforms and Multi-Dimensional Latent Semantic representation. Proceedings of the Joint Conference on Neural Networks, Beijing, China.","DOI":"10.1109\/IJCNN.2014.6889582"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Pryczek, M., and Szczepaniak, P.S. (2006, January 18\u201322). On Textual Documents Classification Using Fourier Domain Scoring. Proceedings of the Web Intelligence, Hong Kong, China.","DOI":"10.1109\/WI.2006.125"},{"key":"ref_40","unstructured":"Ambardar, A. (1999). Analog and Digital Signal Processing, Thomson. [2nd ed.]."}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/13\/8\/204\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:40:07Z","timestamp":1760164807000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/13\/8\/204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,4]]},"references-count":40,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["fi13080204"],"URL":"https:\/\/doi.org\/10.3390\/fi13080204","relation":{},"ISSN":["1999-5903"],"issn-type":[{"type":"electronic","value":"1999-5903"}],"subject":[],"published":{"date-parts":[[2021,8,4]]}}}