K-ary search tree revisited: improving construction and intersection efficiency

Graphical abstract

References

[1] Schlegel B, Gemulla R, Lehner W. K-ary search on modern processors. In: Proceedings of the 5th International Workshop on Data Management on New Hardware. 2009, 52– 60

[2] Kim C, Chhugani J, Satish N, Sedlar E, Nguyen A D, Kaldewey T, Lee V W, Brandt S A, Dubey P. FAST: fast architecture sensitive tree search on modern CPUs and GPUs. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010, 339–350

[3] Wang J , Lin C , He R , Chae M , Papakonstantinou Y , Swanson S . MILC: inverted list compression in memory. Proceedings of the VLDB Endowment, 2017, 10( 8): 853– 864

[4] Zhang J, Lu Y, Spampinato D G, Franchetti F. FESIA: A fast and SIMD-efficient set intersection approach on modern CPUs. In: Proceedings of the 36th IEEE International Conference on Data Engineering. 2020, 1465−1476

[5] Song X, Yang Y, Li X. SIMD-based multiple sets intersection with dual-scale search algorithm. In: Proceedings of the 2017 ACM Conference on Information and Knowledge Management. 2017, 2311−2314

Supporting Information

The supporting information is available online at joumal. hep. com. cn and link. springer. com.

RIGHTS & PERMISSIONS

2021 Higher Education Press 2021