Navigation for large scale graphs

Patent metadata

Field	Value
Publication number	US-9251166-B2
Application number	US-201213692607-A
Country	US
Kind code	B2
Filing date	Dec 3, 2012
Priority date	Nov 1, 2007
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

In one example embodiment, a method is illustrated as retrieving a plurality of search queries and defining relationships between search queries in the plurality of search queries based on semantic data associated with the search queries. A visual representation of the of the plurality of search queries may be generated and the visual representation may be partitioned into a plurality of tiles, each title representing a predefined portion of the visual representation.

First claim

What is claimed is:

1. A computer implemented method comprising:
retrieving a plurality of search queries;
generating, using at least one processor, a plurality of search query nodes that represent one or more of the plurality of search queries;
creating a visual representation of the search query nodes where one or more connections between the search query nodes indicate one or more relationships between two or more of the plurality of search queries;
partitioning the visual representation into a plurality of tiles, each tile representing a defined portion of a rendering of the visual representation, each tile configured to be accessed independently of one or more other tiles of the plurality of tiles;
receiving a submitted search query; and
selecting a tile containing one of the plurality of search query nodes corresponding to the submitted search query, from the plurality of tiles, and one or more tiles surrounding the identified tile.

2. The computer implemented method of claim 1 , wherein creating a visual representation includes assigning Cartesian coordinates to the plurality of search queries.

3. The computer implemented method of claim 1 , wherein the one or more relationships are based on semantic data associated with the search queries, the semantic data including a portion of an attribute shared by a first search query and a second search query.

4. The computer implemented method of claim 1 , wherein creating the visual representation includes generating edges between representations of search queries based on the relationships between queries of the plurality of search queries.

5. The computer implemented method of claim 1 , wherein creating the visual representation of the plurality of search queries includes generating an image file.

6. The computer implemented method of claim 1 , wherein partitioning the visual representation into a plurality of tiles further includes:
setting a tile size;
splitting the visual representation into the plurality of tiles according to the tile size;
determining at least one query of the plurality of search queries located within each of the plurality of tiles; and
generating scaled vector graphic data for the at least one query of the plurality of search queries.

7. The computer implemented method of claim 1 , further including:
storing multiple versions of the plurality of tiles, each version of the multiple versions associated with different zoom levels of the visual representation.

8. The computer implemented method of claim 7 , wherein storing multiple versions of the plurality of tiles further includes:
retrieving metadata defining rendering characteristics of the plurality of search queries, the rendering characteristics including a characteristic defining how to render the plurality of search queries at each zoom level, the rendering of the search queries differing at different zoom levels.

9. A computer implemented method comprising:
identifying a tile displaying one or more search query nodes that represent one or more search queries, the one or more search query nodes organized according to semantic relationships between the search queries, each tile representing a defined portion of a rendering of a visual representation of the search queries, each tile configured to be accessed independently of one or more other tiles of the plurality of tiles;
receiving a selection input selecting a first search query displayed in the tile;
identifying, using at least one processor, an additional tile associated with the first search query and additional search queries organized according to an additional semantic relationship between the search queries; and
displaying the additional tile.

10. The computer implemented method of claim 9 , wherein the search queries are associated with items for sale and the method further includes:
displaying items for sale associated with the first search query.

11. The computer implemented method of claim 9 , further including:
receiving a starting search query; and
searching the visual representation of the search queries for the starting search query.

12. The computer implemented method of claim 9 , wherein the displaying of the additional tile further includes:
retrieving an image file representing the additional tile; and
transmitting the additional tile to a user device.

13. A system comprising:
an application server comprising:
a processor;
a retrieving engine to retrieve a plurality of search queries;
a layout engine to:
generate a plurality of search query nodes that represent one or more of the plurality of search queries;
create a visual representation of the search query nodes where one or more connections between the search query nodes indicate one or more relationships between two or more of the plurality of search queries;

a partitioning engine to partition the visual representation into a plurality of tiles, each tile representing a defined portion of a rendering of the visual representation, each tile configured to be accessed independently of one or more other tiles of the plurality of tiles; and
a selection module to select a tile containing one of the plurality of search query nodes corresponding to the submitted search query, from the plurality of tiles, and one or more tiles surrounding the identified tile.

14. The system of claim 13 , wherein the layout engine is further configured to create the visual representation by assigning Cartesian coordinates to the plurality of search queries.

15. The system of claim 13 , further comprising:
an image database to store multiple versions of the plurality of tiles, each version of the multiple versions associated with different zoom levels of the visual representation.

16. The system of claim 13 , further comprising:
a second retrieving engine to retrieve metadata defining rendering characteristics of the plurality of search queries, the rendering characteristics including a characteristic defining how to render the plurality of search queries at each zoom level, the rendering of the search queries differing at different zoom levels.

17. A non-transitory machine-readable storage medium having machine executable instructions embedded thereon, which when executed by a processor of a machine, cause the machine to perform operations comprising:
retrieving a plurality of search queries;
generating a plurality of search query nodes that represent one or more of the plurality of search queries;
creating a visual representation of the search query nodes where one or more connections between the search query nodes indicate one or more relationships between two or more of the plurality of search queries;
partitioning the visual representation into a plurality of tiles, each tile representing a defined portion of a rendering of the visual representation, each tile configured to be accessed independently of one or more other tiles of the plurality of tiles; and
selecting a tile containing one of the plurality of search query nodes corresponding to the submitted search query, from the plurality of tiles, and one or more tiles surrounding the identified tile.

18. The machine-readable storage medium of claim 17 , wherein the creating of the visual representation includes assigning Cartesian coordinates to the plurality of search queries.

19. The machine-readable storage medium of claim 17 , wherein the one or more relationships are based on semantic data associated with the search queries, the semantic data including a portion of an attribute shared by a first

Assignees

• Ebay Inc

Inventors

• Grandhi Roopnath
• Sundaresan Neelakantan
• Nguyen Hill Trung

Classifications

• G06F17/30424

  Physics · mapped topic

• G06F17/3023 Primary

  Physics · mapped topic

• G06F17/3087

  Physics · mapped topic

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9537 Primary

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title