Light Agents Searching for Hot Information
Light Agents Searching for Hot Information
复制标题
DOI：
10.24963/ijcai.2022/52
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
D. Kowalski;Dominik Pajak
中科院分区：
文献类型：
--
作者：
D. Kowalski;Dominik Pajak
基于代理的爬虫是网络维护和信息收集中常用的爬虫。为了不干扰系统的主要功能，无论是在节点上还是在传输中，它们都需要在线运行，快速执行单个操作并且使用小内存。它们最好是确定性的，因为爬行代理生成大量真正随机比特的能力有限。我们考虑一个系统，其中代理在访问节点时接收一些信息的更新，通常是插入或删除。根据请求，代理需要输出热点信息，即净发生次数高于某个频率阈值的信息。这种代理的期望时间和内存复杂度应该是访问节点数量的多对数，并与频率阈值成反比。我们的代理是第一个具有严格分析和互补几乎匹配的下界的代理。
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.