System and method for indexing high-dimensional data in cluster system
AssigneeElectronic and Telecommunications Research Institute
InventorsKyu-Woong LEE, Mi-Young Lee, Hun-Soon Lee, Myung-Joon Kim
Life of this patent
Estimating the term…
Abstract
Provided are a system and a method for indexing high-dimensional data in parallel in a cluster environment. The system for indexing high-dimensional data in parallel in a cluster environment includes a Spill-tree creation means for creating a Spill-tree using an sampled N-dimensional feature vector, a feature vector division storage means for distributedly storing the N-dimensional feature vector in a terminal node of the Spill-tree, and a local signature creation means for creating and managing a local signature for the N-dimensional feature vector dispersed into each node of the Spill-tree.
Claims11
A system for indexing high-dimensional data in parallel in a cluster environment, the system comprising:
- a Spill-tree creator for creating a Spill-tree using a sampled N-dimensional feature vector;
- a feature vector division storage for distributedly storing the N-dimensional feature vector in a terminal node of the Spill-tree;
- and
- a local signature creator for creating and managing a local signature for the N-dimensional feature vector dispersed into each node of the Spill-tree.
A method for indexing high-dimensional data in parallel in a cluster environment, the method comprising:
- creating a Spill-tree by extracting random samples from a group of N-dimensional feature vectors;
- determining one or more computing nodes in which the N-dimensional feature vectors are distributedly stored in accordance with a configuration of the Spill-tree and storing the N-dimensional feature vectors at the each computing node;
- creating and storing a local signature with respect to the N-dimensional feature vectors distributedly stored at the each computing node.
A method for searching high-dimensional data in parallel in a cluster environment, the method comprising:
- executing a Spill-tree search on the basis of a value of a query feature vector;
- determining a candidate node from one or more terminal nodes having a similar value to the value of the query feature vector in the Spill-tree as the result of the above search;
- generating a signature of query feature vector at the candidate node;
- and
- searching a local signature file on the basis of the generated signature of the query feature vector.
Dependencies are inferred from the claim text.