Balloon: An Adaptive Indexing System for Distributed Collaborative Edge Data Query

Edge computing facilitates the development and implementation of new mechanisms for data storage on edge servers located near users, thereby enabling low-latency edge data retrieval services. However, individual edge servers have limited storage capacity, which restricts their ability to meet edge users' diverse data demands. They often need to cooperate with neighbors. Edge data indexing systems play a crucial role in helping edge servers locate the requested data. Existing edge data indexing systems typically rely on static indexing structures, which may lead to significantly reduced query accuracy or excessive system memory overhead in dynamic edge data query (EDQ) scenarios, making it difficult to meet the high scalability requirements of edge computing systems. In this paper, we address these challenges and propose a novel adaptive edge data indexing system called Balloon, which dynamically scales memory usage to balance query accuracy and memory overhead as data volume varies at runtime. Specifically, each edge server maintains a resizable Adaptive Bloom Filter (ABF) for its local data, and builds a Balloon tree that aggregates the ABFs of neighboring servers within a latency constraint. The size of the Balloon tree dynamically scales with data volume to balance query accuracy and memory overhead. To validate Balloon, we implement and conduct comprehensive experiments using an edge storage system with 50 edge servers. The results indicate that, compared to the state-of-the-art edge indexing system, Balloon improves query accuracy by 26.74% and reduces query time by 18.16%. In the meantime, it reduces up to 35.66% memory overhead.