System and method for indexing streams containing unstructured text data
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.
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.