Efficient lexical trending topic detection over streams of data using a modified sequitur algorithm
Embodiments are directed towards a Modified Sequitur algorithm (MSA) using pipelining and indexed arrays to identify trending topics within a plurality of documents having user generated content (UGC). The documents are parallelized and distributed across a plurality of network devices, which place at least some of the received documents into a buffer for which the MSA may then be applied to the documents within the buffer to identify n-grams or phrases within the documents' contents. The identified phrases are further analyzed to remove extraneous co-occurrences of phrases, and/or words based on a part of speech analysis. A weighting of the remaining phrases is used to identify trending topic phrases. Links to content in the plurality of UGC documents that is associated with the trending topic phrases may then be displayed to a client device.
1. A network device, comprising:
a transceiver to send and receive data over a network; and
a processor that is operative on the received data to perform actions, including:
receiving, for a given time window, a plurality of documents having User Generated Content (UGC);
partitioning the received plurality of documents into groups of documents having a determined maximum dissimilarity of content within each group, the dissimilarity being between the documents within a given group;
distributing the groups of documents across a plurality of other network devices including the network device, wherein each of the other network devices and the network device apply to at least some of the plurality of documents a modified sequitur algorithm to identify a respective plurality of common phrases, wherein the modifications to the modified sequitur algorithm include using an array instead of a doubly-linked list to represent text, marking a diagram using an indexed array to indicate which position in an original sequence of characters is a start or an end of a non-terminal rule, rather than physically replacing the diagram with a non-terminal rule, and encoding frequent phrases or rules as state machines wherein the state machines are used to chain the identified rules for the identified phrases;
receiving from each of the other network devices the respective plurality of common phrases to obtain identified plurality of common phrases;
selecting from the identified plurality of common phrases at least one phrase as a trending topic phrase for at least the given time window;
generating at least one link to at least one of the plurality of documents have content associated with the trending topic phrase; and
displaying the trending topic phrase and the at least one link.
2. The network device of claim 1 , wherein at least one of the network device or the other network devices apply the modified sequitur algorithm using pipelining to the respective received group of documents to identify a respective plurality of common phrases.
3. The network device of claim 1 , wherein applying to at least some of the plurality of documents the modified sequitur algorithm further comprises employing a buffering scheme to manage the at least some of the plurality of documents; and wherein a document within the buffer is replaced with another document from the at least some of the plurality of documents based on a statistical analysis of a number of phrases detected.
4. The network device of claim 1 , wherein selecting from the identified plurality of common phrases, further comprises:
removing any phrases from the identified plurality of common phrases that is determined to have an extraneous co-occurrence of terms within the phrase based on a t-test test analysis.
5. The network device of claim 1 , wherein selecting from the identified plurality of common phrases, further comprises:
removing from the identified plurality of common phrases at least one phrase based on a part of speech analysis.
6. The network device of claim 1 , wherein selecting from the identified plurality of common phrases, further comprises:
generating a plurality of time windows of different time durations, wherein the given time window is enclosed by each of the time windows within the plurality of time windows; and
selecting a phrase as a trending topic phrase if the phrase appears more frequently in the given time window than in each of the plurality of time windows.
7. A system, comprising:
a computer-readable storage device configured to receive a plurality of documents received in a continuous stream; and
a plurality of network devices, at least one of the plurality of network devices is configured to receive the plurality of documents and to partition the documents for distribution to each of the other network devices based on maximizing a determined dissimilarity of content for documents distributed to each given network device, the dissimilarity being between the documents within a given network device, each network device operable to receive at least some of the plurality of documents, and to perform actions, comprising:
applying to at least some of the plurality of documents a modified sequitur algorithm to identify a plurality of common phrases, wherein modifications to the modified sequitur algorithm include using an array instead of a doubly-linked list to represent text, marking a diagram using an indexed array to indicate which position in an original sequence of characters is a start or an end of a non-terminal rule, rather than physically replacing the diagram with a non-terminal rule, and encoding frequent phrases or rules as state machines wherein the state machines are used to chain the identified rules for the identified phrases;
selecting from the identified plurality of common phrases at least one phrase as a trending topic phrase for at least a given time window;
generating at least one link to at least one of the plurality of documents have content associated with the trending topic phrase; and
displaying the trending topic phrase and the at least one link.
8. The system of claim 7 , wherein at least one of the plurality of network devices is configured to perform the modified sequitur algorithm using pipelining.
9. The system of claim 7 , wherein applying to at least some of the plurality of documents the modified sequitur algorithm further comprises employing a buffering scheme to manage the at least some of the plurality of documents; and wherein a document within the buffer is replaced with another document from the at least some of the plurality of documents based on a statistical analysis of a number of phrases detected.
10. The system of claim 7 , wherein selecting from the identified plurality of common phrases, further comprises:
removing any phrases from the identified plurality of common phrases that is determined to have an extraneous co-occurrence of terms within the phrase based on a t-test test analysis.
11. The system of claim 7 , wherein selecting from the identified plurality of common phrases, further comprises:
removing from the identified plurality of common phrases at least one phrase based on a part of speech analysis.
12. The system of claim 7 , wherein selecting from the identified plurality of common phrases, further comprises:
generating a plurality of time windows of different time durations, wherein the given time window is enclosed by each of the time windows within the plurality of time windows; and
selecting a phrase as a trending topic phrase if the phrase appears more frequently in the given time window than in each of the plurality of time windows.
13. A non-transitory computer-readable storage medium having computer-executable instructions, the computer-executable instructions when installed onto a computing device enable the computing device to perform actions, comprising:
receiving a plurality of documents within a given time window from a stream of documents;
partitioning the received plurality of documents into groups of documents having a determined maximum dissimilarity of content within each group, the dissimilarity being between the documents within a given group;
distributing the groups of documents across a plurality of other network devices including the network device, wherein each of the other network devices and the network device apply to the plurality of documents a modified sequitur algorithm to identify a respective plurality of common phrases, wherein modifications to the modified sequitur algorithm include using an array instead of a doubly-linked list to represent text, marking a diagram using an indexed array to indicate which position in an original sequence of characters is a start or an end of a non-terminal rule, rather than physically replacing the diagram with a non-terminal rule, and encoding frequent phrases or rules as state machines wherein the state machines are used to chain the identified rules for the identified phrases;
receiving from each of the other network devices the respective plurality of common phrases to obtain identified plurality of common phrases;
selecting from the identified plurality of common phrases a plurality of phrases as trending topic phrases for at least the given time window;
generating at least one link to at least one of the plurality of documents have content associated with one of the trending topic phrases; and
displaying the trending topic phrases and the at least one link.
14. The non-transitory computer-readable storage medium of claim 13 , wherein applying to the plurality of documents the modified sequitur algorithm further comprises employing a buffering scheme to manage the plurality of documents; and wherein a document within the buffer is replaced with another document from the plurality of documents based on a statistical analysis of a number of phrases detected.
15. The non-transitory computer-readable storage medium of claim 13 , wherein selecting from the identified plurality of common phrases, further comprises:
removing any phrases from the identified plurality of common phrases that is determined to have an extraneous co-occurrence of terms within the phrase based on a t-test test analysis.
16. The non-transitory computer-readable storage medium of claim 13 , wherein selecting from the identified plurality of common phrases, further comprises:
removing from the identified plurality of common phrases at least one phrase based on a part of speech analysis.
17. The non-transitory computer-readable storage medium of claim 13 , wherein selecting from the identified plurality of common phrases, further comprises:
generating a plurality of time windows of different time durations, wherein the given time window is enclosed by each of the time windows within the plurality of time windows; and
selecting a phrase as a trending topic phrase if the phrase appears more frequently in the given time window than in each of the plurality of time windows.
18. The non-transitory computer-readable storage medium of claim 13 , wherein the computer-executable instructions perform actions, further comprising:
sorting each of the trending topic phrases based on a weighting scheme;
for each phrase in the trending topic phrases, performing a search;
extracting search result terms from a result of each search; and
deleting from the trending topic phrases, any phrase having a search result term in a corresponding search result that corresponds to at least one other search result term associated with a higher weighted trending topic phrase.
19. The non-transitory computer-readable storage medium of claim 13 , wherein the plurality of documents include user generated content and non-user generated content.