Identifying items offered by an online concierge system for a received query based on a graph identifying relationships between items and attributes of the items

A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:

• maintain an item graph in a memory of an online system comprising a plurality of nodes and a plurality of edges connecting the nodes, wherein the item graph is generated by:
• generating a plurality of item nodes that each represents an item and a plurality of attribute nodes that each represents an attribute;
• and
• generating the plurality of edges that indicates connections between item and attribute nodes, wherein a connection between an item node and an attribute node indicates that the corresponding item has the corresponding attribute, wherein a connection between two item nodes indicates a value representing a co-occurrence of the corresponding items in historical orders, and wherein a connection between two attribute nodes indicates a value representing a co-occurrence of the corresponding attribute in historical orders;
• receive a plurality of new orders over a computer network from a plurality of different users;
• responsive to receiving the plurality of new orders, update the memory of the online system to update the item graph to include values representing the co-occurrences of the plurality of edges of the item graph based on the co-occurrences of items and attributes in the plurality of new orders;
• receive, at an online concierge system, a search query including one or more search terms from a customer;
• perform language processing on the search query to generate one or more combinations of search terms based on the search query;
• identify candidate items from the updated item graph by identifying one or more item nodes that are connected in the updated item graph to a node that matches one or more of the generated combinations of search terms;
• generate a score for each of the identified candidate items by, for each identified candidate item:
• identifying the edges in a path in the updated item graph that connect the corresponding item node and the node that matches one or more of the generated combination of search terms;
• retrieving, from the updated item graph, the values associated with the identified edges;
• and
• generating the score for the identified candidate items based on the retrieved values;
• select one or more of the identified candidate items based on the scores;
• and
• transmit search results comprising the selected one or more identified candidate items to a client device for display to the customer.

A system comprising:

• a processor;
• and
• a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by the processor, cause the system to:
• maintain an item graph in a memory of an online system comprising a plurality of nodes and a plurality of edges connecting the nodes, wherein the item graph is generated by:
• generating a plurality of item nodes that each represents an item and a plurality of attribute nodes that each represents an attribute;
• and
• generating the plurality of edges that indicates connections between item and attribute nodes, wherein a connection between an item node and an attribute node indicates that the corresponding item has the corresponding attribute, wherein a connection between two item nodes indicates a value representing a co-occurrence of the corresponding items in historical orders, and wherein a connection between two attribute nodes indicates a value representing a co-occurrence of the corresponding attribute in historical orders;
• receive a plurality of new orders over a computer network from a plurality of different users;
• responsive to receiving the plurality of new orders, update the memory of the online system to update the item to include values representing the co-occurrences of the plurality of edges of the item graph based on the co-occurrences of items and attributes in the plurality of new orders;
• receive, at an online concierge system, a search query including one or more search terms from a customer;
• perform language processing on the search query to generate one or more combinations of search terms based the search query;
• identify candidate items from the item graph by identifying one or more nodes in the item graph that match the generated combinations of search terms;
• generate a score for each of the identified candidate items based on connections between the identified attribute nodes and the identified item nodes in the item graph, wherein generating the score comprises:
• for each identified candidate item,
• generating a connection value between the corresponding candidate item node and each identified attribute node;
• updating information identifying relationships between different items and attributes based on items included in newly received orders;
• and
• modifying the connection value based on the updated information;
• select one or more of the identified candidate items based on the scores;
• and
• transmit search results comprising the selected one or more identified candidate items to a client device for display to the customer.