Dynamic indexing information retrieval or filtering system
AssigneeZIX SCM, Inc.
InventorFrank Smadja
Life of this patent
Estimating the term…
Abstract
A system and method for allocating the blocks of index file to the postings for words found in documents of a database is disclosed. The index file is provided with blocks that is partitioned into successively decreasing levels of blocks in size. The blocks in each successive level have same size and the sum of sizes of blocks in each successive level equals the size of initial block. An information retrieval interface allocates to the postings for a word a free block in the level the size of which is closest to the size of postings for the word in the index file.
Claims18
A method for allocating memory space for an index file of an information retrieval or filtering system to hold postings of words found in documents of a database, said method comprising steps of:
- providing the index file with a predetermined sized initial block in the memory space;
- partitioning the initial block into successively decreasing sized levels of blocks, wherein for each successive level said blocks are of a same size and a sum of the sizes of the blocks in each successive level equals the size of initial block;
- and
- allocating a given free block for holding postings of a first word in a selected one of the levels having blocks of a size that most closely matches a size of the postings of the first word in the index file, the size of said given free block being able to accommodate holding postings of the first word in the index file.
A method for updating postings for words in an index file of an information retrieval or filtering system holding the postings for the words found in documents of a database, said method comprising steps of:
- allocating free blocks of memory space available for holding the postings for the words found in the index file wherein the blocks are partitioned into successively decreasing levels of blocks in size, for each successive level the blocks are of a same size and a sum of the sizes of the blocks in one level equals a sum of the sizes of the blocks in another level, said allocating occurring in a selected one of the levels having blocks of a size that most closely matches a size of the postings of the first word in the index file;
- updating postings for a word in a first block for holding additional postings for the word founded in added documents of the database;
- searching from a free block list a second block that is free to accommodate holding the updated postings for the word, said free block list having information about free blocks in each successively decreasing level of free blocks;
- and
- moving the postings for the word from the first block to the second block.
A method for allocating an index file of an information retrieval or filtering system holding postings for words found in documents of a database, said method comprising steps of:
- providing the index file with blocks wherein said blocks are partitioned into successively decreasing sized levels of blocks, said blocks in each successive level being of a same size, a sum of the sizes of the blocks in one level being equal to a sum of the sizes of the blocks in another level;
- computing a size of postings for a word in the index file and determining a selected one of the levels that has blocks of a size that mostly matches the size of the postings for the word in the index file;
- searching a free block within the first level to accommodate holding the postings for the word, said free block list containing information about free blocks of said selected one of the levels;
- and
- allocating the selected free block in said selected one of the levels to the postings for the word.
Dependencies are inferred from the claim text.