DATA STRUCTURE, INDEX CREATION DEVICE, DATA SEARCH DEVICE, INDEX CREATION METHOD, DATA SEARCH METHOD, AND COMPUTER-READABLE RECORDING MEDIUM
1 Assignment
0 Petitions
Accused Products
Abstract
In an inverted list of each node in a taxonomy, among each node, an inverted list of the highest node is a list of integer values indicating an identifier of search subject data, and an inverted list of a node other than the highest node, in place of the identifier, is a list of integer values indicating a position in an inverted list corresponding to a node that is higher by one than the node. Furthermore, a list of integer values in an inverted list of each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before the integer value in the block is converted into a bit string of a variable length integer code.
16 Citations
29 Claims
-
1-10. -10. (canceled)
-
11. In a taxonomy having a tag with respect to search subject data, a data structure configured to take out a set of search subject data which can be reached from each node in said taxonomy comprising:
-
data for ancestor reference indicating an ancestor node that is a higher node of said each node in said taxonomy; and data for an inverted list where an inverted list of said each node is included, and among said each node, an inverted list of a node where said ancestor node is registered in said data for ancestor reference is a list of integer values indicating a position within an inverted list corresponding to registered said ancestor node, and furthermore, a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code.
-
-
12. In a taxonomy having a tag with respect to search subject data, an index creation device configured to create an inverted list used for taking out a set of search subject data which can be reached from each node in said taxonomy, wherein
a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code, and said index creation device comprises: -
an ancestor node determination part configured to select one ancestor node that is a higher node of said node for every node in said taxonomy, and generate data for ancestor reference indicating selected said ancestor node; an ancestor node search part configured to generate an ancestor node list indicating one or more ancestor nodes of a tag in said taxonomy based on said data for ancestor reference; and an ancestor number converting part configured to, upon receiving an identifier of search subject data, with respect to the highest node among each said node in said ancestor node list, adds said identifier as a element of a corresponding inverted list, and with respect to a node other than said highest node, as a element of a corresponding inverted list, in place of said identifier, adds an integer value indicating a position in an inverted list corresponding to a node that is higher by one than said node. - View Dependent Claims (13)
-
-
14. In a taxonomy having a tag with respect to search subject data, a data search device configured to take out a set of search subject data which can be reached from a specified node specified in said taxonomy comprising:
-
an ancestor number inverted list storage part configured to store data for an inverted list where an inverted list of each node in said taxonomy is included, and among said each node, an inverted list of the highest node is a list of integer values indicating an identifier of said search subject data, and an inverted list of a node other than said highest node, in place of said identifier, is a list of integer values indicating a position in an inverted list corresponding to a node that is higher by one than said node, and furthermore, a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code; and an identifier converting part configured to, upon receiving information indicating said specified node, based on said data for an inverted list, create a list of identifiers of said search subject data corresponding to said specified node by repeating processing to take out an integer value of said inverted list corresponding to a higher node of said specified node, which corresponds to said position indicated by an integer value of said inverted list corresponding to said specified node until taking out said identifier of said inverted list corresponding to said highest node. - View Dependent Claims (15, 16, 17, 27)
-
-
18. In a taxonomy having a tag with respect to search subject data, an index creation method configured to create an inverted list used for taking out a set of search subject data which can be reached from each node in said taxonomy, wherein
a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code, and said index creation method comprises: -
a step to, for every node in said taxonomy, select one ancestor node that is a higher node of said node, and generate data for ancestor reference indicating selected said ancestor node; a step to generate an ancestor node list indicating one or more ancestor nodes of a tag in said taxonomy based on said data for ancestor reference; and a step to, upon receiving an identifier of search subject data, with respect to the highest node among each node in said ancestor node list, add said identifier as a element of a corresponding inverted list, and with respect to a node other than the highest node, as a element of a corresponding inverted list, in place of said identifier, add an integer value indicating a position in an inverted list corresponding to a node that is higher by one than said node. - View Dependent Claims (19)
-
-
20. In a taxonomy having a tag with respect to search subject data, a data search method configured to take out a set of search subject data which can be reached from a specified node specified in said taxonomy, comprising:
-
a step to acquire data for an inverted list where an inverted list of each node in said taxonomy is included, and an inverted list of the highest node among said each node is a list of integer values indicating an identifier of said search subject data, and an inverted list of a node other than said highest node, in place of said identifier, is a list of integer values indicating a position in an inverted list corresponding to a node that is higher by one than said node, and furthermore, a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code; and a step to, upon receiving information indicating said specified node, based on said data for an inverted list, create a list of identifiers of said search subject data corresponding to said specified node by repeating processing to take out an integer value of said inverted list corresponding to a higher node of said specified node, which corresponds to said position indicated by an integer value of said inverted list corresponding to said specified node until taking out said identifier of said inverted list corresponding to said highest node. - View Dependent Claims (21, 22, 23)
wherein in a step to take out said node, positions of said identifier in said inverted list corresponding to said highest node are made to be detected, and based on said child node information, detected said positions are made to be compared with integer values in said inverted list corresponding to a node that is lower by one than said highest node, and processing to calculate a frequency of said node based on accordant integer values is made to be at least performed, and furthermore, with respect to a lower node of said node, integer values corresponding to positions of said identifiers in said inverted list corresponding to a higher node is made to be compared with integer values in said inverted list corresponding to a node that is lower by one than said higher node, and based on accordant integer values, processing to calculate a frequency of said node that is lower by one is made to be performed by 0 times or more, and thereby, a frequency of said each node in said search subject data is made to be calculated.
-
-
24. In a taxonomy having a tag with respect to search subject data, a computer-readable recording medium in which recorded is an index creation program to create an inverted list used for taking out a set of search subject data which can be reached from each node in said taxonomy,
wherein a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code, and said index creation program is a program configured to make a computer execute the steps of: -
selecting, for every node in said taxonomy, one ancestor node that is a higher node of said node, and generating data for ancestor reference indicating selected said ancestor node; generating an ancestor node list indicating one or more ancestor nodes of a tag in said taxonomy based on said data for ancestor reference; and upon receiving an identifier of said search subject data, with respect to the highest node among each said node in said ancestor node list, adding said identifier as a element of a corresponding inverted list, and with respect to a node other than said highest node, as a element of a corresponding inverted list, in place of said identifier, adding an integer value indicating a position in an inverted list corresponding to a node that is higher by one than said node. - View Dependent Claims (25)
-
-
26. In a taxonomy having a tag with respect to search subject data, a computer-readable recording medium in which recorded is data search program to take out a set of search subject data which can be reached from a specified node specified in said taxonomy, said data search program being a program configured to make a computer execute the steps of:
-
acquiring data for an inverted list where an inverted list of each node in said taxonomy is included, and an inverted list of the highest node among said each node is a list of integer values indicating an identifier of said search subject data, and an inverted list of a node other than said highest node, in place of said identifier, is a list of integer values indicating a position in an inverted list corresponding to a node that is higher by one than said node, and furthermore, a list of integer values in an inverted list of said each node is divided into two or more blocks, and a differential value between an integer value and an integer value directly before said integer value in said block is converted into a bit string of a variable length integer code; and upon receiving information indicating said specified node, based on said data for an inverted list, creating a list of identifiers of said search subject data corresponding to said specified node by repeating processing to take out an integer value of said inverted list corresponding to a higher node of said specified node, which corresponds to said position indicated by an integer value of said inverted list corresponding to said specified node until taking out said identifier of said inverted list corresponding to said highest node. - View Dependent Claims (28, 29)
-
Specification