Search Results Using Density-Based Map Tiles

Abstract

In one embodiment, a method includes receiving, at the client system, an input of a search query, sending, to a search engine, the search query and a first location associated with the search query, receiving, from the search engine, search results comprising references to a plurality of objects matching the search query, wherein the search results further comprise at least a portion of a first tile of a map comprising a plurality of tiles, the first location being within the first tile, wherein the map is divided into the plurality of tiles such that each tile has an approximately constant object density, and providing, at the client system responsive to the search query, a search-results interface for display comprising at least the portion of the first tile and a threshold number of the search results referencing objects matching the search query having a location within the first tile.

What is claimed is: 
     
         1 . A method comprising, by a client system of a first user:
 receiving, at the client system, an input of a search query by the first user;   sending, to a search engine, the search query and a first location associated with the search query;   receiving, from the search engine, search results comprising references to a plurality of objects matching the search query, wherein the search results further comprise at least a portion of a first tile of a map comprising a plurality of tiles, the first location being within the first tile, wherein the map is divided into the plurality of tiles such that each tile has an approximately constant object density; and   providing, at the client system responsive to the search query, a search-results interface for display, wherein the search-results interface comprises at least the portion of the first tile, and wherein the displayed portion of the first tile comprises a first threshold number of the search results referencing objects matching the search query having a location within the first tile.   
     
     
         2 . The method of  claim 1 , wherein the map comprises a plurality of tiles representing a plurality of geographic areas, respectively, wherein each tile comprises a plurality of objects having locations within the tile, and wherein each tile has below a threshold number of objects located within the tile. 
     
     
         3 . The method of  claim 1 , wherein the plurality of tiles comprises tiles of a plurality of sizes. 
     
     
         4 . The method of  claim 1 , further comprising:
 generating, by the search engine, the plurality of tiles by:
 accessing the map; 
 generating a first set of tiles at a first level, wherein each tile of the first set of tiles has a first number of objects having locations within the tile; and 
 for each tile in the first set of tiles having a number of objects greater than or equal to the threshold number of objects, generating a second set of tiles at a second level within the tile. 
   
     
     
         5 . The method of  claim 1 , further comprising
 generating, by the search engine, the plurality of tiles by:
 accessing the map, wherein the map comprises N levels of tiles; and 
 for each level m of levels 1 to N−1:
 for each tile in level m:
 calculating the number of objects located within the tile; and 
 if the number of objects is greater than or equal to the threshold number of objects, then generating a set of tiles at level m+1 with the tile. 
 
 
   
     
     
         6 . The method of  claim 1 , further comprising:
 identifying, by the search engine, one or more objects corresponding to the first query, each identified object having a location within the first tile.   
     
     
         7 . The method of  claim 6 , wherein identifying one or more objects corresponding to the first query comprises:
 calculating a distance for each object from the first location;   identifying one or more object having a distance less than a threshold distance from the first location.   
     
     
         8 . The method of  claim 6 , further comprising:
 ranking the identified objects; and   wherein the search-results interface comprises references to one or more of the identified objects having a raking greater than a threshold ranking.   
     
     
         9 . The method of  claim 1 , wherein the map comprises N levels of tiles organized in a tree-data structure having a root node corresponding to the map and a plurality of child nodes corresponding to the tiles. 
     
     
         10 . The method of  claim 1 , wherein the first location is received from a geographic-position component of the client system. 
     
     
         11 . The method of  claim 1 , wherein the first location is based on one or more of a global position system (GPS) signal, a Wi-Fi signal, or a cellular radio signal. 
     
     
         12 . The method of  claim 1 , wherein the first location is based on a search history associated with the first user. 
     
     
         13 . The method of  claim 1 , further comprising:
 accessing, by the search engine, a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:
 a first node corresponding to the first user, the first user being associated with an online social network; and 
 a plurality of second nodes corresponding to a plurality of objects associated with the online social network, respectively, each second node being associated with a second location. 
   
     
     
         14 . The method of  claim 13 , wherein the search-results interface comprises references to one or more of the objects corresponding to one or more second nodes, respectively, having a degree of separation from the first node less than a threshold degree of separation. 
     
     
         15 . The method of  claim 1 , wherein the search-results interface further comprises one or more neighboring tiles of the first tile, and wherein the displayed portion of each neighboring tile comprises one or more search results referencing objects matching the search query having a location within the respective neighboring tile. 
     
     
         16 . One or more computer-readable non-transitory storage media embodying software that is operable when executed by a client system to:
 receive, at the client system, an input of a search query by the first user;   send, to a search engine, the search query and a first location associated with the search query;   receive, from the search engine, search results comprising references to a plurality of objects matching the search query, wherein the search results further comprise at least a portion of a first tile of a map comprising a plurality of tiles, the first location being within the first tile, wherein the map is divided into the plurality of tiles such that each tile has an approximately constant object density; and   provide, at the client system responsive to the search query, a search-results interface for display, wherein the search-results interface comprises at least the portion of the first tile, and wherein the displayed portion of the first tile comprises a first threshold number of the search results referencing objects matching the search query having a location within the first tile.   
     
     
         17 . A client system comprising: one or more processors; and a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:
 receive, at the client system, an input of a search query by the first user;   send, to a search engine, the search query and a first location associated with the search query;   receive, from the search engine, search results comprising references to a plurality of objects matching the search query, wherein the search results further comprise at least a portion of a first tile of a map comprising a plurality of tiles, the first location being within the first tile, wherein the map is divided into the plurality of tiles such that each tile has an approximately constant object density; and   provide, at the client system responsive to the search query, a search-results interface for display, wherein the search-results interface comprises at least the portion of the first tile, and wherein the displayed portion of the first tile comprises a first threshold number of the search results referencing objects matching the search query having a location within the first tile.