Random draw forest index structure for searching large scale unstructured data

A system for generating searchable index structure that indexes a plurality of data objects, comprising:

• one or more processing units;
• a system storage device coupled to each of the one or more processing units, the system storage device tangibly storing thereon executable instructions that, when executed by the one or more processing units, cause the one or more processing units to:
• generate a plurality of shuffling permutations that are each associated with a respective index table;
• for each data object in the plurality of data objects:
• generate a compact feature vector for the data object, the compact feature vector including a sequence of hash values that represent the data object,
• shuffle the sequence of hash values included in the compact feature vector using a plurality of shuffling permutations to generate a plurality of shuffled sequences for the data object, each shuffled sequence for the data object including the hash values of the compact feature vector shuffled according to a respective one of the shuffling permutations, and
• index, based on the shuffled sequences, the data object in a plurality of index tables that each correspond to a respective one of the shuffling permutations;
• and
• store, in the system storage device, the plurality of index tables as the searchable index structure which is searchable for candidate data objects that are similar to a query object using a shuffled query sequence of the query object generated using the shuffling permutations.

A computer program product comprising a medium tangibly storing thereon executable instructions that, when executed by a digital processing system, cause the digital processing system to:

• generate a plurality of shuffling permutations that are each associated with a respective index table;
• for each data object in a plurality of data objects:
• generate a compact feature vector for the data object, the compact feature vector including a sequence of hash values that represent the data object,
• generate a plurality of shuffled sequences for the data object, each shuffled sequence for the data object being generated by applying a respective one of the shuffling permutations to the sequence of hash values of the compact feature vector for the data object, and
• index, based on the shuffled sequences, the data object in a plurality of index tables that each correspond to a respective one of the shuffling permutations;
• and
• store the plurality of index tables as a searchable index structure which is searchable for candidate data objects that are similar to a query object using a shuffled query sequence of the query object generated using the shuffling permutations.

A method of searching for data objects that are similar to a query object, the data objects each being indexed in a plurality of index tables that are each associated with a respective random shuffling permutation, the method comprising:

• generating a compact query feature vector for a query object, the compact query feature vector including a sequence of hash values that represent the query object;
• generating a shuffled query sequence for each index table by applying the random shuffling permutation associated with the index table to the sequence of hash values included in the compact query feature vector, the random shuffling permutation specifying a random order for the sequence of hash values included in the compact query feature vector;
• and
• searching each index table using the shuffled query sequence generated for the index table to identify candidate data objects that are similar to the query object.

A system enabling searching for data objects that are similar to a query object, the data objects each being indexed in a plurality of index tables that are each associated with a respective random shuffling permutation, the system comprising:

• one or more processing units;
• a system storage device coupled to each of the one or more processing units, the system storage device tangibly storing thereon executable instructions that, when executed by the one or more processing units, cause the system to:
• generate a compact query feature vector for a query object, the compact query feature vector including a sequence of hash values that represent the query object;
• generate a shuffled query sequence for each index table by applying the random shuffling permutation associated with the index table to the sequence of hash values included in the compact query feature vector, the random shuffling permutation specifying a random order for the sequence of hash values included in the compact query feature vector;
• and
• search each index table using the shuffled query sequence generated for the index table to identify candidate data objects that are similar to the query object.

A computer program product comprising a medium tangibly storing thereon executable instructions that, when executed by a digital processing system, cause the digital processing system to search for data objects that are similar to a query object, the data objects each being indexed in a plurality of index tables that are each associated with a respective random shuffling permutation, by causing the digital processing system to:

• generate a compact query feature vector for a query object, the compact query feature vector including a sequence of hash values that represent the query object;
• generate a shuffled query sequence for each index table by applying the random shuffling permutation associated with the index table to the sequence of hash values included in the compact query feature vector, the random shuffling permutation specifying a random order for the sequence of hash values included in the compact query feature vector;
• and
• search each index table using the shuffled query sequence generated for the index table to identify candidate data objects that are similar to the query object.