Browse Prior Art Database

Set Equality Testing Technique

IP.com Disclosure Number: IPCOM000070282D
Original Publication Date: 1978-Aug-01
Included in the Prior Art Database: 2005-Feb-21

Publishing Venue

IBM

Related People

Authors:
Wegman, M [+details]

Abstract

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.