TY - GEN
T1 - Light Agents Searching for Hot Information
AU - Kowalski, Dariusz R.
AU - Pajak, Dominik
N1 - Funding Information:
Partially supported by Polish National Science Center (NCN) grant 2019/33/B/ST6/02988 and by the NSF grant 2131538.
Publisher Copyright:
© 2022 International Joint Conferences on Artificial Intelligence. All rights reserved.
PY - 2022
Y1 - 2022
N2 - Agent-based crawlers are commonly used in network maintenance and information gathering. In order not to disturb the main functionality of the system, whether acting at nodes or being in transit, they need to operate online, perform a single operation fast and use small memory. They should also be preferably deterministic, as crawling agents have limited capabilities of generating a large number of truly random bits. We consider a system in which an agent receives an update, typically an insertion or deletion, of some information upon visiting a node. On request, the agent needs to output hot information, i.e., with the net occurrence above certain frequency threshold. A desired time and memory complexity of such agent should be poly-logarithmic in the number of visited nodes and inversely proportional to the frequency threshold. Ours is the first such agent with rigorous analysis and a complementary almost-matching lower bound.
AB - Agent-based crawlers are commonly used in network maintenance and information gathering. In order not to disturb the main functionality of the system, whether acting at nodes or being in transit, they need to operate online, perform a single operation fast and use small memory. They should also be preferably deterministic, as crawling agents have limited capabilities of generating a large number of truly random bits. We consider a system in which an agent receives an update, typically an insertion or deletion, of some information upon visiting a node. On request, the agent needs to output hot information, i.e., with the net occurrence above certain frequency threshold. A desired time and memory complexity of such agent should be poly-logarithmic in the number of visited nodes and inversely proportional to the frequency threshold. Ours is the first such agent with rigorous analysis and a complementary almost-matching lower bound.
UR - http://www.scopus.com/inward/record.url?scp=85137938116&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85137938116&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85137938116
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 363
EP - 369
BT - Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
A2 - De Raedt, Luc
A2 - De Raedt, Luc
PB - International Joint Conferences on Artificial Intelligence
T2 - 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Y2 - 23 July 2022 through 29 July 2022
ER -