GRAPH-BASED RECOMMENDATIONS SERVICE SYSTEMS AND METHODS

• US 20150149484A1
• Filed: 11/22/2013
• Published: 05/28/2015
• Est. Priority Date: 11/22/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: KELLEY, Lawrence
• Granted Patent: US 9,760,609 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06Q 30/0278 Product appraisal
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

A recommendation engine may provide recommendations by obtaining a compact graph representation representing a recommendations graph comprising of nodes and weighted edges. Each node is associated with type metadata indicating that it represents a recommendable item or a non-recommendable item. Each weighted edge is associated with edge-weight metadata. The compact graph representation can be stored in primary memory. When servicing a request for an item recommendation, the recommendation engine selects an entry node based at least in part on context metadata associated with the request, and traverses only a highly-weighted portion of the compact graph representation that is proximate to an entry node to select paths leading respectively to potential recommendation nodes. Each path is scored based on the edge-weight metadata of all segments, and at least one recommendation node is selected based at least in part on the path scores.

Claims

1. A recommendations-device-implemented method for providing recommendations, the method comprising:

obtaining, by said recommendations device, a compact graph representation representing a recommendations graph comprising a multiplicity of nodes and a multiplicity of weighted edges, each node of said multiplicity of nodes being associated with type metadata indicating that each node represents one of a multiplicity of recommendable items or one of a multiplicity of non-recommendable items, each weighted edge of said multiplicity of weighted edges joining a source node of said multiplicity of nodes to a target node of said multiplicity of nodes, each weighted edge being associated with edge-weight metadata;

storing said compact graph representation in a primary memory of said recommendations-server device;

receiving, by said recommendations device, a multiplicity of recommendation requests, each request requesting a recommendation of at least one recommendable item for a remote user based at least in part on request-context metadata associated with each request;

processing, by said recommendations device, each request of said multiplicity of recommendation requests, including performing at least the following steps for each request;

selecting an entry node of said multiplicity of nodes based at least in part on said request-context metadata;

traversing, via said compact graph representation in said primary memory, only a highly-weighted portion of said recommendations directed-graph that is proximate to said entry node to select a multiplicity of paths leading respectively to a multiplicity of potential recommendation nodes, each of which represents a recommendable item of said multiplicity of recommendable items, said multiplicity of paths being selected based at least in part on weighted-edge-weights of weighted edges making up a given path;

computing a multiplicity of cumulative node scores corresponding respectively to said multiplicity of potential recommendation nodes, including computing each cumulative node score based at least in part on said weighted-edge-weights of each path of said multiplicity of paths that lead to a given node;

selecting a recommendation node based at least in part on said multiplicity of cumulative node scores; and

providing in response to each request an identifier identifying a recommendable item represented by said selected recommendation node.

2. The method of claim 1, wherein obtaining said compact graph representation comprises:

initializing a nodes referenceable data-structure and an edges referenceable data-structure;

iterating over each node of said multiplicity of nodes, including performing at least the following steps for each node;

determining edge data comprising an edge-count of zero or more outbound weighted edges and for each of said zero or more outbound weighted edges, an edge-weight-related value and a target-node reference referencing data within said nodes referenceable data-structure;

inserting said edge data into said edges referenceable data-structure;

determining node data comprising an item-type reference referencing an item-type associated with each node and an edges-data reference referencing said edge data within said edges referenceable data-structure; and

inserting said node data into said nodes referenceable data-structure.

3. The method of claim 2, wherein for each node that represents a recommendable item, said node data further comprises a recommendable-item-type reference referencing a species of recommendable-item.

4. The method of claim 3, wherein iterating over each node includes further performing at least the following steps for each node that represents a recommendable item:

inserting, into a species-map referenceable data-structure corresponding to said species of recommendable-item, a node-data reference to said node data within said nodes referenceable data-structure.

5. The method of claim 4, wherein for each node that represents a recommendable item:

said node data further comprises a reference to said node-data reference within said species-map referenceable data-structure.

6. The method of claim 1, wherein traversing only a highly-weighted portion of said recommendations directed-graph that is proximate to said entry node comprises:

determining a batch count (“

N”

) and a depth limit; and

from any given node;

ordering outbound weighted edges according to said edge-weight metadata associated therewith; and

following only a top “

N”

outbound weighted edges, as ordered, and only when a length of a path from said entry node to any given node is less than said depth limit.

7. The method of claim 1, wherein computing each cumulative node score comprises decaying said weighted-edge-weights of each path of said multiplicity of paths based at least in part on a given weighted edge'"'"'s distance from said entry node.

8. The method of claim 1, wherein said edge-weight metadata, with which each weighted edge is associated, comprises a date and/or time value and a base weight value.

9. The method of claim 8, wherein computing each cumulative node score comprises, for each weighted edge of each path of said multiplicity of paths that leads to said given node, decaying said base weight value according to said date and/or time value for each weighted edge.

10. A computing apparatus for providing recommendations, the apparatus comprising a processor and a memory storing instructions that, when executed by the processor, configure the apparatus to:

obtain a compact graph representation representing a recommendations directed-graph comprising a multiplicity of nodes and a multiplicity of weighted edges, each node of said multiplicity of nodes being associated with type metadata indicating that each node represents one of a multiplicity of recommendable items or one of a multiplicity of non-recommendable items, each weighted edge of said multiplicity of weighted edges joining a source node of said multiplicity of nodes to a target node of said multiplicity of nodes, each weighted edge being associated with edge-weight metadata;

store said compact graph representation in a primary memory of the computing apparatus;

receive a multiplicity of recommendation requests, each request requesting a recommendation of at least one recommendable item for a remote user based at least in part on request-context metadata associated with each request;

process each request of said multiplicity of recommendation requests, including performing at least the following steps for each request;

selecting an entry node of said multiplicity of nodes based at least in part on said request-context metadata;

traversing, via said compact graph representation in said primary memory, only a highly-weighted portion of said recommendations-graph that is proximate to said entry node to select a multiplicity of paths leading respectively to a multiplicity of potential recommendation nodes, each of which represents a recommendable item of said multiplicity of recommendable items, said multiplicity of paths being selected based at least in part on weighted-edge-weights of weighted edges making up a given path;

computing a multiplicity of cumulative node scores corresponding respectively to said multiplicity of potential recommendation nodes, including computing each cumulative node score based at least in part on said weighted-edge-weights of each path of said multiplicity of paths that lead to a given node;

selecting a recommendation node based at least in part on said multiplicity of cumulative node scores; and

providing in response to each request an identifier identifying a recommendable item represented by said selected recommendation node.

11. The apparatus of claim 10, wherein the instructions that configure the apparatus to obtain said compact graph representation further comprise instructions configuring the apparatus to:

initialize a nodes referenceable data-structure and an edges referenceable data-structure;

iterate over each node of said multiplicity of nodes, including performing at least the following steps for each node;

determining edge data comprising an edge-count of zero or more outbound weighted edges and for each of said zero or more outbound weighted edges, an edge-weight-related value and a target-node reference referencing data within said nodes referenceable data-structure;

inserting said edge data into said edges referenceable data-structure;

determining node data comprising an item-type reference referencing an item-type associated with each node and an edges-data reference referencing said edge data within said edges referenceable data-structure; and

inserting said node data into said nodes referenceable data-structure.

12. The apparatus of claim 11, wherein for each node that represents a recommendable item, said node data further comprises a recommendable-item-type reference reference a species of recommendable-item.

13. The apparatus of claim 12, wherein iterating over each node includes further performing at least the following steps for each node that represents a recommendable item:

inserting, into a species-map referenceable data-structure corresponding to said species of recommendable-item, a node-data reference to said node data within said nodes referenceable data-structure.

14. The apparatus of claim 13, wherein for each node that represents a recommendable item:

said node data further comprises a reference to said node-data reference within said species-map referenceable data-structure.

15. The apparatus of claim 10, wherein the instructions that configure the apparatus to traverse only a highly-weighted portion of said recommendations directed-graph that is proximate to said entry node further comprise instructions configuring the apparatus to:

determine a batch count (“

N”

) and a depth limit; and

from any given node;

order outbound weighted edges according to said edge-weight metadata associated therewith; and

follow only a top “

N”

outbound weighted edges, as ordered, and only when a length of a path from said entry node to any given node is less than said depth limit.

16. A non-transitory computer-readable storage medium having stored thereon instructions that, when executed by a processor, configure the processor to:

obtain a compact graph representation representing a recommendations directed-graph comprising a multiplicity of nodes and a multiplicity of weighted edges, each node of said multiplicity of nodes being associated with type metadata indicating that each node represents one of a multiplicity of recommendable items or one of a multiplicity of non-recommendable items, each weighted edge of said multiplicity of weighted edges joining a source node of said multiplicity of nodes to a target node of said multiplicity of nodes, each weighted edge being associated with edge-weight metadata;

store said compact graph representation in a primary memory of the processor;

receive a multiplicity of recommendation requests, each request requesting a recommendation of at least one recommendable item for a remote user based at least in part on request-context metadata associated with each request;

process each request of said multiplicity of recommendation requests, including performing at least the following steps for each request;

selecting an entry node of said multiplicity of nodes based at least in part on said request-context metadata;

traversing, via said compact graph representation in said primary memory, only a highly-weighted portion of said recommendations directed-graph that is proximate to said entry node to select a multiplicity of paths leading respectively to a multiplicity of potential recommendation nodes, each of which represents a recommendable item of said multiplicity of recommendable items, said multiplicity of paths being selected based at least in part on weighted-edge-weights of weighted edges making up a given path;

computing a multiplicity of cumulative node scores corresponding respectively to said multiplicity of potential recommendation nodes, including computing each cumulative node score based at least in part on said weighted-edge-weights of each path of said multiplicity of paths that lead to a given node;

selecting a recommendation node based at least in part on said multiplicity of cumulative node scores; and

providing in response to each request an identifier identifying a recommendable item represented by said selected recommendation node.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions that configure the processor to obtain said compact graph representation further comprise instructions configuring the processor to:

initialize a nodes referenceable data-structure and an edges referenceable data-structure;

iterate over each node of said multiplicity of nodes, including performing at least the following steps for each node;

determining edge data comprising an edge-count of zero or more outbound weighted edges and for each of said zero or more outbound weighted edges, an edge-weight-related value and a target-node reference referencing data within said nodes referenceable data-structure;

inserting said edge data into said edges referenceable data-structure;

determining node data comprising an item-type reference referencing an item-type associated with each node and an edges-data reference referencing said edge data within said edges referenceable data-structure; and

inserting said node data into said nodes referenceable data-structure.

18. The non-transitory computer-readable storage medium of claim 17, wherein for each node that represents a recommendable item, said node data further comprises a recommendable-item-type reference reference a species of recommendable-item.

19. The non-transitory computer-readable storage medium of claim 18, wherein iterating over each node includes further performing at least the following steps for each node that represents a recommendable item:

inserting, into a species-map referenceable data-structure corresponding to said species of recommendable-item, a node-data reference to said node data within said nodes referenceable data-structure.

20. The non-transitory computer-readable storage medium of claim 19, wherein for each node that represents a recommendable item:

said node data further comprises a reference to said node-data reference within said species-map referenceable data-structure.

21. The non-transitory computer-readable storage medium of claim 16, wherein the instructions that configure the processor to traverse only a highly-weighted portion of said recommendations directed-graph that is proximate to said entry node further comprise instructions configuring the processor to:

determine a batch count (“

N”

) and a depth limit; and

from any given node;

order outbound weighted edges according to said edge-weight metadata associated therewith; and

follow only a top “

N”

outbound weighted edges, as ordered, and only when a length of a path from said entry node to any given node is less than said depth limit.