TY - GEN
T1 - Query Recombination
T2 - To Process a Large Number of Concurrent Top-k Queries towards IoT Data on an Edge Server
AU - Shi, Tuo
AU - Cai, Zhipeng
AU - Li, Yingshu
PY - 2022
Y1 - 2022
N2 - Multi-access Edge Computing is an important technique in the Internet of Things (IoT). It can help people observe the physical world by caching IoT data at an edge server and provide data query services. In this paper, we investigate how to process numerous concurrent top-k queries on an edge server. Since the computation resource of an edge server is limited and costly, processing concurrent top-k queries in the edge is totally different from that in the cloud. Researchers always focus on reducing time/space complexity of processing single top-k query in the cloud. However, how to process numerous top-k queries on an edge server in a cost-efficient manner still remains an open problem. In order to solve the problem, we propose the query recombination concept which aims at using the correlation of queries to reduce resource consumption of query processing. By adopting query recombination, we can make use of a small set of queries to answer the other queries and reduce resource consumption as well. We prove that constructing an optimal query recombination is NP-hard. Three approximate algorithms are proposed accordingly. Simulations are carried out to evaluate the performance of the proposed algorithms further, and the results show that the proposed algorithms are effective and efficient. © 2022 IEEE
AB - Multi-access Edge Computing is an important technique in the Internet of Things (IoT). It can help people observe the physical world by caching IoT data at an edge server and provide data query services. In this paper, we investigate how to process numerous concurrent top-k queries on an edge server. Since the computation resource of an edge server is limited and costly, processing concurrent top-k queries in the edge is totally different from that in the cloud. Researchers always focus on reducing time/space complexity of processing single top-k query in the cloud. However, how to process numerous top-k queries on an edge server in a cost-efficient manner still remains an open problem. In order to solve the problem, we propose the query recombination concept which aims at using the correlation of queries to reduce resource consumption of query processing. By adopting query recombination, we can make use of a small set of queries to answer the other queries and reduce resource consumption as well. We prove that constructing an optimal query recombination is NP-hard. Three approximate algorithms are proposed accordingly. Simulations are carried out to evaluate the performance of the proposed algorithms further, and the results show that the proposed algorithms are effective and efficient. © 2022 IEEE
UR - http://www.scopus.com/inward/record.url?scp=85140905925&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85140905925&origin=recordpage
U2 - 10.1109/ICDCS54860.2022.00060
DO - 10.1109/ICDCS54860.2022.00060
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-1-6654-7178-7
SP - 559
EP - 569
BT - Proceedings - 2022 IEEE 42nd International Conference on Distributed Computing Systems
PB - IEEE
ER -