Social genome

• US 9,679,074 B2
• Filed: 11/09/2015
• Issued: 06/13/2017
• Est. Priority Date: 11/18/2010
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal Mart Stores Inc (WalMart Inc.)
• Inventors: Rajaraman, Anand, Mathihalli, Madhusudan, Lamba, Digvijay Singh, Siripurapu, Taraka Subrahmanya Prasad, Batra, Arvind, Garera, Nikesh
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US14/936,426
• Publication Number:
  US 20160132515A1
• Time in Patent Office: 582 Days
• Field of Search: 707769
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

Systems and methods are provided for processing a data stream in real time to identify connections between one or more social elements social elements and aggregating and storing the identified connections over a rolling time window. Social elements may be stored as nodes and connection between social elements may be stored as labeled connections between nodes. Other embodiments are provided.

Claims

1. A system comprising:

a computer memory;

processing nodes on computing hardware in a distributed architecture;

at least one semantic analysis engine operable on at least one processing node of the processing nodes to apply natural language processing techniques to characterize text from one or more social media posts in a data stream as social elements and connections, the social elements and the connections comprising attribute-value pairs, the social elements each representing a label, the connections representing relationships between the social elements, the social elements and the connections being stored as a multi-graph of nodes and edges, the nodes corresponding to the social elements, the edges corresponding to the connections, each of the nodes and each of the connections comprising one or more of the attribute-value pairs, the computer memory storing a set of slates, and each slate of the set of slates comprising a static data structure storing a subset of the attribute-value pairs;

a mapper at a first processing node of the processing nodes operable to publish a first post to update a first slate of the set of slates; and

an updater at a second processing node of the processing nodes operable to process the first post over a rolling time window to update the first slate of the set of slates and to update the multi-graph in real-time.

2. The system of claim 1, further comprising a filter operable to prevent storing of connections in the multi-graph that appear less than a threshold number of times in the data stream over a portion of the rolling time window.

3. The system of claim 1, further comprising an application program interface enabling querying of the nodes and the connections stored in the multi-graph.

4. The system of claim 1, wherein the at least one semantic analysis engine is further operable to characterize each of the nodes as one of:

(i) a person, (ii) a place, (iii) a thing, (iv) a medium, (v) an event, or (vi) a product.

5. The system of claim 1, wherein the at least one semantic analysis engine is further operable to characterize each of the connections as one or more of:

(i) an asymmetric relationship, (ii) an affinity rating, or (iii) an authority rating.

6. The system of claim 1, wherein the data stream is an unstructured data stream relative to connections embodied therein.

7. The system of claim 1, wherein the updater is further operable over the rolling time window to remove older connections of the connections from the multi-graph and add new connections in real time.

8. The system of claim 1, wherein:

the first processing node is different from the second processing node.

9. The system of claim 1, wherein:

the at least one semantic analysis engine is further operable to perform ambiguity resolution when characterizing the text from the one or more social media posts in the data stream as the social elements and the connections.

10. The system of claim 1, wherein:

each of the connections comprises a value component representing a connection level.

11. A method comprising:

performing natural language processing using at least one semantic analysis engine operable on at least one processing node of processing nodes to characterize text from one or more social media posts in a data stream as social elements and connections, the social elements and the connections comprising attribute-value pairs, the social elements each representing a label, the connections representing relationships between the social elements, the social elements and the connections being stored as a multi-graph of nodes and edges, the nodes corresponding to the social elements, the edges corresponding to the connections, each of the nodes and each of the connections comprising one or more of the attribute-value pairs, a computer memory storing a set of slates, and each slate of the set of slates comprising a static data structure storing a subset of the attribute-value pairs;

publishing, using a mapper operable on a first processing node of the processing nodes, a first post to update a first slate of the set of slates; and

processing, using an updater operable on a second processing node of the processing nodes, the first post over a rolling time window to update the first slate of the set of slates and to update the multi-graph in real-time.

12. The method of claim 11, further comprising filtering to prevent storing of connections in the multi-graph that appear less than a threshold number of times in the data stream over a portion of the rolling time window.

13. The method of claim 11, further comprising providing an application program interface enabling querying of the nodes and the connections stored in the multi-graph.

14. The method of claim 11, wherein performing natural language processing further comprises characterizing each of the nodes as one of:

(i) a person, (ii) a place, (iii) a thing, (iv) a medium, (v) an event, or (vi) a product.

15. The method of claim 11, wherein performing natural language processing further comprises characterizing each of the connections as one or more of:

(i) an asymmetric relationship, (ii) an affinity rating, or (iii) an authority rating.

16. The method of claim 11, wherein the data stream is an unstructured data stream relative to connections embodied therein.

17. The method of claim 11, wherein the updater is operable over the rolling time window to remove older connections of the connections from the multi-graph and add new connections in real time.

18. The method of claim 11, wherein:

the first processing node is different from the second processing node.

19. The method of claim 11, wherein:

the at least one semantic analysis engine is further operable to perform ambiguity resolution when characterizing the text from the one or more social media posts in the data stream as the social elements and the connections.

20. The method of claim 11, wherein:

each of the connections comprises a value component representing a connection level.