System and method for indexing streams containing unstructured text data

• US 9,262,511 B2
• Filed: 03/15/2013
• Issued: 02/16/2016
• Est. Priority Date: 07/30/2012
• Status: Active Grant

• Current Assignee: Mr. Yusefzadeh, Bahram Nmn
• Original Assignee: Red Lambda Incorporated
• Inventors: Leko, Adam, Bird, Robert, Whitlock, Matthew
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/832,767
• Publication Number:
  US 20140032568A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707/743, 707/741, 707/723, 707/736, 707/706, 707/707, 707/711, 707/693, 707/649, 707/636, 707/752, 707/E17.005, 707/E17.002, 707/E17.014, 707/E17.01, 707/E17.032, 715/246, 715/205, 715/234, 709/224, 709/241, 709/233, 704/251, 704/E15.003
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/322 Trees

Abstract

A system, method and computer readable medium for indexing streaming data. Data may be received from distributed devices connected via a network. Data elements may be stored and allocated to data blocks and events of the block stores. Non-text data may be converted into a text representation. The data may be split into terms, and term frequencies of each term within each of the event may be calculated. Block-level term frequency statics may be calculated based on the term frequencies. Tree index structures, such as the Y-tree index, may be generated based on the block-level term frequency data. The Y-tree index structures may use the terms as keys and pointers to the corresponding data blocks and block-level term frequency data. A search query may be performed over the tree index structures.

Claims

1. A method for indexing data, comprising the steps of:

receiving data-streams, wherein the data-streams comprise data-elements;

storing the data-elements of the received data-streams, wherein the stored data-elements are stored via one or more processors in block-stores;

allocating the stored data-elements to data-blocks of the block-stores, wherein the stored data-elements are allocated via the one or more processors to the data-blocks;

further allocating the block-allocated data-elements to events of the data-blocks, wherein each of the data-blocks comprise one or more events, wherein each of the events comprise the block-allocated data-elements of the corresponding data-block, wherein the block-allocated data-elements are allocated via the one or more processors to the events;

splitting the event-allocated data-elements into terms, wherein the event-allocated data-elements are split via the one or more processors into the terms;

calculating a term frequencies of each term in each of the events, wherein the term frequencies are calculated via the one or more processors;

calculating block-level term frequency data for the event-allocated data-elements stored in the corresponding data-block based on the term frequencies, wherein the block-level term frequency data is calculated via the one or more processors; and

,

generating tree index structures for the event-allocated data-elements based on the block-level term frequency data, wherein the tree index structures comprise Y-tree index structures, wherein the terms are used in the Y-tree index structures as keys, wherein the tree index structures are calculated via the one or more processors.

2. The method of claim 1, further comprising the step of:

generating pointers to the data-blocks, wherein the pointers comprise values stored in the Y-tree index structures that identify the corresponding data-blocks and the corresponding block-level term frequency data.

3. The method of claim 1, wherein the event-allocated data-elements comprise text data.

4. The method of claim 1, wherein the event-allocated data-elements comprise a text representation of non-text data, wherein at least one of the data-streams comprises non-text data that is converted into the text representation.

5. The method of claim 1, wherein multiple writers to the data-blocks have an independent tree structure.

6. The method of claim 1, further comprising the step of:

performing a search query of the tree index structures.

7. The method of claim 6, wherein the search query for the data-elements is performed over all of the tree index structures.

8. The method of claim 7, further comprising the step of:

extracting term statistics from query text of the search query.

9. The method of claim 8, further comprising the step of:

generating a list of candidate data-blocks that satisfy the search query based on the Y-tree index structure.

10. The method of claim 9, further comprising the step of:

evaluating the search query against each of the data-blocks to generate a list of matching records.

11. The method of claim 1, further comprising the step of:

performing a term-proximity search query of the tree index structures.

12. The method of claim 11, wherein the term-proximity search query is a wildcard suffix matches search query, wherein a minimum key in the Y-tree index structures satisfies a pattern requirement, and wherein the keys are iterated until reaching a key that is different from the pattern requirement.

13. The method of claim 11, wherein the term-proximity search query is a fuzzy matches search query.

14. The method of claim 11, wherein the term-proximity search query is based on a Soundex algorithm.

15. The method of claim 11, further comprising the step of:

maintaining a list of the terms that are present in a master Y-tree index structure.

16. The method of claim 1, further comprising the step of:

compressing individual pages within the Y-tree index structure.

17. The method of claim 16, wherein the individual pages within the Y-tree index are compressed by compression algorithms.

18. The method of claim 16, wherein the individual pages within the Y-tree index are compressed by storing data-block in the Y-tree index structures via gap-compressed encodings.

19. The method of claim 1, further comprising the step of:

multicasting search queries to a set of dedicated search nodes that perform searches.

20. The method of claim 19, further comprising the step of:

combining query results that are gathered from the search nodes, wherein separate Y-tree index structures are utilized per stream writers.

21. The method of claim 19, further comprising the step of:

generating an index data page cache for the search nodes.

22. The method of claim 19, further comprising the step of:

adjusting a pre-determined amount of time that an index data page resides in cache before being refreshed with a new page.

23. The method of claim 1, wherein the data-streams are received from a plurality of distributed devices, wherein the plurality of distributed devices are connected via a network.

24. The method of claim 1, wherein the block-stores are stored on a plurality of distributed devices, wherein the plurality of distributed devices are connected via a network.

25. The method of claim 1, further comprising the step of:

assigning a block-identifier to data-blocks of the block-stores, wherein the block-identifier is globally unique, wherein each of the data-blocks are read and written as a single unit, and wherein the data-blocks of a single data-stream are logically grouped.

26. A system for indexing data, comprising:

block-stores adapted to store data-elements of data-streams;

data-blocks of the block-stores, the stored data-elements being allocated via one or more processors to the data-blocks;

events of the data-blocks, the block-allocated data-elements being further allocated via the one or more processors to the events of the data-blocks, each of the data-blocks comprising one or more events, each of the events comprising the block-allocated data-elements of a corresponding data-block;

terms generated via the one or more processors by splitting the event-allocated data-elements;

term frequencies calculated via the one or more processors based on the frequency of each term in each of the events;

block-level term frequency data calculated via the one or more processors for the event-allocated data-elements that are stored in a corresponding data-block, the block-level term frequency data being based on the term frequencies; and

,

tree index structures generated via the one or more processors for the event-allocated data-elements based on the block-level term frequency data, the tree index structures comprising Y-tree index structures, the terms being used in the Y-tree index structures as keys.

27. The system of claim 26, wherein the block-stores are stored on a plurality of distributed devices, wherein the plurality of distributed devices are connected via a network.

28. The system of claim 26, wherein the data-streams are received from a plurality of distributed devices, wherein the plurality of distributed devices are connected via a network.

29. A non-transitory computer readable medium having computer readable instructions stored thereon for execution by a processor, wherein the instructions on the non-transitory computer readable medium are adapted to enable a computing device to:

receive data-streams, wherein the data-streams comprise data-elements;

store the data-elements of the received data-streams, wherein the stored data-elements are stored in block-stores;

allocate the stored data-elements to data-blocks of the block-stores;

further allocate the block-allocated data-elements to events of the data-blocks, wherein each of the data-blocks comprise one or more events, wherein each of the events comprise the block-allocated data-elements of the corresponding data-block;

split the event-allocated data-elements into terms;

calculate term frequencies of each term in each of the events;

calculate block-level term frequency data for the event-allocated data-elements stored in the corresponding data-block based on the term frequencies; and

,

generate tree index structures for the event-allocated data-elements based on the block-level term frequency data, wherein the tree index structures comprise Y-tree index structures, wherein the terms are used in the Y-tree index structures as keys.