Methods and apparatus for searching with awareness of geography and languages

[0001] This application is a continuation of U.S. patent application Ser. No. 11/752,205 filed May 22, 2007 which claims priority to U.S. patent application Ser. No. 60/811,989 filed Jun. 7, 2006.

[0002] The field of the invention is searching technologies.

[0003] Globalization necessitates an audience of diverse languages and geographic locations. To satisfy a user's information need, relevance is necessarily a function of both language and location.

[0004] Consider a company whose potential clients are in different countries and regions, speaking difference languages. The company's web site contains pages that are relevant for different clients. For example, one page aims at potential English-speaking clients from Los Angeles (“our sales office is a short distance from the Union Station . . . ”); another page aims at potential clients from Los Angeles speaking Spanish; still another page at clients from Los Angeles speaking Chinese; and still another page at clients from Shanghai speaking Chinese (a Chinese equivalent of the following message “Our Shanghai office handles businesses throughout the Eastern China”).

[0005] Now suppose all these web pages are searchable through a search engine.

[0006] A user query submitted to the search engine might originate from any part of the world, and the user composes the query in a language of her choice. If the search engine can automatically discern the origin, and the language, of the query, then the engine can match information in the most appropriate combination of location and language, and display accordingly. For example, a barber shop's information is typically relevant only to a user from the same or neighboring zip codes, a CPA from the same or neighboring cities, and a software developer maybe the same country, all preferentially speaking the same language as a potential client.

[0007] In searching, the state of the art is to use information contained in user's browser and the user query to detect the country (in prior art FIG. 4, for example), or the geographic location (in prior art FIG. 5, for example), or the preferred language (in prior art FIG. 3, for example). There is also prior art that uses information provided by user's browser to determine both the country and the language (in prior art FIG. 2, for example).

[0008] The state of the art is not satisfactory. For one reason, geographic locations are of different “granularities” arranged in a hierarchical manner. It decidedly enhances relevance if the smallest possible granularity (many times much finer than “country”) is discerned, and used in searching. For example, the zip code 90024 corresponds to an area within the district of West Los Angeles, which in turn is within the city of Los Angeles, which in turn is part of the Greater Los Angeles, Southern California, California, America's West Coast, the United States of America, and North America. When the zip code 90024 is detected, search results associated with the zip code might be the most relevant, those associated with the district are less relevant, and in a decreasing order of relevance those associated with the city, the region, so on.

[0009] The state of the art is not satisfactory, for another reason, that sometimes there could be multiple detected locations. Further, sometimes there could be multiple detected languages. The state of the art uses only one pair of location and language, if that.

[0010] Further, the recent explosion of online videos for consumers, exemplified by contents on and visits to YouTube.com, leads to the contention that an explosion of online video for businesses is in the offing. Continuing the example above, suppose the company's web site features “About Us” videos that are dubbed in different languages aiming at different geographic locations. The need for a search engine to consider the best combinations of location and language is even more pronounced.

[0011] An observation from the example above is that many times a same piece of information exists in different languages for audiences in different locations, which calls for a means to identifying such relationships among records. Current state of the art does not speak to this.

[0012] The discussion above applies to records that comprise of Web pages, documents, catalogues, and advertisements.

[0013] This and all other extraneous materials discussed herein are incorporated by reference in their entirety. Where a definition or use of a term in an incorporated reference is inconsistent or contrary to the definition of that term provided herein, the definition of that term provider herein applies and the definition of that term in the reference does not apply.

[0014] What is still needed is methods that automatically discern geographic locations of the smallest possible granularity, determine the language or the languages of the user query, and evaluate the applicability of the geographic locations using at least the language or the languages. Once locations and languages are determined, best combinations of locations and language help retrieve and display records.

[0015] FIG. 1 depicts the scheme of Claim 1 of this invention, which comprises methods that automatically discern a set of suspected geographical origins from which a user may have connected to a server, identify one or more languages of a user query, use the languages to evaluate applicability of each of the suspected origins, and use the origins and languages in retrieving records and displaying them to the user.

[0016] A geographic origin is the geographic location from which the user is connected to a server in the contemplated system. A geographic location can be a zip code (or generally a postal code), an airport code, a city, a non-political region such as “West Los Angeles” or “New England”, a city, a county, metropolitan or micropolitan statistical areas as defined by the US Census (e.g., “Norfolk-Virginia Beach-Newport News”), a country, or a continent. In the discerning step, a smallest possible origin is sought out. For example, if “Los Angeles” can be discerning, it is preferred to “California”.

[0017] The discerning step utilizes information from user's connection, which could be via a Web browser, a cell phone, or a PDA, to name a few. The step also makes use of the user query, extracting information that is suggestive geographic locations. The result is a set of suspected origins to be further evaluated.

[0018] The use query is analyzed to find out the language, or sometimes languages, of the user query. The result is used in evaluating members of the set of suspected origins.

[0019] Once the origins and languages are determined, both help to guide retrieving of records. Records that match the origins and languages are preferred to those do not. When retrieved records contain at least two records each matching a different origin, with one embodiment, display is arranged so that records from two or more origins are concurrently displayed. Similarly, when retrieved records contain at least two records each matching a different language, with one embodiment, display is arranged so that records two or more languages are concurrently displayed.

[0020] Records are also partitioned so that different partitions are applied different functions in retrieving and displaying. For example, one partition of the records could comprise web pages from a company, and another partition could comprise advertisements in textual or rich media format from a same company.

[0021] Various objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of preferred embodiments of the invention, along with the accompanying drawings in which like numerals represent like components.

[0032] FIG. 1 depicts a class of methods that automatically discern 500 a set of suspected geographical origins from which a user may have connected to a server through a user connection 405, identify one or more languages of a user query 410, use the languages to evaluate 545 applicability of each of the suspected origins, determine 520 at least one preferred language, and use the origins and languages in retrieving records and displaying them to the user.

[0033] FIGS. 2-5 are prior art described in the Background section. FIG. 6 depicts generally an embodiment 100, where a user 400 connects to the system through the Interface 420. Through 420, a user query is submitted to the Front End Sub-system 300, which provides the user query as well as other information, to the Search Sub-system 320, which finds matches among records stored on 200 Records Repository. The Presentation Sub-system 330 is provided with matching records as well as other information from 300 and 320, and display records on the Interface 420. Records on 200 have been processed from information gathered by 110 Information Gathering Sub-system from Web or non-Web sources before a user connects.

[0034] Regarding 200 Records Repository, a record is associated with a geographic location, including but not limited to a postal code, a district, a non-political region, a city, a county, a metropolitan or micropolitan statistical areas for example, as defined by the US Census), a country, and a continent. For example, a post code could be “90210” or “310013”; a political district “Central, Hong Kong”; a city “Los Angeles” or “Hong Kong”; a county “Los Angeles County”; a non-political region “West Los Angeles” or “the Greater Los Angeles” or “the West Coast” or “New England”; a metropolitan or micropolitan statistical area “Norfolk-Virginia Beach-Newport News”; a country “United States of America”; a continent “North America”.

[0035] A record is also associated with at least one language. A language could be “English”, “American English”, “British English”, “Chinese”, “Cantonese”, “Chinese simplified”, “Chinese traditional”, or “Chinese Hong Kong”. Further, a record comprises information in the form of text, or of rich media format (e.g. audio, video, image), or a combination.

[0036] Still further, a record could be a combination of other records. For example, a record labeled as “Record A” could be about a company's general introduction, and is combined from three records, “Record A1”, “Record A2”, “Record A3”, and “Record A4”, where “Record A1” is textual and associated with the geographical location “China mainland” and the language “Chinese simplified”, “Record A2” is textual and associated with the geographical location “California” and the language “US English”, “Record A3” is a video with Chinese dubbing and associated with “China mainland” and the language “Chinese simplified”, and “Record A4” is a video with English dubbing and associated with “California” and “US English”.

[0037] Still further, records on 200 Records Repository are partitioned. For example, one partition of the records could comprise web pages from a company, and another partition could comprise advertisements in textual or rich media format from a same company.

[0038] Through out the discussion below, it is intended that a method applied to one partition might not be the same for another partition.

[0039] FIG. 7 depicts Step 500 of automatically discerning a set of suspected user origins 509, which generally comprises a user connection 405, a user query 410, step 502 discerning origins from the user connection, step 504 discerning origins from the user query, and step 506 deciding on a set of “smallest” suspected origins. A geographical origin is the geographical location from which the user connects to the server.

[0040] A user connection 405 preferably is from a computer (desktop, laptop, workstation, server, etc.), alternatively from a cell phone, or a PDA, or others. In prior art US 20040254932 A1, Gupta et al., Dec. 16, 2004, various such connections are disclosed in paragraph 0030.

[0041] In Step 502, different methods are applied to different connections, to name a few below.

• • [0042] A) A client computer connecting using the HTTP protocol. Typically the client uses a web browser, which transmits various piece of information, as specified by the Common Gateway Interface protocol, including but not limited to (1) the client's Internet Protocol (IP) address which can be used via Reverse IP lookup in order to map to geographic locations. This is disclosed in both US2004/0194099 A1, Lamping et al., Sep. 30, 2004, paragraph 0081, and US2006/0106778 A1, Laura Baldwin, May 18, 2006, paragraph 0038; (2) the client's hostname, which can be mapped via Domain Name Resolution to geographic locations. This is also disclosed by the above two prior arts; and (3) with certain software such WebPlexer, country can be automatically determined, as disclosed in U.S. Pat. No. 6,623,529, David Lakritz, Sep. 23, 2003, section 3.4.1.
  • [0043] B) A client providing a phone number. A cell phone client could provide this information. The phone number's country code, area code, central office code, as well as the other parts of the phone number, can all be used in mapping into geographic locations.
  • [0044] C) A client providing GPS coordinates. GPS coordinates can be mapped into geographic locations.

[0045] In Step 504, the user query string is analyzed for information suggestive of geographical locations. Some of the methods are discussed below:

• • [0046] (504A) Looking for a proper name for geographic locations such as “Los Angeles”, “Shanghai”, the Chinese equivalent of “Shanghai”, a location's nickname such as the “Big Apple”. This method is generally disclosed in US2006/0106778 A1, Laura Baldwin, May 18, 2006, paragraph 0040.
  • [0047] (504.B) Looking for information other than proper names suggestive of geographic locations. For one example, in the query “flying from LAX to JFK”, two geographic locations are present.

[0048] In Step 506, at least two sets of suspected origins are merged, and the goal is to find the set of “smallest” geographical locations, whose preferred definition is that the union of members covers the smallest possible geographical area. For example, given the following two sets: (i) {“United States”}, and (ii) {“California”, “Oregon”, “Arizona”}, the method finds the latter set. All suitable algorithms are contemplated, including but not limited to lookup tables, greedy search algorithms, and shortest path algorithms.

[0049] FIG. 8 depicts Step 520 of detecting languages the user uses, which generally comprises a user connection 405, a user query 410, step 523 of detecting languages from the user connection, step 525 of detecting languages from the user query, and step 527 of merging the previous detections into a set of languages.

[0050] In Step 523, different methods are applied to different connections, to name a few below.

• • [0051] (523.A) A client computer connecting using the HTTP protocol. A web browser transmits various piece of information, as specified by the Common Gateway Interface protocol, and additionally through request message header, including but not limited to (1) the language accepted by the client's web browser. This is disclosed in prior art U.S. Pat. No. 6,632,529, David Lakritz, Sep. 23, 203, section 3.3.4, as well as in US2004/0194099 A1, Lamping et al., Sep. 30, 2004, paragraph 0079 and 0080; and (2) the client's operating system (such as “Microsoft XP Chinese”). Such information can be mapped into geographic locations. For example, “Microsoft XP Chinese” could be mapped to languages of {“China simplified Mainland China”, “Chinese simplified Singapore”}.
  • [0052] (502.B) A client providing a phone number. A cell phone client could provide this information. The phone number's country code is readily mapped into at least one language. Sometimes the area code is readily mapped into at least one dialect (e.g., Cantonese in parts of China).

[0053] In Step 525 of detecting languages from the user query, some contemplated methods are listed below.

• • [0054] (525.A) Technology for language identification for a text string is well known, e.g., the Rosette Language Identifier software from Basis Technology, Inc.
  • [0055] (525.B) In the case of a user query string composed of at least two different languages, new method is developed by this invention, so that a query string is first segmented into different parts, and each part is further detected of its preferred languages.

[0056] In Step 527, at least two sets of languages are merged into one set. The goal is to find a set of “finest” languages. For example, given two sets, (i) {“English”, “Chinese”}; (ii) {“American English”, “Chinese”}, the former is found. All suitable algorithms are contemplated, including but not limited to lookup tables, greedy search algorithms, and shortest path algorithms. In step 529, the system derives at least one preferred language.

[0057] FIG. 9 generally depicts a contemplated strategy 540 for using at least one preferred language 529 to modify the set of the suspected origins 509, and associating a confidence measure on every element in the set of origins. The result is the evaluated set of origins 545.

[0058] The system has knowledge on mapping from languages to geographical locations. One piece of knowledge could be (“Chinese simplified”=>{(“China mainland”, 0.9), (“Singapore”, 0.4), (“China Hong Kong”, 0.1)}. This piece knowledge states that the language “Chinese simplified” corresponds to three geographical locations each of which is associated with a confidence measure of 0.9, 0.4 or 0.1 respectively. Suppose there is a set of suspected geographical origins {“China mainland”, “China Hong Kong”, “Singapore”, “Taiwan”}, and a user query's language is identified as {“Chinese simplified”}, then applying the above piece of knowledge to the set of origins could lead to the removal of the element “Taiwan”, and the remaining three elements are associated with confidence measures partially derided from the piece of knowledge.

[0059] FIG. 10 depicts methods in finding the best combinations of locations and languages, which generally comprises the evaluated set of origins 545, the languages 529, Step 562 applying generally relationships among languages and locations, and Step 564 applying non-general relationships among languages and locations. The result is the best combinations 568.

[0060] In Step 562, general relationships among languages and locations are applies in order to evaluate combinations. Such relationships comprise commonly known language and location combinations that exist. For example, given the set of origins {“London”} and the languages {“US English”, “UK English”}, then the combination of (“London”, “UK English”) is evaluated as a preferred one to (“London”, “US English”). The system stores such relationships, with one embodiment in a lookup table.

[0061] In Step 564, non-general relationships among language and locations are applied. Some sets of such relationships are listed below.

• • [0062] (564.A) One set of such relationships are those of local nature. For example, regions such as Montreal have two prevailing languages, and this local relationship overrides the general relationship of (“Canada”, “English”).
  • [0063] (564.B) Another set of such relationships are those inheritably “conflicting”. For example, a user connects from Shanghai, using a browser on a Microsoft XP Chinese operating system, submitting a query in simplified Chinese that has “90024” in it. The suspected origins are thus {“Shanghai”, “90024”} (90024 is a zip code in Los Angeles), and the language {“Chinese simplified”}. Consider the relative goodness of the two combinations: (“90024”, “Chinese simplified”) and (“Shanghai”, Chinese simplified). The first combination might well be what the user is seeking (information relevant to the zip code, and in simplified Chinese), however, there is very little such information exits. The second combination might not be what the user is seeking, but there is a large amount of such information exists. Such relationships are accumulated through interviewing experts and by collecting statistics, and stored on the system. One embodiment is the storage is lookup tables, another embodiment probability rules.

[0064] Once the suspected origins, the languages, and the best combinations of the two, are derived, they are used in retrieving and displaying records.

[0065] As stated above, a record on 200 Record Repository has been associated with a geographic location and a language. The matching of a user's geographical origin and a record's geographical location is done at smallest geographical area possible. For example, if a set of origins is {“California”, “Arizona”}, and a location is {“Los Angeles”}, then the matching is “Los Angeles”.

[0066] At Search Sub-system 320, the matching of a query's language and a record's language is at the finest possible. For example, if a query's language is “Chinese”, and a record's language is “Chinese simplified”, then the matching is “Chinese simplified”. The Search Sub-system 320 retrieves those records whose geographical locations and languages match a user query with priority over those do not. Further, the best combinations 568 are applied in sorting the retrieved records. All suitable algorithms are contemplated, including but not limited to lookup tables, greedy search algorithms, and shortest path algorithms.

[0067] At Interface 420 where retrieved records are displayed, several methods are contemplated as below.

• • [0068] (420.A) If there are two combinations of location and language, display records in two areas, one for the first combination, and the other for the second combination. If there are more than two good combinations, records in the best two are displayed first.
  • [0069] (420.B) If combinations of locations and languages are not available, the following methods are contemplated:
    • [0070] (420.B.1) If a user query has two suspected origins, our system displays records in two areas, one for the first origin, and two for the second origin. If there are more than two origins, records in the two with highest confidence measures are displayed first. Preferably records are displayed in two areas.
    • [0071] (420.B.2) If a user query has two suspected languages, our system displays records in two areas, one for the first language, and two for the second language. If there are more than two languages, records in the two with finest languages are displayed first. Preferably records are displayed in two areas.

[0072] Thus, specific embodiments and applications of searching with awareness of locations and languages and related improvements have been disclosed. It should be apparent, however, to those skilled in the art that many more modifications besides those already described are possible without departing from the inventive concepts herein. The inventive subject matter, therefore, is not to be restricted except in the spirit of the appended claims. Moreover, in interpreting both the specification and the claims, all terms should be interpreted in the broadest possible manner consistent with the context. In particular, the terms “comprises” and “comprising” should be interpreted as referring to elements, components, or steps in a non-exclusive manner, indicating that the referenced elements, components, or steps may be present, or utilized, or combined with other elements, components, or steps that are not expressly referenced. Where the specification claims refers to at least one of something selected from the group consisting of A, B, C . . . and N, the text should be interpreted as requiring only one element from the group, not A plus N, or B plus N, etc.