Dynamic indexing information retrieval or filtering system

• US 6,687,687 B1
• Filed: 07/26/2000
• Issued: 02/03/2004
• Est. Priority Date: 07/26/2000
• Status: Expired due to Fees

• Current Assignee: McAfee, Inc. (McAfee, LLC)
• Original Assignee: ZIX SCM, Inc.
• Inventors: Smadja, Frank
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Chen, Chongshan
• Application Number:
  US09/625,945
• Time in Patent Office: 1,287 Days
• Field of Search: 711/100, 711/170, 711/171, 711/172, 711/173, 707/2, 707/205, 707/200, 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1. 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.

2. The method of claim 1 further comprising the steps of:

providing a free block list containing information about free blocks; and

examining the free block list of memory space available for allocation to determine whether or not there is at least a free block that is able to accommodate a size of postings for a second word in the index file.

3. The method of claim 2 further comprising the step of increasing the size of the index file where it is determined there there is no free block in the free block list that is able to accommodate holding the postings for the second word in the index file.

4. The method of claim 2 further comprising the steps of:

where it is determined that there is at least one selected free block that is able to accommodate holding the postings for the second word in the index file, determining whether the selected free block is a closest sized block to the size of the postings for the second word in the index file; and

where it is determined that said selected free block is not a closest sized block to the size of the postings for the second word in the index file, partitioning the selected free block into successively decreasing sized levels of blocks to find a closest sized free block that is able to accommodate holding the postings for the second word in the index file; and

allocating the closest sized free block that is larger than the size of postings for the second word in the index file for holding the postings for the second word.

5. The method of claim 2 wherein said free block list contains information about free blocks in each successively decreasing level of free blocks and wherein said information identifies for each free block including whether or not the free block is free.

6. The method of claim 2 further comprising the steps of removing the selected free block from the free block list.

7. The method of claim 4 further comprising the steps of adding to the free block list buddy blocks that are not further partitioned into blocks, said buddy blocks being siblings of the block hat is further partitioned into blocks to find a closest sized free block to accommodate holding the postings for the second word in the index file.

8. 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.

9. The method of claim 8 wherein said searching step comprises the steps of;

where it is determined that there is no free block in the free block list that can accommodate holding the updated postings for the word, increasing the entire size of blocks allocated to the index file.

10. The method of claim 9 further comprising the steps of:

where it is determined that there is at least a free block that can accommodate holding the updated postings for the word in the index file, determining whether the second block is a closest sized block to the size of the updated postings for the word in the index file; and

where it is determined that the second block is not a closest sized block to the size of the updated postings for the word in the index file, partitioning the second block into successively decreasing sized levels of blocks to find a closest sized free block to the size of the updated postings for the word in the index file.

11. The method of claim 8 further comprising the steps of removing the second free block from the free block list.

12. The method of claim 11 further comprising the step of adding to the free block list the buddy blocks that are not further partitioned into blocks, said buddy blocks being siblings of the block that is further partitioned into blocks to find a closest sized free block to the size of the updated postings for the word in the index file.

13. The method of claim 8 further comprising the steps of adding the first block to the free block list.

14. The method of claim 13 wherein said adding step comprises the steps of:

determining whether a buddy block of the first block is free or not; and

where it is determined that a buddy block of the first block is free, combining the first block with the buddy block of the first block; and

adding the combined block to the free block list.

15. 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.

16. The method of claim 15 further comprising the steps of:

where it is determined that there is no free block within said selected one of the levels in the free block list, searching from the free block list a free block in a higher level than said selected one of the levels to accommodate holding the postings for the word.

17. The method of claim 15 further comprising the steps of:

where it is determined that there is no free block in higher successive levels in the free block list, increasing the size of the blocks.

18. The method of claim 15 further comprising the steps of:

where a free block is found in a higher level said selected one of the levels, partitioning the selected free block into successively decreasing sized levels of blocks to find a closest sized block that is able to accommodate holding the postings for the word; and

allocating the closest sized block to the postings for the word.