Method for creating an index and method for searching an index

• US 6,678,687 B2
• Filed: 10/10/2001
• Issued: 01/13/2004
• Est. Priority Date: 01/23/1998
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Watanabe, Yoshiki, Hayata, Hiroshi
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): To, Baoquoc N
• Application Number:
  US09/972,865
• Publication Number:
  US 20020059281A1
• Time in Patent Office: 825 Days
• Field of Search: 707/2, 707/3, 707/6, 707/102, 707/107, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A B+ tree index for a full-text search through documents is created fast and fast searches are implemented using the index. A B+ tree index to register sets of words serving as keys and documents containing the words is constituted of a plurality of B+ tree subindexes; a document identification number id and a word identification number iw are assigned to a document and a word to uniquely identify them; as a function to apply to documents, a hash function Hd is provided that maps a document identification number to a value indicating the position of horizontal direction of a two-dimensional array, and as a function to apply to words, a hash function Hw is provided that maps a word identification number to a value indicating the position of vertical direction of the two-dimensional array; and the occurrence of a word in a document is registered in a corresponding subindex B+ tree (Hd(id), Hw(iw)) by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively. The index is searched using a value with a word identification number as a key and a document identification number concatenated.

Claims

1. A method for creating an index in which keys are associated to search for a value from a specified key, comprising:

constituting the index to register sets of keys and values by providing a B+ tree index that is split to a plurality of subindexes; and

storing each of the subindexes in a two-dimensional array position referenced in a first dimension by a value determined by applying a predetermined function to a value to be registered and referenced in a second dimension by a value determined by applying a predetermined function to a key;

wherein a word is used as the key and one document containing the word is used as the value;

wherein a document identification number and a word identification number are assigned to the document and the word, respectively, to uniquely identify them;

wherein, as the function to apply to documents, a hash function is provided that maps the document identification number to the value indicating a position of one dimension of the two-dimensional array, and as the function to apply to words, a hash function is provided that maps a word identification number to a value indicating a position of another dimension of the two-dimensional array; and

wherein an occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions.

2. A method for creating an index according to claim 1, wherein B+ tree structure is used as the subindexes.

3. A method for creating an index according to claim 1, wherein, when the occurrences of words in a plurality of documents are registered as a single unit, groups are formed by the values obtained by applying a hash function to the document identification numbers of the documents so that the occurrences of words are registered on a group basis.

4. A method for creating an index according to claim 1, wherein a word identification number is assigned to a word to uniquely identify it;

wherein, as a function to apply to the occurrence of a word, a hash function is provided that maps the occurrence count of the word in a document to a value indicating the position of one direction of a two-dimensional array;

wherein, as a function to apply to a word, a hash function is provided that maps a word identification number to a value indicating the position of another direction of the two-dimensional array; and

wherein the occurrence of a word in a document is stored in a corresponding subindex by using values obtained by applying the hash functions to the occurrence count of the word and the word identification number, respectively.

5. A method for creating an index according to claim 4, wherein, when the occurrences of words in a plurality of documents are registered as a single unit, groups are formed by the values obtained by applying a hash function to the occurrence count of the words so that the occurrences of words are registered on a group basis.

6. A method for creating an index according to claim 1, wherein a word identification number is assigned to a word to uniquely identify it;

wherein, as a function to apply to the occurrence of a word, a hash function is provided that maps the occurrence frequency of the word in a document to a value indicating the position of one direction of a two dimensional array;

wherein, as a function to apply to a word, a hash function is provided that maps a word identification number to a value indicating the position of another direction of the two-dimensional array; and

wherein the occurrence of a word in a document is stored in a corresponding subindex by using values obtained by applying the hash functions to the occurrence frequency of the word and the word identification number, respectively.

7. A method for creating an index according to claim 6, wherein, when the occurrences of words in a plurality of documents are registered as a single unit, groups are formed by the values obtained by applying a hash function to the occurrence frequency of the words so that the occurrences of words are registered on a group basis.

8. A method for creating an index according to claim 3, wherein, when the occurrences of all words in documents collected into one group are registered, the occurrences of words are grouped by the values obtained by applying a hash function to the words so that they are registered on a group basis.

9. A method for creating an index according to claim 8, wherein a page cache capable of storing at least one subindex provided in the main storage is used.

10. A method for searching an index which obtains a corresponding document name from a word serving as a key by using an index having a B+ tree index that is split into a plurality of subindexes with document names associated with words contained in the documents,

wherein document identification numbers and word identification numbers are assigned to document names and words, respectively, to uniquely identify them, and

wherein a value with a document identification number concatenated with a word identification number is used as the key;

wherein, as a function to apply to documents, a hash function is provided that maps the document identification number to a value indicating a position of one dimension of a two-dimensional array, and as a function to apply to words, a hash function is provided that maps the word identification number to a value indicating a position of another dimension of the two-dimensional array; and

wherein the occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively.

11. A method for searching an index which constitutes an index with document names associated with words contained in the documents by providing a B+ tree index that is split to a plurality of subindexes, assigns document identification numbers and word identification numbers to document names and words, respectively, to uniquely identify them, and obtains a corresponding document name from a word serving as a key by using an index registered in a subindex in a two-dimensional array position referenced by a value determined by applying a hash function to a document identification number and a value determined by applying a hash function to a word identification number,

wherein a search by a plurality of words is performed in such a way that groups are formed by the values obtained by applying a hash function to the identification numbers of the words and the subindexes are searched on a group basis;

wherein a word is used as a key and one document containing the word is used as a value;

wherein a document identification number and a word identification number are assigned to a document and a word, respectively, to uniquely identify them;

wherein, as a function to apply to documents, a hash function is provided that maps a document identification number to a value indicating the position of one direction of a two-dimensional array, and as a function to apply to words, a hash function is provided that maps a word identification number to a value indicating the position of another direction of the two-dimensional array; and

wherein an occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively.

12. A method for searching an index which constitutes an index with document names associated with words contained in the documents by providing a B+ tree index that is split to a plurality of subindexes, assigns document identification numbers and word identification numbers to document names and words, respectively, to uniquely identify them, and obtains a corresponding document name from a word serving as a key by using an index registered in a subindex in a two-dimensional array position referenced by a value determined by applying a hash function to a document identification number and a value determined by applying a hash function to a word identification number,

wherein an AND or OR search of a plurality of words is performed in such a way that subindexes for documents grouped by the values obtained by applying a hash function to document identification numbers are searched for the occurrence of each word and the AND or OR operation on the search results is performed;

wherein a word is used as the key and one document containing the word is used as the value;

wherein a document identification number and a word identification number are assigned to a document and a word, respectively, to uniquely identify them;

wherein, as a function to apply to documents, a hash function is provided that maps a document identification number to a value indicating the position of one direction of a two-dimensional array, and as a function to apply to words, a hash function is provided that maps a word identification number to a value indicating the position of another direction of the two-dimensional array; and

wherein an occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively.

13. An apparatus for creating an index with keys and values associated, to search for a value from a specified key, comprising:

index storing unit that stores an index constituted by providing a B+ tree index that is split to a plurality of subindexes;

first function application unit that calculates a first value by applying a predetermined function to a value to be registered;

second function application unit that calculates a second value by applying a predetermined function to a key value; and

storing unit that stores a set of said key and said value to be registered in a subindex within said index storing unit in a two-dimensional array position determined in accordance with said first value and second value calculated;

wherein a word is used as the key and one document containing the word is used as the value to be registered;

wherein a document identification number and a word identification number are assigned to a document and a word, respectively, to uniquely identify them;

wherein, as a function to apply to documents, a hash function is provided that maps the document identification number to a value indicating a position of one dimension of a two-dimensional array, and as a function to apply to words, a hash function is provided that maps the word identification number to a value indicating position of another dimension of the two-dimensional array; and

wherein an occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively.

14. A storage medium storing a program for having a computer create an index with keys and values associated, to search for a value from a specified key, in a format readable from the computer for execution,

wherein said program constitutes an index to register sets of keys and values by providing a B+ tree index that is split into a plurality of subindexes and stores the subindexes in a two-dimensional array position referenced in a first dimension by values determined by applying a predetermined function to the values to be registered and referenced in a second dimension by values determined by applying a predetermined function to the keys;

wherein a word is used as a key and one document containing the word is used as a value;

wherein a document identification number and a word identification number are assigned to the document and the word, respectively, to uniquely identify them;

wherein, as a function to apply to documents, a hash function is provided that maps the document identification number to a value indicating a position of one dimension of the two-dimensional array, and as a function to apply to words, a hash function is provided that maps the word identification number to a value indicating a position of another dimension of the two-dimensional array; and

wherein a occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively.

15. An index of a database in which sets of keys and values are registered,

wherein said index is constituted by providing a B+ tree index that is split to a plurality of subindexes, and

each of said subindexes is stored in a two-dimensional storage medium location determined in a first dimension by a first value obtained by applying a predetermined function to a value and determined in a second dimension by a second value obtained by applying a predetermined function to a key;

wherein a word is used as the key and one document containing the word is used as the value;

wherein a document identification number and a word identification number are assigned to each document and word, respectively, to uniquely identify them;

wherein, as a function to apply to documents, a hash function is provided that maps the document identification number to a value indicating a position of one dimension of a two-dimensional array, and as a function to apply to words, a hash function is provided that maps the word identification number to a value indicating a position of another dimension of the two-dimensional array; and

wherein an occurrence of a word in a document is registered in a corresponding subindex by using values obtained by applying the hash functions to the document identification number and the word identification number, respectively.