SYSTEM AND METHOD FOR MULTITHREADED TEXT INDEXING FOR NEXT GENERATION MULTI-CORE ARCHITECTURES

• US 20110252033A1
• Filed: 04/09/2010
• Published: 10/13/2011
• Est. Priority Date: 04/09/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: NARANG, ANKUR, Joseph, Doug, Agrawal, Prashant, Swaminathan, Karthik V.
• Granted Patent: US 8,661,037 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/325 Hash tables

Abstract

A system and method for indexing documents in a data storage system includes generating a single document hash table in storage memory for a single document using an index construction in a multithreaded and scalable configuration wherein multiple threads are each assigned work to reduce synchronization between threads. The single document hash table includes partitioning the single document and indexing strings of partitioned portions of the single document to create a minor hash table for each document sub-part; generating a document level hash table from the minor hash tables; updating a stream level hash table for the strings which maps every string to a global identifier; and generating a term reordered array from the document level hash table.

Claims

1. A method for indexing documents, comprising:

generating a single document hash table in storage memory for a single document using an index construction in a multithreaded and scalable configuration wherein multiple threads are each assigned work to reduce synchronization between threads wherein generating a single document hash table includes;

partitioning the single document a plurality of subparts and indexing strings of partitioned subparts of the single document to create a minor hash table for each subpart;

generating a document level hash table from the minor hash tables;

updating a stream level hash table for the strings which maps every string to a global identifier; and

generating a term reordered array from the document level hash table.

2. The method as recited in claim 1, wherein generating a single document hash table includes generating the single document hash table in a plurality of stages wherein each stage is performed by a separate core.

3. The method as recited in claim 1, wherein the minor hash tables are created using bloom filters.

4. The method as recited in claim 1, wherein the minor hash tables include a plurality of read/write count variables which are employed to synchronize simultaneous writing and reading operations from a same minor hash table.

5. The method as recited in claim 1, wherein updating a stream level hash table for the strings which maps every string to a global identifier includes mapping between strings appearing in the single document and the global identifier to form a document level identifier to global identifier map.

6. The method as recited in claim 1, wherein updating a stream level hash table includes:

fetching collision records of the stream level hash table; and

computing cumulative counts for tethis in the single document for string buffers using a reduce operation.

updating the stream level hash table using threads partitioned by a hash index.

7. The method as recited in claim 1, wherein generating a term reordered array from the document level hash table includes:

partitioning an integer document which is generated by storing document level identifiers for each string;

computing a cumulative sum matrix for terms for each partitions of the integer document and for all the threads,

generating the term reordered array for the single document where counts, global identifiers, frequency and position are formatted in the term reordered array.

8. The method as recited in claim 1, further comprising:

generating an interval hash table in storage memory for a plurality of single document hash tables; and

generating a global hash table in storage memory for a plurality of interval hash tables such that single documents or portions thereof can be searched by employing the global hash table wherein the interval hash table and the global hash table maintain the index construction for the threads.

9. The method as recited in claim 8, wherein generating an interval hash table includes:

merging a plurality of term reordered arrays into the interval hash table; and

generating a serialized interval hash table.

10. The method as recited in claim 9, wherein merging a plurality of term reordered arrays into the interval hash table includes:

computing a hash function over the global identifier of a term, wherein terms are partitioned across threads based upon their computed hash value.

11. The method as recited in claim 8, wherein generating a global hash table includes:

merging a plurality of interval hash tables by hashing term identifiers to populate a collision array such that the global hash table is accessible using the term identifiers to perform searches using the global hash table.

12. The method as recited in claim 1, wherein the threads are processed in a multi-level pipeline having intra-document pipelining and inter-document pipelining.

13. The method as recited in claim 1, further comprising mapping data-structures onto caches at different levels of a hierarchy of a memory system to provide cache conscious multi-threaded processing.

14. A computer readable storage medium comprising a computer readable program for indexing documents, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

generating a single document hash table in storage memory for a single document using an index construction in a multithreaded and scalable configuration wherein multiple threads are each assigned work to reduce synchronization between threads wherein generating a single document hash table includes;

partitioning the single document a plurality of subparts and indexing strings of partitioned subparts of the single document to create a minor hash table for each subpart;

generating a document level hash table from the minor hash tables;

updating a stream level hash table for the strings which maps every string to a global identifier; and

generating a term reordered array from the document level hash table.

15. The computer readable storage medium as recited in claim 14, wherein generating a single document hash table includes:

generating the single document hash table in a plurality of stages wherein each stage is performed by a separate core.

16. The computer readable storage medium as recited in claim 14, wherein the minor hash tables include a plurality of read/write count variables which are employed to synchronize simultaneous writing and reading operations from a same minor hash table.

17. The computer readable storage medium as recited in claim 14, wherein updating a stream level hash table for the strings which maps every string to a global identifier includes:

mapping between strings appearing in the single document and the global identifier to form a document level identifier to global identifier map.

18. The computer readable storage medium as recited in claim 14, wherein generating a term reordered array from the document level hash table includes:

partitioning an integer document which is generated by storing document level identifiers for each string;

computing a cumulative sum matrix for terms for each partition of the integer document and for all the threads; and

generating the term reordered array for the single document where counts, global identifiers, frequency and position are formatted in the term reordered array.

19. The computer readable storage medium as recited in claim 14, further comprising:

generating an interval hash table in storage memory for a plurality of single document hash tables; and

generating a global hash table in storage memory for a plurality of interval hash tables such that single documents or portions thereof can be searched by employing the global hash table wherein the interval hash table and the global hash table maintain the index construction for the threads.

20. The computer readable storage medium as recited in claim 19, wherein generating an interval hash table includes:

merging a plurality of term reordered arrays into the interval hash table; and

generating a serialized interval hash table.

21. The computer readable storage medium as recited in claim 20, wherein merging a plurality of term reordered arrays into the interval hash table includes:

computing a hash function over the global identifier of a term, wherein terms are partitioned across threads based upon their computed hash value.

22. The computer readable storage medium as recited in claim 14, wherein the threads are processed in a multi-level pipeline having intra-document pipelining and inter-document pipelining.

23. The computer readable storage medium as recited in claim 14, further comprising mapping data-structures onto caches at different levels of a hierarchy of a memory system to provide cache conscious multi-threaded processing.

24. A system for indexing documents in a data storage system, comprising:

a plurality of processing cores configured to process threads in accordance with an indexing construction program;

a hierarchical memory storage architecture configured to store hash tables and processing results; and

the indexing construction program configured to assign an index construction to the threads, the index construction providing a multithreaded and scalable configuration configured to generate a single document hash table for a single document wherein the threads are each assigned work to be performed by the plurality of processing cores to reduce synchronization between the threads wherein the single document is partitioned into subparts and strings of partitioned subparts of the single document are indexed to create a minor hash table for each subpart, the single document hash table including;

a document level hash table generated from the minor hash tables;

a stream level hash table updated for the strings which maps every string to a global identifier; and

a term reordered array from the document level hash table.

25. The system as recited in claim 24, wherein the indexing construction program is configured to generate an interval hash table in storage memory for a plurality of single document hash tables;

and generate a global hash table in storage memory for a plurality of interval hash tables such that single documents or portions thereof can be searched by employing the global hash table wherein the interval hash table and the global hash table maintain the index construction for the threads.