Set Equality Testing Technique
Original Publication Date: 1978-Aug-01
Included in the Prior Art Database: 2005-Feb-21
Carter and Wegman  show that certain classes of functions can be used to implement an associative memory in expected linear time, no matter what the inputs are. It is shown herein that those same functions can be used to test equality of sets, with a small probability of error. In this case the result is input (i.e., set) independent.