Light Agents Searching for Hot Information

Dariusz R. Kowalski, Dominik Pajak

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
EditorsLuc De Raedt, Luc De Raedt
PublisherInternational Joint Conferences on Artificial Intelligence
Number of pages7
ISBN (Electronic)9781956792003
StatePublished - 2022
Event31st International Joint Conference on Artificial Intelligence, IJCAI 2022 - Vienna, Austria
Duration: Jul 23 2022Jul 29 2022

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823


Conference31st International Joint Conference on Artificial Intelligence, IJCAI 2022

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Light Agents Searching for Hot Information'. Together they form a unique fingerprint.

Cite this