JP5054234B2 - System and method for displaying search results based on density - Google Patents

Description

[Cross-reference of related applications]
This application claims priority from US patent application Ser. No. 12 / 359,715 filed Jan. 26, 2009, Attorney Docket No. GOOGLE 3.0-038, the entire disclosure of which is incorporated herein by reference. Reference is made to a part of this specification. This application also claims priority of US patent application Ser. No. 12 / 359,734, filed Jan. 26, 2009, and is hereby incorporated by reference in its entirety. Shall be made.

  Services such as Google Maps (maps.google.com) allow users to perform searches limited to a specific geographic area. For example, a user may search for the word “pizza” while browsing a New York City city map or satellite map with a web browser such as Google Chrome. In response, the server causes the user's computer to display an icon that indicates the location of the list that matches the query, such as a restaurant whose name includes “pizza”.

  Query results can be sent in a manner that allows for great interactivity. For example, a map is transmitted as tiles of an image, and a description of the results and their positions are transmitted as text (such as data formatted as JSON (Javascript Object Notation) or HTML). This allows the user's computer to display an icon on the map and display the resulting text list next to the map. The client computer uses Javascript provided by the server to determine whether the user has clicked on the area of the map occupied by the interactive icon and, accordingly, a balloon that contains more information about the list. A plurality of operations such as displaying can be performed.

  Google Maps also allows layers. For example, an icon for an entry in Wikipedia.org associated with a latitude / longitude matching the currently viewed geographic area can be shown (eg, http://en.wikipedia.org/wiki/Wikipedia : WikiProject_Geographical_coordinates). The entry icon is transmitted as an image and overlaid on the map with information about the entry. The information is transmitted by JSON together with information specifying the position of the entry on the map and entry identification information. The location information can be used by the user's computer to determine whether the user has activated the icon (such as by clicking on the icon or hovering the mouse cursor over the icon). It can be used to get more information from the server when the icon is activated. Youtube results can also be shown as layers. These results are not filtered based on the query, but show all entries in the area covered by the map.

  Google Maps displays icons associated with all businesses sent by the server that fall within certain pre-selected categories such as “Italian” and “Pizza” restaurants, banks, gas stations, etc. It also features a “Famous Places” layer that allows you to do so. Users can display search results collectively from searches based on pre-selected categories and custom search terms that are not pre-selected, but the results are separate, ie the icons for the pre-selected categories It does not change based on the definition word, and vice versa. For example, a user may check the box next to “pizza” and type the word “vegetarian”, in which case Google Maps will synthesize the search results and display them together, but associate it with “pizza”. Neither is the selected result selected based on the “vegetarian” query, nor is the result associated with the “vegetarian” query selected based on the selection of “pizza” from the list. www.tavernoxoros.gr (shows many locations on the map depending on the user's choice of pre-selected categories) and www.smalltownbrooklyn.com (shows all businesses on the map) ) Can similarly show all results associated with a pre-selected category.

  In one aspect, a method is provided that includes receiving a query, determining a matching list, selecting a plurality of matching lists, and providing a map. The list includes data associated with an object associated with a geographic location and information associated with the object, the list includes information in the list that matches the query, and the geographic location of the list is Fit when matching the map area. A plurality based on the number of matching lists having a geographic location associated with the first portion of the map area, relative to the number of matching lists having a geographic location associated with the second portion of the map area; A matching list of is selected. The map is provided with an indication of the matching list.

Another aspect provides a system for displaying a map.
This system
A user input device;
Memory for storing instructions and data representing different objects at different geographical locations;
A processor in communication with the user input device to process information received from the user input device according to the instructions;
A display that communicates with the processor and displays information received from the processor.
The instructions are
Reading a map based on location information entered via the user input device;
Reading identification information of an object that matches information input via the user input device, wherein the read identification information includes all of the objects that match the information input via the user input. Less than, selected based on the density of matching objects in the portion of the map;
Displaying the identification information on the map on the display.

Yet another aspect provides a method for displaying a map covering a map area. This method
Transmitting a location and a word from a first computer of a first node of the network to a second computer of a second node of the network, wherein the word is arbitrarily selected by a user When,
Receiving data representing a map and a list, wherein the map covers an area; and
Displaying a map and a list on the map based on the data.
The map data is selected by the second computer based on the location. The list is selected by the second computer based on density criteria and whether or not the list meets, wherein (a) the list includes one or more of the transmitted words. (B) the density criterion is based on the amount of matching list in one area of the map area relative to another area of the map area, if present in the information associated with the list It is. In some aspects of the invention, all of the words must match.

A further aspect provides a method for displaying a map.
This method
Transmitting a location and word arbitrarily selected by a user from a first computer of a first node of the network to a second computer of a second node of the network;
Receiving image data representing a map covering an area;
Receiving image data representing a first set of lists;
Receiving text data representing a second set of lists;
Displaying a map and a list on the map based on the data.
The method is such that the map data is selected by the second computer based on the location. Further, the method is such that the list represented by the list data is selected by the second computer based on density criteria and whether the list is met, Here, (a) the list has a match between the word associated with the list and the transmitted word, and there is a match between the location associated with the list and the area. (B) The density criterion is based on the amount of matching list in one area of the area relative to another area of the area.

  Yet another aspect relates to a system having a means for receiving a query and a means for determining a matching list, wherein the list includes data identifying an object associated with a geographic location and information associated with the object. The determination of matching includes determining whether the list information matches the query and whether the geographic location matches the map area. The system is based on the number of matching lists having a geographic location associated with the first part of the area, relative to the number of matching lists having a geographic location associated with the second part of the area. Means for selecting a plurality of said matching lists. Further, the system provides means for providing an indication of the map area map and the matching list, wherein each indication is located on the map relative to its geographic location. Is provided.

In yet another aspect, a method for displaying a map is provided.
This method
Transmitting a location and word arbitrarily selected by a user from a first computer of a first node of the network to a second computer of a second node of the network;
Receiving image data representing a map covering an area;
Receiving image data representing a first set of lists;
Receiving text data representing a second set of lists, wherein the list in the second set is different from the list in the first set;
Displaying the first set of lists and the second set of lists on the map.
Map data is selected by the second computer based on the location, and both sets of lists are selected by the second computer based on whether the list matches. A list is matched when a match exists between a word associated with the list and the transmitted word, and a match exists between a location associated with the list and the map area. Is considered.

  Non-limiting examples of image data include vector or bitmap format data. Non-limiting examples of text data include data formatted as JSON, XML, or HTML.

Another aspect is:
Memory for storing data and instructions;
A processor that processes the data in accordance with the instructions;
And a display that displays information received from the processor in communication with the processor. The instructions include receiving image data representing a map covering an area, image data representing a first set of lists, and text data representing a second set of lists over a network. The instructions also include displaying a map and a list on the map based on the data, the map data being selected by the server based on the location. In addition, a list is selected by the server based on whether the list matches, the list has a match between the word associated with the list and the transmitted word, and is associated with the list Matches when there is a match between the given location and the map area.

  A still further aspect relates to a method for transmitting a map. This aspect includes receiving, at a first computer of a first node of the network, a location and any word selected by a user from a second computer of the second node of the network. This also includes using a processor in a second computer to select data representing the map of the location and the list. The list is selected based on whether the description associated with the list matches the received word and whether the location associated with the list matches the received location. The method further includes transmitting the map data as image data and generating image data based on the selected list, wherein each selected image is associated with an icon, the icon Matches the location of the list relative to other lists. The method also transmits the image data based on the selected list.

Yet another aspect of the system is:
Means for transmitting a location and word arbitrarily selected by a user from a first computer of a first node of the network to a second computer of a second node of the network;
Means for receiving image data representing a map covering the area;
Means for receiving image data representing a first set of lists;
Means for receiving text data representing a second set of lists;
Means for displaying the map, wherein the first set of lists and the second set of lists on the map comprise means for displaying based on the data.
In this system, the map is selected by the second computer based on the location, and the list represented by the list data is matched by the second computer. Selected based on whether or not the list has a match between the word associated with the list and the transmitted word, and between the location associated with the list and the map area Match if there is a match.

1 is a block diagram of a system according to an aspect of the system and method. FIG. 1 is a schematic diagram of a system according to an aspect of the system and method. FIG. FIG. 6 is a diagram representing the relationship between map areas, map tiles, and regions, according to one aspect of the system and method. 4 is a screen shot of a set of maps and lists according to one aspect of the system and method. 6 is a map display prior to showing a list, according to one aspect of the system and method. It is an example of the map display which shows all the response lists. FIG. 7b shows a portion of the map displayed in FIG. 7b. FIG. 6 is an example of a map display showing a limited number of lists selected based on a displayed map area and the relevance of the list to a user query. FIG. 8b is a diagram showing a portion of the map displayed in FIG. 8b that is different from the portion shown in FIG. 7a. 8 is an example of a map display showing a limited number of lists selected based on the displayed map area and the relevance of the list to the same query as FIG. 7b. 6 is a flowchart in accordance with an aspect of the system and method. FIG. 6 is a diagram illustrating the number of response lists in a region of a map according to one aspect of the system and method. FIG. 4 is a diagram illustrating the density of response lists in a region of a map according to one aspect of the system and method. FIG. 6 is a diagram illustrating the location of a response list in a region according to one aspect of the system and method. 2 is a map display according to one aspect of the system and method. 2 is a map display according to one aspect of the system and method. FIG. 3 is a schematic diagram of an aspect of the system and method. FIG. 6 is an image of a list according to one aspect of the system and method. FIG. 4 is a screen shot of a set of maps and lists displayed in accordance with an aspect of the system and method. 6 is a flowchart in accordance with an aspect of the system and method. 6 is a flowchart in accordance with an aspect of the system and method. 6 is a flowchart in accordance with an aspect of the system and method. 6 is a flowchart in accordance with an aspect of the system and method.

  In one aspect, the system and method display the results of the user's query on a map to indicate in which area the response list is more densely present. To reduce the need for client computer processing, some of the highest score lists can be sent as text to be rendered as interactive icons, while the rest are overlaid on the map Can be sent as an image layer.

  As shown in FIGS. 1 and 2, the system 100 according to one aspect includes a computer 110 that includes a processor 210, a memory 220, and other components typically present in a general purpose computer.

  Memory 220 stores information accessible by processor 210, including instructions 240 that can be executed by processor 210. The memory also includes data 230 that can be retrieved, manipulated, or stored by the processor. The memory may be of any type that can store information accessible by the processor, such as a hard drive, memory card, ROM, RAM, DVD, CD-ROM, writable memory, and read-only memory. it can. The processor 210 may be any known processor, such as an Intel processor. Alternatively, the processor can be a dedicated controller such as an ASIC.

  The instructions 240 may be any set of instructions (such as machine code) that are directly executed by the processor or instructions (such as a script) that are executed indirectly. In this regard, the terms “instructions”, “steps”, and “programs” can be used interchangeably herein. The instructions can be stored in object code form for direct processing by the processor, or any other including a collection of independent source code modules that are interpreted or executed on demand or pre-compiled. It can also be stored in computer language. Instruction functions, methods, and routines are described in more detail below.

  Data 230 can be retrieved, stored, or modified by processor 210 in accordance with instructions 240. For example, the system and method are not limited by any particular data structure, but the data is stored in a relational database in a computer register as a table with a plurality of different fields and records, XML documents, or flat files. Can do. The data can also be formatted in any computer readable format such as, but not limited to, binary values, ASCII, or Unicode. In addition, the data can be associated with numbers, descriptions, ownership codes, pointers, references to data stored in other memory (including other network locations), or information used by functions that calculate related data. Any information sufficient to identify the information can be included.

  Although the processor and memory are functionally shown in the same block in FIG. 1, those skilled in the art can actually include a plurality of processors and memory in the same physical enclosure. It will be understood that it may or may not be stored. For example, some instructions and data can be stored on a removable CD-ROM, while others can be stored in a read-only computer chip. Some or all of the instructions and data can be stored in locations that are physically remote from the processor but still accessible. Similarly, a processor may actually include a collection of processors that may or may not operate in parallel.

  In one aspect, the computer 110 is a server that communicates with one or more client computers 150, 170. Each client computer, like the server 110, can be configured with a processor, memory, and instructions. Each client computer 150, 170 is intended for use by people 190 and 191, and is a central processing unit (CPU), display 160 (eg, a monitor that displays information processed by the processor), CD-ROM, hard drive, user input device. (Eg, mouse, keyboard, touch screen, or microphone), speakers, modems, and / or network interface devices (phones, cables, etc.), and these elements are connected to each other and they are (directly or indirectly) It can be a personal computer having all the internal components normally found in a personal computer, such as all of the components used to enable communication with each other. In addition, a computer according to the systems and methods described herein is any computer that can process instructions and send and receive data to and from other computers, including humans and network computers without local storage capabilities. Devices may be included.

  Although client computers 150 and 170 can include full-size personal computers, many aspects of the system and method are mobile devices that can exchange data wirelessly with a server over a network such as the Internet. Particularly advantageous when used in connection with. For example, the client computer 170 can be a wireless enabled PDA such as a Blackberry phone or an Internet-enabled mobile phone. In that regard, the user enters information using a small keyboard (for Blackberry phones), keypad (for regular cell phones), touch screen (for PDAs), or any other means of user input. Can do.

  Client computers 150 and 170 may include components such as circuitry for determining the geographical location of the device. For example, mobile device 170 can include a GPS receiver 155. As a further example, the component may be based on other signals received at the mobile device 150, such as signals received at the mobile phone antenna from one or more mobile phone towers if the mobile device is a mobile phone. Software for asking for.

  The server 110 and the client computers 150 and 170 can perform direct communication and indirect communication via the network 295 or the like. Although only a few computers are shown in FIGS. 1 and 2, it is understood that a typical system can include a large number of connected computers, with each different computer being at a different node of the network 295. Should. The network and intervening nodes include the Internet, the World Wide Web, an intranet, a virtual private network, a wide area network, a local network, a mobile phone network, a private network using one or more company-developed communication protocols, Ethernet (registered trademark) Various combinations of devices and communication protocols can be included, including WiFi, WiFi, and HTTP. Such communication can be facilitated by any device, such as a modem (eg, dial-up or cable), a network, and a wireless interface that can send data to the other computer from the other computer. Server 110 may be a web server.

  Although certain advantages are obtained when information is transmitted or received as described above, other aspects of the system and method are not limited to any particular information transmission method. For example, in some aspects, the information can be transmitted via a medium such as a disk, tape, or CD-ROM. In other aspects, the information can be transmitted in a non-electronic format and can be manually entered into the system. Furthermore, although some functions are shown as being performed on the server and some functions are illustrated as being performed on the client, various aspects of the system and method may be implemented as a single processor having a single processor. It can also be implemented by other computers.

  The map database 270 of the server 110 stores information related to the map, at least a portion of which can be sent to the client device. For example, the map database 270 can store map tiles 272, where each tile is a map image of a particular geographic area. Depending on the resolution (eg, whether the map is zoomed in or zoomed out), a single tile can cover the entire region, such as a state, relatively roughly. Other tiles can also cover only a few streets in high detail. The map information of the system and method is not limited to any particular format. For example, the images can include street maps, satellite images, or combinations thereof, and can be formatted as vectors (especially with respect to street maps) or bitmaps (especially with respect to satellite images). Each of the various map tiles is associated with a geographic location, whereby server 110 selects, retrieves, and transmits one or more tiles based on receipt of a geographic location or range of geographic locations. Is possible.

  The map database 270 can also store list information identifying business or other objects, or geographic features associated with a particular geographic location. For example, each local business 274 can be associated with a name, category (such as “pizza, Italian restaurant”, or “stadium”), other information (such as opening hours, food on the menu), and location. The location can be expressed in different formats, such as a text-based street address (“1600 Amphitheater Parkway, Mountain View, CA”) or a latitude / longitude position (latitude 37.4303021, longitude-122.083739, etc.). In addition, for business addresses, a plurality of descriptions such as storing both address and latitude / longitude position can be stored in the same manner. The database can be compiled by automatically collecting business information (such as from a website or phone book), or a user can enter local business records themselves via a web page served by the server 110 or It can also be edited.

  In many cases, there is a single list 274 in the map database 270 for each different business. However, it will be appreciated that the same business can be associated with many different lists and that a single list can be associated with many different businesses.

  The list can include other geographically arranged objects in addition to or on behalf of the business. For example, they can specify a house, landmark, road, land, current location of a car, merchandise placed in a store, and the like. Thus, references to business lists are understood as examples only and not as limitations on the types of lists that can be the subject of the present system and method.

  In one aspect of the system and method, each list is also allocated to one or more geographic regions called “region cells”. For example, the earth can be considered divided into individual regions of various levels and sizes. At the highest level, the earth can be regarded as being divided into four regional cells, two north and two below the equator. At the second highest level, these cells (such as cells north of the equator and east of the prime meridian) can be further divided into four other cells. At the third highest level, each of the second highest level cells can be further divided into four more cells. This can continue until the desired number of levels in the area cell has been achieved (it is not necessary that the earth be initially divided into four cells or each level is divided by four cells). Absent.)

  Thus, any particular point on the earth will be contained in many different area cells, one for each level. Similarly, each regional cell is associated with a geographic area.

  The map database 270 can store, for each list 274, an area cell in which the list exists. For example, a Manhattan pizzeria is associated with many cells, which are (1) a large area cell containing all of the northern hemisphere east of the prime meridian, and (2) a much smaller cell containing only the neighborhood of Manhattan. Including both area cells. Alternatively, the applicable region cells in the list can be determined on demand, if necessary, such as after a query is received.

  FIG. 3 illustrates how map areas, region cells, and tile boundaries can be related to each other. Block 310 (thick solid line) represents the map area to be displayed. Blocks 320 and 321 and other boxes defined by thin solid lines represent individual map tiles sent to and bound by the client computer to show the map. Boxes 330 and 331 and other boxes defined by dashed lines represent one level of area cells associated with the map area. The edges of map areas, tiles, and area cells may not be perfectly aligned with each other, but each is associated with a particular geographic location, so their location relative to each other is known.

  In addition to the operations shown in FIG. 18, various operations in accordance with various aspects of the present system and method will now be described. It should be understood that the following operations need not be performed in the exact order described below. Rather, the various steps can be processed in reverse order or simultaneously.

  FIG. 4 shows a screen shot of a map viewed by the user. For example, the system and method can be implemented in connection with an Internet browser such as Google Chrome that displays a web page showing maps and other information.

  The user can perform a search of the list associated with a particular location by entering a query, for example, the user can enter one or more of the servers by typing “Pizza nyc” in the text box 410 Search terms (such as “pizza”) and location (such as “nyc”), and search for businesses related to pizza in New York City (FIG. 4 uses the fictional town “Anytown” as an example) ).

  In one aspect of the invention, the query includes any word selected by the user. For example, rather than limiting the user to a predefined list of search terms or search types, the user may use his keyboard to type any one or more words he desires one character at a time. it can.

  The user can also select a particular geographic area by using a mouse, keyboard, or other user input device, and pan and zoom as desired. Queries can be provided in other formats as well, such as by providing audio and images.

  In response to the user's query, the server can send search results as well as images of the map 440. Rather than drawing the response list on the map and sending the map, the server 110 sends the list description and its location to the client 150. This allows the user computer to easily interact with the list, such as drawing an icon 420 that responds to the click. The user computer can also list the text 430 at a separate location adjacent to the map 440.

  When multiple lists are returned, the system and method can display them all. However, the icons used to display the list on the map overlap so extensively that the map may become unacceptably difficult to see. For example, FIG. 5 and FIG. 6 show that icons “520” are displayed for all lists in the city with “pizza” in the name before and after (respectively) searching for “pizza nyc”. It shows how a New York City map 510 might look.

  In addition, many client computers cannot process and display hundreds of lists in an acceptable manner. For example, if the client computer is a relatively low power low memory device such as a mobile phone and the list is sent as a text-based file such as JSON or XML, the client computer will pan the map by the user. In some cases, it may be very difficult to quickly draw all of the list and quickly rearrange the list. There may be tens of thousands of restaurants selling pizza in New York City.

  As described above in the background section, only a certain number of response lists can be sent to reduce visual clutter or processing requirements at the client computer. FIG. 7b shows a map 720 with the top 25 pizza lists (indicated by black pins such as pin 710) containing all of the very dense Manhattan 730 and some of the less dense Brooklyn / Queens 740. One possible result is shown when shown. Block 750 of FIG. 7a shows the outline of the map 720 for the rest of New York City. Due to the difference in density, the number of lists 760 shown in Manhattan (22 lists) far exceeds the number of Brooklyn / Queens lists 770 (two lists). This conveys the impression that Manhattan is extremely and densely filled with high-score lists, while Brooklyn / Queens has relatively few high-score lists.

  More when the New York City view is panned to include much more Brooklyn / Queens and much less Manhattan, as shown in FIG. 8, and the list of the top 25 scores in the map 820 is shown. It is expected that a list of Brooklyn / Queens will be shown, and a lower Manhattan list. One possible result is shown in FIG. However, the list of top scores 860 changes dramatically as the set of queried lists changes (here, only a portion of Manhattan is seen in the map 820 and more Brooklyn / Queens are seen). There is a case. For example, the Manhattan list 860 may appear much less dense than the Manhattan list 760 of FIG. Furthermore, although Manhattan's list 860 still appears denser than Brooklyn / Queens' list 870, the difference between the neighborhoods is much less pronounced in FIG. 8b than in FIG. 7b. The user view map FIG. 8b has a much different impression than the user view map FIG. 7b regarding the difference between Manhattan and Brooklyn / Queens when it comes to how close the list is to each other.

  In one aspect of the system and method, a list is selected in response to a query based at least in part on the geographic proximity of the list to other lists. For example, lists are more likely to be displayed when other lists are in dense geographic areas.

  In this regard, the system and method compare the number of lists in one area (such as Manhattan) with another displayed geographic area (such as Brooklyn) and select a portion of the list based on the difference. In other words, if Manhattan has a list twice that of Brooklyn, then Brooklyn's twice list will be shown in Manhattan.

  Furthermore, the list can be selected based on how well the list matches the query. For example, if the system shows 30 lists at the same time in a map that includes both Manhattan and Brookling, and if there are twice as many response lists in Brooklyn as Manhattan, the top 20 best matching lists in Manhattan are in Manhattan. Displayed and the top 10 best matching lists in Brooklyn are displayed in Brooklyn. In other words, the map shows both Manhattan and Brooklyn, but even if all of the top 100 lists are in Manhattan, it will still show 10 matches in Brooklyn. Similarly, the map will still show 20 matches in Manhattan even if all of the top 100 lists are in Brooklyn.

  Showing more lists can help convey the greater meaning of the distribution of the list. However, as described above in connection with FIG. 6, even if the list is selected based on density, it may be difficult for the client computer to present a large number of lists on the map. The list can be drawn directly on the map and sent to the client, but the client computer can provide the same interactivity to the user as if the list were sent in text as described in connection with FIG. There are cases where it is not possible.

  One aspect of the system and method is the use of a server to locate some of the lists on an image and a client computer to provide various types of lists and map information. Position some of them.

  As shown in FIG. 9, in response to a query from the client computer 910, the server 920 describes information about the map image 930 (bitmap or vector-based tile), some of the information identifying the top list. 940 (such as a text-based HTML, JSON, or XML file) and other list images 950 for the client computer to overlay on map image 930 are sent. The processor of client computer 910 receives and processes this information to create and display a single image 960.

  For example, the client computer can display the map 960 in the web browser, and uses the information included in the list information 940 to determine the position of the user-actuable icon 990 on the map 930. And render the information as text 991 next to the map. In one aspect, the list is sent as text based on the likelihood of interest of the user.

  The client computer 910 also overlays other list images 950 on the map, thereby allowing the user to view other list indications 980 beyond the list contained within the list information 940. Like the lists included in the list information 940, these lists also respond to user queries. In addition, these lists can be selected to reflect density as discussed above.

  Because other list images are rendered by the server, in one aspect of the system and method, the client computer need not calculate or even know the location of the list on the overlay. Rather, since the lists are already positioned on the overlay by the server 920, the client computer 910 can quickly display other lists on the map 930. Furthermore, even if there are hundreds of other lists shown on the map, the client computer does not need to receive or process those locations, nor does it need to display their activations individually. There is no need to test. This aspect of the system and method can be particularly advantageous in connection with devices having limited user input or processing power.

  The aspects of the system and method advantageously allow various features to be used simultaneously without overloading the processor of the client computer. By way of example, if “pizza” is queried when the user is browsing a high density area such as New York City, the image overlay 950 indicates that there are many lists in response to the user's query. Makes it possible to see. In addition, if the server selects a list in overlay 950 based on the density described above, the user can also see where the list is most concentrated. This can be very valuable when seeking an area that a user may want to visit. Both sets of lists are selected based at least in part on a query that includes any word provided by the user rather than a category or term pre-selected by the server.

  This aspect also has the advantage of allowing the user to interact greatly with the list. For example, the client computer can activate the icon by clicking on the icon 990 associated with the list 991. Activating the icon can provide more information (such as displaying a balloon with additional information such as address and photo). Similarly, clicking on the text list 991 can highlight the associated icon 990 in the list on the map. Thus, the list that is likely to be the user's greatest interest remains highly interactive.

  Next, one possible system and method for selecting a list based on the user's arbitrary query, list density, and processing the image overlay of the list will be described by way of example and not limitation.

  As shown in FIGS. 1 and 2, the user 190 causes the web browser program on the client computer 150 to connect to the web server 110 via the network 295. The server 110 transmits a web page including Javascript to the browser. The processor of the client computer executes a Javascript instruction. The Javascript instruction includes requesting an initial map at a particular location from the server. The initial location can be any, including using the last location viewed by the user, causing the server to select a default location, appending the location to the URL used to log into the server, and many other methods It can be specified in a number of ways. The system and method are not limited to any particular method of identifying a location.

  The user can then enter a query into the web browser. The query is sent to the web server. After receiving the query from the client computer 150, the server 110 determines whether the query is associated with a location and, if so, determines where the location is. For example, if the query is “pizza nyc”, the server may determine that the “nyc” portion of the query is associated with a location and proceed to determine the latitude / longitude position of that location. In that regard, the portion associated with the location can be passed to a geocoding routine, which can provide an address (such as “1600 Amphitheater Parkway, Mountain View, CA”) with an address (latitude 39.4303021 and longitude −122). To geographic coordinates (such as .083939). Similarly, the geocoding routine can also convert “nyc” to the latitude / longitude of the New York City center.

  In addition to determining latitude / longitude or similar location, the server 110 also determines how many geographic areas to display. For example, a request for a specific street address may cause the server 110 to select a location rectangle that includes an area approximately one mile square centered on that address. Similarly, if the user specifies only a city such as “nyc”, the server can select a location rectangle that describes the whole of New York City. The size of the location rectangle can be determined by other factors as well, such as by using the current zoom level of the user's map (assuming the user is currently viewing the map).

  If a location is found in the query, it can be assumed that the server is searching a list in or near the geographic area the user last viewed. In this case, the server can select a location rectangle corresponding to the geographic area the user is currently viewing. Other shapes can also be used. For example, the surface of a hemisphere, such as the Earth, is not strictly rectangular, and therefore other shapes can be selected if the rectangle is considered insufficient. For example, other four-vertex shapes, polygons, and curved shapes can be used instead of rectangles as well.

  The location rectangle can also be affected by the desired zoom level. For example, if the user is browsing the map at the time the user performs a search, the server can determine the location area using its currently selected zoom level.

  The processor 210 of the server 110 uses the user's query (eg, “pizza”) and a location rectangle (eg, a rectangle that has four corners at different latitude / longitude locations and defines all or most of New York City). Query. Next, the server is within the location rectangle or relatively close to the location rectangle and the requested word (eg “pizza”), its variants (eg “pizzeria”), words that are known to be highly relevant. (E.g., "parlor"), or proceed to look for matches, such as any list that contains words that otherwise match the user query in a way that is defined as showing matches by the system and method. A list that is considered relevant may hereinafter be specifically referred to as a “response list”.

  The server 110 determines the response list score. As an example, the score can be a value related to the likelihood that the list is of interest to the user. A relatively high score can represent a relatively high likelihood of interest, and a relatively low score can represent a relatively low likelihood of interest. The score can be based on any number of factors and any number of formulas, such as assigning positive or negative values to various characteristics and summing those values. Several characteristics are described below, but the following characteristics are not required in all aspects of the system and method. Furthermore, other characteristics can be used as well.

  Some characteristics of the score can rely on comparing the list of queries. For example, if a word in a user's query exactly matches a name in a list or category (for example, the user is searching for “pizza” and the business name is “Joe's Pizza”) High values can be added to the score. The user ’s word partially matches other information in the list (for example, the user is searching for “pizza” and the business is serving “pizza burgers” somewhere on the website (It is the stadium that happens to be mentioned), and you can add a lower value to the score.

  In one aspect, the score may be changed depending on the proximity of the list to the location requested by the user. For example, a very high value can be added to the score if the user provides a street address and the list location exactly matches. If the user provides a city name and the list address is in a nearby city, a lower value can be added.

  The score can also be based on information not relevant to a particular query. For example, if the list has been viewed by many different users in the past, a high value can be added to the score. A lower value can be added to the score if the list has been shown many times to other users in the past and was rarely selected.

  Some scores can be so low that the server may determine that no further processing of the list is required. In that regard, a particular list can be considered irrelevant even if the list fits to some degree in the query.

  The server can select a certain number of top score lists to send to the client computer. For reference purposes only, such a list may be referred to herein as a “top list”, but it is understood that the top list can also be selected based on being the list with the highest score. The

  The response list is then analyzed based on the score. For example, the server can create two histograms. Here, the first histogram stores a list having names or categories that match the user's query (or some other criterion that is considered to greatly suggest predicting the user's interest in the list). The second histogram may include a list with other elements such as reviews or web pages that match the user's query.

  Each histogram is divided into bands including ranges in ascending or descending order of scores. Each list is sorted within the appropriate band of the appropriate histogram.

  The server can also analyze the score of the response list to determine whether a list beyond the top list should be shown. For example, if there are few results in the high score histogram and many results in the low score histogram, the server determines that the user is unlikely to be interested in the rest of the list and sets the trigger to `` false '' Can be set to The trigger can be set to “true” if there are many results in the high score histogram, or if there are few results in the low score histogram but there are many results in the high score histogram.

  The analysis results can be sent to the client computer for processing or evaluation. For example, the server 10 can create an HTML or JSON file that describes the top list.

  The description of the top list is sent as text to the client computer and can provide the client computer with enough information to at least show the list on the map. In one aspect, the information includes a list name, street address, and telephone number. Information pops up a bubble that displays a list of clickable areas on the map associated with the list, and what happens when those areas are clicked (more information about the list associated with the area And the like can also be included. In another aspect, the top list information may include information identifying where the client computer can find further information about the list on the server 110 or the Internet in general. In yet another aspect, this information may be received in response to a different file (eg, a first JSON file that identifies relatively little information about the list, and then a client computer indicating that it is ready for information). In a separate JSON file).

  The server 110 transmits the text-based information of the upper list to the client computer 150 via the network 295.

  Server 110 further selects and transmits tile 272 from map database 270 based on the location area indicated to the user. Based on the zoom level, the server 110 can retrieve all tiles having a latitude / longitude position indicating that the location area's latitude / longitude boundary is met. Server 110 can also send neighboring tiles to prevent new tiles from being requested if the user pans the map a bit.

  If the client computer receives an indication that it should show a list that exceeds the top list, the client computer prepares to display these lists. For example, according to a Javascript instruction sent by the server 110 but executed by the client computer processor 150, the client parses the JSON file for triggering.

  If the trigger indicates that other results should be displayed, the client computer will display a graphic layer that is displayed between the map layer and the layer used to display the icon for the top list. Create an instance. The client computer also creates a request for an image that represents another result.

  If the client computer is determined to display other lists beyond the top list, the server selects a list that responds to the user's query (such as “pizza”) and reflects the density.

  Server 110 compares lists in different geographic areas of the map area to select the list in proportion to density. For example, the server can analyze the map area using the area cell and select an appropriate area cell level considering the map area. The server selects the appropriate region cell level so that smaller region cells are used when the map is zoomed in, and thus changing the zoom can change the list selected for display. The zoom level can be used as a basis.

  The geographic area with the highest density can be used to determine the amount of listing that will be shown in all of the geographic areas. For example, the server can determine the number of response lists in each cell for each area cell that covers the map area. FIG. 10 shows a map 1010 (represented by a dashed line) divided into nine cells. Here, the number in each cell indicates the number of response lists in the cell. For example, the northwestern part of the map contains 32 response lists, while the center of the map contains 300 response lists.

  Next, the geographic area with the largest number of lists is identified. If each of the area cells is relatively the same size, the area cell with the largest number of lists is the cell with the highest density. Thus, as shown in FIG. 10, the center tile 1020 is identified as having the highest density because it has more lists (300) than another cell in the map.

Based on the most crowded geographic area, a threshold is then calculated for each area. Here, the threshold is used to determine how many lists are shown in the area. For example, one possible expression for calculating such a threshold is:
density_threshold (C) = d * (1 + density (C) / max_density)
And where
C refers to a specific region cell,
density_threshold (C) is the maximum number of lists that will be shown in cell C;
d is a constant used to set the maximum number of lists that can be shown in any cell (can be set automatically or based on visual experiments);
density (c) is the number of lists contained in cell C;
max_density is the number of lists contained in a cell with most lists.

  According to the above formula, the high density area has a higher threshold than the low density area. Since the maximum value is twice that of “d”, this helps to ensure that even the most congested cells are not too dense.

Other formulas can be used to calculate the density threshold. For example, the above equation is
density_threshold (C) = d * (1 + a * density (C) / max_density)
A skew multiplier that changes the range between the highest threshold and the lowest threshold, such as “a” in FIG. By increasing the range, it is possible to make particularly dense areas appear more dense than other areas.

  Once the density threshold for the geographic area is established, the threshold is applied to the list associated with the geographic area.

  One method of applying the density threshold includes selecting a plurality of lists from the cell that are equal to or proportional to the density threshold. For example, if the density thresholds of two cells are 20 and 30, respectively, the 20 lists with the highest score from the first cell can be selected for display, and the score from the second cell is The highest 30 lists can be selected for display.

  Alternatively, the database can parse the score information and query once for the purpose of density, and then query again using the score threshold as part of the query to obtain the actual list. be able to.

  In that regard, a histogram can be created for each region cell associated with a map area. The histogram is filled with the list contained within the cell, and each band of the histogram is associated with a different range of scores. Thus, the highest possible score in the list is 10, the lowest possible score is 1, and scores A = 4, B = 6, C = 7, D = 7, E = 8 in a particular cell. , F = 9, G = 9, if there are seven lists “A”-“G”, the histogram of that cell may have 10 bands representing each possible score. The fourth band may have 10 bands representing each possible score. The fourth band contains list A, the sixth band contains list B, the seventh band contains both lists C and D, and the remaining bands are filled as well.

  After the histogram is filled, the server repeats the histogram from the highest band to the lowest band. This iteration keeps an intermediate result for the number of cells in the band and continues to progress until the intermediate result exceeds the density threshold. Using the above cell example, if density_threshold (Q) = 5, the intermediate result in band 10 is zero, the intermediate result in band 9 is 2 (list F, G), and the intermediate result in band 8 is Since it is 3 (F, G, E) and the intermediate result in band 7 is 5 (F, G, E, C, D), the server stops at the list with score 7.

  Based on the score of the list in the cell and the density threshold of the cell, a threshold based on the score can thus be assigned to the cell. When the above example is used, the density threshold is 5 and there are five lists with a score of 7 or more, so the score threshold of cell Q is 7.

  The list is then re-queried using the score-based threshold and cell identification information. For example, the original query (without location) is used again to retrieve the list, but this time the query identifies both the cell and the minimum score (eg, “has score 9 and is in cell Q, or “All lists of“ pizza ”with score 3 and in cell R, or in cell S with score 9”). This allows the map database to return a list of lists already filtered for density.

  As described above, one system and method for displaying search results based on density includes comparing a list in one area with a list in another area. If the areas do not overlap, artifacts can appear. FIGS. 11-13 show extreme examples for illustrative purposes. As shown in FIG. 11, there are nine cells with a small list and a low density of the outer cells. The inner cell has many lists and is dense.

  FIG. 12 shows where a selected list, such as list 1210, may appear relative to those cell boundaries, such as boundary 1220. Each dot represents the selected list and its position in the cell. FIG. 12 shows how these lists look when drawn on the map. Due to the difference between the list in the center cell and the list in other cells, an unclear outline of the boundary of the center cell may be seen when the list is drawn on the map as shown in FIG. (Eg grid artifacts). Thus, the user may inappropriately conclude that the area stores are clustered within the central square 130 of the map 1320. However, the square shape is a function of the location of the area cell and does not represent the actual geographical feature of the map or its associated list.

  In one aspect of the system and method, the system and method select a list that is displayed to mitigate potential artifacts associated with the geographic area used to determine the density. One possible way to obscure the boundary is to use a smoothing process. The list can be selected not only based on the density of the cells of the list relative to other cells, but also based on the position of individual lists relative to other cells. When such a smoothing process is applied to the list of FIG. 13, the selected list continues to show relative density, but does not show much of the visual artifacts described above. FIG. 14 shows one possible result of applying the smoothing process to the list shown in FIG.

  One technique for performing smoothing is as follows. For each list that is considered to be displayed, such as the list 1510 in FIG. 15, the four cells C0 to C3 that are closest to the list are identified.

  A score threshold for the cell is established. If there is no score threshold (due to missing lists), a score threshold of zero is assigned.

You can also find the center of the cell. If the list 1510 is located within a rectangle 1520 formed by these centers, the score value at the list position can be determined using linear interpolation. For example, if (xL, yL) is the coordinates of the list and (x0, y0) is the coordinates of C0, the equation can be derived as follows:
(1-u) * x0 + u * x2 = xL
(1-v) * y0 + v * y1 = yL
inh = (1-v) * ((I-u) * z0 + u * z2) + v * ((1-u) * z1 + u * z3)
Here, 0 ≦ u <1 and 0 ≦ v <1, and inh is a score threshold.

  The third equation is score thresholds z0,. . , Z3 are used as if they were assigned to the center of the cell. The above three parameter equations should establish a hyperbolic paraboloid sheet (saddle) within the four central rectangles.

If this process is extended to all applicable cells, a continuous plane is obtained that provides a score threshold at any point in the area covered by the cell. From the first two equations, u and v can be obtained.
u = (xL-x0) / (x2-x0)
v = (yL-y0) / (yl-y0)

  The value of inh can be obtained by plugging in the values of u and v into the third equation above. Eventually, if the score of the list is lower than inh, the list is filtered out.

  These smoothed score thresholds can be used to query the database (as described above). In response, the server selects a response list, but this time the selected list has fewer cell artifacts than it appears without smoothing.

  The technique described above filters the list using a form of linear smoothing to remove cell artifacts. However, the system and method are not limited to any particular process. For example, cubic smoothing can be used. Cubic smoothing tends to change the score threshold more at the boundary than at the center, and therefore tends to provide a more visually pleasing result when the density of neighboring cells differs relatively greatly. .

  If another list is selected based on density or the like, the server creates an image of the other list for the location. For example, the server can create a bitmap image 1610 as shown in FIG. In one aspect, the image is sized to be equal to the map area displayed to the user. The server renders an indication of the selected list of maps, such as black dots 1620.

  The dot position corresponds to the geographical location of the list. Thus, the position of the dot 1620 relative to the other list is proportional to the latitude / longitude position of the list relative to the latitude / longitude position of the other list.

  The background of the image can be transparent, such as the background indicated by region 1630. For example, if an image was created in PNG format, pixels not occupied by other list icons (or other indications) are flagged as transparent.

  In another aspect, the overlay image shown in FIG. 16 can be divided into sections that match the map tiles sent to the user.

  Next, another list of overlay images 1610 is sent by the server to the client computer. In one aspect of the system and method, if other list indications are already selected and rendered by the server, the client computer processor does not need to perform any calculations on the list and the position of the list. The system and method can also send a score threshold to a client computer.

  As shown in FIG. 17, the client computer assembles the map and image overlay in a web browser. Overlays are drawn on the top layer of the map so that other lists of indications 1710 appear at their respective positions on the map. Since the background of the overlay layer is transparent, the map tile will show through an area without indication, such as a lake in the area 1720.

  The client computer draws the upper list as the icon 1730 on the upper layer of the map and draws another list. The client computer further provides a text description 1740 of the top list adjacent to the map. As described above, the upper list icon 1730 performs an action in response to a user action and also responds to a user action performed on the text description.

In that regard, FIG.
(A) a graphical indication representing a set of features having a geographical location that is most likely of interest to the user based on the user's query and other factors, wherein the text data provided by the server is represented on the client computer; Graphical indication, icon is displayed by processing
(B) a graphical indication representing another set of features that are less likely to be of interest to the user but still have a geographic location that matches the user's query;
(C) graphical indications of other features selected to represent the relative density of all features as required by the user;
(D) a graphical indication that is pre-rendered as an image by the server so that the client computer can more easily display other features;
(E) a text list of at least some of the features, and (f) a query that includes any word selected by the user compared to the list provided by the server,
Various aspects of the system and method are shown in combinations including:

  In one aspect of the system and method, the client computer is also provided with information that allows interaction with other lists. For example, when a user of a client computer hovers the mouse cursor on the map, the client computer identifies the tile under the mouse cursor and associates it with that tile (or a portion such as a quarter tile under the mouse cursor) Requests for information about other lists submitted can be sent. Accordingly, for each list, the server is associated with each of the other lists in the tile, such as the identification number of the list on the server, JSON-formatted data that identifies the position (in pixels) of the list on the map. Information can be sent. When the user clicks the map, the client computer uses this information to determine whether the user clicked one of the other lists, and if clicked, retrieves and displays further information about the list from the server To do.

  As mentioned above, the system and method are not limited to any particular configuration of servers and databases. Even so, the present system and method are particularly advantageous when used in conjunction with databases and servers that perform separate functions. By way of example only, one server can create a query and return a list, while another server parses the query. In that regard, and as described above, the present system and method allows a second server to requery the first server rather than selecting and reprocessing the list on its own.

  Furthermore, the method need not be divided between the server and the client computer system, as described above. In one aspect of the invention, the server can assemble other lists of images directly on a map and send the other lists of maps and indications as a single composite image.

  It will also be appreciated that the map area being viewed by the user as described above and the map area being analyzed need not be the same. For example, the system and method can analyze tiles and geographic areas that are not currently displayed to the user. Such tiles and geographic areas can also be sent to the client computer to avoid performing a new set of queries and analysis when the user pans the map.

  In fact, one aspect of the present system and method is particularly advantageous as long as the density of the other lists does not change by panning the map (see the description above with respect to FIGS. 7 and 8).

  Most of the alternative embodiments described above are not inconsistent with each other and can be implemented in various combinations to achieve unique advantages. These variations and combinations of the features discussed above, as well as other variations and combinations, can be utilized without departing from the invention as defined by the claims, so the foregoing description of the embodiments is The invention as defined by the claims is to be taken as illustrative rather than limiting.

  The present invention enjoys a wide range of industrial applicability, including but not limited to image mapping systems and methods, and density distribution analysis and mapping techniques.

Claims (16)

A method of providing a map covering an area executed on a computer system comprising a memory having stored instructions and a processor coupled to the memory, the method comprising:
The processor executing the instructions to receive a query , the query having a search term and a search area;
The processor executing the instructions to determine a matching list , the matching list having information corresponding to the search term associated with a geographic location in the search area; The step of asking, including
The processor executing the instructions to divide the search area into a plurality of regions and select a number of lists that match for each region; Splitting and selecting, wherein the selected number is proportional to the density of the matching list in the region;
Said processor executing said instructions to determine a score for each said matching list in a given region;
The processor executes the instructions to determine the match in the given region based on a distance between a geographic location associated with the match list and a location in the given region. Smoothing the score for each list to be performed;
The processor executing the instructions to use the smoothed score for each matching list in the given region, wherein the number of matching lists for the given region is Selecting, using, and
The processor executing the instructions to provide information on the map of the search area and the selected number of matching lists for each of the areas in the search area; How to provide a map to cover.   The method of claim 1, wherein the list has information corresponding to the search term when the list has information that includes the search term.   The method of claim 2, wherein the matching list includes a business list associated with a street address.   The method of claim 1, wherein the search area is determined from the coordinates of a map displayed to the user.   The method of claim 1, wherein the plurality of regions are substantially equal in area.   The information about the selected number of matching lists for each region includes a second map indicating the location in at least one of the selected number of matching lists. the method of. The method of claim 6, further comprising the processor executing the instructions to combine the second map with the map of the search area.   The method of claim 1, wherein the information regarding the selected number of matching lists for each region includes text data regarding at least one of the selected number of matching lists. A system that provides a map that covers an area,
A memory having stored instructions;
A processor coupled to the memory and configured to execute the instructions stored in the memory, thereby
Receiving a query, wherein the query includes a search term and a search area;
Seeking a matching list, wherein the matching list includes a list associated with a geographic location in the search area having information corresponding to the search term;
The search area is divided into a plurality of regions, and the number of lists is selected for each region, where for each region, the selected number of the matching lists is the matching list within the region. Is proportional to the density of
Find a score for each said matching list in a given region,
Smoothing the score for each matching list in the given area based on a distance between the geographic location associated with the matching list and a location in the given area;
Selecting the number of matching lists for the given region using the smoothed score for each matching list in the given region;
A system for providing an area-covering map comprising: a processor for providing information about the search area map and the selected number of matching lists for each of the areas in the search area.   The system of claim 9, wherein the list has information corresponding to the search term when the list has information that includes the search term.   The system of claim 9, wherein the matching list includes a business list associated with a street address.   The system according to claim 9, wherein the search area is obtained from coordinates of a map displayed to the user.   The system of claim 9, wherein the plurality of regions are substantially equal in area.   The information about the selected number of matching lists for each region includes a second map indicating at least one of the locations of the selected number of matching lists. system.   The system of claim 14, wherein the processor is further configured to execute instructions for synthesizing the second map using the map of the search area.   The system of claim 9, wherein the information regarding the number of the selected number of matching lists per region includes text data regarding at least one of the selected number of matching lists.

Images