Loading...
Please wait, while we are loading the content...
Similar Documents
Importance-aware Bloom Filter for Set Membership Queries in Streaming Data
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kulkarni, Pramod Bhoraskar, Ravi Gabale, Vijay |
| Copyright Year | 2011 |
| Abstract | Various data streaming applications like news feeds, stock trading generate a continuous sequence of data items. In such applications, based on the priority of different items, a set of items are more important than others. For instance, in stock trading, some stocks are more important than others, or in a cache-based system, the cost of fetching new objects into the cache is directly related to the the size of the objects. Motivated by these examples, our work focuses on developing a time and space efficient indexing and membership query scheme which takes into account data items with different importance levels. In this respect, we propose Importance-aware Bloom Filter (IBF), an extension of Bloom Filter (BF) which is a popular data structure to approximately answer membership queries on a set of items. As part of IBF, we provide a set of insertion and deletion algorithms to make BF importance-aware and to handle a set of unbounded data items. Our comparison of IBF with other Bloom filter-based mechanisms, for synthetic as well as real data sets, shows that IBF performs very well, it has low false positives, and low false negatives for important items. Importantly, we find properties of IBF analytically, for instance, we show that there exists a tight upper bound on false positive rate independent of the size of the data stream. We believe, IBF provides a practical framework to balance the application-specific requirements to index and query data items based on the data semantics. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.cse.iitb.ac.in/internal/techreports/reports/TR-CSE-2011-40.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
