Back to results
US 11,106,708 B2Granted
Layered locality sensitive hashing (LSH) partition indexing for big data applications
AssigneeHuawei Technologies Canada Co., Ltd.
InventorsYangdi Lu, Wenbo He, Amirhosein Nabatchian
Life of this patent
Estimating the term…
Abstract
System and method of partitioning a plurality of data objects that are each represented by a respective high dimensional feature vector is described, including performing a hashing function on each high dimensional feature vector to generate a respective lower dimensional binary compact feature vector for the data object that is represented by the high dimensional feature vector; performing a further hashing function on each compact feature vector to assign a sub-index ID to the compact feature vector; and partitioning the compact feature vectors into respective partition groups that correspond to the sub-index IDs assigned to the compact feature vectors.
Claims14
A method of partitioning a plurality of data objects that are each represented by a respective high dimensional feature vector, comprising:
- performing a locality sensitive hashing function on each high dimensional feature vector to generate a respective lower dimensional binary compact feature vector for the data object that is represented by the high dimensional feature vector;
- performing on each respective lower dimensional binary compact feature vector a further locality sensitive hashing function to generate a sub-index ID for the respective lower dimensional binary compact feature vector and assigning the sub-index ID to the respective lower dimensional binary compact feature vector;
- partitioning the lower dimensional binary compact feature vectors that are assigned identical sub-index IDs into respective partition groups;
- generating a searchable sub-index structure for each respective partition group by:
- generating a plurality of twisted compact feature vector sets for the partition group, each twisted compact feature vector set being generated by applying a respective bit order shuffling permutation to all of the lower dimensional binary compact feature vectors included in the partition group;
- generating a respective index table for each twisted compact feature vector set of the partition group by indexing each of the twisted compact feature vectors included compact feature vector set in the index table based on bit order similarities,
- the searchable sub-index structure for the partition group including the index tables for all of the twisted compact feature vector sets of the partition group,
- and
- storing the sub-index structures as independently searchable structures.
6 more elements
A system for partitioning a plurality of data objects that are each represented by a respective high dimensional feature vector, comprising:
- one or more processing units;
- a system storage device coupled to each of the 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:
- perform a locality sensitive hashing function on each high dimensional feature vector to generate a respective lower dimensional binary compact feature vector for the data object that is represented by the high dimensional feature vector;
- perform on each respective lower dimensional binary compact feature vector a further locality sensitive hashing function to generate a sub-index ID or the respective lower dimensional binary compact feature vector and assign the sub-index ID to the respective lower dimensional binary compact feature vector;
- partition the lower dimensional binary compact feature vectors that are assigned identical sub-index IDs into respective partition groups;
- generate a searchable sub-index structure for each of the respective partition group by:
- generating a plurality of twisted compact feature vector sets for the partition group, each twisted compact feature vector set being generated by applying a respective bit order shuffling permutation to all of the lower dimensional binary compact feature vectors included in the partition group;
- generating a respective index table for each twisted compact feature vector set of the partition group by indexing each of the twisted compact feature vectors included compact feature vector set in the index table based on bit order similarities,
- the searchable sub-index structure for the partition group including the index tables for all of the twisted compact feature vector sets of the partition group,
- and
- store the sub-index structures in one or more storages as independently searchable structures.
8 more elements
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:
- perform a locality sensitive hashing function on each of a plurality of high dimensional feature vectors to generate a respective lower dimensional binary compact feature vector, the high dimensional feature vectors each representing a respective data object;
- perform on each respective lower dimensional binary compact feature vector a further locality sensitive hashing function to generate a sub-index ID for the respective lower dimensional binary compact feature vector and assign the sub-index ID to the respective lower dimensional binary compact feature vector;
- and
- partition the lower dimensional binary compact feature vectors that are assigned an identical sub-index ID into a respective partition group;
- partition the lower dimensional binary compact feature vectors that are assigned identical sub-index IDs into respective partition groups;
- generate a searchable sub-index structure for each of the respective partition group by:
- generating a plurality of twisted compact feature vector sets for the partition group, each twisted compact feature vector set being generated by applying a respective bit order shuffling permutation to all of the lower dimensional binary compact feature vectors included in the partition group;
- generating a respective index table for each twisted compact feature vector set of the partition group by indexing each of the twisted compact feature vectors included compact feature vector set in the index table based on bit order similarities,
- the searchable sub-index structure for the partition group including the index tables for all of the twisted compact feature vector sets of the partition group,
- and
- store the sub-index structures in one or more storages as independently searchable structures.
8 more elements
Dependencies are inferred from the claim text.