Efficient data structures and protocols with applications in space-time constrained systems.

摘要

Space-time efficient data structures can benefit many application systems. Space-efficiency describes a data structure that can fit compactly into the memory. The term time-efficiency implies that accessing/updating it requires short period of time. In this work, we cover space-time efficient data structures related to four abstract problems: set membership checking, multi-set membership checking, distributed set joining, and set size estimation. The goal is to improve the space-time efficiency of existing solutions.;We first study an efficient set representation -- the Bloom filter. Traditional Bloom filters offer excellent space efficiency, but each lookup requires multiple hash computations and multiple memory accesses. We propose a new family of space-time efficient Bloom filters that provide the same space efficiency, but requires much fewer memory accesses for each lookup. Due to wide applicability, any improvement to the performance of Bloom filters can potentially have a broad impact in many areas of research.;Then we further propose a data structure for representing multi-sets, where a set ID is associated with each member element. Our proposed data structure can reduce the space and computational complexity, yet keep the error ratio in a pretty low level.;Next, we design another Bloom filter variant called adaptive Bloom filter for efficient joining two distributed sets. When two nodes in distributed system exchange their elements to find out common ones, the Bloom filter can be used to encode element IDs with fewer network overhead. Our design can further reduce the amount of data that is exchanged.;Then, we apply our efficient Bloom filter idea to cyber-physical systems. We show that the space-time domain in computer/network system can be mapped to the time-energy domain of an RFID system. Based on the partitioned Bloom filter and our efficient Bloom filter idea, we design two time-energy efficient protocols for RFID systems. We show how to tweak the data structures to adapt to application-specific features.;Last, we propose two light-weighted protocols to estimate the cardinality of vehicles in a region. Future vehicles may be equipped with wireless devices to form a powerful vehicular peer to peer network. For a stationary wireless network, this problem has been extensively studied. However, it becomes much more challenging for mobile vehicular peer-to-peer networks whose topologies are constantly changing, and the estimation protocol has to be fast to take a useful snapshot of the dynamic network. Our protocols are based on circled random walks and tokened random walks. With simulations under two different mobility models, we show the efficiency of our protocols.