National Engineering Laboratory for Information Security Technologies, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100091, China.

---

Abstract—This paper proposes a simple intersection algorithm for two sorted integer sequences. Our algorithm is designed based on x-fast trie since it provides efficient find and successor operators. We present that our algorithm outperforms skip list based algorithm when one of the sets to be intersected is relatively ‘dense’ while the other one is (relatively) ‘sparse’. Finally, we propose some possible approaches which may optimize our algorithm further.

Index Terms—Set intersection, algorithm, x-fast trie.

[PDF]

Cite: Bangyu Ye, "A Set Intersection Algorithm Via x-Fast Trie," Journal of Computers vol. 11, no. 2, pp. 91-98, 2016.