Abstract
We investigate multiset membership lookup prob-lem, a pivotal functionality in many computing and networking paradigms. We devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first propose multi-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure called balanced multi-hash color table to improve the compactness by integrating load balancing.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022 |
| Publisher | IEEE Computer Society |
| Pages | 1491-1492 |
| Number of pages | 2 |
| ISBN (Electronic) | 9781665408837 |
| DOIs | |
| Publication status | Published - 2022 |
| Event | 38th IEEE International Conference on Data Engineering, ICDE 2022 - Virtual, Online, Malaysia Duration: 9 May 2022 → 12 May 2022 |
Publication series
| Name | Proceedings - International Conference on Data Engineering |
|---|---|
| Volume | 2022-May |
| ISSN (Print) | 1084-4627 |
Conference
| Conference | 38th IEEE International Conference on Data Engineering, ICDE 2022 |
|---|---|
| Country/Territory | Malaysia |
| City | Virtual, Online |
| Period | 9/05/22 → 12/05/22 |
Fingerprint
Dive into the research topics of 'Multiset Membership Lookup in Large Datasets (Extended abstract)'. Together they form a unique fingerprint.Cite this
Chen, L., & Yu, J. (2022). Multiset Membership Lookup in Large Datasets (Extended abstract). In Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022 (pp. 1491-1492). (Proceedings - International Conference on Data Engineering; Vol. 2022-May). IEEE Computer Society. https://doi.org/10.1109/ICDE53745.2022.00122