JP6974666B1 - Search device, search method, and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To search information at high speed for each search condition having variations. A record index storage unit 4113 that stores two or more record indexes corresponding to a combination of different key items, a condition reception unit 121 that accepts a search condition having a key item value, and two or more records. From the index, the record position information paired with the key item value of the search condition is acquired from one record index corresponding to the combination of one or more key items including the key item corresponding to the key item value of the search condition. Then, the search unit 432 that acquires the attribute value in the record corresponding to the position specified by the record position information from the data source, and the result output unit 441 that outputs the search result including the attribute value acquired by the search unit 432. With the search device 4 provided with the above, information retrieval can be performed at high speed for each search condition having variations. [Selection diagram] FIG. 17

Description

The present invention relates to a search device or the like for retrieving information.

Conventionally, there has been a search system for the purpose of realizing a high-speed search using an index (see, for example, Patent Document 1).

Japanese Unexamined Patent Publication No. 2006-9427

However, in the prior art, it has been difficult to perform information retrieval at high speed for each search condition having variations.

The search device of the first invention corresponds to a record of a data source including two or more records having a key item value corresponding to two or more key items and an attribute value corresponding to one or more attribute identifiers. An index, two or more record indexes that are a set of record position information that identifies the position of a record that contains one or more key item values and one or more key item values that correspond to a combination of one or more key items. A record index storage unit that stores two or more record indexes corresponding to different combinations of key items, a condition reception unit that accepts search conditions having key item values, and two or more record indexes. Select one record index corresponding to one or more key item combinations including the key item corresponding to the key item value of the search condition, and from the selected record index, the key item value of the search condition and The search unit that acquires the paired record position information and acquires the attribute value in the record corresponding to the position specified by the record position information from the data source, and outputs the search result including the attribute value acquired by the search unit. It is a search device provided with a result output unit.

With such a configuration, information retrieval can be performed at high speed for each search condition having variations.

Further, in the search device of the second invention, an attribute value exists for each one or more records of two or more records and for each one or more attributes of each record with respect to the first invention. Further includes an array index storage unit for storing an array index having attribute position information for specifying a position to be performed, the search condition further has an attribute identifier, and the search unit has an attribute corresponding to the attribute identifier possessed by the search condition. It is a search device that acquires position information from an array index and uses attribute position information to acquire an attribute value corresponding to an attribute identifier of a search condition from a data source.

With such a configuration, information retrieval can be performed at higher speed for each search condition having variations.

Further, in the search device of the third invention, with respect to the first or second invention, in each of two or more record indexes, two or more sets of one or more key item values and record position information are one. The combination of the above key item values is sorted as a key, and the search unit selects the key item at the beginning of the record index from the two or more record indexes as the key item corresponding to the key item value of the search condition. If there is a match, select the record index, obtain the record position information that is paired with the key item value of the search condition from the selected record index, and record the record corresponding to the position specified by the record position information. It is a search device that acquires the attribute value inside from the data source.

With such a configuration, information retrieval can be performed at high speed for each search condition having variations.

Further, in the search device of the fourth invention, with respect to the third invention, the search unit has two or more key items in which the first key item of the record index matches the key item corresponding to the key item value of the search condition. If the record index of is present, the next key item of two or more record indexes is determined to match the key item of the search condition, and the most key items from the beginning of the record index are searched. Select one record index included in the key item of the condition, acquire the record position information that is paired with the key item value of the search condition from the selected record index, and place it at the position specified by the record position information. It is a search device that acquires the attribute value in the corresponding record from the data source.

With such a configuration, information retrieval can be performed at high speed for each search condition having variations.

Further, the search device of the fifth invention refers to the data source for any one of the first to fourth inventions, and the key item value and the record position information of each of two or more records of the data source. A set of two or more record indexes, each of which generates two or more record indexes corresponding to different combinations of one or more key items, and further adds a record index generator to be stored in the record index storage. It is a search device equipped.

With such a configuration, it is possible to generate an index for high-speed information retrieval for each search condition having variations.

Further, in the search device of the sixth invention, for the fifth invention, the record index generation unit determines two or more sets of combinations of one or more key items satisfying the selection condition, and two or more sets. A search device that generates a record index that is a set of key item values and record position information of two or more records corresponding to a combination of one or more key items in each set of, and stores them in the record index storage unit. Is.

With such a configuration, it is possible to generate an appropriate index for high-speed information retrieval for each search condition having variations.

Further, the search device of the seventh invention corresponds to the sixth invention that the selection condition corresponds to the attribute value in which the dispersion of the attribute values contained in each of the two or more records of the data source is equal to or more than the threshold value or larger than the threshold value. One or more keys that are a combination of one or more key items that include the key items to be used, or that include key items that correspond to attribute values that are included at or above the threshold value or at a frequency higher than the threshold value in one or more search conditions in the past. It is a search device that is a combination of items.

With such a configuration, it is possible to generate an appropriate index for high-speed information retrieval for each search condition having variations.

According to the search device according to the present invention, information retrieval can be performed at high speed for each search condition having variations.

Conceptual diagram of the search system A in the first embodiment Block diagram of the search system A Block diagram of the search device 1 constituting the search system A A flowchart illustrating an operation example of the search device 1. A flowchart illustrating an example of the index generation process. Flowchart explaining an example of the source index generation process A flowchart illustrating an example of the same array label index generation process. A flowchart illustrating an example of the same array index generation process. A flowchart illustrating an example of the record index generation process. A flowchart illustrating an example of the secondary index generation process. A flowchart illustrating an example of the search process. Diagram showing an example of the same data source A diagram illustrating an example of index generation processing and an example of search processing. The figure explaining the search processing example Conceptual diagram of the search system B in the second embodiment Block diagram of the search system B Block diagram of the search device 4 A flowchart illustrating an operation example of the search device 4. A flowchart illustrating an example of the index generation process. A flowchart illustrating an example of the record index generation process. Flow chart explaining an example of the same key item set determination process Flowchart explaining an example of the same search condition usage process Flow chart explaining an example of the distributed use processing A flowchart illustrating the first example of the search process. A flowchart illustrating a second example of the search process. A flowchart illustrating an example of the record index determination process. Diagram showing an example of the same data source The figure explaining the search processing example Overview of the computer system in the above embodiment Block diagram of the computer system

Hereinafter, embodiments of the search device and the like will be described with reference to the drawings. In addition, since the components with the same reference numerals perform the same operation in the embodiment, the description may be omitted again.

(Embodiment 1)
In the present embodiment, a search system including a search device for searching information on a data source using one or more types of indexes will be described. The one or more types of indexes are, for example, an array index described later, an array label index described later, a record index described later, a secondary index described later, and a source index described later.

Further, in the present embodiment, a search system including a search device for generating one or more types of indexes corresponding to the data source by using the data source will be described.

Further, in the present embodiment, a search system including a search device for automatically updating the index will be described.

FIG. 1 is a conceptual diagram of the search system A according to the present embodiment. The search system A includes, for example, a search device 1, 1 or 2 or more data source management devices 2, or 1 or 2 or more terminal devices 3.

The search device 1 is a device for searching information from a data source. The data source management device 2 is a device in which one or more data sources are stored. The terminal device 3 is a terminal used by a user who searches for information.

The search device 1 and the data source management device 2 are, for example, so-called servers, for example, a cloud server, an ASP server, and the like. The type of the search device 1 and the data source management device 2 does not matter. Further, the search device 1 may be a stand-alone device. In such a case, the search system A does not have to have the data source management device 2 and the terminal device 3. In such a case, the data source is stored in the search device 1.

FIG. 2 is a block diagram of the search system A according to the present embodiment. FIG. 3 is a block diagram of the search device 1 constituting the search system A.

The search device 1 includes a storage unit 11, a reception unit 12, a processing unit 13, and an output unit 14. The storage unit 11 includes a data source storage unit 111 and an index storage unit 112. The index storage unit 112 includes an array index storage unit 1121, an array label index storage unit 1122, a record index storage unit 1123, a secondary index storage unit 1124, and a source index storage unit 1125. The reception unit 12 includes a condition reception unit 121. The processing unit 13 includes an index generation unit 131, a search unit 132, and an index update unit 133. The index generation unit 131 includes an array index generation unit 1311, an array label index generation unit 1312, a record index generation unit 1313, a secondary index generation unit 1314, and a source index generation unit 1315. The output unit 14 includes a result output unit 141.

The data source management device 2 includes a data source storage unit 111.

The terminal device 3 includes a terminal storage unit 31, a terminal reception unit 32, a terminal processing unit 33, a terminal transmission unit 34, a terminal reception unit 35, and a terminal output unit 36.

Various types of information are stored in the storage unit 11 that constitutes the search device 1. The various types of information are, for example, a data source described later and one or more types of indexes described later.

One or two or more data sources are stored in the data source storage unit 111. The search device 1 does not have to have the data source storage unit 111. In such a case, the data source to be searched is stored in the data source management device 2.

A data source is a set of data to be searched. Data can be called information. The data source is usually a single file. However, the data source may be, for example, one database, one table in the database, or the like. A data source usually has one or more records. A record may be called a line, a tuple, or the like, for example. The delimiter is recognizable, for example, the records are separated by the first delimiter. The first delimiter is, for example, a return code, a TAB code, a space, or the like, but it does not matter. The data source may have data other than the search target. The data other than the search target is, for example, an item label and an attribute identifier. The item label is an item label, but may be an item name. The item has, for example, a key item and a detailed item. The key item is an identifier for the key item value. Further, two or more key items may exist in one record. The item item is an item including a key item. It may be considered that the key item and the detail item are also attribute identifiers. That is, it may be considered that the key item value and the detail item value are also attribute values constituting the record. The attribute identifier is information that identifies the attribute. The attribute identifier is, for example, an attribute name or an attribute ID. Records usually have two or more attribute values. The record may also have key item values and item item values. However, the record may have one attribute value. The delimiters are recognizable, for example, separated by a second delimiter between the attribute values in the record. The second delimiter is, for example, a comma ",", a colon ":", a semicolon ";", a space, a TAB code, or the like, but it does not matter. The data source corresponds to the source identifier. The source identifier is information that identifies a data source, and is, for example, a file name or a file ID. The key item value is, for example, predetermined. It should be noted that what is predetermined means that it is usually determined at the time of index generation according to the user's specification.

Attribute values in data sources are usually variable length rather than fixed length. Also, the records in the data source are usually variable length rather than fixed length. However, the attribute values and records in the data source may have a fixed length.

It is preferable that the data source corresponds to one or more source attribute values. The source attribute value is the attribute value of the data source. The source attribute value is, for example, last update information, updater identifier, size, and type identifier. The information at the time of the last update is information for specifying the time of the last update of the data source, and is, for example, the year, month, day, hour, minute, second, and month, day, hour, and minute. The updater identifier is information that identifies the updater (usually the last updater) of the data source. The size is the data size of the data source, for example, the number of bytes and the number of bits. The type identifier is information that identifies the type of data source, and is, for example, a "file", "RDB", or "table". "File" indicates that the data source is a file. "RDB" indicates that the data source is an RDB (relational database). "Table" indicates that the data source is tabular information.

The index storage unit 112 stores one or two or more types of indexes. An index is information (usually an index) that is referenced to retrieve desired information from a data source. The index is, for example, an array index described later, an array label index described later, a record index described later, a secondary index described later, and a source index described later.

Each index of one or more types is, for example, a file. However, the index may be information in a database such as RDB, and its physical structure does not matter. The information in the database is, for example, a table.

It is preferable that the index is associated with the information at the time of generation. The generation time information is information that specifies the time when the index is generated, and is, for example, the year, month, day, hour, minute, second, and month, day, day, and minute.

The array index is stored in the array index storage unit 1121. The array index storage unit 1121 usually stores an array index for each data source. That is, the array index usually corresponds to a source identifier that identifies the data source. If there is only one data source to be searched, the array index does not need to correspond to the source identifier.

The array index is information for specifying the position of the attribute value in the record. The array index has one or more array index records that are record-by-record information that the data source has. The array index record has attribute position information for each attribute of each record. The attribute position information is information that identifies the position where the attribute value exists. The attribute position information is usually an offset within the record of the attribute value. However, the attribute position information may be an offset or the like in the data source. The attribute position information corresponds to, for example, a record identifier that identifies a record and an attribute identifier.

It is preferable that the array index has the attribute position information of some attribute values corresponding to all the records, but it has the attribute position information of all the attribute values corresponding to all the records of the data source. It may have the attribute position information of all the attribute values corresponding to some records, or may have the attribute position information of some attribute values corresponding to some records.

When the array index has only the attribute position information of some attribute values, the array index has the attribute position information in the order of the list of the attribute values in the record of the data source.

The array label index storage unit 1122 stores the array label index. The array label index storage unit 1122 usually stores an array label index for each data source. That is, the array label index usually corresponds to the source identifier. If there is only one data source to be searched, the array label index does not need to correspond to the source identifier.

The array label index is information for specifying the order of attributes in the records of the data source. The array label index has one or more array label index records that are record-by-record information that the data source has. The array label index record is information indicating the order of attributes in the record. An array label index record is, for example, a set of an attribute identifier and attribute order information. Each of the two or more array label index records may be, for example, an attribute identifier arranged in order in the record. It is preferable that the array label index is information that identifies the order of all attributes in the record. In the array label index, it is preferable that the attribute identifiers are sorted.

The record index is stored in the record index storage unit 1123. The record index storage unit 1123 normally stores a record index for each data source. That is, the record index usually corresponds to the source identifier. If there is only one data source to be searched, the record index does not need to correspond to the source identifier.

A record index is an index that corresponds to a record in the data source. The record index has one or more record index records for locating records in the data source. The record index record has a key item value or a combination of two or more key item values and record position information. The record index record may be a set of a key item value, a record position information, and a record index record position information.
It is also preferable to have a different record index with different key item values within the same record, or a combination of key item values and record position information.

The key item value is an attribute value included in the record and is a key attribute value. The key item value is preferably unique information that can identify the record, but does not have to be unique information.

The record position information is information that identifies the position of the record including the key item value. The record position information is, for example, an offset in the data source that identifies the position of the record. The record position information is, for example, the offset at the beginning of the record. The record position information may be, for example, an offset of the last information of the record.

The record index record position information is information that identifies the position of the record index record in the record index. The record index record position information is, for example, the offset of the record index record in the record index.

It is preferable that the key item values are sorted in the record index.

Further, it is preferable that the record index record and the array index record are associated with each other. The record index record and the array index record are associated with each other by, for example, a key item value.

The secondary index is stored in the secondary index storage unit 1124. The secondary index storage unit 1124 usually stores a secondary index for each data source. That is, the secondary index usually corresponds to the source identifier. When there is only one data source to be searched, the secondary index does not need to correspond to the source identifier.

The secondary index is an index for high-speed access to the record index. The quadratic index is information corresponding to each one or more records that is a part of the two or more records possessed by the data source. The secondary index has a secondary index record for each record. The secondary index record is a set of the key item value and the record index record position information. Record index The record position information is a place in the record index and is information for specifying a place where the record position information exists. The key item value is the key item value that the record has.

It is preferable that the key item values in the secondary index are sorted.

The source index is stored in the source index storage unit 1125. The source index is an index for each data source. A source index is, for example, a collection of source index records for each data source.

A source index record is, for example, a set of a source identifier, a minimum key item value, and a maximum key item value. The minimum key item value is the minimum key item value that the data source identified by the source identifier has. The maximum key item value is the maximum key item value possessed by the data source identified by the source identifier. In such cases, different records are usually stored in each of the two or more data sources.

A source index record is, for example, a set of a source identifier, a minimum attribute identifier, and a maximum attribute identifier. The minimum attribute identifier is the smallest attribute identifier of the data source identified by the source identifier. The maximum attribute identifier is the largest attribute identifier of the data source identified by the source identifier. In such a case, usually, attribute values of different attributes are stored in each of two or more data sources.

A source index record is, for example, a set of a source identifier, a minimum key item value, a maximum key item value, a minimum attribute identifier, and a maximum attribute identifier. In such a case, usually, the attribute values of some attributes of some records are stored in each of two or more data sources.

The reception unit 12 receives various instructions and information. The various instructions and information are, for example, search conditions, data sources, and some information constituting the data source, which will be described later.

Here, the reception is usually reception from the terminal device 3, but reception of information input from an input device such as a keyboard, mouse, or touch panel, and reading from a recording medium such as an optical disk, a magnetic disk, or a semiconductor memory. It may be a concept including acceptance of the provided information.

The condition reception unit 121 accepts search conditions. The search condition includes, for example, one or more attribute identifiers. The search condition includes, for example, one or more key item values. The search condition includes, for example, one or more attribute identifiers and one or more key item values.

The processing unit 13 performs various processes. The various processes are, for example, processes performed by the index generation unit 131, the search unit 132, and the index update unit 133.

When the receiving unit 12 receives the data source, the processing unit 13 stores the data source in the data source storage unit 111. At that time, the processing unit 13 acquires the last update information from a clock (not shown) and associates the last update information with the data source.

When the receiving unit 12 receives a part of the information constituting the data source, the processing unit 13 updates the data source by using the part of the information. At that time, the processing unit 13 acquires the last update information from a clock (not shown) and associates the last update information with the data source.

The index generator 131 generates an index from each of one or more data sources.

The array index generation unit 1311 generates an array index for each one or more data sources and stores it in the array index storage unit 1121.

The array index generation unit 1311 acquires the attribute position information for each record in the data source and for each attribute value of 1 or more.

The array index generation unit 1311 acquires an array index record having attribute position information of a part of each attribute value for each record in the data source, and constitutes an array index having one or more array index records. , It is preferable to store in the array index storage unit 1121. However, the array index generation unit 1311 acquires an array index record having attribute position information of all each attribute value for each record in the data source, and obtains an array index having one or more array index records. It may be configured and stored in the array index storage unit 1121.

It is preferable that the array index record is information having only the attribute position information of some of the attribute values among all the attribute values in the record. It does not matter how to select some of these attribute values. It is preferable that some attribute values are selected for each predetermined value (for example, every four such as the first, fifth, ninth, etc.), but even if a predetermined number are randomly selected. good.

The array index generation unit 1311 acquires the attribute position information for each one or more records of the two or more records in the data source and for each attribute value of one or more. Then, the array index generation unit 1311 generates an array index having attribute position information for each record and each attribute value, and stores the array index in the array index storage unit 1121.

The array index generation unit 1311 stores, for example, the acquired attribute position information in the array index storage unit 1121 so as to correspond to the record identifier or the key item value and the attribute value identifier.

The array index generation unit 1311 usually scans the data source, recognizes a record for each first delimiter, scans the record, recognizes an attribute value for each second delimiter, and for example, from the beginning of the record. The next position of each second delimiter is acquired as the attribute position information of each attribute value.

The array label index generation unit 1312 generates an array label index for each one or more data sources and stores it in the array label index storage unit 1122.

The array label index generation unit 1312 acquires, for example, an attribute value identifier and attribute order information for each of two or more attributes from a data source, and the array label is a set of the attribute value identifier and the attribute order information. -Acquires an index record, constitutes an array label index having two or more array label index records, and stores the array label index in the array label index storage unit 1122.

It is preferable that the array label index generation unit 1312 sorts the array label index records as the attribute value identifier key to form the array label index.

Also, if the array index record has attribute position information for all attribute values, then the array label index is not needed.

The record index generation unit 1313 refers to the data source and acquires a record index record having a key item value and record position information of each of two or more records of the data source for each record. Then, the record index generation unit 1313 generates a record index having a set of record index records for each record, and stores the record index in the record index storage unit 1123.

The record index generation unit 1313 acquires the record index record position information that specifies the position of the record index record in the record index for each one or more record index records, and obtains the record index record position information. It is preferable to construct a record index record having a record.

It is preferable that the record index generation unit 1313 sorts the record index records using the key item value as a key to form a record index.

The secondary index generation unit 1314 determines the record index record position information and the key item value of the record for each one or more records that are a part of the two or more records possessed by the data source for each data source. A set of secondary index records is acquired, a secondary index having one or more secondary index records is configured, and the secondary index records are stored in the secondary index storage unit 1124.

Further, when the attribute value position information of the array index is the information for specifying the position in the data source, the record index may be omitted.

The secondary index generation unit 1314 refers to, for example, the record index corresponding to the data source for each data source, is a part of the records possessed by the record index, and is a record index possessed by each of two or more records. A secondary index record, which is a set of record position information and a key item value, is acquired, a secondary index having two or more secondary index records is generated, and the secondary index is stored in the secondary index storage unit 1124.

The secondary index record corresponds to a part of the record index record, but the method of selecting the part of the record index record does not matter. It is preferable that some record index records are selected for each predetermined value (for example, every four such as the first, fifth, ninth, etc.), but a predetermined number are randomly selected. May be.

The secondary index speeds up the search for records, but it is not necessary.

The source index generation unit 1315 acquires a source index record for each of two or more data sources, generates a source index having two or more source index records, and stores the source index in the source index storage unit 1125. .. The source index record is, for example, a set of a source identifier, a minimum key item value, and a maximum key item value. A source index record is, for example, a set of a source identifier, a minimum attribute identifier, and a maximum attribute identifier. A source index record is, for example, a set of a source identifier, a minimum key item value, a maximum key item value, a minimum attribute identifier, and a maximum attribute identifier.

If there is only one data source, the source index generation unit 1315 is unnecessary.

The search unit 132 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index, and uses the attribute position information to set the attribute value corresponding to the attribute identifier of the search condition as the key item value. Obtained from a data source containing one or more records with two or more attribute values.

The search unit 132 has, for example, the first attribute position information corresponding to the attribute identifier that identifies the attribute value arranged before the attribute value identified by the attribute identifier of the search condition received by the condition reception unit 121. , The second attribute position information corresponding to the attribute identifier that identifies the attribute value arranged after the attribute value identified by the attribute identifier of the search condition is acquired from the array index. Next, the search unit 132 is an attribute value existing between the position specified by the first attribute position information and the position specified by the second attribute position information, and corresponds to the attribute identifier of the search condition. Get the attribute value to be used from the data source.

The search unit 132 acquires, for example, the attribute order information corresponding to the attribute identifier of the search condition received by the condition reception unit 121 from the array label index. Next, the search unit 132 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index by using the attribute order information. Next, the search unit 132 acquires the attribute value corresponding to the attribute identifier of the search condition from the data source by using the attribute position information.

The search unit 132 acquires, for example, the attribute order information corresponding to the attribute identifier of the search condition received by the condition reception unit 121 from the array label index. The search unit 132 is arranged after the first attribute position information corresponding to the attribute identifier that identifies the attribute value arranged before the order indicated by the attribute order information and the order indicated by the attribute order information. The second attribute position information corresponding to the attribute identifier that identifies the attribute value is acquired from the array index. Next, the search unit 132 is an attribute value existing between the position specified by the first attribute position information and the position specified by the second attribute position information, and corresponds to the attribute identifier of the search condition. Get the attribute value to be used from the data source.

The search unit 132 acquires, for example, the record position information paired with the key item value of the search condition from the record index. Next, the search unit 132 determines the record corresponding to the position specified by the record position information, and obtains the attribute value in the record and the attribute value corresponding to the attribute identifier of the search condition from the data source. get. If the attribute identifier is not shown in the search condition, it may be considered that the attribute identifier possessed by the search condition is all the attribute identifiers.

The search unit 132 acquires, for example, two key item values sandwiching the key item value of the search condition from the secondary index. Next, the search unit 132 acquires the first record index record position information and the second record index record position information paired with the acquired two key item values from the secondary index. Next, the search unit 132 searches for a record index record between the first record index record position information and the second record index record position information, and includes the key item value of the search condition. The record index record is determined, and the record position information in the record index record is acquired. Next, the search unit 132 acquires the attribute value corresponding to the attribute identifier of the search condition, which is the attribute value in the record corresponding to the position specified by the record position information, from the data source. The search unit 132 acquires the attribute position information of the attribute value corresponding to the attribute identifier of the search condition by using the array index, and acquires the attribute value of the position specified by the attribute position information from the data source. Is suitable.

Further, when the key item values are sorted in the record index, it is preferable that the search unit 132 determines the record index record including the key item value of the search condition by binary search, but sequentially. You can also search.

The search unit 132 acquires, for example, a source identifier that matches the key item value of the search condition or is paired with the minimum key item value and the maximum key item value with the key item value sandwiched between them from the source index. Next, the search unit 132 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index from the data source identified by the source identifier. Next, the search unit 132 acquires the attribute value corresponding to the attribute identifier of the search condition, which is the attribute value in the record, by using the attribute position information.

The search unit 132 acquires, for example, a source identifier that matches the attribute identifier of the search condition or that is paired with the minimum attribute identifier and the maximum attribute identifier with the attribute identifier sandwiched between them from the source index. The search unit 132 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index corresponding to the data source identified by the source identifier. The search unit 132 uses the attribute position information to acquire the attribute value in the record in the data source identified by the source identifier and the attribute value corresponding to the attribute identifier of the search condition.

The search unit 132 acquires, for example, a source identifier corresponding to the key item value of the search condition and the attribute identifier of the search condition from the source index. The search unit 132 acquires two key item values sandwiching the key item value of the search condition from the secondary index corresponding to the data source identified by the source identifier. Next, the search unit 132 acquires the first record index record position information and the second record index record position information paired with the acquired two key item values from the secondary index. Next, the search unit 132 searches for a record index record between the first record index record position information and the second record index record position information, and includes the key item value of the search condition. The record index record is determined, and the record position information in the record index record is acquired. Further, the search unit 132 acquires the attribute order information corresponding to the attribute identifier of the search condition from the array label index. Next, the search unit 132 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index by using the attribute order information. Next, the search unit 132 acquires the attribute value in the record specified by the acquired record position information from the data source.

When the index update unit 133 satisfies a predetermined condition, the last update time indicated by the last update time information acquired from the data source is the generation time indicated by the generation time information corresponding to one or more types of indexes. It is determined whether or not it is later, and if it is later, the index generation unit 131 is operated to form one or more types of indexes. Further, the index update unit 133 usually overwrites each of the configured indexes of one or more types with the old index of the index storage unit 112. Each type of index of 1 or more is one or more of an array index, an array label index, a record index, a secondary index, and a source index. Further, the predetermined conditions are, for example, that an instruction from the user has been received, that the time has reached a predetermined time, and that the data source has been updated.

The output unit 14 acquires various types of information. Various types of information are, for example, search results described later. The output here is usually transmission to the terminal device 3, but display on a display, projection using a projector, printing by a printer, storage on a recording medium, other processing devices and other devices. The concept may include delivery of the processing result to a program or the like.

The result output unit 141 outputs the search result including the attribute value acquired by the search unit 132. Search results usually have attribute values.

The data source management device 2 manages one or more data sources. The data source management device 2 includes a data source storage unit 111.

Various types of information are stored in the terminal storage unit 31 that constitutes the terminal device 3. Various types of information are, for example, search conditions and data sources.

The terminal reception unit 32 receives various instructions and information. Various instructions and information are, for example, search conditions, data sources, and information of a part of data sources.

The acceptance here means acceptance of information input from input devices such as keyboards, mice, and touch panels, reception of information transmitted via wired or wireless communication lines, optical disks, magnetic disks, semiconductor memories, etc. It is a concept including acceptance of information read from a recording medium of.

The terminal processing unit 33 performs various processes. The various processes are, for example, a process of converting an instruction or information received by the terminal reception unit 32 into an instruction or information of a data structure to be transmitted. The various processes are, for example, a process of converting the information received by the terminal receiving unit 35 into the information of the data structure to be output.

The terminal transmission unit 34 transmits various information and instructions. The terminal transmission unit 34 usually transmits various information and instructions to the search device 1. Various information and instructions are, for example, search conditions and data sources.

The terminal receiving unit 35 receives various types of information. The terminal receiving unit 35 receives various information from the search device 1. The various information is, for example, a search result.

The terminal output unit 36 outputs various information. The various information is, for example, a search result.

Storage unit 11, data source storage unit 111, index storage unit 112, array index storage unit 1121, array label index storage unit 1122, record index storage unit 1123, secondary index storage unit 1124, source index storage unit 1125, A non-volatile recording medium is suitable for the terminal storage unit 31, but a volatile recording medium can also be used.

The process of storing information in the storage unit 11 or the like does not matter. For example, the information may be stored in the storage unit 11 or the like via the recording medium, or the information transmitted via the communication line or the like may be stored in the storage unit 11 or the like. Alternatively, the information input via the input device may be stored in the storage unit 11 or the like.

The reception unit 12, the condition reception unit 121, and the terminal reception unit 35 are usually realized by wireless or wired communication means, but may be realized by means for receiving broadcasts.

Processing unit 13, index generation unit 131, search unit 132, index update unit 133, array index generation unit 1311, array label index generation unit 1312, record index generation unit 1313, secondary index generation unit 1314, source index generation. The unit 1315 and the terminal processing unit 33 can usually be realized from a processor, a memory, or the like. The processing procedure of the processing unit 13 and the like is usually realized by software, and the software is recorded in a recording medium such as ROM. However, it may be realized by hardware (dedicated circuit). The processor is a CPU, MPU, GPU, or the like, and the type thereof does not matter.

The output unit 14, the result output unit 141, and the terminal transmission unit 34 are usually realized by wireless or wired communication means, but may be realized by broadcasting means.

The terminal reception unit 32 can be realized by a device driver for input means such as a touch panel or a keyboard, control software for a menu screen, or the like.

The terminal output unit 36 may or may not include an output device such as a display or a speaker. The terminal output unit 36 can be realized by the driver software of the output device, the driver software of the output device, the output device, or the like.

Next, an operation example of the search system A will be described. First, an operation example of the search device 1 will be described with reference to the flowchart of FIG.

(Step S401) The index generation unit 131 determines whether or not it is time to generate an index. If it is the timing to generate an index, it goes to step S402, and if it is not the timing to generate an index, it goes to step S406.

(Step S402) The index generation unit 131 substitutes 1 for the counter i.

(Step S403) The index generation unit 131 determines whether or not the i-th data source for which the index is generated exists. If the i-th data source exists, the process goes to step S404, and if the i-th data source does not exist, the process returns to step S401.

(Step S404) The index generation unit 131 generates an index corresponding to the i-th data source. An example of the index generation process will be described with reference to the flowchart of FIG.

(Step S405) The index generation unit 131 increments the counter i by 1. Return to step S403.

(Step S406) The index update unit 133 determines whether or not it is time to update the index. If it is the timing to update the index, the process goes to step S407, and if it is not the timing to update the index, the process goes to step S414.

(Step S407) The index update unit 133 substitutes 1 for the counter i.

(Step S408) The index update unit 133 determines whether or not the i-th data source exists. If the i-th data source exists, the process goes to step S409, and if the i-th data source does not exist, the process returns to step S401.

(Step S409) The index update unit 133 acquires the last update information which is the attribute value of the i-th data source.

(Step S410) The index update unit 133 acquires information at the time of generation of an index (for example, an array index) corresponding to the i-th data source from the array index storage unit 1121.

(Step S411) The index update unit 133 determines whether or not the time indicated by the last update information acquired in step S409 is newer than the time indicated by the generation information acquired in step S410. If it is new, it goes to step S412, and if it is not new, it goes to step S413.

(Step S412) The index update unit 133 instructs the index generation unit 131 to operate. As a result, the index generation unit 131 generates an index, associates it with the i-th data source, and accumulates the index. By such processing, the index corresponding to the i-th data source is updated. An example of the index generation process is the flowchart of FIG.

(Step S413) The counter i is incremented by 1. Return to step S408.

(Step S414) The condition reception unit 121 determines whether or not the search condition has been accepted. If the search condition is accepted, the process goes to step S415, and if the search condition is not accepted, the process returns to step S401.

(Step S415) The search unit 132 performs a search using the search conditions. An example of such a search process will be described with reference to the flowchart of FIG.

(Step S416) The result output unit 141 outputs the search result acquired in step S415. Return to step S401.

In the flowchart of FIG. 4, the process ends when the power is turned off or an interrupt for the end of the process is interrupted.

Next, an example of the index generation process in step S404 will be described with reference to the flowchart of FIG.

(Step S501) The source index generation unit 1315 generates a source index. An example of such a source index generation process will be described with reference to the flowchart of FIG.

(Step S502) The array label index generation unit 1312 generates an array label index. An example of such an array label index generation process will be described with reference to the flowchart of FIG. 7.

(Step S503) The array index generation unit 1311 generates an array index. An example of such an array index generation process will be described with reference to the flowchart of FIG.

(Step S504) The record index generation unit 1313 generates a record index. An example of such a record index generation process will be described with reference to the flowchart of FIG.

(Step S505) The secondary index generation unit 1314 generates a secondary index. An example of such a secondary index generation process will be described with reference to the flowchart of FIG.

In the flowchart of FIG. 5, for example, the record index and the array index may be generated together for each record. That is, the procedure and order of generating various indexes are not limited.

Next, an example of the source index generation process in step S501 will be described with reference to the flowchart of FIG.

(Step S601) The source index generation unit 1315 determines whether or not different records exist in each of the two or more data sources. If there are different records, the process goes to step S602, and if there are no different records, the process goes to step S604.

(Step S602) The source index generation unit 1315 refers to the data source for which the index is generated, and acquires the minimum key item value of the data source.

(Step S603) The source index generation unit 1315 refers to the data source for which the index is generated, and acquires the maximum key item value of the data source.

(Step S604) The source index generation unit 1315 determines whether or not attribute values of different attributes exist in each of the two or more data sources. If the attribute values of different attributes exist, the process goes to step S605, and if the attribute values of different attributes do not exist, the process goes to step S607.

(Step S605) The source index generation unit 1315 refers to the data source for which the index is generated, and acquires the minimum attribute identifier of the data source.

(Step S606) The source index generation unit 1315 refers to the data source for which the index is generated, and acquires the maximum attribute identifier of the data source.

(Step S607) The source index generation unit 1315 acquires the source identifier of the data source for which the index is generated.

(Step S608) The source index generation unit 1315 constitutes a source index record. The source index record has, for example, a minimum key item value and a maximum key item value. The source index record has, for example, a minimum attribute identifier and a maximum attribute identifier. The source index record has, for example, a minimum key item value, a maximum key item value, a minimum attribute identifier, and a maximum attribute identifier. The source index record corresponds to the source identifier. Needless to say, corresponding to the source identifier may mean having the source identifier.

(Step S609) The source index generation unit 1315 adds the source index record configured in step S608 to the source index storage unit 1125. Return to higher-level processing.

Next, an example of the array label index generation process in step S502 will be described with reference to the flowchart of FIG. 7.

(Step S701) The array label index generation unit 1312 assigns 1 to the counter i.

(Step S702) The array label index generation unit 1312 acquires the attribute identifier of the i-th attribute of the data source for which the index is generated.

The array label index generation unit 1312 acquires, for example, the attribute identifier of the i-th attribute of the record in the first row in the data source for which the index is generated. The array label index generation unit 1312 may acquire the attribute identifier of the i-th attribute from the data source schema information stored in the storage unit 11, for example. The data source schema information is information that specifies the structure of the data source, and has, for example, two or more attribute identifiers.

(Step S703) The array label index generation unit 1312 determines whether or not the attribute identifier of the i-th attribute could be acquired in step S702. If it can be acquired, it goes to step S704, and if it cannot be acquired, it returns to the higher-level processing.

(Step S704) The array label index generation unit 1312 constitutes an array label index record having the attribute identifier of the i-th attribute acquired in step S702 and i (attribute order information). The array label index record is information that constitutes the array label index.

(Step S705) The array label index generation unit 1312 adds the array label index record configured in step S704 to the array label index storage unit 1122 in association with the data source for which the index is generated.

(Step S706) The array label index generation unit 1312 increments the counter i by 1. Return to step S702.

In the flowchart of FIG. 7, it is preferable to sort the array label index record using the attribute identifier as a key to form the array label index.

Next, an example of the array index generation process in step S503 will be described with reference to the flowchart of FIG.

(Step S801) The array index generation unit 1311 substitutes 1 for the counter i.

(Step S802) The array index generation unit 1311 determines whether or not the i-th record exists in the data source for which the index is generated. If the i-th record exists, the process proceeds to step S803, and if the i-th record does not exist, the process returns to higher processing.

(Step S803) The array index generation unit 1311 assigns 1 to the counter j.

(Step S804) The array index generation unit 1311 determines whether or not the j-th attribute exists in the data source for which the index is generated. If the j-th attribute exists, the process goes to step S805, and if the j-th attribute does not exist, the process goes to step S809.

(Step S805) The array index generation unit 1311 determines whether or not to use the j-th attribute for the array index. If the jth attribute is used for the array index, go to step S806, and if not, go to step S808.

(Step S806) The array index generation unit 1311 acquires the attribute position information of the attribute value of the j-th attribute of the i-th record from the data source for which the index is generated.

(Step S807) The array index generation unit 1311 adds the attribute position information acquired in step S806 to the buffer of the array index record.

(Step S808) The array index generation unit 1311 increments the counter j by 1. Return to step S804.

(Step S809) The array index generation unit 1311 adds the array index record of the buffer of the array index record to the array index storage unit 1121.

(Step S810) The array index generation unit 1311 increments the counter i by 1. Return to step S802.

Next, an example of the record index generation process in step S504 will be described with reference to the flowchart of FIG.

(Step S901) The record index generation unit 1313 assigns 1 to the counter i.

(Step S902) The record index generation unit 1313 determines whether or not the i-th record exists in the data source for which the index is generated. If the i-th record exists, the process proceeds to step S903, and if the i-th record does not exist, the process returns to higher processing.

(Step S903) The record index generation unit 1313 refers to the data source for which the index is generated, and acquires the record position information of the i-th record.

(Step S904) The record index generation unit 1313 refers to the data source for which the index is generated, and acquires the key item value of the i-th record.

(Step S905) The record index generation unit 1313 acquires the record index record position information which is the position information in the record index of the i-th record index record.

(Step S906) The record index generation unit 1313 has the record position information acquired in step S903, the key item value acquired in step S904, and the record index record position information acquired in step S905. Make up a record.

(Step S907) The record index generation unit 1313 adds the record index record configured in step S906 to the record index storage unit 1123.

(Step S908) The record index generation unit 1313 increments the counter i by 1. Return to step 902.

In the flowchart of FIG. 9, it is preferable that the record index generation unit 1313 sorts the record index records using the key item value as a key. In such a case, it goes without saying that the record index generation unit 1313 acquires the record index record position information in the sorted state for each record index record.

Next, an example of the secondary index generation process in step S505 will be described with reference to the flowchart of FIG.

(Step S1001) The secondary index generation unit 1314 substitutes 1 for the counter i.

(Step S1002) The secondary index generation unit 1314 determines whether or not the i-th record index record exists in the record index. If the i-th record / index record exists, the process goes to step S1003, and if it does not exist, the process returns to higher processing.

(Step S1003) The secondary index generation unit 1314 determines whether or not to use the i-th record index record for the secondary index. If it is used for the secondary index, it goes to step S1004, and if it is not used for the secondary index, it goes to step S1006.

The secondary index generation unit 1314 uses some record index records among all the record index records. In the secondary index generation unit 1314, for example, when the numbers of all records and index records are divided by N (N is a natural number of 2 or more), the remainder value is M (M is an integer, 0 <= M <N−). It is determined that the record index record corresponding to the number in 1) is used. Further, the secondary index generation unit 1314 determines that, for example, some predetermined record index records are used.

(Step S1004) The secondary index generation unit 1314 acquires the key item value and the record index record position information from the i-th record index record, and constitutes a secondary index record having the information.

(Step S1005) The secondary index generation unit 1314 adds the secondary index record configured in step S1004 to the secondary index storage unit 1124.

(Step S1006) The secondary index generation unit 1314 increments the counter i by 1. Return to step 1002.

In the flowchart of FIG. 10, it is preferable that the secondary index records are sorted using the key item value as a key.

Next, an example of the search process in step S415 will be described with reference to the flowchart of FIG.

(Step S1101) The search unit 132 acquires one or more attribute identifiers and one or more key item values corresponding to the accepted search conditions. In addition, one or more attribute identifiers specify an attribute value to be acquired as a search result. The key item value of 1 or more specifies the record for which information is acquired as a search result. That is, the search unit 132 is the attribute value in the record of one or more key item values acquired here, and acquires the attribute value identified by each of the one or more attribute identifiers acquired here.

(Step S1102) The search unit 132 refers to the source index and acquires one or more attribute identifiers acquired in step S1101 and one or more source identifiers corresponding to one or more key item values. Here, the search unit 132 uses the acquired one or more source identifiers as one or more attribute identifiers of the attribute values included in the data source identified by the source identifiers and the data source identified by the source identifiers. Corresponds to one or more key item values of the included record.

(Step S1103) The search unit 132 substitutes 1 for the counter i.

(Step S1104) The search unit 132 determines whether or not the i-th source identifier exists among the one or more source identifiers acquired in step S1102. If the i-th source identifier exists, the process goes to step S1105, and if it does not exist, the process goes to step S1118.

(Step S1105) The search unit 132 substitutes 1 for the counter j.

(Step S1106) The search unit 132 determines whether or not the j-th key item value exists among the one or more key item values associated with the i-th source identifier in step S1102. If the j-th key item value exists, the process goes to step S1107, and if it does not exist, the process goes to step S1117.

(Step S1107) The search unit 132 refers to the secondary index corresponding to the i-th source identifier, and the first record index record position information and the second record index record corresponding to the j-th key item value. Get location information. The first record index record position information is the record index record position information paired with the largest key item value among the key item values smaller than the jth key item value. The second record index record position information is the record index record position information paired with the smallest key item value among the key item values larger than the jth key item value. Further, here, the search unit 132 may acquire one record / index record position information paired with the j-th key item value from the secondary index.

(Step S1108) When the first record index record position information and the second record index record position information are acquired in step S1107, the search unit 132 uses the first record index record position information and the second record index record position information. The record index record between the record index record position information and the record index record of (for example, binary search or sequential search) is searched, and the jth key item value is detected. Next, the search unit 132 acquires the record position information paired with the j-th key item value from the record index.

Further, when one record index record position information is acquired in step S1107, the search unit 132 acquires the record position information paired with the record index record position information from the record index.

(Step S1109) The search unit 132 substitutes 1 for the counter k.

(Step S1110) The search unit 132 determines whether or not the k-th attribute identifier corresponding to the i-th source identifier exists. If the k-th attribute identifier exists, the process goes to step S1111. If the k-th attribute identifier does not exist, the process goes to step S1116.

(Step S1111) The search unit 132 refers to the array label index corresponding to the i-th source identifier, and acquires the attribute order information paired with the k-th attribute identifier from the array label index.

(Step S1112) The search unit 132 refers to the array index corresponding to the i-th source identifier, and determines whether or not the attribute order information matching the attribute order information acquired in step S1111 exists in the array index. to decide. When the attribute order information that matches the attribute order information exists, the search unit 132 acquires the attribute position information that is paired with the attribute order information and is paired with the jth key item value from the array index. ..

If there is no attribute order information that matches the attribute order information, the search unit 132 acquires two attribute order information sandwiching the attribute order information. That is, the search unit 132 acquires the first attribute order information having a value smaller than the attribute order information and having the smallest difference from the attribute order information. Further, the search unit 132 acquires the second attribute order information having a value larger than the attribute order information and having the smallest difference from the attribute order information. The first attribute order information and the second attribute order information are information sandwiching the attribute order information. Next, the search unit 132 acquires the attribute position information that is paired with the first attribute order information and is paired with the jth key item value from the array index. Further, the search unit 132 acquires the attribute position information that is paired with the second attribute order information and is paired with the jth key item value from the array index.

(Step S1113) When one attribute position information is acquired in step S1112, the search unit 132 selects the record at the position indicated by the record position information paired with the jth key item value acquired in step S1108. The attribute value of the position indicated by one attribute position information acquired in step S1112 is acquired from the data source identified by the i-th source identifier.

Further, when the two attribute position information is acquired in step S1112, the search unit 132 uses the two records at the positions indicated by the record position information paired with the j-th key item value acquired in step S1108. The attribute value of the position specified by each attribute position information is inspected by, for example, sequential search, and the attribute value existing in the order of the attribute order information paired with the kth attribute identifier is identified by the i-th source identifier. Obtained from a data source.

(Step S1114) The search unit 132 temporarily stores the attribute value acquired in step S1113 in a buffer (not shown) in association with the j-th key item value and the k-th attribute identifier.

(Step S1115) The search unit 132 increments the counter k by 1. Return to step 1110.

(Step S1116) The search unit 132 increments the counter j by 1. Return to step 1106.

(Step S1117) The search unit 132 increments the counter i by 1. Return to step 1104.

(Step S1118) The search unit 132 constitutes a search result including one or more attribute values temporarily stored in a buffer (not shown). Return to higher-level processing. The method of constructing the search results does not matter. It is preferable that the attribute identifier corresponding to the attribute value included in the search result is included in the search result in a manner in which it is clearly indicated that the attribute value corresponds to the attribute value. Further, it is preferable that the search result includes the j-th key item value.

Next, an operation example of the data source management device 2 will be described. The data source management device 2 reads out the data source of the data source storage unit 111 and transmits it to the search device 1 in response to the access from the search device 1. In such a case, the data source management device 2 may read and transmit only a part of the data source.

Next, an operation example of the terminal device 3 will be described. The terminal reception unit 32 of the terminal device 3 accepts search conditions. Next, the terminal processing unit 33 configures the search condition to be transmitted. Next, the terminal transmission unit 34 transmits the search condition to the search device 1. Then, in response to the transmission of the search condition, the terminal receiving unit 35 receives the search result. Next, the terminal processing unit 33 configures the search result to be output by using the received search result. Next, the terminal output unit 36 outputs the search result.

Hereinafter, a specific operation example of the search system A in the present embodiment will be described.

Now, three or more data sources including the three data sources (1201, 1202, 1203) shown in FIG. 12 are stored in the data source storage unit 111 of the search device 1 or the data source storage unit 111 of the data source management device 2. It is assumed that it has been done. It is assumed that each of the three data sources is one file here.

And the data source of FIG. 12 has a header record, a label record, and a large number of records. The label record and each record are separated by the first delimiter. Further, the first delimiter is, for example, a return code here.

A header record is a so-called header of a file and has one or more source attribute values. The source attribute value is, here, the source identifier, the report number, and the information at the time of the last update. The source identifier is File Name in FIG. 12, and the value is “File1”. The report number is a number for identifying the source of the data source, and the value is "A12345". The information at the time of the last update is Date in FIG. 12, and the value is "XXXX-XX-XX".

The label record is, for example, the first line of the file. If the header record is the first line of the file, the label record is the second line of the file. A label record is a set of item labels and a set of attribute identifiers. Item labels are key item labels or line item labels. The key item is an attribute that is a key of the record, and here, it is a "PID (personal ID)". The "PID" is an ID that identifies a user. The detail item is a user attribute value corresponding to "PID", and here, the detail item includes "No." and "Age". “No.” is a record ID, and its value is [1] [2] [3] of 1201 in FIG. Further, (Pos.) Under "No." is the record position information of each record (here, the offset at the beginning of the record in the data source). "Age" is the age of the user. In FIG. 12, the attribute identifier is “TestB”, “TestE”, “TestC”, or the like. In FIG. 12, the attribute order information is described under the attribute identifier. The attribute order information is [1] [2] [3] or the like under the attribute identifier.

Each record in FIG. 12 has a key item value, a detail item value, and an attribute value. The key item value is the value of the key item, and here, it is the PID (for example, 236,029) of each user. It is preferable that which value is used as the key item value can be specified as a parameter for index generation, and other values (for example, "Age" and "PID and Age pair") may be used, and two or more values may be used. It is also possible to have a key item value. Here, the item item value is, for example, a value of "No." or a value of "Age". Here, the value of "No." is [1], [2], or the like. The values (for example, (1), (121), (241), etc.) existing under the value of "No." ([1], [2], [3], etc.) are the record position information of each record.

The attribute values of the record corresponding to the record identifier [1] are 0.11, 0.4, 0.57, and the like. Further, in FIG. 12, the attribute value position information ((57) (62) (73), etc.) of each attribute value is written below the attribute value (0.11, 0.4, 0.57, etc.). ing.

It is assumed that the data source here includes a set of gene / genomic information. In addition, data dealing with general gene / genome information includes data such as a base sequence of a gene and an amino acid sequence of a protein, and the length of one record may be, for example, several GB. In addition, the number of attribute values in one record becomes enormous, and the data size often becomes enormous. In many cases, data dealing with gene / genome information is stored and distributed in a flat file (general text file) in a relatively simple layout, and the data source (see FIG. 12) in this specific example is This is an example.

In such a situation, the following three specific examples will be described. Specific example 1 is an example of index generation processing. Specific Example 2 is an example of the search process in the case where the source index has a set of the minimum key item value and the maximum key item value and does not have the set of the minimum attribute identifier and the maximum attribute identifier. Specific Example 3 is an example of the search process when the source index has a set of the minimum key item value, the maximum key item value, the minimum attribute identifier, and the maximum attribute identifier.

(Specific example 1)
An example of various index generation processes by the index generation unit 131 of the search device 1 will be described with reference to FIG. Here, it is assumed that the key item is "PID".
(1) Source index generation process

The source index generation unit 1315 accesses the file "data source 1301" and acquires the source identifier (here, the file name) "file1" of the data source 1301. Further, the source index generation unit 1315 opens the data source 1301. Next, the source index generation unit 1315 acquires the minimum key item value "029" which is the minimum PID and the maximum key item value "451" which is the maximum PID among the PIDs of the data source 1301. When the PIDs are sorted in the data source 1301, the source index generation unit 1315 acquires the first PID and the last PID. If the PIDs are not sorted, the source index generator 1315 sequentially inspects the PIDs and obtains the minimum key item value and the maximum key item value from the data source 1301.

Further, the source index generation unit 1315 acquires the minimum attribute identifier "TestA" and the maximum attribute identifier "TestE" among the attribute value identifiers of the label record of the data source 1301. When the attribute identifiers are sorted in the data source 1301, the source index generation unit 1315 acquires the first attribute identifier and the last attribute identifier from the label record. If the attribute identifiers are not sorted, the source index generator 1315 sequentially inspects the attribute identifiers and obtains the minimum attribute identifier and the maximum attribute identifier from the label record.

Next, the source index generation unit 1315 obtains the source index record “file1,029,451, TestA, TestE” from the acquired source identifier, minimum key item value, maximum key item value, minimum attribute identifier, and maximum attribute identifier. , And accumulates in the source index storage unit 1125.

Similarly, the source index generation unit 1315 constitutes a source index record for other data sources (files “file2”, “file3”, etc.) and stores them in the source index storage unit 1125.

By the above processing, the source index of 1302 of FIG. 13 is accumulated in the source index storage unit 1125.
(2) Array label index generation process

The array label index generation unit 1312 accesses the file "data source 1301" and acquires the source identifier (file name) "file1" of the data source 1301. Further, the source index generation unit 1315 opens the data source 1301.

Next, the array label index generation unit 1312 acquires the attribute identifiers in the order in which they are arranged in the label index of the data source 1301 together with the attribute order information in that order. Then, for each attribute identifier, an array label index record which is a set of the attribute identifier and the attribute order information is configured.

Next, the array label index generation unit 1312 sorts the array label index records using the attribute identifier as a key, for example, in ascending order. Then, the array label index generation unit 1312 stores the sorted array label index records in the array label index storage unit 1122.

The array label index generation unit 1312 similarly forms an array label index for other data sources (files “file2”, “file3”, etc.) and stores them in the array label index storage unit 1122.

By the above processing, the array label index of 1303 in FIG. 13 is accumulated in the array label index storage unit 1122.
(3) Array index generation process

The array index generation unit 1311 accesses the file "data source 1301" and acquires the source identifier (file name) "file1" of the data source 1301. Further, the source index generation unit 1315 opens the data source 1301.

The array index generation unit 1311 acquires the attribute order information of the data source 1301 by skipping a predetermined number (here, three), for example, the first, fourth, seventh, and so on. Further, the array index generation unit 1311 advances the file pointer to the attribute value in the order of each acquired attribute order information while detecting the second delimiter for each record, for example, the record of the attribute value in that order. Gets the attribute position information that is the offset within. Next, the array index generation unit 1311 concatenates the acquired attribute position information in the order indicated by the attribute order information in association with the PID of the record for each record of the data source 1301 to form an array index record.

Next, the array index generation unit 1311 sorts the array index records in ascending order, for example, using the corresponding PID as a key, constitutes an array index, and stores the array index records in the array index storage unit 1121.

Further, the array index generation unit 1311 similarly forms an array index for other data sources (files “file2”, “file3”, etc.) and stores them in the array index storage unit 1121.

By the above processing, the array index of 1304 in FIG. 13 is accumulated in the array index storage unit 1121.
(4) Record index generation process

The record index generation unit 1313 accesses the file “data source 1301” and acquires the source identifier (file name) “file1” of the data source 1301. Further, the source index generation unit 1315 opens the data source 1301.

The record index generation unit 1313 acquires the key item value and the record position information which is the offset of the record in the data source 1301 from the data source 1301 for each record in the data source 1301 and constitutes the record index record. do.

Then, the record index generation unit 1313 sorts the set of the key item value and the record position information in ascending order, for example, using the key item value as a key. Next, the record index generation unit 1313 acquires the position information (Pos.) Of each record index record in the record index. Such position information (Pos.) Is record index record position information.

Here, the record / index record position information (Pos.) Is the position information (Pos.) Of a record having the position information (Pos.), A set of a key item value and a record position information, and an array index record. Is preferable. That is, it is preferable that the record index record and the array index record are communicated for each record of the data source.

Next, the record index generation unit 1313 stores the record index record for each record in the data source 1301 in the record index storage unit 1123.

Further, the record index generation unit 1313 similarly forms a record index for other data sources (files “file2”, “file3”, etc.) and stores the record index in the record index storage unit 1123.

By the above processing, the record index of 1305 of FIG. 13 is accumulated in the record index storage unit 1123.
(5) Secondary index generation process

The secondary index generation unit 1314 reads the record index of the record index storage unit 1123.

Next, the secondary index generation unit 1314 skips a predetermined number (here, three), for example, the first, fourth, seventh, and so on, and the key item value (here, here) included in the record index record. , PID) and the record index record position information (Pos.) To acquire the secondary index record which is a set.

Next, the secondary index generation unit 1314 adds the acquired secondary index record to the secondary index storage unit 1124. In the secondary index, the secondary index records are sorted using the PID as a key.

Further, the secondary index generation unit 1314 similarly forms a secondary index for other data sources (files “file2”, “file3”, etc.) and stores them in the secondary index storage unit 1124.

By the above processing, the secondary index of 1306 in FIG. 13 is accumulated in the secondary index storage unit 1124.

(Specific example 2)
Now, it is assumed that the data source of 1401 of FIG. 14 is stored in the data source storage unit 111 of the data source management device 2 or the data source storage unit 111 of the search device 1.

In such a case, it is assumed that the user has input the search condition "Select PID, Age, Test, TestValue from data source where PID = 155 AND Test = TestC" in the terminal device 3. It is assumed that "Test" of "PID, Age, Test, TestValue" is an attribute value identifier, and "TestValue" is an attribute value.

Then, the terminal reception unit 32 of the terminal device 3 accepts such a search condition. Next, the terminal processing unit 33 configures the search condition to be transmitted. Next, the terminal transmission unit 34 transmits the search condition to the search device 1.

Next, the condition receiving unit 121 of the search device 1 receives the search condition "Select PID, Age, Test, TestValue from data source where PID = 155 AND Test = TestC".

Next, the search unit 132 of the search device 1 has the attributes of "PID", "Age", the attribute identifier "TestC", and the TestC in the record matching "PID = 155 AND Test = TestC" as follows. Get the value.

That is, first, the search unit 132 acquires "PID = 155" included in the search condition. Further, the search unit 132 acquires the attribute value identifier "TestC" included in the search condition (1406 in FIG. 14).

Next, the search unit 132 refers to the source index (1402) and sandwiches the acquired "PID = 155" between Min (minimum key item value) and Max (maximum key item value). The record is detected and the source identifier "File1" possessed by the source index record is acquired.

Further, the search unit 132 refers to the secondary index (1403) corresponding to the source identifier "File1", detects the PIDs "029" and "236" having "PID = 155" in between, and detects the PID "029" and "236". The record index record position information (1) and (151) paired with "029" and "236" are acquired from the secondary index (1403).

Next, the search unit 132 refers to the record index (1404) corresponding to the source identifier “File1”, and sets between the record index record position information (1) and (151), for example, “PID = 155”. Is used as a key for a binary search, and a record index record containing "PID = 155" is detected. Then, the search unit 132 acquires the record position information (241) paired with "PID = 155" from the record index record. The search unit 132 may detect a record index record including "PID = 155" by performing a sequential search instead of a binary search.

Next, the search unit 132 temporarily stores the acquired record position information (241) and the record index record position information (101) in a buffer (not shown).

Next, the search unit 132 refers to the array label index (1405) corresponding to the source identifier "File1", and uses the attribute identifier "TestC" included in the search condition as a key to perform a binary search for the array label index. , Detects the attribute identifier "TestC" and acquires the attribute order information (3) paired with the attribute identifier "TestC". Here, the search unit 132 may acquire the attribute order information (3) by performing a sequential search instead of a binary search.

Next, the search unit 132 refers to the array index corresponding to the source identifier "File1", and sandwiches the attribute order information (3) in the array index with the first attribute order information (1) and the first. Acquire the second attribute order information (4).

Next, the search unit 132 acquires the attribute value position information (54) corresponding to the first attribute order information (1) from the record index corresponding to the record index record position information (101) of the buffer (not shown). However, it is temporarily stored in a buffer (not shown). Further, the search unit 132 acquires the attribute value position information (84) corresponding to the record index record position information (101) and the second attribute order information (4) from the record index, and is not shown. Temporarily accumulate in the buffer.

Next, the search unit 132 accesses the data source identified by the source identifier "File1" and opens the file.

Next, the search unit 132 acquires the record position information (241), the attribute value position information (54), and the attribute value position information (84) from a buffer (not shown), and the record position information (241) specifies the record position information (241). The attribute value "0.381", which is an attribute value between the attribute value position information (54) and the attribute value position information (84) in the position record and corresponds to the attribute order information (3), is the relevant. Get from the file. Further, the search unit 132 acquires Age "62" from the file in the record at the position specified by the record position information (241).

Then, the search unit 132 constitutes a search result having a PID "155", an Age "62", an attribute value identifier "TestC", and an attribute value "0.381".

Next, the result output unit 141 transmits the configured search result to the terminal device 3. The search result is, for example, 1407 in FIG.

Next, the terminal receiving unit 35 of the terminal device 3 receives the search result. Next, the terminal processing unit 33 configures the search result to be output by using the received search result. Next, the terminal output unit 36 outputs the search result.

(Specific example 3)
Now, it is assumed that the data source of 1301 of FIG. 13 is stored in the data source storage unit 111 of the data source management device 2 or the data source storage unit 111 of the search device 1.

In such a case, it is assumed that the user has input the search condition "Select PID, Age, Test, TestValue from data source where PID = 155 AND Test = TestC" in the terminal device 3.

Then, the terminal reception unit 32 of the terminal device 3 accepts such a search condition. Next, the terminal processing unit 33 configures the search condition to be transmitted. Next, the terminal transmission unit 34 transmits the search condition to the search device 1.

Next, the condition receiving unit 121 of the search device 1 receives the search condition "Select PID, Age, Test, TestValue from data source where PID = 155 AND Test = TestC".

Next, the search unit 132 of the search device 1 has the attributes of "PID", "Age", the attribute identifier "TestC", and the TestC in the record matching "PID = 155 AND Test = TestC" as follows. Get the value.

That is, first, the search unit 132 acquires "PID = 155" included in the search condition. Further, the search unit 132 acquires the attribute value identifier "TestC" included in the search condition.

Next, the search unit 132 refers to the source index (1302) and acquires the source identifier “File1” corresponding to the acquired “PID = 155” and “TestC”.

After that, the search unit 132 obtains a search result by the same process as that described in the second embodiment.

Next, the result output unit 141 transmits the configured search result to the terminal device 3. The search result is, for example, 1307 in FIG.

Next, in response to the transmission of the search condition, the terminal receiving unit 35 receives the search result. Next, the terminal processing unit 33 configures the search result to be output by using the received search result. Next, the terminal output unit 36 outputs the search result.

As described above, according to the present embodiment, a desired attribute value can be searched at high speed from a data source having a large data size.

Further, according to the present embodiment, it is possible to search for a desired attribute value at high speed, particularly for a data source having a very long record length.

Further, according to the present embodiment, an index for high-speed information retrieval can be automatically generated.

Further, according to the present embodiment, it is possible to automatically generate an index for high-speed information retrieval, particularly for a data source having a very long record length.

Further, according to the present embodiment, the index in the latest state can be maintained.

Further, the processing in the present embodiment may be realized by software. Then, this software may be distributed by software download or the like. Further, this software may be recorded on a recording medium such as a CD-ROM and disseminated. It should be noted that this also applies to other embodiments herein. The software that realizes the search device 1 in the present embodiment is the following program. That is, this program has a data source storage unit that stores a data source containing two or more records having a key item value and two or more attribute values, and one or more records out of two or more records. And for each one or more attributes of each record, a search condition that includes an attribute identifier for a computer that can access the array index storage unit that stores the array index that has the attribute position information that identifies the position where the attribute value exists. And the attribute position information corresponding to the attribute identifier of the search condition are acquired from the array index, and the attribute value corresponding to the attribute identifier of the search condition is used by using the attribute position information. Is a program for functioning as a search unit acquired from the data source and a result output unit that outputs a search result including the attribute value acquired by the search unit.

(Embodiment 2)
In the present embodiment, a search system including a search device for searching information on a data source using a plurality of record indexes will be described.

Further, in the present embodiment, a search system including a search device for searching information on a data source using two or more types of indexes including a record index will be described. In addition to the record index, the two or more types of indexes are, for example, one or more of an array index, an array label index, a secondary index, and a source index.

Further, in the present embodiment, a search system including a search device that generates a plurality of record indexes will be described.

FIG. 15 is a conceptual diagram of the search system B according to the present embodiment. The search system B includes a search device 4, one or more data source management devices 2, and one or more terminal devices 3.

The search device 4 is a device for searching information from a data source. The search device 4 is, for example, a so-called server, for example, a cloud server, an ASP server, or the like. The type of the search device 4 does not matter. The search device 4 may search for information from a data source stored in a data source management device 2 which is an external device, or may search for information from a data source inside the search device 4. In addition, each data source management device 2 of 1 or 2 or more is usually a device different from the search device 4.

Further, the search device 4 and the data source management device 2 of 1 or more can communicate with each other via a network such as the Internet or a LAN. Further, the search device 4 and the terminal device 3 can communicate with each other via a network such as the Internet or a LAN.

FIG. 16 is a block diagram of the search system B according to the present embodiment. FIG. 17 is a block diagram of the search device 4.

The search device 4 includes a storage unit 41, a reception unit 12, a processing unit 43, and an output unit 44. The storage unit 41 includes an index storage unit 411. The storage unit 41 may include a data source storage unit 111. The index storage unit 411 includes an array index storage unit 1121, an array label index storage unit 1122, a record index storage unit 4113, a secondary index storage unit 1124, and a source index storage unit 1125. The reception unit 12 includes a condition reception unit 121. The processing unit 43 includes an index generation unit 431, a search unit 432, and an index update unit 433. The index generation unit 431 includes an array index generation unit 1311, an array label index generation unit 1312, a record index generation unit 4313, a secondary index generation unit 1314, and a source index generation unit 1315. The search unit 432 includes a source determination unit 4321, a record index determination unit 4322, and a search unit 4323. The output unit 44 includes and a result output unit 441.

It is preferable that the search device 4 has the same function as the search device 1 except that it can generate a plurality of record indexes and search for information using a plurality of record indexes.

The data source management device 2 includes a data source storage unit 111.

The terminal device 3 includes a terminal storage unit 31, a terminal reception unit 32, a terminal processing unit 33, a terminal transmission unit 34, a terminal reception unit 35, and a terminal output unit 36.

Various types of information are stored in the storage unit 41 that constitutes the search device 4. The various information is, for example, one or more types of indexes, data sources, and one or more search conditions described above.

Note that one or more search conditions correspond to the data source. The one or more search conditions are search conditions entered by the user for searching for information.

The index storage unit 411 stores one or more types of indexes described above. Two or more record indexes are stored in the index storage unit 411. Further, each index of the index storage unit 411 may have an index structure such as a secondary index, a BTREE, or an inverted index.

The array index is stored in the array index storage unit 1121. The array index may be present for each of the two or more record indexes. That is, two or more array indexes may be stored in the array index storage unit 1121. However, it is preferable that only one array index is stored in the array index storage unit 1121. Such one array index is information corresponding to any of two or more record indexes.

Two or more record indexes are stored in the record index storage unit 4113. The record index storage unit 1123 usually stores one or more record indexes for each data source. If there are two or more record indexes corresponding to one data source, each of the two or more record indexes is a record index corresponding to a different key item combination.

Each of the two or more record indexes has one or more record index records. A record index record is a set of one or more key item values and record position information.
If two or more record indexes correspond to one array index, the record index record is a set of one or more key field values and the position information of the records in the array index, and each record in the array index is It may be configured to have the record position information so as to correspond to the record of the data source. Even in such a case, since the record index record is associated with the record position information of the data source, it may be considered that the record index record has the record position information.
Also, record index records correspond to records in the data source. One or more key item values possessed by such a record index record correspond to a combination of one or more key items. A combination of one or more key items is one key item or a combination of two or more key items.

It is preferable that the record index records in the record index are sorted in ascending or descending order with one or more key items as keys. Also, it is preferable that there are as many record index records in the record index as there are all records in the corresponding data source. Further, if the record index corresponds to two or more key items, the two or more key items are ordered.

It is preferable that the record index storage unit 4113 stores the schema information of the record index corresponding to each of two or more record indexes. The schema information of such a record index usually has a key item identifier (attribute identifier) corresponding to each one or more key item values possessed by the record index.

Each record index in the record index storage unit 4113 may have an index structure such as a secondary index, a BTREE, and an inverted index.

The processing unit 43 performs various processes. The various processes are, for example, processes performed by the index generation unit 431, the search unit 432, and the index update unit 433.

The index generator 431 generates an index from each of one or more data sources. The index generated by the index generator 431 includes two or more record indexes. It is preferable that the index generated by the index generation unit 431 includes an array index, an array label index, a secondary index, and a source index.

The record index generator 4313 generates one or more record indexes for each data source. The processing when the record index generation unit 4313 generates one record index for one data source is the same as the processing of the record index generation unit 1313, and thus the description thereof is omitted here. ..

Here, a case where the record index generation unit 4313 generates two or more record indexes for each one or more data sources will be described.

The record index generation unit 4313 refers to the data source, generates two or more record indexes, and stores them in the record index storage unit 4113. Such two or more record indexes are two or more record indexes corresponding to different combinations of one or more key items.

More specifically, the record index generation unit 4313 acquires information of two or more sets that specify a combination of one or more key items. Next, the record index generation unit 4313 sets the key item value (attribute value) corresponding to one or more key items corresponding to each set for each record of the data source for each set of two or more. Acquires a record index record having record position information. Then, the record index generation unit 4313 sorts the record index records using one or more key items as keys for each set of two or more, and the record index which is a set of the sorted record index records. Is configured and stored in the record index storage unit 4113.

That is, for example, the record index generation unit 4313 determines two or more sets of one or more key item combinations satisfying the selection condition, and corresponds to one or more key item combinations of each of the two or more sets. A record index, which is a set of a key item value of each of two or more records and record position information, is generated and stored in the record index storage unit 4113. The selection condition is a condition for automatically determining the set of key items. Specific examples of the selection conditions will be described later.

As a method for the record index generation unit 4313 to acquire information on the combination of one or more of the above key items, there are (1) a method specified by a user and (2) a method by automatic acquisition. Further, in the method by (2) automatic acquisition, for example, there are a method of using (2-1) a search condition, a method of using (2-2) dispersion, and the like. Hereinafter, each method will be described.
(1) User-specified method

The record index generation unit 4313 acquires two or more sets of one or more key item identifier combinations specified by the user. It should be noted that two or more sets of information are included in the index generation instruction input by the user. Each set of two or more pieces of information is one key item identifier or a set of two or more key item identifiers.
(2) Method by automatic acquisition

The record index generation unit 4313 acquires two or more sets of information satisfying the selection condition.
(2-1) How to use search conditions

The record index generation unit 4313 acquires, for example, an attribute identifier whose appearance frequency satisfies the selection condition in the past one or more search conditions as a key item identifier. The frequency of appearance may be the number of appearances in one or more search conditions in the past, or the appearance ratio. The selection condition is, for example, that the frequency of appearance is equal to or greater than the threshold value or greater than the threshold value.

The record index generation unit 4313 acquires, for example, a set of two or more attribute identifiers whose co-occurrence frequency satisfies the selection condition as a set of key item identifiers in the past one or more search conditions. The co-occurrence frequency may be the number of co-occurrence in one or more search conditions in the past, or the co-occurrence rate. The selection condition is, for example, that the co-occurrence frequency is equal to or greater than the threshold value or greater than the threshold value.
(2-2) Method using dispersion

The record index generation unit 4313 acquires, for example, the attribute identifier of each of the two or more attributes whose distribution of the attribute values included in each of the two or more records of the data source for which the index is generated satisfies the selection condition as the key item identifier. do. The selection condition is that the variance is an attribute value above or above the threshold.

The record index generation unit 4313 is, for example, N (N is A combination of 1 or more natural numbers) or less is acquired as a combination of 1 or more key item identifiers.

The search unit 432 selects one record index from two or more record indexes using the search condition accepted by the condition reception unit 121, and the key item value of the search condition from the selected record index. The record position information paired with is acquired, and the attribute value in the record corresponding to the position specified by the record position information is acquired from the data source. The acquired attribute value is, for example, the attribute value corresponding to the attribute identifier specified in the search condition, or all the attribute values in the record. You may also think that the key item value is also an attribute value.

The method by which the search unit 432 searches using the search conditions is as follows. That is, the search unit 432 selects one record index corresponding to one or more key item combinations including the key item corresponding to the key item value of the search condition. The details of the process of selecting one record index will be described later as the process of the record index determining means 4322.

For example, the search unit 432 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index, and uses the attribute position information to obtain the attribute value corresponding to the attribute identifier of the search condition as a data source. Get from.

The search unit 432 is, for example, one record corresponding to a combination of one or more key items including a key item corresponding to the key item value of the search condition received by the condition reception unit 121 from two or more record indexes. An index is selected, the record position information paired with the key item value of the search condition is acquired from the selected record index, and the record corresponding to the position specified by the record position information is determined. Next, the search unit 432 acquires the attribute position information corresponding to the attribute identifier of the search condition from the array index, and uses the attribute position information to determine the attribute value corresponding to the attribute identifier of the search condition. Get from the recorded record.

For example, from two or more record indexes, the search unit 432 selects the record index when the key item at the beginning of the record index matches the key item corresponding to the key item value of the search condition. Then, from the selected record index, the record position information that is paired with the key item value of the search condition is acquired, and the attribute value in the record corresponding to the position specified by the record position information is acquired from the data source. do.

When the search unit 432 has two or more record indexes whose first key item of the record index matches the key item corresponding to the key item value of the search condition, the search unit 432 is next to the two or more record indexes. It is determined whether the key item matches the key item of the search condition, and the record index with the most key items included in the key item of the search condition is selected from the beginning of the record index. From the selected record index, the record position information paired with the key item value of the search condition is acquired, and the attribute value in the record corresponding to the position specified by the record position information is acquired from the data source.

The source determination means 4321 acquires from the source index a source identifier that matches the key item value of the search condition or is paired with the minimum key item value and the maximum key item value having the key item value in between.

The record index determining means 4322 determines one record index to be used for the search process from two or more record indexes. The record index determining means 4322 determines one record index from, for example, two or more record indexes paired with the source identifier acquired by the source determining means 4321.

The record index determining means 4322 selects, for example, one record index corresponding to a combination of one or more key items including the key item of the search condition accepted by the condition receiving unit 121 from two or more record indexes. do. The key item possessed by the search condition may be considered as a key item corresponding to the key item value possessed by the search condition. Further, the key item possessed by the search condition may be considered as the key item identifier possessed by the search condition.

For example, when the first key item of one record index matches the key item of the search condition, the record index determining means 4322 selects the record index from two or more record indexes. .. The record index determining means 4322 is, for example, when there are two or more record indexes in which the first key item of the record index matches the key item of the search condition, the record index determining means 4322 is next to the two or more record indexes. It is determined whether the key item matches the key item of the search condition, and the most key item from the beginning of the record index is one record index included in the key item of the search condition. Select from the above record indexes.

The search means 4323 acquires the record position information paired with the key item value of the search condition from the record index selected by the record index determination means 4322. Next, the search means 4323 acquires one or more attribute values in the record corresponding to the position specified by the record position information from the data source. It should be noted that the one or more attribute values may be attribute values corresponding to the attribute identifier included in the search condition, or may be all attribute values of the record at the position specified by the record position information.

When the search means 4323 acquires the record position information paired with the key item value of the search condition from the record index, the search means 4323 searches the record index in half and acquires the record position information, for example. You may. Further, the search means 4323 may search the record position information using the index structure from the record index having the index structure, for example.

The search means 4323 acquires the record position information paired with the key item value of the search condition from the record index selected by the record index determination means 4322. Next, the search means 4323 acquires, for example, the attribute position information corresponding to the attribute identifier of the search condition from the array index. Then, the search means 4323 is, for example, an attribute value in the record at the position specified by the record position information, and acquires the attribute value at the position specified by the attribute position information.
The search means 4323 acquires the position information of the record of the array index from the record index selected by the record index determining means 4322, and the record position information of the data source from the record indicated by the position information of the record of the array index. Is an attribute value in the record of the position specified by the record position information, and the attribute value of the position specified by the attribute position information corresponding to the attribute identifier of the search condition may be acquired.

When the record index determining means 4322 does not select the record index, the search means 4323 normally searches the data source to be searched sequentially and acquires one or more attribute values corresponding to the search conditions.

Further, if the first key item of any record index is not included in the search condition and the second and subsequent key items are included in the search condition, the search means 4323 scans the entire record index. Therefore, it is preferable to acquire the record position information that matches the search condition. Even in such a case, a high-speed search is usually possible rather than a sequential search of the entire data source.

When the index update unit 433 satisfies a predetermined condition, the last update time indicated by the last update time information acquired from the data source is the generation time indicated by the generation time information corresponding to one or more types of indexes. It is determined whether or not it is later, and if it is later, the index generation unit 431 is operated to form one or more types of indexes. Further, the index update unit 433 usually overwrites each of the configured indexes of one or more types with the old index of the index storage unit 411. Each type of index of 1 or more is one or more of an array index, an array label index, a record index, a secondary index, and a source index. Further, the predetermined conditions are, for example, that an instruction from the user has been received, that the time has reached a predetermined time, and that the data source has been updated.

The index update unit 433 updates two or more record indexes of the data source, for example, when one data source satisfies a predetermined condition.

The output unit 44 outputs various information. Various types of information are, for example, search results described later. The output here is usually transmission to the terminal device 3, but display on a display, projection using a projector, printing by a printer, storage on a recording medium, other processing devices and other devices. The concept may include delivery of the processing result to a program or the like.

The result output unit 441 outputs a search result including one or more attribute values acquired by the search unit 432.

The storage unit 41, the index storage unit 411, and the record index storage unit 4113 are preferably non-volatile recording media, but can also be realized by a volatile recording medium.

The process of storing information in the storage unit 41 or the like does not matter. For example, the information may be stored in the storage unit 41 or the like via the recording medium, or the information transmitted via the communication line or the like may be stored in the storage unit 41 or the like. Alternatively, the information input via the input device may be stored in the storage unit 11 or the like.

The processing unit 43, the index generation unit 431, the search unit 432, the index update unit 433, the record index generation unit 4313, the source determination unit 4321, the record index determination unit 4322, and the search unit 4323 usually come from a processor, memory, or the like. It can be realized. The processing procedure of the processing unit 13 and the like is usually realized by software, and the software is recorded in a recording medium such as ROM. However, it may be realized by hardware (dedicated circuit). The processor is a CPU, MPU, GPU, or the like, and the type thereof does not matter.

The output unit 44 and the result output unit 441 are usually realized by wireless or wired communication means, but may be realized by broadcasting means.

Next, an operation example of the search system B will be described. First, an operation example of the search device 4 will be described with reference to the flowchart of FIG. In the flowchart of FIG. 18, the same steps as the flowchart of FIG. 4 will be omitted.

(Step S1801) The index generation unit 431 generates an index corresponding to the i-th data source. An example of the index generation process will be described with reference to the flowchart of FIG.

(Step S1802) The index update unit 433 instructs the index generation unit 431 to operate. As a result, the index generation unit 431 generates an index, associates it with the i-th data source, and accumulates the index. By such processing, the index corresponding to the i-th data source is updated. An example of the index generation process is the flowchart of FIG.

(Step S1803) The search unit 432 performs a search using the search conditions. An example of such a search process will be described with reference to the flowcharts of FIGS. 24 and 25.

In the flowchart of FIG. 18, it is preferable that the search conditions accepted in step S414 are associated with the data source to be searched and stored in the storage unit 41.

Further, in the flowchart of FIG. 18, the processing is terminated by the power off or the interrupt of the processing termination.

Next, an example of the index generation processing in steps S1801 and S1802 will be described with reference to the flowchart of FIG. In the flowchart of FIG. 19, the same steps as the flowchart of FIG. 5 will be omitted.

(Step S1901) The record index generation unit 4313 generates one or more record indexes. An example of such a record index generation process will be described with reference to the flowchart of FIG.

Next, an example of the record index generation process in step S1901 will be described with reference to the flowchart of FIG. In the flowchart of FIG. 20, the same steps as the flowchart of FIG. 4 will be omitted.

(Step S2001) The record index generation unit 4313 determines one or more key item sets corresponding to the record index to be generated. An example of such a key item set determination process will be described with reference to the flowchart of FIG. The key item set is one or more key items. The process of determining a key item set is usually a process of acquiring one or more key item identifiers.

(Step S2002) The record index generation unit 4313 substitutes 1 for the counter i.

(Step S2003) The record index generation unit 4313 determines whether or not the i-th key item set exists in the key item set acquired in step S2001. If the i-th key item set exists, the process proceeds to step S2004, and if it does not exist, the process returns to higher-level processing.

(Step S2004) The record index generation unit 4313 substitutes 1 for the counter j.

(Step S2005) The record index generation unit 4313 determines whether or not the jth record exists in the target data source. If the jth record exists, it goes to step S2006, and if it does not exist, it goes to step S2012.

(Step S2006) The record index generation unit 4313 acquires the record position information of the jth record.

(Step S2007) The record index generation unit 4313 is a key item which is one or more key item values of the j-th record and is a value (attribute value) of one or more key items of the i-th key item set. Get the value.

(Step S2008) The record index generation unit 4313 acquires the position information of the jth record index record.

(Step S2009) The record index generation unit 4313 constitutes the j-th record index record having record position information, one or more key item values, and record index record position information.

(Step S2010) The record index generation unit 4313 adds the j-th record index record configured in step S2009 to the i-th record index.

(Step S2011) The record index generation unit 4313 increments the counter j by 1. Return to step S2005.

(Step S2012) The record index generation unit 4313 acquires and accumulates the schema information of the i-th record index. The schema information has one or more key item identifiers (attribute identifiers) possessed by the i-th key item set.

(Step S2013) The record index generation unit 4313 stores the i-th record index in the record index storage unit 4113. Here, it is preferable that the record index generation unit 4313 also stores the schema information of the i-th record index in association with the i-th record index.

(Step S2014) The record index generation unit 4313 increments the counter i by 1. Return to step S2003.
In the flowchart of FIG. 20, when the secondary index does not exist, step S2008 is unnecessary, and in step S2009, the record index generation unit 4313 has record position information and one or more key item values. It constitutes the jth record index record.

Next, an example of the key item set determination process in step S2001 will be described with reference to the flowchart of FIG.

(Step S2101) The record index generation unit 4313 determines whether or not one or more key item sets specified by the user exist. If one or more key item sets specified by the user exist, the process goes to step S2102, and if they do not exist, the process goes to step S2103.

(Step S2102) The record index generation unit 4313 acquires one or more key item sets specified by the user and temporarily stores them in a buffer (not shown). Return to higher-level processing.

(Step S2103) The record index generation unit 4313 is a past search condition stored in the storage unit 41, and whether or not the number of past search conditions for the target data source is large enough to satisfy the condition. to decide. If the condition is satisfied, the process goes to step S2104, and if the condition is not satisfied, the process goes to step S2105. The condition is, for example, that the number of search conditions is equal to or greater than the threshold value or greater than the threshold value.

(Step S2104) The record index generation unit 4313 determines one or more key item sets by using the search condition of the storage unit 41. An example of such a search condition utilization process will be described with reference to the flowchart of FIG.

(Step S2105) The record index generation unit 4313 determines one or more key item sets by utilizing the distribution of attribute values for each attribute of the data source. Return to higher-level processing. An example of such distributed utilization processing will be described with reference to the flowchart of FIG.

In the flowchart of FIG. 21, the process of acquiring one or more key item sets specified by the user, the process of acquiring one or more key item sets using the past search conditions, and the distribution of attribute values are used. The process of acquiring one or more key item sets has been described. In FIG. 21, two or more of the above three processes may be performed to acquire one or more key item sets. In such a case, the same key item set is not acquired more than once.

Next, an example of the search condition utilization process in step S2104 will be described with reference to the flowchart of FIG.

(Step S2201) The record index generation unit 4313 substitutes 1 for the counter i.

(Step S2202) The record index generation unit 4313 determines whether or not the i-th attribute identifier exists. If the i-th attribute identifier exists in one or more attribute identifiers of the target data source, the process goes to step S2203, and if it does not exist, the process goes to step S2207. The one or more attribute identifiers of the data source may be key item identifiers.

(Step S2203) The record index generation unit 4313 acquires the frequency of occurrence of the i-th attribute identifier of the target data source in the search condition in the storage unit 41. The frequency of appearance may be the number of appearances or the rate of appearance.

(Step S2204) The record index generation unit 4313 determines whether or not the appearance frequency acquired in step S2203 satisfies the selection condition 1. If the selection condition 1 is satisfied, the process goes to step S2205, and if the selection condition 1 is not satisfied, the process goes to step S2206. The selection condition 1 is, for example, that the appearance frequency is equal to or higher than the threshold value or higher than the threshold value.

The selection condition 1 may be, for example, that the appearance frequency is within the upper N (N is a natural number of 1 or more) among the attribute identifiers of 2 or more. Under such a condition, the record index generation unit 4313 determines the attribute identifiers to be stored in the buffer (not shown) after acquiring the appearance frequencies of all the attribute identifiers.

(Step S2205) The record index generation unit 4313 stores the i-th attribute identifier in a buffer (not shown). The i-th attribute identifier is a set of key items to form a record index. The key item set here is one attribute identifier.

(Step S2206) The record index generation unit 4313 increments the counter i by 1. Return to step S2202.

(Step S2207) The record index generation unit 4313 substitutes 1 for the counter j.

(Step S2208) The record index generation unit 4313 determines whether or not a combination of two or more attribute identifiers at the j-th position exists. If the j-th or higher combination of attribute identifiers exists, the process goes to step S2209, and if it does not exist, the process returns to the higher-level processing.

(Step S2209) The record index generation unit 4313 acquires the co-occurrence frequency in the search condition of the combination of the j-th two or more attribute identifiers. The co-occurrence frequency is the number or ratio of search conditions including all two or more attribute identifiers.

(Step S2210) The record index generation unit 4313 determines whether or not the co-occurrence frequency acquired in step S2209 satisfies the selection condition 2. If the selection condition 2 is satisfied, the process goes to step S2211, and if the selection condition 2 is not satisfied, the process goes to step S2212. The selection condition 2 is, for example, that the co-occurrence frequency is equal to or greater than the threshold value or greater than the threshold value.

The selection condition 2 may be, for example, that the co-occurrence frequency is within the upper N (N is a natural number of 1 or more) in the set of 2 or more combinations of attribute identifiers. Under such conditions, the record index generation unit 4313 determines the combination of attribute identifiers to be stored in a buffer (not shown) after acquiring the co-occurrence frequency of all combinations of attribute identifiers.

(Step S2211) The record index generation unit 4313 stores a combination of two or more attribute identifiers at the j-th position in a buffer (not shown). The combination of the j-th or higher attribute identifiers is a set of target key items constituting the record index. The key item set here is two or more attribute identifiers.

(Step S2212) The record index generation unit 4313 increments the counter j by 1. Return to step S2208.

Next, an example of the distributed utilization process in step S2105 will be described with reference to the flowchart of FIG.

(Step S2301) The record index generation unit 4313 substitutes 1 for the counter i.

(Step S2302) The record index generation unit 4313 determines whether or not the i-th attribute identifier exists. If the i-th attribute identifier exists in one or more attribute identifiers of the target data source, the process goes to step S2303, and if it does not exist, the process goes to step S2308. The one or more attribute identifiers of the data source may be key item identifiers.

(Step S2303) The record index generation unit 4313 acquires the attribute value corresponding to the i-th attribute identifier of each record of the target data source.

(Step S2304) The record index generation unit 4313 calculates the variance of two or more attribute values acquired in step S2303.

(Step S2305) The record index generation unit 4313 determines whether or not the variance calculated in step S2304 satisfies the selection condition 3. If the selection condition 3 is satisfied, the process goes to step S2306, and if the selection condition 3 is not satisfied, the process goes to step S2307. The selection condition 3 is, for example, that the variance is equal to or greater than the threshold value or larger than the threshold value. Further, the selection condition 3 may be, for example, that the variance is within the upper N (N is a natural number of 1 or more).

(Step S2306) The record index generation unit 4313 stores the i-th attribute identifier in a buffer (not shown). The i-th attribute identifier is a set of key items to form a record index. The key item set here is one attribute identifier.

(Step S2307) The record index generation unit 4313 increments the counter i by 1. Return to step S2302.

(Step S2308) The record index generation unit 4313 substitutes 1 for the counter j.

(Step S2309) Whether or not the j-th attribute identifier combination within N (N is a natural number of 2 or more) exists in the set of attribute identifiers accumulated in step S2306 by the record index generation unit 4313. To judge. If the j-th attribute identifier combination exists, the process proceeds to step S2310, and if it does not exist, the process returns to the higher-level processing.

(Step S2310) The record index generation unit 4313 stores the j-th attribute identifier combination in a buffer (not shown). The combination of the j-th or higher attribute identifiers is a set of target key items constituting the record index. The key item set here is two or more attribute identifiers.

(Step S2311) The record index generation unit 4313 increments the counter j by 1. Return to step S2309.

Next, a first example of the search process in step S1803 will be described with reference to the flowchart of FIG. 24. In the flowchart of FIG. 24, the same steps as the flowchart of FIG. 11 will be omitted.

(Step S2401) The record index determining means 4322 determines the record index to be used for the search. An example of the determination process of such a record index will be described with reference to the flowchart of FIG.

In the flowchart of FIG. 26, in step S1108, the search unit 432 acquires the record position information by using the record index determined in step S2401.

Next, a second example of the search process in step S1803 will be described with reference to the flowchart of FIG. In the flowchart of FIG. 25, the same steps as those of the flowcharts of FIGS. 11 and 24 will be omitted.

(Step S2501) The search means 4323 searches the record index determined in step S2401, determines the record index record corresponding to the key item value of the search condition, and records the record position information of the record index record. To get.

(Step S2502) The search means 4323 determines whether or not an array index corresponding to the data source to be searched exists. If the array index exists, it goes to step S2503, and if it does not exist, it goes to step S2510.

(Step S2503) The search means 4323 substitutes 1 for the counter i.

(Step S2504) The search means 4323 determines whether or not the i-th attribute identifier included in the search condition (obtained by the search) exists. If the i-th attribute identifier exists, the process goes to step S2504, and if it does not exist, the process goes to step S2509.

(Step S2505) The search means 4323 acquires the attribute position information corresponding to the i-th attribute identifier from the array index.

(Step S2506) The search means 4323 acquires the attribute value specified by the attribute position information acquired in step S2505 from the data source in the records specified by the record position information acquired in step S2501.

(Step S2507) The search means 4323 temporarily stores the attribute value acquired in step S2506 in a buffer (not shown) in association with the i-th attribute identifier.

(Step S2508) The search means 4323 increments the counter i by 1. Return to step S2504.

(Step S2509) The search means 4323 configures a search result by using attribute values and the like temporarily stored in a buffer (not shown). Return to higher-level processing.

(Step S2510) The search means 4323 substitutes 1 for the counter i.

(Step S2511) The search means 4323 determines whether or not the i-th attribute identifier included in the search condition (obtained by the search) exists. If the i-th attribute identifier exists, the process goes to step S2512, and if it does not exist, the process goes to step S2509.

(Step S2512) The search means 4323 acquires the order of the attributes of the i-th attribute identifier in the data source. It should be noted that the order is the order in which the attribute values corresponding to the i-th attribute identifier are stored, and is the order of the attribute values in the record. The information in this order may exist in the data source or may exist in the storage unit 41.

(Step S2513) The search means 4323 acquires the attribute values existing in the positions in the order acquired in step S2512 among the records specified by the record position information acquired in step S2501.

(Step S2514) The search means 4323 temporarily stores the attribute value acquired in step S2513 in a buffer (not shown) in association with the i-th attribute identifier.

(Step S2515) The search means 4323 increments the counter i by 1. Return to step S2511.

Next, an example of the process of determining the record index in step S2401 will be described with reference to the flowchart of FIG.

(Step S2601) The record index determining means 4322 acquires one or more key item identifiers corresponding to the key item attribute values of the search condition. The search condition may have one or more key item identifiers.

(Step S2602) The record index determining means 4322 substitutes 1 for the counter i.

(Step S2603) The record index determining means 4322 determines whether or not the i-th record index exists. If the i-th record index exists, it goes to step S2604, and if it does not exist, it goes to step S2613.

(Step S2604) The record index determining means 4322 assigns 1 to the counter j.

(Step S2605) The record index determining means 4322 substitutes 0 (initial value) for the score for the i-th record index.

(Step S2606) The record index determining means 4322 refers to the schema information of the i-th record index, and the j-th key item identifier possessed by the schema information is included in the key item identifier acquired in step S2601. Determine if it is possible. If it is included, it goes to step S2607, and if it is not included, it goes to step S2611.

(Step S2607) The record index determining means 4322 adds 1 to the score for the i-th record index.

(Step S2608) The record index determining means 4322 determines whether or not it can be determined that all the key item identifiers acquired in step S2601 are included in the schema information of the i-th record index. If such a determination can be made, the process goes to step S2609, and if the determination cannot be made, the process goes to step S2610.

(Step S2609) The record index determining means 4322 determines the i-th record index as the record index used for the search. Return to higher-level processing. The determination is, for example, reading the i-th record index, acquiring the identifier of the i-th record index, and the like.

(Step S2610) The record index determining means 4322 increments the counter j by 1. Return to step S2606.

(Step S2611) The record index determining means 4322 associates the score of the i-th record index with the i-th record index and temporarily stores the score in a buffer (not shown).

(Step S2612) The record index determining means 4322 increments the counter i by 1. Return to step S2603.

(Step S2613) The record index determining means 4322 refers to a buffer (not shown) and determines the record index corresponding to the maximum score as the record index to be used for the search. Return to higher-level processing.

Hereinafter, a specific operation example of the search system B in the present embodiment will be described.

Now, it is assumed that one data source (X) shown in FIG. 27 is stored in the data source storage unit 111 of the data source management device 2. The structure of the data source of FIG. 27 is generally the same as the structure of the data source of FIG. 12, although the presence or absence of "Region" in the label record is different.
The label record is here the first line of the file. A label record is a set of attribute identifiers. Some attribute identifiers in the set of attribute identifiers can be key item identifiers. In FIG. 27, [No. ] Is a record ID, and its value is [1] [2] [3] or the like in FIG. 27. In addition, [No. ] Is the record position information of each record (here, the offset at the beginning of the record in the data source). "PID" is a user identifier. "Age" is the age of the user. The "Region" is the area where the user lives (here, the prefecture).

In such a situation, two specific examples will be described. Specific example 1 is an example of a process for generating two or more record indexes. Specific example 2 is an example of a process of selecting one record index from two or more record indexes and searching using the record index.

(Specific example 1)
It is assumed that the administrator of the search device 4 has input the index generation instruction to the terminal device 3. It is assumed that the index generation instruction includes information for specifying the data source (X) and information for specifying a set of one or more key items. Specifically, it is assumed that the index generation instruction includes "<data source> X <key item set> (Age, PID) <key item set> (Region, Age) <key item set>(PID)".

Next, the terminal device 3 receives the index generation instruction and transmits the index generation instruction to the search device 4.

Next, the reception unit 12 of the search device 4 receives the index generation instruction from the terminal device 3. Next, the index generation unit 131 generates a record index of the data source (X) as follows.

That is, the record index generation unit 4313 acquires the key item set "<key item set> (Age, PID) <key item set> (Region, Age) <key item set> (PID)" that the index generation instruction has. do.

Next, the record index generation unit 4313 uses "<data source> X" and "<key item set> (Age, PID)" to store the data source (X) in the data source management device. Access 2 and read the data source (X). Next, the record index generation unit 4313 selects a record index record including the attribute value "Age", the attribute value "PID", and the record position information of each record of the data source (X) in the data source (X). Get for each record. Next, the record index generation unit 4313 sorts the record index records using the two attribute values of "Age" and "PID" as keys, and constitutes a record index to be accumulated. Then, the record index generation unit 4313 stores the record index in the record index storage unit 4113.

In the record index, the records are sorted in ascending or descending order using the two attribute values of the first key "Age" and the second key "PID" as keys. Further, the record index generation unit 4313 stores the schema information (Age, PID) of the record index in the record index storage unit 4113 in association with the record index. Here, the schema information includes one or more attribute identifiers. Further, when the schema information has two or more attribute identifiers, the two or more attribute identifiers have an order. Further, the record index accumulated here is referred to as a record index (1) (see FIG. 28).

Next, the record index generation unit 4313 uses "<data source> X" and "<key item set> (Region, Age)" to store a data source (X). Access 2 and acquire a record index record including the attribute value "Region", the attribute value "Age", and the record position information of each record of the data source (X) for each record of the data source (X). Next, the record index generation unit 4313 sorts the record index records using the two attribute values of "Region" and "Age" as keys, and constitutes a record index to be accumulated. Then, the record index generation unit 4313 stores the record index in the record index storage unit 4113.

In the record index, the records are sorted in ascending or descending order using the two attribute values of the first key "Region" and the second key "Age" as keys. Further, the record index generation unit 4313 stores the schema information (Region, Age) of the record index in the record index storage unit 4113 in association with the record index. Further, the record index accumulated here is referred to as a record index (2) (see FIG. 28).

Next, the record index generation unit 4313 uses "<data source> X" and "<key item set> (PID)" in the data source management device 2 in which the data source (X) is stored. Access and acquire a record index record including the attribute value "PID" of each record of the data source (X) and the record position information for each record of the data source (X). Next, the record index generation unit 4313 sorts the record index records using the attribute of "PID" as a key, and constitutes a record index to be accumulated. Then, the record index generation unit 4313 stores the record index in the record index storage unit 4113.

Further, the record index generation unit 4313 stores the schema information (PID) of the record index in the record index storage unit 4113 in association with the record index. Further, the record index accumulated here is referred to as a record index (3) (see FIG. 28).

Through the above processing, the record indexes (1), (2), and (3) of FIG. 28 and the record index schema information 2801 are accumulated in the record index storage unit 4113.

(Specific example 2)
It is assumed that the user of the search device 4 inputs the search condition "Select PID, Region, Age, TestA, TestB where Region = Tokyo AND Age = 30 from data source (X)" to the terminal device 3. The information representing the where clause in the search conditions is 2802 in FIG. 28.

Then, the terminal device 3 accepts the search condition and transmits the search condition to the search device 4.

Next, the condition receiving unit 121 of the search device 4 receives the search condition from the terminal device 3.

Next, the record index determining means 4322 inspects the schema information (2801 in FIG. 28) of the record index using the "Region = Tokyo AND Age = 30" of the search condition, and sets it as the attribute identifier "Region". A record index (2) containing both "Age" is determined as the record index to be used for the search.

Next, the search means 4323 searches the record index (2) for the record index record 2803 that matches the where clause “Region = Tokyo AND Age = 30”. Then, the search means 4323 acquires the record position information (Record Pos) "241" possessed by the record 2803 from the record index (2).

Next, the search means 4323 reads the data source (X) and moves the file pointer to the position of the record corresponding to the record position information "241" (see 2804 in FIG. 28). Next, the search means 4323 acquires the attribute identifier "PID, Region, Age, TestA, TestB" included in the search condition to be searched from the record of 2804. Next, the search means 4323 refers to the schema information (not shown) of the data source (X), the order "1" of the attribute identifier "PID", the order "3" of the attribute identifier "Region", and the attribute identifier "Age". "2", the order "Y (Y is a natural number of 4 or more)" of the attribute identifier "TestA", and the order "Y + 1" of the attribute identifier "TestB" are acquired. Then, the search means 4323 sequentially scans the attribute values of the records specified by the record position information "241", acquires the attribute values indicated by the order for each attribute identifier, and associates the attribute values with the attribute identifiers. And accumulate. Then, the search means 4323 obtains the search result "<PID> 155 <Region> Tokyo <Age> 30 <TestA> 0.2 <TestB> 0.24".

Next, the result output unit 141 transmits the acquired search result to the user's terminal device 3.

Next, the terminal device 3 receives and outputs the search result. An output example of such a search result is 2805 of FIG. 28.

As described above, according to the present embodiment, by searching for information from a data source using two or more record indexes, information retrieval can be performed at high speed for each search condition having variations.

Further, according to the present embodiment, it is possible to generate two or more appropriate record indexes.

The processing in this embodiment may be realized by software. Then, this software may be distributed by software download or the like. Further, this software may be recorded on a recording medium such as a CD-ROM and disseminated. It should be noted that this also applies to other embodiments herein. The software that realizes the search device 4 in this embodiment is the following program. That is, this program is an index corresponding to a record of a data source including two or more records having a key item value corresponding to two or more key items and an attribute value corresponding to one or more attribute identifiers. A record index of two or more, which is a set of a set of record position information that specifies the position of a record containing one or more key item values corresponding to one or more key item combinations and the one or more key item values. A computer that can access a record index storage unit that stores two or more record indexes corresponding to different combinations of key items, a condition reception unit that accepts search conditions having key item values, and the above two or more units. From the record index, one record index corresponding to one or more key item combinations including the key item corresponding to the key item value of the search condition is selected, and the search condition is selected from the selected record index. A search unit that acquires the record position information paired with the key item value of the data source and acquires the attribute value in the record corresponding to the position specified by the record position information from the data source, and the search unit acquires the attribute value. This is a program for functioning as a result output unit that outputs a search result including the attribute value.

Further, FIG. 29 shows the appearance of a computer that executes the program described in the present specification to realize the search device 4 and the like in the various embodiments described above. The above-described embodiment can be realized by computer hardware and a computer program executed on the computer hardware. 29 is an overview view of the computer system 300, and FIG. 30 is a block diagram of the system 300.

In FIG. 29, the computer system 300 includes a computer 301 including a CD-ROM drive, a keyboard 302, a mouse 303, and a monitor 304.

In FIG. 30, in addition to the CD-ROM drive 3012, the computer 301 includes an MPU 3013, a bus 3014 connected to the CD-ROM drive 3012, the ROM 3015 for storing a program such as a boot-up program, and the MPU 3013. It includes a RAM 3016 that is connected and for temporarily storing instructions of an application program and providing a temporary storage space, and a hard disk 3017 for storing an application program, a system program, and data. Although not shown here, the computer 301 may further include a network card that provides a connection to the LAN.

The program for causing the computer system 300 to execute the functions of the search device 4 and the like according to the above-described embodiment may be stored in the CD-ROM 3101, inserted into the CD-ROM drive 3012, and further transferred to the hard disk 3017. Alternatively, the program may be transmitted to the computer 301 via a network (not shown) and stored in the hard disk 3017. The program is loaded into RAM 3016 at run time. The program may be loaded directly from the CD-ROM3101 or the network.

The program does not necessarily have to include an operating system (OS), a third-party program, or the like that causes the computer 301 to execute the functions of the search device 4 or the like according to the above-described embodiment. The program only needs to include a part of instructions that call the appropriate function (module) in a controlled manner and obtain the desired result. It is well known how the computer system 300 works, and detailed description thereof will be omitted.

In the above program, in the step of transmitting information and the step of receiving information, the processing performed by the hardware, for example, the processing performed by the modem or the interface card in the transmission step (only performed by the hardware). Processing) is not included.

Further, the number of computers that execute the above program may be singular or plural. That is, centralized processing may be performed, or distributed processing may be performed.

Further, it goes without saying that in each of the above embodiments, the two or more communication means existing in one device may be physically realized by one medium.

Further, in each of the above embodiments, each process may be realized by centralized processing by a single device, or may be realized by distributed processing by a plurality of devices.

It goes without saying that the present invention is not limited to the above embodiments, and various modifications can be made, and these are also included in the scope of the present invention.

As described above, the search device 4 according to the present invention has an effect that information retrieval can be performed at high speed for each search condition having variations, and is useful as a search server or the like.

1, 4 Search device 2 Data source management device 3 Terminal device 11, 41 Storage unit 12 Reception unit 13, 43 Processing unit 14, 44 Output unit 31 Terminal storage unit 32 Terminal reception unit 33 Terminal processing unit 34 Terminal transmission unit 35 Terminal reception Section 36 Terminal output section 111 Data source storage section 112, 411 Index storage section 121 Condition reception section 131, 431 Index generation section 132, 432 Search section 133, 433 Index update section 141, 441 Result output section 1121 Array index storage section 1122 Array Label index storage unit 1123, 4123 Record index storage unit 1125 Source index storage unit 1311 Array index generation unit 1312 Array label index generation unit 1313, 4313 Record index generation unit 1315 Source index generation unit 4321 Source determination means 4322 Record index determination means 4323 Search means

Claims (9)

An index corresponding to a record in a data source containing two or more records having a key item value corresponding to two or more key items and an attribute value corresponding to one or more attribute identifiers, and is an index corresponding to one or more key items. Two or more record indexes that are a set of record position information sets that specify the position of a record containing one or more key item values corresponding to a combination and the one or more key item values, each of which has a different key item. A record index storage unit that stores two or more record indexes corresponding to a combination,
Condition reception unit that accepts search conditions with key item values,
From the two or more record indexes, one record index corresponding to the combination of one or more key items including the key item corresponding to the key item value of the search condition is selected, and from the selected record index. , A search unit that acquires the record position information paired with the key item value of the search condition and acquires the attribute value in the record corresponding to the position specified by the record position information from the data source.
A search device including a result output unit that outputs a search result including the attribute value acquired by the search unit. An array index storage unit that stores an array index having attribute position information that specifies the position where the attribute value exists for each one or more records of two or more records and for each one or more attributes of each record. Further equipped,
The search condition further has an attribute identifier and
The search unit
The attribute position information corresponding to the attribute identifier of the search condition is acquired from the array index, and the attribute value corresponding to the attribute identifier of the search condition is obtained from the data source using the attribute position information. The search device according to claim 1 to be acquired. In each of the two or more record indexes, two or more sets of one or more key item values and record position information are sorted using a combination of one or more key item values as a key.
The search unit
If the key item at the beginning of the record index from the two or more record indexes matches the key item corresponding to the key item value of the search condition, the record index is selected and selected. The record position information paired with the key item value of the search condition is acquired from the record index, and the attribute value in the record corresponding to the position specified by the record position information is acquired from the data source. The search device according to claim 1 or claim 2. The search unit
If there are two or more record indexes whose first key item in the record index matches the key item corresponding to the key item value of the search condition, the next key item of the two or more record indexes is said. It is determined whether or not it matches the key item of the search condition, and one record index in which the most key items are included in the key item of the search condition is selected from the beginning of the record index, and the selected record is selected. -A billing that acquires the record position information paired with the key item value of the search condition from the index and acquires the attribute value in the record corresponding to the position specified by the record position information from the data source. Item 3. The search device according to item 3. With reference to the data source, two or more record indexes that are a set of key item values and record position information of two or more records of the data source, each corresponding to a combination of one or more different key items. The search device according to any one of claims 1 to 4, further comprising a record index generation unit that generates two or more record indexes and stores the record index storage unit. The record index generator is
Two or more sets of combinations of one or more key items satisfying the selection condition are determined, and the key item values and records of the two or more records corresponding to the combination of one or more key items of each of the two or more sets. The search device according to claim 5, wherein a record index that is a set with position information is generated and stored in the record index storage unit. The selection condition is a combination of one or more key items including a key item corresponding to an attribute value whose distribution of the attribute values contained in each of the two or more records of the data source is equal to or greater than the threshold value or is greater than the threshold value. The search device according to claim 6, wherein the search device is a combination of one or more key items including a key item corresponding to an attribute value included in one or more search conditions of the threshold value or more or more frequently than the threshold value. An index corresponding to a record in a data source containing two or more records having a key item value corresponding to two or more key items and an attribute value corresponding to one or more attribute identifiers, and is an index corresponding to one or more key items. Two or more record indexes that are a set of record position information sets that specify the position of a record containing one or more key item values corresponding to a combination and the one or more key item values, each of which has a different key item. It is a search method realized by a record index storage unit that stores two or more record indexes corresponding to a combination, a condition reception unit, a search unit, and a result output unit.
A condition reception step in which the condition reception unit accepts a search condition having a key item value,
The search unit selects one record index corresponding to a combination of one or more key items including the key item corresponding to the key item value of the search condition from the two or more record indexes, and the selection is made. The record position information paired with the key item value of the search condition is acquired from the obtained record index, and the attribute value in the record corresponding to the position specified by the record position information is acquired from the data source. Search steps and
A search method in which the result output unit includes a result output step that outputs a search result including the attribute value acquired in the search step. An index corresponding to a record in a data source containing two or more records having a key item value corresponding to two or more key items and an attribute value corresponding to one or more attribute identifiers, and is an index corresponding to one or more key items. Two or more record indexes that are a set of record position information sets that specify the position of a record containing one or more key item values corresponding to a combination and the one or more key item values, each of which has a different key item. A computer that has access to a record index store that stores two or more record indexes that correspond to a combination.
Condition reception unit that accepts search conditions with key item values,
From the two or more record indexes, one record index corresponding to the combination of one or more key items including the key item corresponding to the key item value of the search condition is selected, and from the selected record index. , A search unit that acquires the record position information paired with the key item value of the search condition and acquires the attribute value in the record corresponding to the position specified by the record position information from the data source.
A program for functioning as a result output unit that outputs a search result including the attribute value acquired by the search unit.

Images