KR100985450B1 - Local search - Google Patents

Abstract

The system of the present invention receives yellow page data, third-party map provider data, and document data in response to a local search query, and geocodes these data to assign a geographical identifier and one or more addresses in the local search query. Match with. The system of the present invention also indexes the geocoded data to identify business information and location information corresponding to a local search query. The system of the present invention also provides a map and local search results based on the indexed data.

Description

Local search {LOCAL SEARCH}

The present invention relates to information retrieval, and more particularly to identifying local search results.

The World Wide Web (simply referred to as the "web") contains a vast amount of information. However, finding the desired portion of this vast amount of information will require considerable effort. This problem is complicated and cumbersome as the amount of information on the web and the number of users without the experience of web searching increase rapidly.

The search system attempts to return hyperlinks to web pages of interest to the user. In general, a search system is based on a determination of the user's interest in a search term entered by the user (called a "search query"). The purpose of a search system is to provide a user with links to search results (eg, web pages) of high quality and appropriately based on the search query. Typically, a search system completes a task by matching a search term in a search query to a corpus of web pages previously stored. The web page containing the user's search term may be referred to as a "hit" or a "search result" and may be provided as a link to the user.

Local search systems attempt to provide relevant web pages and / or business listings within a particular geographic area. In some countries, detailed address information may not be available for certain businesses. Thus, it may be difficult to perform a local search.

According to a feature of the invention, the method of the invention comprises the steps of: receiving, in response to a local search query, yellow page data, third party map provider data, and document data, yellow page data, third party map provider data; And geocoding one or more of the document data, assigning a geographic identifier to one or more addresses in the local search query, and matching the one or more addresses in the local search query. The method also includes indexing the geocoded data to identify business information and location information corresponding to a local search query, and based on the identified business information and location information. Providing search results and third-party maps.

According to another aspect, a method of geocoding based on a local search query includes receiving third party map provider data and yellow page data, generating an address based on a local search query, and parsing the address. Processing, identifying at least a portion of the address by finding the longest matching prefix in the address, and finding a combination within the address to verify that the address is correct.

According to another aspect, a method of indexing based on a local search query includes: preprocessing yellow page data in a predetermined format, extracting business information from document data, storing the business information in a repository, Indexing the address information from the third party map provider data. The method also includes clustering yellow page data and third party map provider data, and highlighting snippets in the document data. In the case of point location, the method includes setting a search distance for the local search query to a predetermined distance. For bound location, the method includes setting the search distance to an approximate maximum distance from the center of the border area location to the corner of the border area location.

According to another aspect, the method of the present invention comprises the steps of creating a synonym list related to a local search query, rewriting the local search query to expand the query, and generating a local search result based on the expanded query. Obtaining a map from third-party map provider data based on the local search results, and creating an advertisement based on geographic information related to the local search results.

According to another feature, the system of the present invention receives third-party map provider data, yellow page data and document data, preprocesses the yellow page data to determine business information, extracts information from the document data, and retrieves a local search. An indexer for identifying the location information in the query and the index address data of the third party map provider data. The system also includes a geocoder for receiving information from the indexer and assigning a geographic identifier, receiving information from the geocoder, rewriting local search queries, and mapping from third-party map provider data. And a front end server for generating a local search result based on the local search query.

According to yet another aspect, a system of the present invention includes means for receiving yellow page data, third party map provider data, and document data in response to a local search query, and yellow page data, third party map provider data. And geocoding means for geocoding one or more of the document data, assigning a geographic identifier to one or more addresses in the local search query, and matching the one or more addresses in the local search query. The system also includes means for indexing geocoded data to identify business information and location information corresponding to a local search query; And means for providing a local search result and a third-party map based on the identified business information and location information.

According to yet another aspect, a system of the present invention includes a memory for storing a plurality of instructions; And a processor for executing instructions in the memory. The processor identifies a location associated with the local search query, identifies local search results related to the local search query and associated with the identified location, identifies an identifier for each of the group of local search results, and maps a third party. From the provider, perform the operation of receiving a map associated with the identified location. The map identifies the location of one or more local search results within a group of local search results.

According to another aspect, the method of the present invention includes receiving a local search query, identifying a location associated with the local search query, and receiving a series of search results associated with the identified location and associated with the local search query. Identifying and identifying an identifier for each of the group of search results. The method also includes providing an third party map provider with an identifier for each of the group of search results; And receiving, from a third party map provider, a map associated with the identified location, the map identifying the location of one or more search results within the group of search results.

According to another aspect, the method of the present invention comprises the steps of: creating a list of tokens, identifying a potential address in a web document, and determining whether the possible address includes a token associated with a city Parsing the possible addresses from the beginning in order to do so. The method also includes further parsing the possible address to determine whether the possible address includes a token associated with the district, and the longest possible address within the next possible address of the token associated with the city or the token associated with the district. Identifying a longest-matching token, and determining whether a possible address is a real address based on the token associated with the city, the token associated with the district, and the longest matching token identified.

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate one or more embodiments of the invention and, together with the description, describe features of the invention.

1 is a view schematically showing an embodiment disclosed herein.

2 is a diagram illustrating an example of a network in which the systems and methods disclosed herein may be implemented.

3 is a diagram illustrating an example of a client or server in the network of FIG.

4 is a functional block diagram illustrating an example of a system for identifying local search results and providing a map associated with an identified location.

5 is a diagram illustrating an example of an index / document repository of the system of FIG. 4.

6 is a diagram illustrating an example of a geocoder of the system of FIG. 4.

7 is a diagram illustrating an example of an indexer of the system of FIG. 4.

8 is a diagram illustrating an example of a front-end server of the system of FIG. 4.

9 is a diagram illustrating an example of a map created by the system of FIG. 4 and an area search result.

10A-10D are flowcharts illustrating an example of a process for identifying local search results and providing a map associated with an identified location.

DETAILED DESCRIPTION The following detailed description of the invention refers to the accompanying drawings. Like numbers refer to like elements throughout. In addition, the following detailed description does not limit the invention.

In some countries, such as China, map data and yellow page data cannot be obtained from a single provider and must be obtained from several different providers. Because of export restrictions, it may not be possible to obtain detailed map data to represent a map of a given area or to obtain the actual latitude and longitude of an address within that area. As such, address approximation can be used for geocoding the address. When results from a local search are provided to the user, the local results page may include a list of relevant results and a pointer to a server (third party) of the map provider. The map provider may play a role in generating a map displayed to the user.

summary

Embodiments of the invention may identify local search results and generate a map associated with the identified location. For example, in one embodiment, as shown in FIG. 1, the system receives a local search query entered by a user and identifies a location associated with the received local search query. )can do. The system may identify a series of local search results (eg, search result "A" through search result "H") that may be related to a local search query and that may be related to the identified location. The local search results may include links to documents that may be related to local search queries. The system can identify an identifier for a group of local search results and provide this identifier to a map provider. The system can receive a map associated with the identified location from a map provider. The map may identify the location of one or more search results (eg, search result “A” shown in FIG. 1) within a group of local search results.

The term "document" as used herein is to be broadly interpreted as encompassing all machine-readable or machine-storable workpieces. Such documents may include, for example, emails, files, combinations of files, one or more files with links embedded in other files, news group postings, blogs, web advertisements, and the like. With regard to the Internet, a general document is a web page. The web page may include textual information and may include embedded information (eg, meta information, images, hyperlinks, etc.) and / or embedded instructions (eg, JavaScript, etc.).

As used herein, the term "link" should be construed broadly to include references to other documents or to all references to other parts of a document.

Configuration example of network

2 illustrates an example of a network 200 that may implement a system and method in accordance with the present invention. In the network 200, a plurality of clients 210 are connected to a plurality of servers 220-240 via a communication network 250. In FIG. 2, for the sake of simplicity, two clients 210 and three servers 220-240 are shown connected to the communication network 250. In practice, there may be more or fewer clients and servers. Also, in some cases, the client may perform one or more functions of the server, and the server may perform one or more functions of the client.

The client 210 may include a client entity. An entity may be a device such as a personal computer, a wireless telephone, a personal digital assistant (PDA), a laptop computer, or another kind of computing or communication device, a thread running on one of these devices, or It may be defined as an object executable by a process and / or one of these devices. Servers 220-240 may include server entities that collect, process, retrieve, and / or manage documents.

In one embodiment, server 220 may include a local search system 225 that may be used by client 210. The server 220 may crawl a corpus of documents, index the documents, and store information related to the documents in a repository, which is a storage location of the documents. Regardless of how the servers 220-240 are combined, a local search system 225 may be implemented to identify local search results and provide a map related to the identified location.

Although servers 220-240 are shown as separate entities, one or more servers 220-240 may perform one or more functions of one or more other servers 220-240. For example, two or more servers among the servers 220-240 may be implemented as a single server. One of the servers 220-240 may be implemented as two or more separate (possibly distributed) devices.

The communication network 250 may include a local area network (LAN), a wide area network (WAN), a telephone network such as a public switched telephone network (PSTN) or a cellular network, an intranet, or the Internet. (Internet), or a combination of these networks. Clients 210 and servers 220-240 may be connected to communication network 250 via wired, wireless and / or optical connection media.

Example of Client / Server Architecture

3 illustrates an example of a client or server entity (hereinafter referred to as a "client / server entity") that may correspond to one or more clients 210 and servers 220-240. The client / server entity may include a bus 310, a processor 320, a main memory 330, a read only memory (ROM) 340, a storage device 350, an input device 360, an output device 370, And a communication interface 380. Bus 310 may include a path that enables communication between components of a client / server entity.

Processor 320 may include a processor, a microprocessor, or processing logic capable of interpreting and executing instructions. Main memory 330 may include random access memory (RAM), or another type of dynamic storage device capable of storing information and instructions for execution by processor 320. ROM 340 may include a ROM device or other type of static storage device capable of storing static information and instructions for use by processor 320. The storage device 350 may include a magnetic and / or optical recording medium and a corresponding drive.

Input device 360 is a mechanism that allows an operator to enter information into a client / server entity and may include a keyboard, mouse, pen, voice recognition and / or biomechanical mechanism, and the like. The output device 370 is a mechanism for outputting information to an operator and may include a display, a printer, a speaker, and the like. The communication interface 380 may include any transmit and receive mechanism as long as it enables the client / server entity to communicate with other devices and / or systems. For example, communication interface 380 may include a mechanism for communicating with another device or another system, such as via communication network 250.

The client / server entity may perform certain operations, which will be described in detail later. The client / server entity may perform this predetermined operation in response to the processor 320 executing software instructions contained in a computer readable medium, such as memory 330. Computer-readable media may be defined as physical or logical memory devices and / or carrier waves.

Software instructions may be entered into the memory 330 from another computer readable medium, such as data storage 350, or from another device via communication interface 380. The software 320 included in the memory 330 allows the processor 320 to perform the process, which will be described later. In addition, hardwired circuitry may be used in place of or in conjunction with software instructions to implement the processes (processes) disclosed herein. Embodiments of the invention are not limited to any particular combination of hardware circuitry and software.

Local Search System Example

4 is a functional block diagram illustrating an example of a system (eg, local search system 225) for identifying local search results and providing a map associated with an identified location. According to one embodiment, one or more functions of local search system 225 may be a combination of a server (eg, server 220), a portion of server 220, and servers 220-240, as described below. It can be performed by. According to another embodiment, one or more of these functions may be performed by a computer associated with an entity that is separate from the server 220, such as a client 210, a server 220, or one of the servers 230 or 240. .

As shown in FIG. 4, local search system 225 may include map provider data 400, yellow page data 405, web document data 410, index / document repository 415, addresses, and points of point of interest. interest (point of interest) identification (420), address fingerprint (FP) and POI ID mapping information (425), geocoder (430), indexer (435), front end The server may include a front end server 440, map uniform resource locator information 445, and a local search result 450. Map provider data 400, yellow page data 405, and web document data 410 may be provided to indexer 435. Map provider data 400 may be used to obtain address / POI ID information 420 and address FP and POI ID mapping information 425. Indexer 435 may be connected to index / document repository 415 and geocoder 430. The address / POI ID information 420 may be provided to the geocoder 430. The front end server 440 may be connected to the geocoder 430 and the index / document repository 415 and may receive address FP and POI ID mapping information 425. The front end server 440 may generate the map URL information 445 and the local search result 450. Local search system 225 may optionally include other connections and / or component interrelationships, not shown in FIG.

In general, geocoder 430 receives address / POI ID information 420 and / or information from indexer 435, assigns geographic identifiers (eg, location, coordinates, etc.) to objects, The output can be provided to the front end server 440. The indexer 435 receives the map provider data 400, the yellow page data 405, and / or the web document data 410, preprocesses the yellow page data 405 to store business information. Extract business information from the web document data 410, identify location information in the search query, index the address data of the map provider data 400, index / document repository 415, and / Alternatively, the output may be provided to the geocoder 430. The front end server 440 receives address FP and POI ID information 425, information from the geocoder 430, and / or information from the index / document repository 415 and rewrites the search query ( and generate map URL information 445, local search results 450, and / or geographic information for use by an ad server (not shown).

Map Provider Data ( Map Provider Data )

There are two types of data for Chinese address information: map data and yellow page data. The map provider data 400 may include various kinds of information. For example, in one embodiment, a third party map provider may be a series of POIs (e.g., businesses and other points of interest such as art galleries, parks, hospitals, schools, etc.), and the addresses of these POIs for various cities in China. Can be provided. For each POI, there may be associated POI ID information. Due to legal restrictions, the map provider may not be able to provide latitude and longitude information for each POI. However, the map provider can divide the map into grids (e.g., three hundred meters by three hundred meters grids) and provide a grid index and program for each POI, thereby providing distance between grids. Can be calculated. The map provider data 400 may be updated periodically (eg, daily, weekly, monthly, etc.), and each time an update is made, the POI ID may be changed.

In another embodiment, map provider data 400 may include: (1) a normal POI, which may include a business name, address, phone number, and a grid index; (2) a road POI, which may include a street name and a grid index for the center of the street; And / or (3) postal code POI information, which may include a predetermined postal code and a grid index of an approximate center of the postal code.

In another embodiment, there may be a problem with map provider data 440. For example, map provider data 400 may include only a portion of the address and no other portion. Due to regulations in China, in map provider data 440, for example, there may be no street number (eg, only 20% -30% of POI may have a street address). Thus, map provider data 400 may include only street names of the POIs or may include some high level abstractions. In addition, some of the POIs of map provider data 400 may not have telephone numbers. In addition, the address provided by the map provider data 400 may be in an inappropriate format.

yellow  Page data ( Yellow Page Data )

Yellow page data 405 may include a variety of information and may be received from multiple sources (eg, third party providers). For example, in one embodiment, yellow page data 405 may include addresses for POIs (eg, county, city, province) and / or phone number information, business name, email address, It can include a facsimile number, website address, CEO name, business descriptions, categories based on SIC, and business type. In other embodiments, yellow page data 405 may not include latitude and longitude information at all. As a result, complete (or substantially complete) information about the POI (eg, address, phone number, map location information) can be inferred from the map provider data 400 and the yellow page data 405.

Web document data ( Web Document Data )

The web document data 410 may include various kinds of information. For example, in one embodiment, web document data 410 may include email, files, combinations of files, one or more files with links embedded in other files, newsgroup postings, blogs, web advertisements, the web. Pages (which may include textual information and may include embedded information (eg, meta information, images, hyperlinks, etc.) and / or embedded commands (eg, JavaScript, etc.) Business information (eg, address, telephone number, etc.). Web document data 410 may also include documents found based on local search queries.

address/ POI ID  Information

The address / POI ID information 420 may include various kinds of information. For example, in one embodiment, the address / POI ID information 420 may include an address extracted from the map provider data 400, a POI ID extracted from the map provider data 400, and the like. In another embodiment, the address / POI ID information 420 may include, as information related to a Chinese address, address data provided by the map provider data 400 (eg, address of POI, center of distance); POIs (eg, schools, parks, buildings, hospitals, etc.); Postal code center (ie, the center of the area included in the postal code); Additional cities, which may not be included in the list provided by map provider data 400, and the like.

address FP  And POI ID Mapping  Information

The address FP and POI ID mapping information 425 may include various kinds of information. For example, in one embodiment, the address FP / POI ID mapping information 425 may include mapping between address fingerprints and a corresponding POI ID. The mapping between the address fingerprint (FP) and the corresponding POI ID may be used by the front end server 440 to look up the POI ID for each local search result. This will be described later in detail. In another embodiment, the POI ID may be derived directly without a mapping between the address FP and the corresponding POI ID. In such an embodiment, the address FP / POI ID mapping information 425 may include a directly derived POI ID.

Although the example of the information included in the map provider data 400, the yellow page data 405, the web document data 410, the address / POI ID information 420, and the address FP / POI ID mapping information 425 has been described. In other embodiments, additional or other information regarding the address that may be used to identify local search results may be included in the example of the information.

5-8 show examples of some components within the local search system 225 of FIG.

Index / Document Repository ( Index Of Document Repository )

Index / document repository 415 may be installed in a single storage device (eg, main memory 330, ROM 340, and / or storage device 350). As shown in FIG. 5, the index / document repository 415 may store various information related to the document, the yellow page data 405, and / or the map provider data 400. For example, in one embodiment, index / document repository 415 may include, as information related to an address in Chinese, address data provided by map provider data 400 (eg, address of POI, distance center); POIs (eg, schools, parks, buildings, hospitals, etc.); Postal code center (ie, the center of the area included in the postal code); Information such as additional cities that may not be included in the list provided by the map provider data 400 may be stored.

In another embodiment, as shown in FIG. 5, the index / document repository 415 may include the [province] field 500, the [city] field 510, the [district] field ( 520), a [street] field 530 (which may additionally or alternately include an address field and / or a POI name field). The example shown below may correspond to Chinese address information stored in the index / document repository 415.

BeiJing City [XiCheng District] [BeiLiShi Road];

([Beijing City] [Shicheng District] [Beijing City Street])

[BeiJing City] [HaiDian District] [YiHeYuan Road 5 Number];

([Beijing City] [Heidiian District] [Iheyuan Street 5])

[BeiJing City] [HaiDian District] [BeiJing University];

([Beijing City] [Heidiian District] [Beijing University])

[JiangSu Province] [NanJing City] [GuLou District] [HanZhong Road]

([Jiangsu Province] [Nanjing City] [Gurogu] [Hanjong Street])

In yet another embodiment, the index / document repository 415 may include an address fingerprint (FP) field 540 and an FP accuracy field 550. Each address may be treated as a point by the geocoder 430 using address FP and FP accuracy (eg, the building will have a higher FP accuracy than the center of the street). The address FP may be a fingerprint generated based on an address (e.g., a hash value that can be generated based on that address) that can be used to look up the POI ID to represent an accurate map. Can be. For example, the FP generator 570 receives an address (eg, [province] field 500, [city] field 510, [district] field 520, [street] field 530, etc.). Based on this address, an address FP (eg, [FP] field 540) and an FP accuracy (eg, [FP accuracy] field 550) can be generated. Address FP and FP accuracy may be used by the POI ID lookup table 580 (eg, using local search results) to look up the POI ID for displaying an accurate map. FP generator 570 and / or POI ID lookup table 580 may be provided within geocoder 430, indexer 435, or front end server 440.

In yet another embodiment, index / document repository 415 may include a [zcode] field 560 associated with the address. The zcode may include a code such as a postal code and, in the case of China, may be calculated from a six-digit administrative code for the district in China. Locations such as JiangSu Province, BeiJing City, BeiJing City XiCheng District, etc., are geocoder 430 as bounds that include all point locations within them. Can be calculated by

To improve recall, various addresses can be determined and stored in the index / document repository. For example, single character synonyms for provinces and cities can be identified (eg, Shanghai City-> Lu; HeBei Province-> Qi]. Additionally or alternatively, the address portion may be omitted (eg, Shanghai City-> Shanghai; HaiDian District-> HaiDian; HuaiHai Central Road-> HuaiHai Road). Additionally or alternatively, for famous places there may be synonyms (eg, Shanghai City Temple-> Old City Temple; LiuRong Temple-> LiuRong Ta).

5 illustrates an example of information included in index / document repository 415, but in other embodiments, index / document repository 415 may include any information as long as it can be used to identify local search results. Can be.

Geocoder ( Geocoder )

As shown in FIG. 6, the geocoder 430 may perform various operations to help identify a local search result. For example, in one embodiment, geocoder 430 may assign a geographical identifier (eg, location, coordinates, etc.) to objects. For example, geocoder 430 may match an address to an address in index / document repository 415. The output from the geocoder 430 can be used for various purposes. For example, yellow page data 405 may be parsed to determine business information (eg, address, phone number, email address, facsimile number, business hours, etc.) for the POI. Business information may be extracted from the web document data 410 and / or location information provided in the search query may be identified.

In order to index the yellow page data 405, the indexer 435 needs to look at the Chinese address and determine the map position, but there are many problems with this. For example, it is not easy to use accurate location and detailed address information for most of the addresses in China. Chinese addresses do not have a properly defined format and hierarchy. Possible components of a Chinese address include city, district, town, village, village, street, street, street number, and building. Can be. Yellow page data 405 may be free in its format, particularly in rural areas (eg, does not conform to any particular format or form), and for some POIs, the corresponding address component may not be available. . Give an example of a Chinese address.

ShenZhen City HeGang Town AnLiang Village AnLiang Road 172 Number JingCheng Building;

ShenZhen City LongHua Town MingZhiMingLe Office Complex;

ShenZhen City FuHong Road ShiMao Square Block A 17 Floor; And

Beijing City HaiDian District SiJiQingXiaoFu.

The geocoder 430 may optimally match the address in the yellow page data 405 with the address provided in the map provider data 400 to obtain the most accurate map location possible. The geocoder 430 may include an address list generator 600, a parser 610, a longest matching prefix locator 620, a combination locator 630, and a query geocoding unit. ) 640 and the like. The components of the geocoder 430 may perform many tasks for each address (eg, ShenZhen City HeGang Town AnLiang Village AnLiang Road 172 Number JingCheng Building).

The address list builder 600 may receive the map provider data 400 and the yellow page data 405, and from the map provider data 400 and / or the yellow page data 405, the province, the city. A list of addresses (called "tokens") can be created based on a city, district, street name, address, POI name, or a combination thereof. For each address, the parser 610 makes an attempt to parse the city from the beginning of the address. For example, "ShenZhen City" from the address may be parsed by parser 610. The parser 610 may parse the district from the address. For example, since there is no district in the example of the address described above, parser 610 will not be able to parse the district from the address.

The longest matching prefix locator 620 of the geocoder 430 may be used to locate another portion of the address. For example, longest matching prefix locator 620 attempts to find the longest matching prefix (eg, token) from the address list. However, this operation will fail if there are no specific tokens in the address list (eg, there is no "HeGang Town" in the address list). The longest matching prefix locator 620 will proceed to the end of the word "Town" if the word "Town" is included in the address list. When there is an entire token (eg, "HeGang Town AnLiang Village AnLiang Road") in the address list, the longest matching prefix locator 620 may identify the token as a good match (eg, "HeGang Town" as a good match). Can be identified). Longest matching prefix locator 620 attempts to find the longest matching prefix (eg, token) again from the address list. If this fails, the longest matching prefix locator 620 may proceed to the end of the word "Village" if the word "Village" is present (eg, "AnLiang Village"). The longest matching prefix locator 620 may repeat the process (process) to find the longest matching prefix (eg, token) again from the address list. In this case, the longest matching prefix locator 620 may attempt to match the street name (eg, "Road" or "Street"). The longest matching prefix locator 620 may proceed to the end of these words "Road" or "Street" if these words "Road" or "Street" are present (eg, "AnLiang Road"). Longest matching prefix locator 620 may also proceed to the end of this word "Number" if the word "Number" is present (eg, "172 Number"). Finally, the longest matching prefix locator 620 may attempt to find the longest matching prefix (eg, token) from the POI name. This can provide matching for names of buildings, schools, parks, and the like (eg, "JingCheng Building").

The combination locator 630 finds the location of a particular combination, first finding the POI name, then finding the various levels of address, and finally finding the district or city. By this locating arragement, it can be ensured that most specific addresses can be obtained by the combinatorial locator 630. For example, the combination locator 630 may find an example of the following combination.

City + district + POI name;

Address found by city + district + longest matching prefix locator 620 (eg, "Road" or "Street")

Address found by city + district + longest matching prefix locator 620 (eg, "Village")

Address found by city + district + longest matching prefix locator 620 (eg, "Town")

City + district; And / or

city

If a local search query is entered by the user, the location part of the search query may be sent to a map server owned by the map provider. If the location query contains Chinese, Japanese, or Korean (CJK) characters, the map server can send the query to a query geocoding unit 640 for geocoding to be done. . If the location entered by the user is not clear (eg, when the score of the first result from the geocoder is less than twice the score of the second result), the query geocoding unit 640 may make a suggestion to the user. have. For example, if the location query is "History Museum", the query geocoding unit 640 may be "Do you want to look for TianJian City HeDong District History Museum, or ShangHai City PuDong District ShangHai History Museum You can make a suggestion that asks, "Do you look for a history museum in Hedong-gu, Tianzien City or a Shanghai history museum in Pudong-gu, Shanghai?"

The query geocoding unit 640 may calculate a score of the search result based on a number of points within the search result location. For example, if ChangChuan City Yang District has a smaller score than Beijing City ChaoYang District, Beijing City ChaoYang District may be displayed if the user's query location is "ChaoYang District." have.

6 shows an example of the work performed by the geocoder 430, but in other embodiments, the geocoder 430 may perform additional or other work that may be used to identify local search results. In addition, although FIG. 6 shows that the components of the geocoder 430 are interconnected, in other embodiments, the components of the geocoder 430 may be separate, non-interconnected components.

Indexer ( Indexer )

The indexer 435 may perform a number of tasks to help identify local search results, as shown in FIG. 7. For example, in one embodiment, indexer 435 preprocesses yellow page data 435 to determine business information (eg, address, phone number, email address, fax number, business hours, etc.) for the POI. preprocess, extract business information from web document data 410, and / or identify location information within a search query. The indexer 435 may include a map data indexer 700, a yellow page data preprocessor 710, a business information extractor 720, a distance flattener 730, a clusterer 740, and a business information repository 750. ), A snippet highlighter 760, and the like.

Map data indexer 700 may index address data from map provider data 400, which may include map location information. Geocoder 430 makes an attempt to geocode the address again based on the indexed address data. The clusterer 740 (described below) may set the cluster position if the cluster position is different from the given position, but above a predetermined distance threshold (eg, within 3 kilometers). You cannot set the cluster location. Such a configuration can be used to improve clustering. This will be described later in detail.

The yellow page data preprocessor 710 may receive yellow page data 405 from various providers, and may preprocess the yellow page data 405 in a common format. Such formatted data may be provided to the geocoder 430 during the indexing process. Geocoder 430 may make an attempt to geocode an address. If the address can be geocoded up to the building or street level, the address can be indexed as a normal entry. If the address can be geocoded at the city or district level, the address can be indexed as an entry with an approximate position. During the scoring process, entries can be treated as if they are 20 kilometers or more from the center (must have a low level score). If the address cannot be geocoded, the address can be treated as an entry without a location. In the indexing process, an entry without a location is clustered with another entry, and the entry can remain. Otherwise, the entry will be discarded.

Business information extractor 720 may extract business information (eg, address and phone number) from web document data 410 using various techniques. This technique can be changed according to different formats of address and phone number in China and Japan.

For example, as a first technique, business information extractor 720 may include a classifier capable of analyzing a document having an address to determine business information associated with an address based on a statistical model. Can be. The document analyzed by the classifier may include a document with an address without corresponding yellow page data 405 and / or a document with an address with incorrect yellow page data 405. The function performed by the classifier may vary depending on whether the business information corresponds to mutual (title) information or telephone number information. Another function may be performed when the business information includes information other than the mutual information or the telephone number information. The trade name (title) can be identified by interpreting terms near the address and determining the likelihood that each term will be part of the title. A confidence score may be assigned to each candidate title that is identified.

A telephone number can be associated with an address by identifying a series of candidate telephone numbers in the document. Based on the statistical model, if each candidate phone number has a window of terms near the candidate and candidate phone numbers associated with the previous candidate phone number (eg, looking up a predetermined number of terms left / right), the address Can be determined. Confidence scores can be assigned to candidate phone numbers based on their determined probabilities. Optionally, an optimal phone number for that address can be determined. The telephone number is then associated with the address to compose or supplement the business listing.

As a second technique, business information extractor 720 may include a location extractor that may be included as part of a search engine. The location extractor may receive a search query and determine whether the search query includes a geographic reference. If the search query includes a geographic criterion, the location extractor may separate the geographic criterion from the search term in the query and then provide it to the local search engine. If the search query does not include geographic criteria, the location extractor may provide the search term to a web search engine, which may include a conventional web search engine that returns a series of documents related to the search query. The local search engine may include a dedicated search engine, such as a business list search engine. The local search engine may receive, from the location extractor, the geographical criteria of search terms and search queries from the location extractor. The local search engine may identify a set of documents (ie, documents containing a set of search terms of the search query) that match the search query by comparing the search terms to documents in the document corpus relating to the geographic area associated with the geographic criteria. The local search engine may score the identified documents, sort them based on their scores, and then output them as a list of search results.

The location extractor may determine unambiguous addresses (eg, cities) in the search query by setting the variable i to 1 and performing a search for the city name of each city [city (i)] in the city list. Can be. The number of search results for this search may be counted as countcity. A search for a city name may also be performed with the name of the corresponding province. The number of search results for this search may be counted as countcity / province.

It may be determined whether countcity / province is greater than or equal to X% of countcity (where X is a number greater than zero). If couuntcity / province is at least X% of countcity, the city may be considered an "unambiguous city." By "obvious city" is meant a city with a name that can be used alone in a search query, and it will be understood that the user does not intend anything other than the city. If countcity / province is not at least X% of countcity, it may be determined whether any more cities are on the list. If more cities are on the list, the variable i is incremented by one, and the next city in the list can be evaluated.

The documents of the search results can be analyzed to identify any postal codes that these documents contain. Postal codes can be identified using pattern matching techniques and verified by comparing the postal codes to a list of postal codes. It may be determined whether the postal code corresponds to the postal code associated with city (i). The number of documents containing the postal code associated with city (i) can be counted as countpostal. It may be determined whether the countpostal is greater than or equal to X% (eg, 5%) of countcity. If countpostal is greater than or equal to X% of countcity, the city may be considered to be an explicit city.

As a third technique, business information extractor 720 may identify geographically relevant documents. Geographically relevant document, as used herein, includes any document that, in some manner, may be determined to have a particular association with a geographical location. A business list (eg, a yellow page list) may be considered to be a geographically relevant document related to the geographic area defined by the business's address. Other documents, such as web documents, may also have specific geographic relevance. For example, a business may have a home page, may be the subject of a document describing or evaluating the business, and may be referred to by a web page associated with the business in some other way. The particular geographic location with which the document is associated can be determined in many ways, such as a postal address or other geographic indication.

Geographic regions associated with geographically relevant documents may be mapped to corresponding location identifiers. Additional location identifiers may be specified for the document. In particular, a location identifier corresponding to the peripheral area within the predetermined area may also be determined. Each geographically relevant document may be indexed as if including a location identifier associated with the region of the document and the identified surrounding region.

7 shows that business information extractor 720 is a component of indexer 435, in other embodiments, business information extractor 720 may be separated from indexer 435. In order to ensure that a set of composite documents can be used in the indexing process, information extracted by the business information extractor 720 may be provided in the business information repository 750. The business information repository 750 may include a variety of information, for example, a document from which business information is extracted by the business information extractor 720. The business information repository 750 may be provided in the indexer 435 with the extracted business information. Although FIG. 7 shows the business information repository 750 as a component of the indexer 435, in other embodiments, the business information repository 750 may be separate from the indexer 435.

Distance flattener 730 may set a search radius or distance for a local search query. For example, in one embodiment, each local search query may be geocoded at a specific location by geocoder 430. Each location may be a point location (eg, building, famous tourist place, school, street center, etc.) or a boundary area location (eg, district, city, castle, etc.). For point locations, distance flattener 730 may set the search radius to a predetermined distance (e.g., approximately 5 kilometers around that point). For boundary region locations, distance flattener 730 may set the approximate maximum distance from the center of the location to the corner as the search radius. Scores of search results within a set of zcodes associated with a location (eg, a set of zcodes constituting that location). In this way, if a user searches near a district name, the top results will be within that district.

The clusterer 740 may cluster the map provider data 400 and the yellow page data 405 together. Many map provider data 400 may be accurately displayed on a map by including accurate location information, but may not include detailed address or phone number information (eg, include an address without a street address or May not exist). The yellow page data 405 may include detailed address and phone number information, but may not include accurate location information. For example, map provider data 400 may include a source (eg, map provider), a title (eg, "Beijjing University"), an address (eg, "Beijing City HaiDian District YiHeYuan Road"), and / or a POI ID (map Display) (eg, "A1234567"). In this regard, yellow page data 405 may include a source (eg, yellow page data provider), a title (eg, “Beijjing University”), an address (eg, “Beijing City HaiDian District YiHeYuan Road 5 Number”), and / or It may include a telephone number (eg, "010-62752114"). When these entries are clustered by the clusterer 740, the front end server 440 can provide the user with the correct location on the map as well as detailed address and phone number information.

The location obtained by geocoding an address from the yellow page data 405 (eg, by geocoder 430) may be an approximation, and may be located far from the exact location provided by map provider data 400. Can be. In this case, the same businesses provided from two providers may be located in many different locations and thus may not be clustered with each other by clusterer 740. As a solution to this, it may include processing to geocode (eg, by geocoder 430) the address from the map provider data 400 to the cluster location. The cluster location may be used for neighbor generation and clustering by the clusterer 740. The actual location provided by the map provider data 400 may be used for map display.

Snippet highlighter 760 may highlight snippets in a document (eg, a web document). Snippet highlighting of web documents is typically accomplished by term offsets within the document. Because CJK (Chinese, Japanese, Korean) documents have terms that are counted differently from other languages (for example, they do not use spaces as delimiters, and you may need to split long paragraphs of text to obtain the term). In order to emphasize a specific term, it is possible to segment the entire document to obtain a corresponding term, but it is not efficient. However, snippet highlighter 760 may store byte offsets instead of term offsets to identify addresses or phone numbers (or some other business information) within web documents during indexing. Snippet highlighter 760 may use the byte offset to perform highlighting and does not need to perform segmentation. Although FIG. 7 shows snippet highlighter 760 as a component of indexer 435, in other embodiments, snippet highlighter 760 may be detached from the indexer or in another component (eg, a front-end server). 440].

7 illustrates an example of the operation performed by indexer 435, but in other embodiments, indexer 435 may perform additional or other tasks that may be used to identify local search results. In addition, although FIG. 7 illustrates that the components of the indexer 435 are interconnected, in other embodiments, the components of the indexer 435 may be separated and not interconnected.

Front-end server ( Front End Server )

As shown in FIG. 8, front-end server 440 may perform a variety of tasks to aid in the identification of local search results. In one embodiment, the front end server 440 may include a query rewriter 800, a local search generator 810, a map generator 820, a geographic information generator 830, and the like. Although FIG. 8 shows an example of the work performed by the front end server 440, in other embodiments, the front end server 440 may be further or otherwise capable of being used to aid in the identification of local search results. Can be done.

In one embodiment, the query rewrite 800 may perform various tasks. For example, because the number of web document clusters may be much smaller in Chinese data than in English data, matching in title or category may be used to obtain valid results. Also, in Chinese, there may be several synonyms that mean the same term. For example, the term "restaurant" (restaurant) may have several synonyms in Chinese. In addition, different providers of yellow page data 400 may use different names to represent the same category. In order to provide the maximum recall for the search query entered by the user, the query rewrite 800 may create a synonym list for each category. The query rewrite 800 may rewrite each local search query to expand the query into a pair of search terms that may be combined by an "OR" (logical sum) operand.

The local search generator 810 may generate a local search result 450. For example, local search generator 810 may generate results corresponding to relevant web pages and / or business listings within a particular geographic area based on address information obtained and processed by local search system 225. Can be. Local search results 450 may be displayed (eg, to a user entering a local search query) on a display (eg, output device 370).

The map generator 820 may generate a map related to the local search result 450. For example, to display a map for local search results, map generator 820 may construct an iframe (i.e., a floating frame embedded within a web page) on the search results page. And post action against the URL provided by the map provider. The parameters in the post may include the following fields for each search result. That is, it may include a title, address, phone number, POI ID (to indicate a point on the map), and an accuracy field. Locations that can be geocoded up to the building level can be marked with accuracy on the map by the map generator 820. Locations that can be geocoded up to a distance level (or some higher level abstract portion) may be marked as estimated on the map by the map generator 820. 9 shows how these two levels of accuracy can be distinguished on a map 900 generated based on a local search result 910. For example, accurate locations 920 may be identified by one marker color (eg, green), and estimated locations 930 are identified by another marker color (eg, red). Can be. Although two levels of accuracy (accurate and estimated) are shown in FIG. 9, additional levels of accuracy may be used in embodiments according to the invention.

In the indexing process by the indexer 435, the fingerprint of the address (eg, address FP 540) may be stored along with the associated accuracy (eg, FP accuracy 550). The mapping between the address fingerprint and the POI ID (eg, address FP / POI ID mapping information 425) may be used by the map generator 820 to examine the POI ID for each search result. The POI ID is used by the map generator 820 to identify a location on the map (eg, map 900) for the map provider, allowing the map provider to indicate the location on the map provided in the results page.

In order to display local ads (ads) in China, geographic information generator 830 may provide geographic information to ads server 840 in a variety of ways. For example, in one embodiment, a province or self-administered city may have two numeric codes, which are region codes defined by ISO-3166-2. It can be the second part of). Geocoder 430 may index this code (e.g., "CN-dd") at each address and forward to front-end server 440 for all successfully geocoded addresses. The geographic information generator 830 may provide this code to the ads server 840 as a geo-region-code.

In another embodiment, an advertiser may use keyword pairs of <keyword, location> instead of geo-targeting, which, in the case of web search, It is not as effective in this region as it is in the United States. There may be more inventory of advertisements for these keyword pairs. Thus, the geographic information generator 830 may associate a keyword with a location entered by the search query, and may use this concatenation as a keyword provided to the ads server 840. For example, if a user searches for "restaurant" near "Beijing", the keyword provided to the ads server 840 by the geographic information generator 830 would be "restaurnat Beijing". This configuration can be applied to Japan and China.

In another embodiment, geographic information generator 830 may determine whether the search query includes a geographic reference. If the search query does not include geographic criteria, then regular advertisements may be presented by the ads server 840. However, it may be determined whether an indicator of the user's location, such as the user's IP address, is available. If a user's location indicator is available, a local advertisement may be presented based on the user's location.

On the other hand, if the search query includes a geographic criterion, the geographic information generator 830 determines whether the geographic criterion corresponds only to the city name (i.e. without any other geographic information, such as no province information). It can be determined. If the search query includes geographic criteria other than the city name, a local advertisement may be presented.

If the search query includes a geographic criterion that corresponds only to the city name, the geographic information generator 830 may determine whether the city corresponds to an apparent city. If the city does not correspond to an apparent city, a regular advertisement may be presented. If the city corresponds to an apparent city, geographic information generator 830 may determine whether the city name with one or more other search terms in the query appears on the blacklist. Blacklists, when combined with one or more words, may be maintained for obvious city names meaning something other than their respective cities. If a city name with one or more other search terms in the query appears on the blacklist, a regular advertisement may be presented. If a city name with one or more other search terms in the query does not appear on the blacklist, a local advertisement may be presented based on the geographic criteria of the query.

If a local (“targeted”) advertisement is to be presented, information related to the user's location (eg, the user's IP address) is used by the geographic information generator 830 to determine where the location corresponds to a geographic criterion. It is possible to determine whether it is within a predetermined distance of. If the user's location falls within a predetermined distance, a local advertisement may be presented. If the user's location is outside of a predetermined distance, a regular advertisement will be presented.

The front end server 440 (or components of the front end server 440) may perform some tasks that may be used only in China. For example, the front-end server 440 hides the driving direction, provides display units (kilometers versus miles) that can vary from country to country, and is sensitive to keywords when the user is in China. Filter for, provide a specific format of Chinese address and phone number for display, indicate a geocoded location at the top of the map, and / or round the distance to 0.5 km instead of 0.1 km and redirect the direction Can be removed

Example of process (processing)

10A-10D are flowcharts illustrating an example of a process for identifying local search results and providing a map associated with an identified location.

Example of the process of generating local search results and maps

As shown in FIG. 10A, a process 1000 for identifying local search results and providing a map associated with an identified location begins with receiving a yellow page, map provider, and document data (block 1005). For example, in one embodiment described above with respect to FIG. 4, the map provider data 400, yellow page data 405, and web document data 410 may be provided to the indexer 435, and the map Provider data 400 may also be used to derive address / POI ID information 420 and address FP / POI ID mapping information 425.

Process 1000 may perform geocoding on the data (block 1010). For example, in one embodiment described above with respect to FIG. 6, the address list builder 600 of the geocoder 430 receives the map provider data 400 and the yellow page data 405, and the map provider data. From 400 and / or yellow page data 405, an address list can be created based on the last name, city, district, street name, address, POI name, or a combination thereof. The parser 610 of the geocoder 430 may parse the city and / or district from the beginning of each address. The longest matching prefix locator 620 of the geocoder 430 may be used to find a different portion of each address. The geocoder's combination locator 620 looks for a particular combination, first looking for the POI name, then the various levels of address, and finally looking for the district or city. The query geocoding unit 640 of the geocoder 430 may calculate a score of the search result based on the number of points at the search result location.

As shown in FIG. 10A, process 1000 may perform indexing on the data (block 1015). For example, in one embodiment described above with respect to FIG. 7, the map data indexer 700 of the indexer 435 may index address data from map provider data 400, which may include map location information. . The yellow page data preprocessor 710 of the indexer 435 may receive yellow page data 405 from various providers and may preprocess the yellow page data 405 in a common format. The business information extractor 720 of the indexer 435 may extract business information (eg, address and phone number) from the web document data 410 using various techniques. This technique can be changed according to different formats of address and telephone number in China and Japan. The extracted business information may be provided in the business information repository 750. The distance flattener 730 of the indexer 435 may set a search radius for a local search query. The clusterer 740 of the indexer 435 may cluster the map provider data 400 and the yellow page data 405 together. Snippet highlighter 760 of indexer 435 may highlight snippets within a document (eg, a web document).

Process 1000 may generate a local search result and provide a map URL (block 1020). For example, in one embodiment described above with respect to FIG. 8, local search generator 810 of front-end server 440 is obtained by local search results 450 (eg, local search system 225). Based on the address processed, a list of relevant web pages and / or businesses within a particular geographic area may be generated. The map generator 820 of the front end server 440 may generate a map related to the local search result 450. For example, to display a map for that search result, map generator 820 constructs an iframe (i.e., a floating frame embedded within a web page) on the search results page, and a map provider You can execute a post action against the URL provided by.

Geocoding  Process example

Process block 1010 (FIG. 10A) in process 1000 may include the block shown in FIG. 10B. Thus, process block 1010 may create an address list (block 1025). For example, in one embodiment described above with respect to FIG. 6, the address list builder 600 of the geocoder 430 receives the map provider data 400 and the yellow page data 405, and the map provider data. From 400 and / or yellow page data 405, an address list (token) can be created based on the last name, city, district, street name, address, POI name, or a combination thereof. Process block 1010 may perform parsing processing on each address in the address list (block 1030). For example, in one embodiment described above with respect to FIG. 6, for each address, the parser 610 of the geocoder 430 may parse the city and district from the address.

As shown in FIG. 10B, process block 1010 may find the longest matching prefix from each address in the address list (block 1035). For example, in one embodiment described above with respect to FIG. 6, the longest matching prefix locator 620 of the geocoder 430 may be an additional portion of the address (eg, city, town, road or street, street, POI name). Etc.). If the longest matching prefix cannot be found in the address (NO in block 1040), process block 1010 may continue to find an additional portion of the address (block 1035).

If the longest matching prefix can be found in the address (YES in block 1040), process block 1010 can find a combination in each address (block 1045). For example, in one embodiment described above with respect to FIG. 6, the combination locator 630 of the geocoder 430 finds a particular combination, which first looks for a POI name, then finds various levels of addresses, and then Find the earth or city. This search configuration can ensure or confirm that most specific possible addresses can be obtained by the combination locator 630.

Indexing  Process example

Process block 1015 (FIG. 10A) of process 1000 may include the block shown in FIG. 10C. Thus, process block 1015 may preprocess the yellow page data (block 1050). For example, in one embodiment described above with respect to FIG. 7, the yellow page data preprocessor 710 of the indexer 435 may receive yellow page data 405 from various providers, and the yellow page data ( 405 may be preprocessed in a common (or predetermined) format. Such formatted data may be provided to the geocoder 430 during the indexing process, and the geocoder 430 may attempt to geocode the address. If the address can be geocoded up to the building or street level, the address can be geocoded as a regular entry. If the address can be geocoded up to the city or district level, the address can be indexed as an entry with an approximate position.

Process block 1015 may extract business information from the document (block 1055) and store the extracted business information (block 1060). For example, in one embodiment described above with respect to FIG. 7, business information extractor 720 of indexer 435 may use business information (eg, address and phone number) using various techniques from web document data 410. Can be extracted. This technique can vary depending on the different formats of address and phone numbers in China and Japan. In another embodiment described above with reference to FIG. 7, the extracted business information may be provided in the business information repository 750. The business information repository 750 may include various information, for example, a document for extracting business information by the business information extractor 720.

Process block 1015 may index the address data received from the map provider (block 1065). For example, in one embodiment described above with respect to FIG. 7, the map data indexer 700 of the indexer 435 may index address data from map provider data 400, which may include map location information. . Geocoder 430 makes an attempt to geocode the address again based on the indexed address data. The clusterer 740 may set the cluster position when the cluster position is different from the given position, but may not set the cluster position above a predetermined distance threshold (eg, within 3 kilometers).

As shown in FIG. 10C, process block 1015 may cluster yellow page data and map provider data (block 1070). For example, in one embodiment described above with respect to FIG. 7, the clusterer 740 of the indexer 435 may cluster the map provider data 400 and the yellow page data 405 together. Once these entries are clustered together by the clusterer 740, the front end server 440 can provide the user with detailed address and phone number information and an accurate location on the map.

Process block 1015 may highlight the excerpt provided in the document (block 1075). For example, in the embodiment described above with respect to FIG. 7, snippet highlighter 760 of indexer 435 may highlight excerpts in a document (eg, a web document). Snippet highlighter 760 may store byte offsets instead of term offsets to identify addresses or phone numbers (or some other business information) within web documents during indexing. Snippet highlighter 760 may use the byte offset to perform emphasis and may not require segmentation.

As shown in FIG. 10C, process block 1015 may set a search distance (block 1080). For example, in one embodiment described above with respect to FIG. 7, the distance flatter 730 of the indexer 435 sets the search radius for the geocoded local search query by the geocoder 430 to a specific location. Can be. Each location may be a point location (eg, building, famous tourist place, school, street center, etc.) or a boundary area location (eg, district, city, castle, etc.). For point locations, distance flattener 730 may set the search radius to a predetermined distance (eg, approximately 5 kilometers around the point). For boundary region locations, distance flattener 730 may set the approximate maximum distance from the center of the location to the corner as the search radius.

Example of Front End Server Process

Process block 1020 (FIG. 10A) of process 1000 may include the block shown in FIG. 10D. Accordingly, process block 1020 may rewrite the search query (block 1085). For example, in one embodiment described above with respect to FIG. 8, there may be several synonyms for a term in Chinese. In addition, different providers of yellow page data 400 may use different names to represent the same category. In order to provide the maximum recall for the search query entered by the user, the query rewrite 800 of the front-end server 440 may create a synonym list for each category. The query rewrite 800 may rewrite each local search query to expand the query into a pair of search terms that may be combined by an "OR" (logical sum) operand.

Process block 1020 may generate a local search result based on the search query and create a map indicating the location of the generated search result (block 1090). For example, in one embodiment described above with respect to FIG. 8, the local search generator 810 of the front-end server 440 may be configured for local search results (eg, addresses obtained and processed by the local search system 225). Based on the relevant web pages and / or business listings within a particular geographic area. In another embodiment described above with respect to FIG. 8, the map generator 820 of the front-end server 440 constructs an iframe (ie, a floating frame embedded within a web page) on the search results page. For example, you can execute a post action on a URL provided by a map provider. The POI ID is used by the map generator 820 to identify a location on the map (eg, map 900) for the map provider, allowing the map provider to indicate the location on the map provided in the results page.

As shown in FIG. 10D, process block 1020 may generate geographic information for an ads server (block 1095). For example, in one embodiment described above with respect to FIG. 8, in order to display local ads in China, the geographic information generator 830 of the front-end server 440 is geo-located on the ads server 840. Information can be provided. For example, the geographic information generator 830 may provide the area code to the ads server 840 as a geo-region-code. In another embodiment, geographic information generator 830 may associate a keyword with a location entered by the user by a search query, and may use this association as a keyword provided to ads server 840.

conclusion

Embodiments disclosed herein may provide a system and method for identifying local search results and creating a map associated with an identified location. The system of the present invention may receive a local search query entered by a user and identify a location associated with the received local search query. The system may identify a series of local search results that may be related to a local search query and that may be associated with an identified location. The local search results may include links to documents that may be related to local search queries. The system of the present invention may identify an identifier for a group of local search results and provide this identifier to a map provider. The system of the present invention may receive a map associated with the identified location from a map provider. The map may identify the location of one or more search results in the group of local search results.

Embodiments of the present invention have one or more of the following advantages. For example, map data and yellow page data may be used from several different providers to identify local search results and create a map associated with the identified location. Local search results may be conveniently displayed on the map. This arrangement produces local search results and does not require a pointer to the server of the third party map provider.

In another embodiment, the map may provide detailed map data based on yellow page data. This suggests that in countries where export restirctions may limit the use of detailed map data to create maps or the use of actual latitude and longitude of addresses within the area, it may be possible to create maps containing detailed map data. It is possible to write.

The embodiments of the present invention are for illustration and description, and are not intended to limit the invention only to the forms disclosed. Modifications and variations are possible in light of the above teachings and practice of the invention. For example, with respect to the series of operations described in connection with FIGS. 10A-10D, the order of these operations may be varied in embodiments in accordance with the present invention. Independent operations may also be performed in parallel. In one embodiment, server 220 may perform most, if not all, of the operations associated with the processing of FIGS. 10A-10D. In other embodiments, one or more or all of these operations may be performed by other entities, such as other servers 230 and / or 240 or client 210.

In other embodiments, other methods may be used to geocode addresses that are not provided by the map provider. As another alternative, geocoder 430 may attempt to find the nearest point to the address to be geocoded. For example, assume that points "1 ABC Street" (1 ABC Street) and "10 ABC Street" (10 ABC Street) are identified by the map provider. When geocoding the address "3 ABC Street", the geocoder 430 may provide the location of "1 ABC Street", which is the point closest to "3 ABC Street" (3 ABC Street). In another example, geocoder 430 may make an attempt to interpolate a point. For example, if "1 ABC Street" is at grid index (0, 0) and "10 ABC Street" is at grid index (10, 20), geocoder 430 is based on interpolation processing, "3 ABC" Street "can be determined to be at grid index (3, 6).

In another embodiment, other methods for obtaining a POI ID may be used to draw the map. As another alternative, the POI ID may be stored as location data from a map provider. The POI ID may be returned by the front end server 440 during operation. The POI ID may be changed to another version of the map provider data. Storing a POI ID in an index causes the index to depend on data from the map provider. Alternatively, the address of the search result may be geocoded during operation, and geocoder 430 may be asked to provide the closest matching point. Geocoder 430 may return the POI ID of that point. Since the request for the closest matching point can be provided as a batch of geocoding requests (e.g., 10 batches), the impact on performance can be small.

In another example, while describing a system and method in connection with a Chinese local search, in other embodiments, some of the techniques disclosed herein may be equally applied to local searches in other countries.

Those skilled in the art will appreciate that features of the present invention may be implemented in many different forms of software, firmware, and hardware in the implementation illustrated in the figures, as described above. The actual software code or dedicated control hardware used to implement the features of the present invention does not limit the present invention. Thus, operations and actions of the features of the invention have been disclosed without reference to dedicated software code. That is, those skilled in the art will appreciate that software and hardware may be designed to implement features based on the description herein.

Any component, operation or instruction used in the present application should not be construed as essential to the invention unless expressly disclosed. As used herein in the singular, the phrase “a” or “an” may be interpreted to mean one or more. If only one, use the expression "one" or similar. The expression "based on" should be interpreted to mean "at least partially based" unless stated otherwise.

Claims (46)

delete delete delete delete delete delete delete delete delete delete As a method of geocoding based on local search queries, Receiving third party map provider data and yellow page data; Generating an address based on the local search query and information included in the third party map provider data and the yellow page data; Parsing the address; Identifying one or more portions of the address by finding the longest matching prefix within the address; And Finding a combination of parts of the address to verify that the address is correct Including, Generating the address,   Generating a list of synonyms related to the local search query;   Rewriting the local search query based on the synonym to produce an extended query,   Generating a local search result based on the expanded query,   Obtaining a map from a third party map provider based on the local search results, and   Generating an advertisement based on geographic information related to the local search result Including, geocoding method. delete The method of claim 11, And parsing a city and a district from the address. The method of claim 11, And wherein the portion of the address comprises one or more of the name of a town, a village, a road, a street, a number, or a POI. The method of claim 11, Finding the combination within the address to first find a name of a region of interest (POI), second to find another portion of the address, and third to find a district or city. The method of claim 11, If the address includes a building or street portion, indexing the address as an exact position. The method of claim 11, If the address comprises a city part or a district part, indexing the address as an approximate position. delete delete delete delete delete delete delete delete The method of claim 11, And recomposing the local search query by combining the search terms using an AND (OR) operand. The method of claim 11, Obtaining the map,   Constructing a map frame using the local search results;   Executing a post action on a URL provided by the third party map provider, and   Identifying the location on the map such that the third party map provider can indicate the location on the map. Including, geocoding method. The method of claim 11, And creating the advertisement based on a region code associated with the region search result. The method of claim 11, Associating a keyword with a location related to the local search query; And Creating the ad based on the associated keyword Geocoding method comprising more. delete delete delete delete delete delete delete delete delete delete delete delete delete delete A memory for storing a plurality of instructions; And A processor for executing instructions in the memory Including; The processor executes the instruction, Identify locations related to local search queries, Identify a local search result related to the local search query and associated with the identified location, to generate a list of synonyms associated with the local search query, based on the synonym, to identify the local search result Rewrite the search query to create an extended query, generate the local search results based on the expanded query, Identify an identifier for each of the groups of local search results, Provide an identifier for each of the groups of local search results to a third party map provider, Receive, from the third party map provider, a map associated with the identified location, The map identifies a location of one or more local search results within the group of local search results. Receiving a local search query; Identifying a location associated with the local search query; Identifying a series of search results related to the local search query and associated with the identified locations; Identifying an identifier for each of the group of search results; Providing the identifier for each of the group of search results to a third party map provider; And Receiving, from the third party map provider, a map associated with the identified location Including; Identifying the series of search results,    Generating a list of synonyms related to the local search query;    Rewriting the local search query based on the synonym to produce an extended query, and    Generating the series of search results based on the expanded query Including, The map identifies a location of one or more search results within the group of search results. delete

Images