Method and system for efficiently searching an encoded vector index

• US 6,285,994 B1
• Filed: 05/25/1999
• Issued: 09/04/2001
• Est. Priority Date: 05/25/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bui, Thuan Quang, Egan, Randy Lynn, Kathmann, Kevin James
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): LE, DEBBIE M
• Application Number:
  US09/318,691
• Time in Patent Office: 833 Days
• Field of Search: 707/2, 707/100, 707/101, 707/3-5, 707/1
• US Class Current: 707/745
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Method and system aspects for efficiently searching an encoded vector index are provided. The aspects include the translation of a search query into a candidate bitmap, and the mapping of data from the candidate bitmap into a search result bitmap according to entry values in the encoded vector index. Further, the translation includes the setting of a bit in the candidate bitmap for each entry in a symbol table that corresponds to candidate of the search query. Also included in the mapping is the identification of a bit value in the candidate bitmap pointed to by an entry in an encoded vector.

Claims

1. A method for efficiently searching an encoded vector index, the method comprising:

translating a search query into a candidate bitmap; and

mapping data from the candidate bitmap into a search result bitmap according to entry values in the encoded vector index.

2. The method of claim 1 wherein the step of translating further comprises setting a bit in the candidate bitmap for each entry in a symbol table that corresponds to candidate of the search query.

3. The method of claim 2 wherein the number of entries in the candidate bitmap equals the number of entries in the symbol table.

4. The method of claim 1 wherein the step of mapping further comprises identifying a bit value in the candidate bitmap pointed to by an entry in an encoded vector.

5. The method of claim 4 further comprising entering the identified bit value for each entry of the encoded vector into the search result bitmap.

6. The method of claim 5 wherein the encoded vector and the search result bitmap have an equivalent number of entries.

7. A system for improving encoded vector index searching, the system comprising:

at least one computer processor; and

at least one data storage device coupled to the at least one computer processor for storing one or more relational databases that utilize encoded vector indexing and for storing relational database managerial processing instructions, including search query instructions, wherein the at least one computer processor processes the search query instructions by translating a search query into a candidate bitmap, and mapping data from the candidate bitmap into a search result bitmap according to entry values in an encoded vector index.

8. The system of claim 7 wherein the at least one computer processor performs translating by setting a bit in the candidate bitmap for each entry in a symbol table stored in the at least one storage device that corresponds to candidate of the search query.

9. The system of claim 8 wherein the number of entries in the candidate bitmap equals the number of entries in the symbol table.

10. The system of claim 7 wherein the at least one computer processor performs mapping by identifying a bit value in the candidate bitmap pointed to by an entry in an encoded vector.

11. The system of claim 10 wherein the identified bit value for each entry of the encoded vector is entered into the search result bitmap.

12. The system of claim 11 wherein the encoded vector index and the search result bitmap have an equivalent number of entries.

13. A method to improve encoded vector index searching, the method comprising:

generating a candidate bitmap for a search query;

identifying a bit value from the candidate bitmap corresponding to each entry in an encoded vector; and

generating a temporary bitmap from the identified bit values as a search result for the search query.

14. The method of claim 13 wherein the step of generating further comprises utilizing a symbol table as a basis for the candidate bitmap.

15. The method of claim 14 wherein the number of entries in the candidate bitmap match the number of entries in the symbol table with each entry in the candidate bitmap corresponding to an entry in the symbol table.

16. The method of claim 14 further comprising setting a bit for an entry in the candidate bitmap for each symbol entry that is a candidate code based on the search query.

17. The method of claim 16 further comprising performing parallel processes to set the bits in the candidate bitmap.

18. A computer readable medium containing program instructions for efficiently searching an encoded vector index comprising:

translating a search query into a candidate bitmap; and

mapping data from the candidate bitmap into a search result bitmap according to entry values in the encoded vector index.

19. The computer readable medium of claim 18 wherein the program instruction for translating further comprises setting a bit in the candidate bitmap for each entry in a symbol table that corresponds to candidate of the search query.

20. The computer readable medium of claim 19 wherein the number of entries in the candidate bitmap equals the number of entries in the symbol table.

21. The computer readable medium of claim 18 wherein the program instructions for mapping further comprises identifying a bit value in the candidate bitmap pointed to by an entry in an encoded vector.

22. The computer readable medium of claim 21 further comprising program instructions for entering the identified bit value for each entry of the encoded vector into the search result bitmap.

23. The computer readable medium of claim 22 wherein the encoded vector and the search result bitmap have an equivalent number of entries.