1 Introduction
In many real-world and large-scale network applications, it is more attractive and interesting to support Approximate Membership Query (AMQ), i.e., “, ” rather than exact-matching membership query, i.e., “.” By transforming “ ” to “, ” we do not need to probe the presence of point but its proximity to any member in the set under a given metric. Existing data ocean makes exact-matching queries costly that are too fragile and sensitive to data inconsistency and staleness. The brute-force searching to respond the exact-matching query can cause extremely high cost. In contrast, AMQ can relax constraints on user request to take much shorter time for the user to get satisfactory results. It also helps to identify uncertain and inaccurate inputs. In fact, the exact and approximate membership queries are not a new problem [1] but become crucial to existing and possible future applications due to their wide applications and performance requirements for query optimization that is unfortunately not fully addressed by conventional approaches. Recent research in [2], and [3] reveals that improvements made to AMQ can benefit both users and system performance.