Patent ID: 7937399
Filing Date: 2011-05-03
Classification: G06F

Abstract:
1. A method for searching a partial tree in a computer: wherein the computer includes data having a tree data structure in which: unique sequential integers are assigned to nodes including a root node as node identifiers in such a manner that child nodes of a certain node are assigned identifiers earlier than nodes in the same generation as the certain node; wherein a parent-child relationship between nodes is represented by an aggregation array wherein pairs are arranged in order of node identifiers assigned to nodes having one or more child nodes, each pair consisting of the node identifier assigned to a node having one or more child nodes and an occurrence count of the one or more child nodes in which a parent node is a node having the one or more child nodes; wherein the partial tree is a tree having the same topology as a tree serving as a search key in trees identified by a first aggregation array to be searched; and wherein the method comprises the steps of: (a) generating a second aggregation array as a search key array representing the tree serving as the search key in a storage device; (b) adding an offset to node identifiers in the search key array and comparing node identifiers, to which the offset is added, with node identifiers contained in a portion in the first aggregation array, the portion being located at a region which has been shifted according to the offset; and (c) generating a search result in the storage device, wherein the search result represents node identifiers included in the portion wherein all node identifiers matched in comparison, the portion being contained in the first aggregation array.