TY - GEN
T1 - Multiset Membership Lookup in Large Datasets (Extended abstract)
AU - Chen, Lin
AU - Yu, Jihong
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85136433022
U2 - 10.1109/ICDE53745.2022.00122
DO - 10.1109/ICDE53745.2022.00122
M3 - Conference contribution
AN - SCOPUS:85136433022
T3 - Proceedings - International Conference on Data Engineering
SP - 1491
EP - 1492
BT - Proceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022
PB - IEEE Computer Society
T2 - 38th IEEE International Conference on Data Engineering, ICDE 2022
Y2 - 9 May 2022 through 12 May 2022
ER -