Browse Prior Art Database

Privacy Preserving Expertise Locator Using a modification of traditional Bloom Filters

IP.com Disclosure Number: IPCOM000175965D
Original Publication Date: 2008-Oct-29
Included in the Prior Art Database: 2008-Oct-29
Document File: 2 page(s) / 32K

Publishing Venue

IBM

Abstract

We propose that instead of directly sharing the mined information of expertise subjects, a bloom filter representing the same data can be shared. Bloom filters are devices traditionally used to decide probable membership in sets. Thus, it efficiently answers the question "Is element E a member of the set S represented by this bloom filter?".

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 44% of the total text.

Page 1 of 2

Privacy Preserving Expertise Locator Using a modification of traditional Bloom Filters

Privacy Preserving Expertise Locator Using a modification of traditional Bloom FiltersPrivacy Preserving Expertise Locator Using a modification of traditional Bloom Filters

We propose that instead of directly sharing the mined information of expertise subjects , a bloom filter representing the same data can be shared. Bloom filters are devices traditionally used to decide probable membership in sets. Thus, it efficiently answers the question "Is element E a member of the set S represented by this bloom filter?". In our case, the set S is the set of subjects that has been determined as the area of expertise of a given person P. The question being asked (by a different person) is whether a subject E is in this set S. If it is, the other person can approach P and ask her for more details.

Traditionally, Bloom filters store 0s and 1s in a vector to answer this question (if the element E, when looked up in the filter, yields a 0, then E is not a member of the set S. if it yields a 1, then there is some probability that E is a member of S). We modify this data structure to instead store the name of the person P instead of a 1. We also describe an algorithm to merge bloom filters obtained from many different persons. Using this modification, a person can look up any subject in her merged bloom filter and obtain as an answer the name of a contact who might be an expert on the subject.

The key to preservation of privacy is this: The bloom filter construction itself gives a positive answer only with some uncertainty. Furthermore, the disclosed algorithm for merging bloom filters introduces additional uncertainty. Thus, if people are confronted about their knowledge on a sensitive subject (e.g. do you know anything about the subject "expected job cuts") they can deny any knowledge of it because of the uncertainty involved. No matter how many times our data structure successfully finds the subject experts, it is guaranteed to turn up with the wrong answer at some point, for some subject values.

Optionally, we also allow people distributing their bloom filters to add "salt" by storing a 1 in a random set of places in the vector. Essentially, this claims the knowledge of some (unknown & indeterminate) set of subjects, which when looked up in the bloom filter would yield a 1 in the places where the salt is stored. While this further decreases the accuracy of lookup, this also allows the authors of the bloom filters to more easily deny knowledge.

3

333.... DescriptionDescriptionDescription

Description :

diagrams and flow charts as appropriate

diagrams and flow charts as appropriatediagrams and flow charts as appropriate .

..

In this disclosure we assume that a data mining algorithm has been used to go through the emails a person has sent and...