Could something be done with bloom filters? The downside of a false positive is just querying for records where none would be found.