User interface framework for viewing large scale graphs on the web

• US 9,947,119 B2
• Filed: 08/29/2014
• Issued: 04/17/2018
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Grandhi, Roopnath, Nguyen, Hill Trung, Sundaresan, Neelakantan
• Primary Examiner(s): Johnson, M Good
• Application Number:
  US14/473,929
• Publication Number:
  US 20150054831A1
• Time in Patent Office: 1,327 Days
• Field of Search: None
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Various embodiments provide a computer-implemented system and method providing a user interface framework for viewing large scale graphs. An example embodiment includes obtaining graph data including information related to a plurality of nodes, the plurality of nodes corresponding to search queries performed on a particular host site; constructing a plurality of sub-graphs, the sub-graphs being clusters of search results that are formed based on an amount of overlap among the search results produced from the search queries; rendering the graph by displaying each of the plurality of nodes at a respective absolute position within the graph and generating a plurality of tiles representing images of the plurality of sub-graphs; and displaying a sub-graph image corresponding to a selected position and zoom level.

Claims

1. A method comprising:

obtaining graph data including information related to a plurality of nodes;

the plurality of nodes corresponding to search queries performed on a host site;

constructing a sub-graph of additional nodes that represent search results of the search queries, the constructing of the sub-graph including generating links between the additional nodes based on an amount of overlap among the search results produced from the search queries that correspond to the one or more of the plurality of nodes, the additional nodes included in the sub-graph being clusters of the search results;

rendering a graph by displaying each node at a respective absolute position within the graph and generating a plurality of tiles that depict images of the sub-graph at each of a plurality of zoom levels; and

displaying a sub-graph image corresponding to a selected position and zoom level.

2. The method of claim 1, further comprising:

assigning the absolute position to each of the plurality of nodes prior to the constructing the sub-graph.

3. The method of claim 1;

wherein the constructing the sub-graph includes;

generating the additional nodes related to the one or more of the plurality of nodes; and

generating links between the additional nodes and the one or more of the plurality of nodes based on determining that the amount of overlap exceeds a threshold value.

4. The method of claim 3, wherein the additional nodes are each assigned an absolute position within the graph that is proximate to the absolute position of each of the plurality of nodes.

5. The method of claim 1, further comprising:

storing the plurality of tiles representing images of the sub-graph in a database.

6. The method of claim 1, wherein the search queries are top search queries identified based on a number of instances in which the search queries are performed by users of the host site.

7. The method of claim 1, wherein the generating the plurality of tiles at each of the plurality of zoom levels includes generating the plurality of tiles at various levels of detail based on the plurality of zoom levels.

8. The method of claim 1, further comprising:

generating a global graph depicting a relationship between the plurality of nodes and the sub-graph related to the one or more of the plurality of nodes.

9. The method of claim 1, further comprising:

displaying a snapshot view of a highest zoom level showing an approximate area of a graph a user is viewing.

10. The method of claim 1, further comprising:

displaying meta information at each node of the plurality of nodes.

11. A system comprising:

one or more processors and executable instructions accessible on a computer-readable medium that, when executed, configure the one or more processors to at least;

obtain graph data including information related to a plurality of nodes, the plurality of nodes corresponding to search queries performed on a host site;

construct sub-graph of additional nodes that represent search results of the search queries, the constructing of the sub-graph including generating links between the additional nodes based on an amount of overlap among the search results produced from the search queries that correspond to the one or more of the plurality of nodes, the additional nodes included in the sub-graph being clusters of the search results;

render a graph by displaying each node at a respective absolute position within the graph and generating a plurality of tiles that depict images of the sub-graph at each of a plurality of zoom levels; and

display a sub-graph image corresponding to a selected position and zoom level.

12. The system of claim 11, wherein the one or more processors are further configured to assign the absolute position to each of the plurality of nodes prior to the construction of the sub-graph.

13. The system of claim 11, wherein the one or more processors are further configured to:

generate the additional nodes related to the one or more of the plurality of nodes; and

generate links between the additional nodes and the one or more of the plurality of nodes based on determining that the amount of overlap exceeds a threshold value.

14. The system of claim 13, wherein the additional nodes are each assigned an absolute position within the graph that is proximate to the absolute position of each of the plurality of nodes.

15. The system of claim 11, wherein the one or more processors are further configured to store the plurality of tiles representing images of the sub-graph in a database.

16. The system of claim 11, wherein the search queries are top search queries identified based on a number of instances in which the search queries are performed by users of the host site.

17. The system of claim 11, wherein the one or more processors are further configured to generate the plurality of tiles at various levels of detail based on the plurality of zoom levels.

18. The system of claim 11, wherein the one or more processors are further configured to generate a global graph depicting a relationship between the plurality of nodes and the sub-graph related to the one or more of the plurality of nodes.

19. The system of claim 11, wherein the one or more processors are further configured to display a snapshot view of a highest zoom level showing an approximate area of a graph a user is viewing.

20. A non-transitory machine-readable medium storing instructions that, when executed by one or more processors of a machine, cause the machine to perform operations comprising:

obtaining graph data including information related to a plurality of nodes, the plurality of nodes corresponding to search queries performed on a host site;

constructing a sub-graph of additional nodes that represent search results of the search queries, the constructing of the sub-graph including generating links between the additional nodes based on an amount of overlap among the search results produced from the search queries that correspond to the one or more of the plurality of nodes, the additional nodes included in the sub-graph being clusters of the search results;

rendering a graph by displaying each node at a respective absolute position within the graph and generating a plurality of tiles that depict images of the sub-graph at each of a plurality of zoom levels; and

displaying a sub-graph image corresponding to a selected position and zoom level.