An Index for Set Intersection With Post-Filtering
R. Wang, Shangqi Lu, Yufei Tao · IEEE Transactions on Knowledge and Data Engineering · 2023
This paper studies how to design an index structure on a collection of sets$S_{1}, S_{2},{\ldots }, S_{n}$to answer the following queries: given distinct set ids$a, b \in [1, n]$, report$F(S_{a} \cap S_{b})$where$F(.)$is a filtering function. We present a solution that can support a great variety of filtering functions — range research, skyline, convex hull, nearest neighbor search, quantile (to name just a few) — with attractive performance guarantees. The guarantees are sensitive to the set collection'spseudoarboricity, a new notion for quantifying the density of$\lbrace S_{1}, S_{2},{\ldots }, S_{n}\rbrace$. Our index structures are simple to understand and implement.