HK1191120A - Method for searching for data using network device in communication with client device - Google Patents

Abstract

The invention discloses clustered search processing. The invention provides methods and apparatus for searching data and grouping search results into clusters that are ordered according to search relevance. Each cluster comprises one or more data type, such as images, web pages, local information, news, advertisements, and the like. In one embodiment, a search term is evaluated for related concepts indicating categories of data sources to search. Data sources may also be identified by context information such as a location of a client device, a currently running application, and the like. Search results in each cluster are ordered by relevance and each cluster is given a score based on an aggregate of the relevance within the cluster. Each cluster score may be modified based on one or more corresponding concepts and/or context information. The clusters are ordered based on the modified scores. Content, including advertisements, may also be added to the ordered list to appear as another cluster.

Description

Clustered search processing

The present application is a divisional application of chinese patent application No.200780049318.7 entitled "search processing for clusters" on an application date of 2007, 12 and 10.

Technical Field

The present invention relates generally to searching data and more particularly, but not exclusively, to grouping search results into clusters ordered according to search relevance.

Background

Tremendous changes have occurred in the internet which have affected our daily lives. For example, mobile computing devices are becoming more and more prevalent in today's society. Many mobile computing devices, such as personal digital assistants, cellular telephones, and the like, may be used to communicate voice messages, electronic mail, text messages, and the like, as well as search for information over the internet. It is not uncommon to see someone using their mobile device to search for merchants, restaurants, music, businesses, etc. on a bus, train, or even boat.

However, performing a search query for user-related information is still cumbersome. Often, a user may have to perform several search queries to obtain relevant search results. Irrelevant search results mean that the likelihood that they will find when the user is looking for is reduced, which in turn can be interpreted as a loss of business opportunity or other business to the merchant that benefits the user. Thus, many businesses are looking for new ways to make search results more relevant to users. One technique is to group search results that match the submitted search term. Some search systems provide predefined groupings of data types for search results, such as web pages, images, videos, local results, shopping-related results, jobs, news, advertisements, and so forth. The packets are typically arranged in the same order, and each packet typically includes only one data type.

Another technique is to determine groupings based on textual similarity of search results. However, text-like groupings generally do not take into account any information about the searcher. Thus, the grouping determined by textual similarity may not be the most relevant grouping to the searcher. Similarly, the ranking of text-like groupings may not be in the order most relevant to the searcher. Current grouping systems also typically provide only links to search results and brief summary information. The returned search results page generally does not include any substantive content without search term-based links. Accordingly, the present invention has been made in view of these considerations and others.

Drawings

The following figures describe non-limiting and non-exhaustive embodiments of the invention. Like reference numerals refer to like parts throughout the drawings unless otherwise specified.

For a better understanding of the present invention, reference is made to the following detailed description, taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a system diagram of one embodiment of an environment in which the present invention may be practiced;

FIG. 2 illustrates one embodiment of a mobile device that may be included in a system implementing the invention;

FIG. 3 illustrates one embodiment of a server device that may be included in a system implementing the invention;

FIG. 4 illustrates one example of a search results page for a topical search term that is relevant to determining a relatively intuitive concept of a search result;

FIG. 5 illustrates one example of a search results page for search terms that are relevant to determining less intuitive concepts of search results;

FIG. 6 illustrates a logical flow diagram generally showing one embodiment of an overall process for searching data;

FIG. 7 illustrates a logical flow diagram generally showing one embodiment of a process for determining concept-specific data sources; and

FIG. 8 illustrates a logical flow diagram generally showing one embodiment of a process for modifying cluster scores of clusters of search results.

Detailed Description

The present invention now will be described more fully hereinafter with reference to the accompanying drawings, which form a part hereof, and which show, by way of illustration, specific exemplary embodiments by which the invention may be practiced. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. Among other things, the present invention may be embodied as methods or devices. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. The following detailed description is, therefore, not to be taken in a limiting sense.

Throughout the specification and claims, the following terms have the meanings explicitly associated herein, unless the context clearly dictates otherwise. The phrase "in one embodiment" as used herein does not necessarily refer to the same embodiment, although it may. Moreover, the phrase "in another embodiment" as used herein does not necessarily refer to a different embodiment, although it may. Thus, as described below, the various embodiments of the invention may be readily combined without departing from the scope or spirit of the invention.

Furthermore, the term "or" as used herein is an inclusive "or" operator (operator) and is equivalent to the term "and/or," unless the context clearly dictates otherwise. The term "based on" is non-exclusive and allows for being based on additional factors not described, unless the context clearly dictates otherwise. Furthermore, throughout the specification, the meaning of "a", "an" and "the" includes plural references. The meaning of "in.

Exemplary operating Environment

FIG. 1 illustrates the components of one embodiment of an environment in which the invention may be practiced. Not all of the components may be required to practice the invention, and variations in the arrangement and type of the components may be made without departing from the spirit or scope of the invention. As shown, the system 100 of fig. 1 includes a network that enables communication between client and server devices. The network 105 may include one or more local area networks ("LANs")/wide area networks ("WANs"). Wireless network 110 may include a LAN, WAN, telephone network, etc. The system 100 also includes a general-purpose client device 101, a mobile client device 102, a search server 106, and a content server 107.

One embodiment of the mobile device 102 and 103 is described in more detail below in conjunction with fig. 2. In general, however, the mobile device 102 and 104 may include virtually any portable computing device capable of receiving and sending messages over a network, such as the network 105, the wireless network 110, and so forth. The mobile device 102 and 104 may also be generally described as a client device configured to be portable. Thus, the mobile device 102 and 104 may include virtually any portable computing device capable of connecting to another computing device and receiving information. Such devices include portable devices such as cellular telephones, smart phones, display pagers, Radio Frequency (RF) devices, Infrared (IR) devices, Personal Digital Assistants (PDAs), handheld computers, laptop computers, wearable computers, tablet computers, integrated devices combining one or more of the preceding devices, and the like. Thus, mobile devices 102-104 typically vary widely in terms of capabilities and features. For example, a cellular telephone may have a numeric keypad and a few lines of monochrome LCD display on which only text may be displayed. In another example, a web-enabled mobile device may have a touch sensitive screen, a stylus (stylus), and several lines of color LCD display where both text and graphics may be displayed.

A web-enabled mobile device can include a browser application configured to receive and transmit web pages, web-based messages, and the like. The browser application may be configured to receive and display graphics, text, multimedia, etc., and the browser application may use virtually any web-based language, including wireless application protocol messages (WAP), etc. In one embodiment, the browser application can use Handheld Device Markup Language (HDML), Wireless Markup Language (WML), WMLScript, JavaScript, standard generalized markup language (SMGL), hypertext markup language (HTML), extensible markup language (XML), and the like, to display and send messages. In one embodiment, a user of a mobile device may use a browser application to perform a search over a network. However, another application may also be used to perform the search over the network.

The mobile device 102 may also include at least one other client application configured to receive content from another computing device. The client application may include the ability to provide and receive textual content, graphical content, audio content, and the like. The client application may also provide information identifying itself, including type, capabilities, name, and the like. In one embodiment, the mobile devices 102 and 104 may uniquely identify themselves through any of a variety of mechanisms, including a telephone number, Mobile Identification Number (MIN), Electronic Serial Number (ESN), or other mobile device identifier. The information may also indicate content formats that the mobile device can use. Such information may be provided in a message or the like sent to search server 106, client device 101, or other computing device.

In one embodiment, the mobile device 102 and 104 may also provide the physical location to another computing device. However, in one embodiment, the mobile device 102 and 104 may provide physical location information in terms of latitude and longitude, among other things. However, the mobile device 102 and 104 may also provide other information that may be used to determine the physical location of the device, including, for example, a cell tower (cell tower) address, a MAC address, an IP address, and the like.

The mobile device 102 may also be configured to include a client application that enables an end user to log into an end user account that may be managed by another computing device, such as the search server 106. For example, such end-user accounts may be configured to enable end-users to receive emails, send/receive IM messages, SMS messages, access selected web pages, participate in social networking activities, perform search queries, and so forth. However, participating in various social networking activities, performing search queries, etc. may also be performed without logging into the end user account.

Client device 101 may include virtually any computing device capable of communicating over a network to send and receive information, including search query information, location information, social networking information, and the like. The set of such devices may include devices that typically connect using a wired or wireless communications medium such as personal computers, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, and the like.

The wireless network 110 is configured to couple the mobile device 102 and its components 104 with the network 105. The wireless network 110 may include any of a variety of wireless sub-networks that may also overlay stand-alone ad-hoc networks, etc. to provide an infrastructure-oriented connection to the mobile device 102 and 104. Such subnetworks may include cellular networks, mesh networks, wireless lan (wlan) networks, and so forth.

Wireless network 110 may also include an autonomous system of terminals, gateways, routers, and the like connected by wireless radio links, and the like. These connectors may be configured to move freely and randomly and organize themselves arbitrarily such that the topology of wireless network 110 may change rapidly.

Wireless network 110 may also use a variety of access technologies including 2(2G), 3(3G) generation cellular system radio access, WLAN, Wireless Router (WR) mesh, and the like. Access technologies such as 2G, 3G, and future access networks may enable wide area coverage for mobile devices such as mobile device 102 and 104 with various degrees of mobility. For example, the wireless network 110 may implement radio connections through radio network access such as global system for mobile communications (GSM), General Packet Radio Service (GPRS), Enhanced Data GSM Environment (EDGE), Wideband Code Division Multiple Access (WCDMA), and so on. In essence, the wireless network 110 may include virtually any wireless communication mechanism by which information may travel between the mobile device 102 and 104 and another computing device, network, and the like.

The network 105 is configured to couple the search server 106 and its components with other computing devices including the mobile device 102 and 104, the client device 101, and to couple the search server 106 and its components to the mobile device 102 and 104 through the wireless network 110. The network 105 can use any form of computer readable media to communicate information from one electronic device to another. Further, the network 105 may include the internet as well as a Local Area Network (LAN), a Wide Area Network (WAN), a direct connection, such as through a Universal Serial Bus (USB) port, other forms of computer readable media, or any combination thereof. On an interconnected set of LANs, including those based on differing architectures and protocols, a router acts as a link between LANs, enabling messages to be sent from one to another. Further, the communication links within a LAN typically comprise twisted wire pairs or coaxial cables, while the communication links between networks may use analog telephone lines, fully or partially dedicated digital lines (including T1, T2, T3, and T4), Integrated Services Digital Networks (ISDN), Digital Subscriber Lines (DSL), wireless links including satellite links, or other communication links known to those skilled in the art. In addition, remote computers and other related electronic devices can be remotely connected to either LANs or WANs via a modem and temporary telephone link. Essentially, network 105 includes any communication method by which information may travel between search server 106, client device 101, and other computing devices.

Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave, data signal, or other transport mechanism and includes any information delivery media. The terms "modulated data signal" and "carrier signal" include the following signals: one or more characteristics of the signal may be set or changed in such a manner as to encode information, instructions, data, and/or the like, in the signal. By way of example, communication media includes wired media such as twisted pair, coaxial cable, fiber optics, wave guides, and other wired media and wireless media such as acoustic, RF, infrared, and other wireless media.

One embodiment of search server 106 is described in more detail below in conjunction with FIG. 3. Briefly, however, search server 106 may comprise any computing device capable of connecting to network 105 in order to perform data searching, filtering, sorting, and other data management operations. Search server 106 may also provide web portal information and/or services, including tracking their online behavior with user permissions and providing content. Search server 106 may also enable aggregation and management of social networking information. Devices that may operate as search server 106 include personal computers desktop computers, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, servers, and the like.

Although FIG. 1 illustrates search server 106 as a single computing device, the invention is not so limited. For example, one or more functions of search server 106 may be distributed across one or more different computing devices. For example, managing searches, search results, Instant Messaging (IM) sessions, SMS messages, email messages, sharing of contact information, collecting behavior information, aggregating and/or storing of social networking information, etc., may be performed by multiple computing devices without departing from the scope or spirit of the present invention.

The content server 107 represents a variety of content and/or other data that may be used on the mobile device 102 and/or on the client 101. Such content may include web content, audio content, video content, FTP data, and the like. Data services may include, but are not limited to, web services, third party services, audio services, video services, email services, IM services, SMS services, VOIP services, calendar services, photo services, and the like. In addition, information related to content and/or services provided by content server 107 may be used to provide results to search queries.

Devices that may operate as content server 107 include personal computers desktop computers, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, servers, and the like.

Exemplary Mobile client Environment

FIG. 2 illustrates one embodiment of a mobile device 200 that may be included in a system implementing the invention. Mobile device 200 may include many more or fewer components than those shown in fig. 2. However, the components shown are sufficient to disclose an illustrative embodiment for practicing the present invention. For example, the mobile device 200 may represent one embodiment of at least one of the mobile devices 102 and 104 of FIG. 1.

As shown, mobile device 200 includes a Central Processing Unit (CPU)222 in communication with a mass memory 230 via a bus 224. Mobile device 200 also includes a power supply 226, one or more network interfaces 250, an audio interface 252, a display 254, a keypad 256, an illuminator 258, an input/output interface 260, a haptic interface 262, and an optional Global Positioning System (GPS) receiver 264. Power supply 226 provides power to mobile device 200. Rechargeable or non-rechargeable batteries may be used to provide power. Power may also be provided by an external power source, such as an AC adapter or a powered cradle (docking cradle) that supplements and/or recharges the batteries.

Mobile device 200 may optionally communicate with a base station (not shown), or directly with another computing device. Network interface 250 includes circuitry for coupling mobile device 200 to one or more networks and is constructed for use with one or more communication protocols and techniques including, but not limited to, global system for mobile communications (GSM), Code Division Multiple Access (CDMA), Time Division Multiple Access (TDMA), User Datagram Protocol (UDP), transmission control protocol/internet protocol (TCP/IP), SMS, General Packet Radio Service (GPRS), WAP, Ultra Wideband (UWB), IEEE802.16 worldwide interoperability for microwave access (WiMax), SIP/RTP, or any of a variety of other wireless communication protocols. Network interface 250 is sometimes referred to as a transceiver, transceiving device, or Network Interface Card (NIC).

Audio interface 252 is arranged to generate and receive audio signals such as the sound of a person's voice. For example, audio interface 252 may be coupled to a speaker and microphone (not shown) to enable communication with others and/or generate audio acknowledgements for some actions. Display 254 may be a Liquid Crystal Display (LCD), gas plasma, Light Emitting Diode (LED), or any other type of display used in conjunction with a computing device. Display 254 may also include a touch sensitive screen arranged to receive input from an object such as a stylus or a finger of a human hand.

Keypad 256 may include any input device arranged to receive input from a user. For example, the keypad 256 may include a push button numeric dial or a keyboard. Keypad 256 may also include command buttons associated with selecting and sending images. Illuminator 258 may provide status indications and/or provide light. Illuminator 258 may remain active for specific periods of time or in response to events. For example, when illuminator 258 is active, it may backlight the buttons on keypad 256 and remain on while the client device is powered on. Further, illuminator 258 may backlight these buttons in various modes when performing certain actions, such as dialing another client device. Illuminator 258 may also cause a light source located within a transparent or translucent housing of the client device to emit light in response to the action. In another embodiment, illuminator 258 may include a flash for a built-in camera (not shown).

Mobile device 200 also includes input/output interface 260 for communicating with external devices, such as a headset or other input not shown in FIG. 2Input or output devices. The input/output interface 260 may use one or more communication technologies, such as USB, infrared, Bluetooth^TMAnd the like. The haptic interface 262 is arranged to provide haptic feedback to a user of the client device. For example, the haptic interface may be used to vibrate mobile device 200 in a particular manner when another user of the computing device is calling.

Optional GPS transceiver 264 can determine the physical coordinates of mobile device 200 on the surface of the earth, which typically outputs a location as latitude and longitude values. GPS transceiver 264 can also use other geolocation mechanisms including, but not limited to, triangulation, assisted GPS (agps), enhanced observed time difference (E-OTD), Cellular Identifier (CI), Service Area Identifier (SAI), Enhanced Timing Advance (ETA), Base Station Subsystem (BSS), etc. to further determine the physical location of mobile device 200 on the surface of the earth. It is to be appreciated that under different conditions, GPS transceiver 264 can determine the physical location of mobile device 200 within millimeters; and in other cases the determined physical location may be less accurate, such as within meters or significantly greater distances. However, in one embodiment, the mobile device may provide, through other components, other information that may be used to determine the physical location of the device, including, for example, a MAC address, an IP address, and the like.

Mass memory 230 includes RAM232, ROM234, and other storage devices. Mass memory 230 illustrates another example of computer storage media for storage of information such as computer readable instructions, data structures, program modules or other data. Mass memory 230 stores a basic input output system ("BIOS") 240 for controlling low-level operations of mobile device 200. The mass memory also stores an operating system 241 for controlling the operation of mobile device 200. It should be appreciated that this component may include a dedicated client communication operating system such as a Windows Mobile^TMOrOperating system, or general-purpose operating system such as UNIX version or LINUX^TM. The operating system may include JaThe va virtual machine module interfaces with, or otherwise controls the operation of, the hardware components and/or the operating system via Java application programs.

Memory 230 also includes one or more data stores 244, which data stores 244 can be employed by mobile device 200 to store, among other things, applications 242 and/or other data. For example, data storage 244 may also be employed to store information that describes various capabilities of mobile device 200. This information may then be provided to another device based on any of a variety of events, including being sent as part of a header during a communication, being sent upon request, etc. Further, the data store 244 may also be employed to store search data, user preferences, address books, buddy lists, aliases, social networking information, and the like. At least a portion of the information may also be stored on a disk drive or other storage medium (not shown) within mobile device 200.

Applications 242 may include computer-executable instructions that, when executed by mobile device 200, send, receive, and/or otherwise process messages (e.g., SMS, MMS, IM, email, and/or other messages), audio, video, and enable communication with another user of another client device. Other examples of application programs include calendars, search programs, email clients, IM applications, SMS applications, VOIP applications, contact managers, task managers, transcoders (transcoders), database programs, word processing programs, security applications, spreadsheet programs, games, search programs, and so forth. One application shown in the figure is a browser 245.

Browser 245 may include virtually any application configured to receive and display graphics, text, multimedia, etc., using virtually any web-based language. In one embodiment, the browser application can use Handheld Device Markup Language (HDML), Wireless Markup Language (WML), WMLScript, JavaScript, standard generalized markup language (SMGL), hypertext markup language (HTML), extensible markup language (XML), and the like, to display and send messages. However, any of a variety of other web-based languages may be used.

In one embodiment, browser 245 may be configured to enable access to a search application, such as may be made by search server 106 and/or content server 104 of FIG. 1. In one embodiment, a user of mobile device 200 may enter a variety of search terms into a search application for obtaining search results. Browser 245 may also provide location information or information that may be used in determining its physical location. In one embodiment, such information may be used to automatically (e.g., transparent to user input) modify the search query.

Exemplary Server Environment

Fig. 3 shows an embodiment of a server device according to an embodiment of the invention. Server device 300 may include many more components than those shown. However, the components shown are sufficient to disclose an illustrative embodiment for practicing the present invention. For example, server device 300 may represent search server 106 and/or content server 107 of FIG. 1.

Server device 300 includes central processing unit 312, video display adapter 314, and a mass memory, all in communication with each other via bus 322. The mass memory generally includes RAM 316, ROM 332, and one or more permanent mass storage devices, such as hard disk drive 328, tape drive, optical drive, and/or floppy disk drive. The mass memory stores operating system 320 for controlling the operation of server device 300. Any general purpose operating system may be used. A basic input output system ("BIOS") 318 is also provided for controlling low-level operation of server device 300. As shown in FIG. 3, server device 300 may also communicate with the Internet or some other communication network via a network interface unit 310, network interface unit 310 being constructed for use with various communication protocols including the TCP/IP protocol. Network interface unit 310 is sometimes referred to as a transceiver, transceiving means, or Network Interface Card (NIC).

The mass memory as described above illustrates another type of computer-readable media, namely computer storage media. Computer storage media may include volatile, nonvolatile, removable, and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. Examples of computer storage media include RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, Digital Versatile Disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computing device.

The mass memory also stores program code and data. One or more applications 350 are loaded into mass memory and run on operating system 320. Examples of application programs may include transcoders, schedulers (schedulers), calendars, database programs, word processing programs, HTTP programs, customizable user interface programs, IPSec applications, encryption programs, security programs, VPN programs, SMS message servers, IM message servers, email servers, account management, and so forth. The search module 352 and/or the search clustering module 354 may also be included within the application 350 as an application program or as a separate application program.

The search module 352 is configured to receive search terms from client devices, determine other search parameters, perform searches of data sources, provide search results, and perform other search-related operations. The search clustering module 354 may be part of the search module 352 or separate from the search module 352. The search clustering module 354 is configured to organize the search results into groups and rank the groups of results. The search module 352 and/or the search clustering module 354 may use processes substantially similar to those described below.

General purpose operation

The operation of certain aspects of the present invention will now be described with reference to fig. 4-8. FIG. 4 is an illustration of a search results display 400 on a mobile device. The entire search result may be scrolled through a display of limited area. In addition to search results, content may be displayed among the search results. The content may include information, such as content 402, related to the submitted search term 401. Alternatively, or in addition, the content may include location information 404, advertisements, or other information. Generally, the content information is formatted to appear similar to the search results, although the content may be formatted in any other manner.

The first cluster element 406 indicates a first cluster of search results. The cluster elements may be selected to switch between an expanded view of the search results and a closed view of only the cluster elements. The cluster element may also include the search results themselves. The first cluster of search results is displayed near the top of the results display 400. The first cluster generally includes search results that are most relevant to the submitted search term. The clusters include search results for one or more particular data types, such as local listing information, news articles, web page links, images, shopping information, other suggested searches, and the like. For example, a first cluster element 406 indicates a cluster of local listing information for coffee shops identified by the search term and within a predefined radius of the mobile device location. In this example, the local listing information is determined to be the most relevant cluster of information based on several factors, such as the search term, information determined from a comprehensive analysis of the click stream (selections made by numerous users) after the search term is entered, previous behavior of the user in the search term, location of the mobile device, and/or other information. This particular search term 401 is associated with the concept of a retail store and with the concept of a company. However, the concept of a retail store may have a higher relevance to more users than the concept of a company. Thus, the cluster of the local list information is arranged as the first cluster.

The clustered search results may also include content indicating a data type or other information. For example, symbol 408 may indicate the type of information provided in the search results. Additionally, or alternatively, logos or other content may be placed on one or more search results, for example, based on a paid layout. The selectable expansion control element 409 may be used to display additional results in the cluster.

The second ranked cluster is displayed after the first ranked cluster. In this example, the second ranked cluster element 410 identifies a cluster of search results that includes multiple data types. This example cluster includes web site search results 410, stock quote search results 412, and links 414 to specialized company profile information. This cluster illustrates a cluster type defined to include a plurality of specific data types. Alternatively, the cluster type may be generated using multiple data types, which may be determined based on search criteria and/or other information. As shown by the second ranked clustering, a customized cluster type may be defined as a plurality of data types that include search results and/or content.

Other cluster types may include a single data type of the search results, such as first ranked cluster, third ranked cluster 412, and fourth ranked 414. In those cases, the cluster type may be equivalent to the data type. Lower ranked clusters may also be displayed with fewer search results or with only a spaced cluster selection element. For example, the low-ranked clusters 416 are displayed using only cluster selection elements that require the user to select a cluster selection element to expand the view of the corresponding search result. Thus, the relevance of a cluster may be indicated by location, size, and other attributes.

The search terms used in FIG. 4 are generally topical search terms related to relatively intuitive concepts. Some search terms are not so intuitive. FIG. 5 illustrates one example of a search results page 500 for a search term 501, the search term 501 being less intuitively related to concepts that a user may want the search results to address. The search term "today" alone may not directly suggest search results of certain data types that the user may desire. This search term may indicate a morning television show, a concept of a newspaper title, or other unrelated concept. In this case, contextual information such as the location of the mobile device may provide a better indication of the user's intent. Thus, the context information may be given more weight to determine which data sources to search and how to rank the clusters of search results. If the mobile device is in New York City and the user enters the search term "today," the user may be searching for information related to daily life in the city.

Such information may include content related to the city of the day. For example, the data content 504 may provide the current date and enable the user to access a calendar. Similarly, weather information 506 may display current weather conditions in a city and forecast weather conditions in the city. One or more advertisements 502 may also be included. Each of these content items may be obtained from a dedicated data source or from a separate data source in the same manner that clusters of search results are obtained. The or each content item may also be ranked relative to the other clusters as if the content cluster or content item were another cluster among the multiple clusters of search results. In this case, the content information may be regarded as a first ranked cluster. The traffic alert cluster 508 may be considered a second ranked cluster. Similarly, local news cluster 510 would be a third ranked cluster, sports cluster 514 would be a fourth ranked cluster, and so on. Clusters of search results may not have data types intuitively associated with the search term, whereas contextual data may be used to obtain and rank clusters of related search results.

FIG. 6 illustrates a logical flow diagram generally showing one embodiment of an overall process 600 for searching data and ranking clusters of search results and/or content. The process may be performed by a server, a combination of servers, a stand-alone computing device, and/or other configurations of computing devices and/or software modules. To simplify the discussion, the following embodiments are described in terms of a single server communicating with a single mobile client device. At operation 602, a human administrator may predefine certain concepts, cluster types, data types, concept processing rules, context rules, relevance scoring rules, and/or other information that may be used to determine data sources, rank search results, rank clusters of search results, add content, determine user preferences, determine user behavior, and/or perform other operations. Alternatively, or in addition, automated analysis may be performed to determine one or more of the above information types, operational rules, and/or other data. For example, a click stream analysis may be performed on the aggregated data to determine multipliers and/or other factors that may be used in determining the resources and/or ranking information. In another embodiment, no such pre-processing is performed.

At operation 604, the server receives one or more search terms from the mobile device. To simplify the discussion, a single search term will be assumed. Iterative processing and/or other logic may be used in alternative embodiments. The server may also receive or obtain context data at operation 606. For example, the server may examine the user's current location, current applications running on the mobile device, mobile device profile data, preferred online profile data, behaviors, past purchases, social networking relationships, and/or other user-specific data. Similarly, the server may obtain or compute aggregated data from click stream analysis and/or other statistical analysis. The context information may be used to adjust the default weight multiplier prior to and/or during the search process. In another embodiment, no context data is received or determined. Some additional examples of context may include, but are not limited to:

web page or screen of client device for submitting search terms

Tracked user behavior (e.g. purchase history, number of searches)

User specific data (e.g. demographic data such as gender)

Time of day of query time

Time zone of user

Characteristics of search query (e.g. language, length of query, media type)

Data planning of devices or users

Device capabilities or characteristics (e.g. screen size)

Preferences expressed by the user (e.g. not presenting images)

Proximity (e.g. to other devices or other users)

Direction of the device (e.g. device facing north)

Movement of the device (e.g. device is heading north, device is moving at 10 mph)

Tracked behavior or other context of a user in relation to user initiated searches

Social network (e.g. user A's friends searching for sports, so sports are more relevant for user A)

Network characteristics (e.g. speed)

Content owned by the user or on the device used by the user, which may be, but is not necessarily, the same as the mobile device (e.g., the user has documents on their PC that are relevant to a search made on the mobile device)

At decision operation 608, the server determines whether any known concepts were identified from the submitted search term. The server may perform a lookup operation for concepts associated with the search term, or may perform other interpretations (interpretions) such as natural language processing to determine concepts. Concepts generally identify categories of information related to a search term. For example, the search term "Chicago" relates to the concept of a city and the concept of a drama (play). As another example, the search term "chicago pizza" relates to the concept of the style of pizza and the concept of food in the city of chicago.

Each concept may be associated with one or more particular data sources. For example, a local theater's drama or movie schedule may be in particular data sources that will not be searched normally unless it is determined that the user wishes the search term to be associated with a drama or movie. Other examples of concept-specific data sources may include, but are not limited to:

web	stock quote data	Parts inventory data
			wap	Date/individual	Photo
Image of a person	Dictionary	Aircraft timetable
			Photo	Electronic mail	Podcast (podcast)
Video	Entertainment system	Printed material
			Local list	Encyclopedia	Product(s)
News	Event(s)	Ring tone
			Weather (weather)	Ferry timetable	RSS

Multimedia	Finance	Screen saver
			Address book	Flight qualification	Shopping
Astrology	Game machine	Sports
			Audio frequency	Stock keeping	Dictionary for storing dictionary data
Book with detachable cover	Work by	Time of day
			Bus timetable	Landmark	Time zone
Celebrity	Lottery ticket	Train timetable
			City	Movie program time	Translation
Classified into	Cinema for carrying out the method	Traffic control system
			Consumable product	Film	TV broadcasting time
State of the country	Music	Wallpaper
			Currency unit	Human being	Location of a site

Each concept-specific data source may include data of a single data type, such as all stock quote data. Alternatively, the concept-specific data source may actually comprise multiple data sources having the same or different data types. If the server identifies any concepts from the search term, the server searches the corresponding concept-specific data sources at operation 610. More details of one embodiment of the concept-specific search process are provided below in connection with the description of FIG. 7. The search results from each concept-specific data source include clusters of search results. The cluster type of the cluster may be the same as a data type of the plurality of data types or a custom cluster type.

After searching for concept-specific data sources, or if no concepts are identified, the server determines whether any context data is submitted or available at decision operation 612. If context data is available, the server looks up or determines an association between the context data and the context-specific data source. The server searches for associated context-specific data sources at operation 614. The search results from each context-specific data source include another cluster of search results. As above, a context-specific data source may include data of a single data type, such as a list of all restaurants within a certain radius of the current location of the mobile device. Alternatively, a context-specific data source may include multiple data sources having the same or different data types. Thus, the cluster type of the cluster may be the same as the data type of the plurality of data types or a custom cluster type.

After searching for the context-specific data source, or if no context data is available, the server searches for non-specific data sources at operation 616. Non-specific data sources may include data that will always be searched, such as web page indexes, news data, images, shopping data, and the like. At operation 618, the server sorts the results in each cluster of search results obtained from each data source. Search results within a cluster are generally ranked based on relevance of the search results to the search term. Several techniques may be used to rank the search results within the cluster. The weighting factors, rules, and/or other processing may use aggregated clickstream data, user-specific clickstream data, user behavior information, and/or other information. In some cases, at operation 620, particular clusters are populated with search results from multiple data sources and ranked.

At operation 622, the server determines a score for each cluster as a whole. The server may determine a cluster score using the relevance scores of the search results within the cluster. For example, the server may determine a weighted average based on the cumulative score of the relevance scores and based on predefined or dynamically determined factors. At operation 624, each cluster score may be modified based on the concept and or context data. Further details regarding this operation are described below in relation to FIG. 8. All clusters are then arranged in an order based on the cluster scores at operation 626.

In this example embodiment, the ranked clusters are utilized to generate search result web pages, such as those shown in fig. 4 and 5. At operation 628, additional content, such as non-clustered advertisements, logos, and/or other content may be added to the search results web page. The search results web page is then returned to the mobile device for display.

Further details regarding operation 610 are now provided. FIG. 7 illustrates a logical flow diagram generally showing one embodiment of a process 700 for determining and searching concept-specific data sources. At decision operation 702, the server determines whether a plurality of concepts are identified from the search term. If only a single concept is identified, the server searches for a corresponding concept-specific data source at operation 712. If multiple concepts are identified, the server determines a score for each concept at operation 704. Like the cluster scores, the concept scores may be determined based on the relevance of the concepts to the search terms and/or based on an aggregate analysis.

At decision operation 706, the server checks whether any context data was received or determined. If context data is available, the server applies context-specific multipliers to the concept scores. The multipliers may be predefined or dynamically determined to indicate the relevance of each concept to each context.

After modifying the concept scores, or if no context data is available, the server determines the most relevant concept at operation 710. The server may select a single most relevant concept or may rank multiple concepts. At operation 712, the server searches for one or more concept-specific data sources associated with the most relevant concepts. Alternatively, the server may search concept-specific data sources for each of the ranked concepts. To simplify the discussion this exemplary embodiment selects the most relevant concepts and searches a single corresponding concept-specific data source. The search results include concept-specific clusters.

Further details regarding operation 610 of fig. 6 are now provided. FIG. 8 illustrates a logical flow diagram generally showing one embodiment of a process 800 for modifying cluster scores. At decision operation 802, the server checks whether any concepts are identified from the search term. If a concept is identified, the server applies a multiplier to the cluster scores of the respective clusters associated with the concept at operation 804.

After applying the concept multiplier, or if no concept is identified, the server checks if any context data is available at decision operation 806. If context data is available, the server applies one or more context-specific multipliers to the concept score. The modified concept scores are then returned for subsequent ordering of the clusters. It will be understood that each block of the flowchart illustrations, and combinations of blocks in the flowchart illustrations, can be implemented by computer program instructions. These program instructions may be provided to a processor to produce a machine, such that the instructions, which execute on the processor, create means for implementing the actions specified in the flowchart block or blocks. The computer program instructions may be executed by a processor to cause a series of operational steps to be performed by the processor to produce a computer implemented process such that the instructions, which execute on the processor, provide steps for implementing the actions specified in the flowchart block or blocks. The computer program instructions may also cause at least some of the operational steps illustrated in the blocks of the flowchart to be performed in parallel. Further, some steps may also be performed across more than one processor, such as may occur in a multi-processor computer system. Furthermore, one or more blocks or combinations of blocks in the flowchart illustrations may also be performed concurrently with other blocks or combinations of blocks, or even in a different order than illustrated without departing from the scope or spirit of the invention.

Accordingly, blocks of the flowchart illustrations support combinations of means for performing the specified actions, combinations of steps for performing the specified actions and program instruction means for performing the specified actions. It will also be understood that each block of the flowchart illustrations, and combinations of blocks in the flowchart illustrations, can be implemented by special purpose hardware-based systems which perform the specified actions or steps, or combinations of special purpose hardware and computer instructions.

The above specification, examples and data provide a complete description of the manufacture and use of the composition of the invention. Since many embodiments of the invention can be made without departing from the spirit and scope of the invention, the invention resides in the claims hereinafter appended.

Cross Reference to Related Applications

This application claims the benefit of U.S. patent application No. 11/651,102, filed on 5/1/2007, which is incorporated herein by reference in its entirety.

Claims (20)

1. A method for searching data using a network device in communication with a client device, comprising:

determining a plurality of concepts identifying a plurality of categories of information based on a search query received from the client device;

scoring each concept of the determined plurality of concepts based on relevance of the plurality of concepts to the search query;

performing a search on each of a plurality of concept-specific data sources, a plurality of non-concept-specific data sources, and a plurality of context-specific data sources selected based on the scored concepts and the determined context data for the search query to produce a plurality of clusters of search results, wherein the search results from each data source comprise different ones of the plurality of clusters;

generating an ordered list of the plurality of clusters based on cluster scores determined for each cluster of the plurality of clusters as a whole, the cluster scores determined from the scores of each result in a given cluster;

modifying the ordered list of the plurality of clusters by modifying at least one cluster score based on a weighting of clusters associated with at least one of the plurality of concepts identifying a plurality of categories of the information or the context data determined for the search query; and

the plurality of clusters are arranged in an order based on the at least one modified cluster score.

2. The method of claim 1, wherein the relevance is determined by applying a weighting factor to determine a relevance score that employs user behavior information.

3. The method of claim 1, wherein the context data comprises at least one of: information about an application currently running on the client device, past behavior of a user of the client device, or past purchases by the user of the client device.

4. The method of claim 1, wherein at least one cluster of the plurality of clusters is associated with a plurality of particular data types.

5. The method of claim 1, further comprising:

transmitting at least one of the sorted plurality of clusters for display on the client device.

6. The method of claim 5, wherein the at least one of the sorted plurality of clusters transmitted for display on the client device comprises one or more data types.

7. The method of claim 6, wherein the one or more data types are displayed based on a relevance of the one or more data types to the ordered plurality of clusters.

8. The method of claim 1, wherein at least one cluster of the plurality of clusters is configured to display more search results than another cluster of the plurality of clusters to indicate that the at least one cluster is more relevant to the search query than the another cluster.

9. The method of claim 1, wherein the cluster score determined as a whole is determined using a weighted average of cumulative scores based on relevance scores for each result in the given cluster.

10. The method of claim 1, wherein the context data is determined from at least one of:

a characteristic of the search query;

a current location of a user of the client device;

profile data for the client device;

online profile data of a user of the client device;

a preference of a user of the client device;

a social network relationship of a user of the client device; or

Other user specific data.

11. The method of claim 1, wherein the modifying at least one cluster score is based on using context-specific weighting.

12. The method of claim 1, wherein performing a search further comprises performing a search by employing at least one highest ranked concept of the determined plurality of concepts.

13. A network device that searches for data on a network in communication with a client device, comprising:

means for determining a plurality of concepts identifying a plurality of categories of information based on a search query received from the client device;

means for scoring each concept of the determined plurality of concepts based on relevance of the plurality of concepts to the search query;

means for performing a search on each of a plurality of concept-specific data sources, a plurality of non-concept-specific data sources, and a plurality of context-specific data sources selected based on the scored concepts and the determined context data for the search query to produce a plurality of clusters of search results, wherein the search results from each data source comprise different clusters in the plurality of clusters;

means for generating an ordered list of the plurality of clusters based on cluster scores determined for each cluster of the plurality of clusters as a whole, the cluster scores determined from the score of each result in a given cluster;

means for modifying the ordered list of the plurality of clusters by modifying at least one cluster score based on a weighting of clusters associated with at least one of the plurality of concepts identifying a plurality of categories of the information or the context data determined for the search query; and

means for ranking the plurality of clusters in an order based on the at least one modified cluster score.

14. The apparatus of claim 13, wherein the relevance is determined by applying a weighting factor to determine a relevance score that employs user behavior information.

15. The apparatus of claim 13, wherein the context data comprises at least one of: information about an application currently running on the client device, past behavior of a user of the client device, or past purchases by the user of the client device.

16. The apparatus of claim 13, further comprising:

means for transmitting at least one of the sorted plurality of clusters for display on the client device.

17. The apparatus of claim 16, wherein means for transmitting at least one of the sorted plurality of clusters for display on the client device comprises means for transmitting one or more data types.

18. The apparatus of claim 17, wherein the one or more data types are displayed based on a relevance of the one or more data types to the ordered plurality of clusters.

19. The apparatus of claim 13, wherein the context data is determined from at least one of:

a characteristic of the search query;

a current location of a user of the client device;

profile data for the client device;

online profile data of a user of the client device;

a preference of a user of the client device;

a social network relationship of a user of the client device; or

Other user specific data.

20. A client device in communication with a network device for searching for data on a network, comprising:

a transceiver for transmitting the data; and

a processor configured to:

determining a plurality of concepts identifying a plurality of categories of information based on a search query received from the client device;

scoring each concept of the determined plurality of concepts based on relevance of the plurality of concepts to the search query;

performing a search on each of a plurality of concept-specific data sources, a plurality of non-concept-specific data sources, and a plurality of context-specific data sources selected based on the scored concepts and the determined context data for the search query to produce a plurality of clusters of search results, wherein the search results from each data source comprise different ones of the plurality of clusters;

generating an ordered list of the plurality of clusters based on cluster scores determined for each cluster of the plurality of clusters as a whole, the cluster scores determined from the scores of each result in a given cluster;

modifying the ordered list of the plurality of clusters by modifying at least one cluster score based on a weighting of clusters associated with at least one of the plurality of concepts identifying a plurality of categories of the information or the context data determined for the search query; and

the plurality of clusters are arranged in an order based on the at least one modified cluster score.