USER INTERFACE FRAMEWORK FOR VIEWING LARGE SCALE GRAPHS ON THE WEB

• US 20090115785A1
• Filed: 10/31/2008
• Published: 05/07/2009
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Sundaresan, Neelakantan, Nguyen, Hill Trung, Grandhi, Roopnath
• Granted Patent: US 8,823,709 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• 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 top search queries; assigning an absolute position in a graph for each of the nodes of the plurality of nodes; constructing a plurality of sub-graphs related to one or more of the plurality of nodes, the sub-graphs corresponding to search result clusters related to the top search queries corresponding to the one or more of the plurality of nodes; rendering the graph and generating a plurality of tiles representing sub-graph images of the plurality of sub-graphs at each of a plurality of zoom levels; 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 top search queries;

assigning an absolute position in a graph for each of the nodes of the plurality of nodes;

constructing a plurality of sub-graphs related to one or more of the plurality of nodes, the sub-graphs corresponding to search result clusters related to the top search queries corresponding to the one or more of the plurality of nodes;

rendering the graph and generating a plurality of tiles representing sub-graph images of the plurality of sub-graphs 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 as claimed in claim 1 wherein the graph data includes visual attributes of at least one node of the plurality of nodes.

3. The method as claimed in claim 1 wherein the graph data includes configuration parameters, the configuration parameters including a number of zoom levels.

4. The method as claimed in claim 1 including adding links between related nodes.

5. The method as claimed in claim 1 including generating a global graph depicting a relationship between the plurality of nodes and the plurality of sub graphs related to the one or more of the plurality of nodes.

6. The method as claimed in claim 1 wherein topologically related nodes are assigned an absolute position in a similar vicinity.

7. The method as claimed in claim 1 including using a position of a node of the plurality of nodes to update relative co-ordinates of nodes in a related sub graph.

8. The method as claimed in claim 1 including embedding a sub-graph at a position of a node of the plurality of nodes in a global graph.

9. The method as claimed in claim 1 including displaying a snapshot view of a highest zoom level showing an approximate area of a graph a user is viewing.

10. The method as claimed in claim 1 including displaying meta information at each node of the plurality of nodes.

11. An apparatus comprising:

a first interface to receive graph data including information related to a plurality of nodes, the plurality of nodes corresponding to top search queries;

a graph layout component to assign an absolute position in a graph for each of the nodes of the plurality of nodes, and to construct a plurality of sub-graphs related to one or more of the plurality of nodes, the sub-graphs corresponding to search result clusters related to the top search queries corresponding to the one or more of the plurality of nodes;

a graph rendering component to render the graph and to generate a plurality of tiles representing sub-graph images of the plurality of sub-graphs at each of a plurality of zoom levels; and

a second interface to output for display a sub-graph image corresponding to a selected position and zoom level.

12. The apparatus as claimed in claim 11 wherein the graph data includes visual attributes of at least one node of the plurality of nodes.

13. The apparatus as claimed in claim 11 wherein the graph data includes configuration parameters, the configuration parameters including a number of zoom levels.

14. The apparatus as claimed in claim 11 wherein the graph layout component being further configured to add links between related nodes.

15. The apparatus as claimed in claim 11 wherein the graph layout component being further configured to generate a global graph depicting a relationship between the plurality of nodes and the plurality of sub graphs related to the one or more of the plurality of nodes.

16. The apparatus as claimed in claim 11 wherein topologically related nodes are assigned an absolute position in a similar vicinity.

17. The apparatus as claimed in claim 11 wherein the graph layout component being further configured to use a position of a node of the plurality of nodes to update relative co-ordinates of nodes in a related sub graph.

18. The apparatus as claimed in claim 11 wherein the graph layout component being further configured to embed a sub-graph at a position of a node of the plurality of nodes in a global graph.

19. The apparatus as claimed in claim 11 wherein the graph rendering component being further configured to display a snapshot view of a highest zoom level showing an approximate area of a graph a user is viewing.

20. The apparatus as claimed in claim 11 wherein the graph rendering component being further configured to display meta information at each node of the plurality of nodes.

21. An article of manufacture comprising a machine-readable storage medium having machine executable instructions embedded thereon, which when executed by a machine, cause the machine to:

obtain graph data including information related to a plurality of nodes, the plurality of nodes corresponding to top search queries;

assign an absolute position in a graph for each of the nodes of the plurality of nodes;

construct a plurality of sub-graphs related to one or more of the plurality of nodes, the sub-graphs corresponding to search result clusters related to the top search queries corresponding to the one or more of the plurality of nodes;

render the graph and generate a plurality of tiles representing sub-graph images of the plurality of sub-graphs at each of a plurality of zoom levels; and

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

22. The article of manufacture as claimed in claim 21 wherein the graph data includes visual attributes of at least one node of the plurality of nodes.