Browse Prior Art Database

Set Equality Testing Technique Disclosure Number: IPCOM000070282D
Original Publication Date: 1978-Aug-01
Included in the Prior Art Database: 2005-Feb-21

Publishing Venue


Related People

Wegman, M [+details]


Carter and Wegman [1] 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.