Multi-user probabalistic array

Patent metadata

Field	Value
Publication number	US-10558634-B2
Application number	US-201615257216-A
Country	US
Kind code	B2
Filing date	Sep 6, 2016
Priority date	Sep 6, 2016
Publication date	Feb 11, 2020
Grant date	Feb 11, 2020

Abstract

A system receives an association of first item with first system user, generates first hash value by applying first hash function associated with first system user to first item identifier associated with first item, and sets a bit corresponding to first hash value in array. The system receives an association of second item with second system user, generates second hash value by applying second hash function associated with second user to second item identifier associated with second item, and sets a bit corresponding to second hash value in array. The system receives a request to determine whether third item is associated with first system user, generates third hash value by applying first hash function to third item identifier associated with third item, and outputs message that third item is not associated with first user if a bit corresponding to third hash value is not set in array.

First claim

The invention claimed is:

1. A system for a multi-user probabilistic array, the system comprising:
one or more processors; and
a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to:
generate a first hash value by applying a first hash function, that is received from and uniquely associated with a first system user, to an identifier of a first item, the first item being associated with the first system user;
set a bit corresponding to the first hash value in an array;
generate a second hash value by applying a second hash function, that is received from and uniquely associated with a second system user, to an identifier of a second item, the second item being associated with the second system user;
set a bit corresponding to the second hash value in the array;
generate a third hash value by applying the first hash function to an identifier of a third item, the third hash value being generated in response to receiving a request to determine whether the third item is associated with the first system user;
determine whether a bit corresponding to the third hash value is set in the array; and
cause a message to be outputted, in response to a determination that the bit corresponding to the third hash value is not set in the array, the message specifying that the third item is not associated with the first user.

2. The system of claim 1 , wherein applying the first hash function to the first item identifier comprises creating a product by multiplying the first item identifier by a prime number, and creating both a quotient and a remainder by dividing the product by a number associated with a size of the array, the first hash value comprising the remainder.

3. The system of claim 1 , wherein the array is stored in a computer memory and the first hash function is received from outside the computer memory.

4. The system of claim 1 , comprising further instructions, which when executed, cause the one or more processors to:
generate an additional hash value by applying an additional hash function, that is received from and uniquely associated with the first system user to the first item identifier; and
set a bit corresponding to the additional hash value in the array.

5. The system of claim 1 , wherein the first system user is a first tenant in a multi-tenant database system and the second system user is a second tenant in the multi-tenant database system.

6. The system of claim 1 , comprising further instructions, which when executed, cause the one or more processors to output a message, in response to a determination that the bit corresponding to the third hash value is set in the array, the message specifying that the third item is associated with the first user.

7. A computer program product comprising computer-readable program code to be executed by one or more processors when retrieved from a non-transitory computer-readable medium, the program code including instructions to:
generate a first hash value by applying a first hash function, that is received from and uniquely associated with a first system user to an identifier of a first item, the first item being associated with the first system user;
set a bit corresponding to the first hash value in an array;
generate a second hash value by applying a second hash function, that is received from and uniquely associated with a second system user to an identifier of a second item, the second item being associated with the second system user;
set a bit corresponding to the second hash value in the array;
generate a third hash value by applying the first hash function to an identifier of a third item, the third hash value being generated in response to receiving a request to determine whether the third item is associated with the first system user;
determine whether a bit corresponding to the third hash value is set in the array; and
cause a message to be outputted, in response to a determination that the bit corresponding to the third hash value is not set in the array, the message specifying that the third item is not associated with the first user.

8. The computer program product of claim 7 , wherein applying the first hash function to the first item identifier comprises creating a product by multiplying the first item identifier by a prime number, and creating both a quotient and a remainder by dividing the product by a number associated with a size of the array, the first hash value comprising the remainder.

9. The computer program product of claim 7 , wherein the array is stored in a computer memory and the first hash function is received from outside the computer memory.

10. The computer program product of claim 7 , wherein the program code comprises further instructions to:
generate an additional hash value by applying an additional hash function, that is received from and uniquely associated with the first system user to the first item identifier; and
set a bit corresponding to the additional hash value in the array.

11. The computer program product of claim 7 , wherein the first system user is a first tenant in a multi-tenant database system and the second system user is a second tenant in the multi-tenant database system.

12. The computer program product of claim 7 , wherein the program code comprises further instructions to cause a message to be outputted, in response to a determination that the bit corresponding to the third hash value is set in the array, the message specifying that the third item is associated with the first user.

13. A method comprising:
generating, by a database system, a first hash value by applying a first hash function, that is received from and uniquely associated with a first system user to an identifier of a first item, the first item being associated with the first system user;
setting, by the database system, a bit corresponding to the first hash value in an array;
generating, by the database system, a second hash value by applying a second hash function, that is received from and uniquely associated with a second system user to an identifier of a second item, the second item being associated with the second system user;
setting, by the database system, a bit corresponding to the second hash value in the array;
generating, by the database system, a third hash value by applying the first hash function to an identifier of a third item, the third hash value being generated in response to receiving a request to determine whether the third item is associated with the first system user;
determining, by the database system, whether a bit corresponding to the third hash value is set in the array; and
causing, by the database system, a message to be outputted in response to a determination that the bit corresponding to the third hash value is not set in the array, the message specifying that the third item is not associated with the first user.

14. The method of claim 13 , wherein applying the first hash function to the first item identifier comprises creating a product by multiplying the first item identifier by a prime number, and creating both a quotient and a remainder by dividing the product by a number associated with a size of the array, the first hash value comprising the remainder.

15. The method of claim 13 , wherein the array is stored in a computer memory, and the first hash function is received from outside the computer memory.

16. The method of claim 13 , wherein the method further comprises:
generating, by the database system, an additional hash value by applying an additional hash function, that is

Assignees

• Salesforce Com Inc

Inventors

• Fuchs Matthew

Classifications

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F7/20

  Comparing separate sets of record carriers arranged in the same sequence to determine whether at least some of the data in one set is identical with that in the other set or sets · CPC title

• H04L67/22

  Electricity · mapped topic

• H04L67/535

  Tracking the activity of the user (network monitoring arrangements H04L43/00; recording of computer activity G06F11/34) · CPC title