TY - GEN
T1 - Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
AU - Qin, Lianke
AU - Reddy, Aravind
AU - Song, Zhao
AU - Xu, Zhaozhuo
AU - Zhuo, Danyang
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing data-structure for fast pairwise summation estimation. Given a data-set X ⊂ ℝd, a binary function f : ℝd × ℝd → ℝ, and a point y ∈ ℝd, the Pairwise Summation Estimate PSEX(y): = 1/|X|ΣxϵX f(x,y). For any given data-set X, we need to design a data-structure such that given any query point y ∈ ℝd, the data-structure approximately estimates PSEX(y) in time that is sub-linear in |X|. Prior works on this problem have focused exclusively on the case where the data-set is static, and the queries are independent. In this paper, we design a hashing-based PSE data-structure which works for the more practical dynamic setting in which insertions, deletions, and replacements of points are allowed. Moreover, our proposed Adam-Hash is also robust to adaptive PSE queries, where an adversary can choose query qj ∈ ℝd depending on the output from previous queries q1, q2,..., qj-1.
AB - In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing data-structure for fast pairwise summation estimation. Given a data-set X ⊂ ℝd, a binary function f : ℝd × ℝd → ℝ, and a point y ∈ ℝd, the Pairwise Summation Estimate PSEX(y): = 1/|X|ΣxϵX f(x,y). For any given data-set X, we need to design a data-structure such that given any query point y ∈ ℝd, the data-structure approximately estimates PSEX(y) in time that is sub-linear in |X|. Prior works on this problem have focused exclusively on the case where the data-set is static, and the queries are independent. In this paper, we design a hashing-based PSE data-structure which works for the more practical dynamic setting in which insertions, deletions, and replacements of points are allowed. Moreover, our proposed Adam-Hash is also robust to adaptive PSE queries, where an adversary can choose query qj ∈ ℝd depending on the output from previous queries q1, q2,..., qj-1.
UR - http://www.scopus.com/inward/record.url?scp=85147941185&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147941185&partnerID=8YFLogxK
U2 - 10.1109/BigData55660.2022.10020385
DO - 10.1109/BigData55660.2022.10020385
M3 - Conference contribution
AN - SCOPUS:85147941185
T3 - Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022
SP - 115
EP - 120
BT - Proceedings - 2022 IEEE International Conference on Big Data, Big Data 2022
A2 - Tsumoto, Shusaku
A2 - Ohsawa, Yukio
A2 - Chen, Lei
A2 - Van den Poel, Dirk
A2 - Hu, Xiaohua
A2 - Motomura, Yoichi
A2 - Takagi, Takuya
A2 - Wu, Lingfei
A2 - Xie, Ying
A2 - Abe, Akihiro
A2 - Raghavan, Vijay
T2 - 2022 IEEE International Conference on Big Data, Big Data 2022
Y2 - 17 December 2022 through 20 December 2022
ER -