Pigeonring: A Principle for Faster Thresholded Similarity Search

Jianbin Qin, Chuan Xiao

The pigeonhole principle states that if $n$ items are contained in $m$ boxes, then at least one box has no more than $n/m$ items. It is utilized to solve many data management pro…