BRPI0707345A2 - servir resultados de consulta cached com base em uma porção de consulta - Google Patents

Abstract

SERVIR RESULTADOS DE CONSULTA CACHED COM BASE EM UMA PORçãO DE CONSULTA. As modalidades consideram um sistema e método para obter resultados relacionados para uma porção de uma consulta e para gerar um conjunto atualizado de consultas para um cache de um servidor. Outras consultas iniciando com a porção da consulta podem ser identificadas e obtidas a partir de uma estrutura de dados que inclui um cache de servidor e um conjunto de consultas comuns. Após as outras consultas serem identificadas, os resultados para as outras consultas são obtidos a partir do cache de servidor ou a partir de um banco de dados back-end. Um conjunto de consultas comuns, que pode incluir consultas deletadas e adicionais, pode ser utilizado para gerar o conjunto atualizado de consultas para o servidor. Tanto as consultas faltantes como as consultas deletadas que podem pertencer ao servidor com base em uma função de atribuição são inseridas em uma fila, que é posteriormente fornecida ao cache do servidor. A transferência pode ocorrer durante baixa atividade ou estado inativo.

Description

"SERVIR RESULTADOS DE CONSULTA CACHED COM BASE EMUMA PORÇÃO DE CONSULTA"

ANTECEDENTES

Um motor de busca de rede orienta uma busca de u-suário ou consulta, a um servidor de distribuidor, que, porsua vez, remete a consulta para um servidor front-end. Oservidor front-end pode conter consultas e resultados cor-respondentes ou pode consultar com um banco de dados back-end para o resultado de consultas. O motor de busca de redefreqüentemente recebe consultas repetidas a partir de usuá-rios que entram os mesmos termos de busca. Consultas recen-tes e seus resultados podem ser mantidos nos caches front-end do servidor front-end por um periodo de tempo predeter-minado, uma vez que é mais eficiente e menos demorado con-sultar o cache front-end para os resultados desejados do queé consultar o banco de dados back-end, que contém um índicede rede completo e é tipicamente maior do que o cache front-end. Um índice de rede completo pode incluir todos os resul-tados disponíveis na rede, como páginas da rede; portanto,resultando em uma busca demorada uma vez que o índice é mui-to maior do que os resultados armazenados no cache front-end. Entretanto, se os resultados desejados não forem encon-trados no cache front-end, o banco de dados back-end podeser consultado.

Além de armazenar consultas e resultados recentes,os caches front-end podem servir também como um registro debuscas úteis, que podem incluir aqueles resultados que usuá-rios consultaram mais freqüentemente ou aqueles resultadosque um administrador de sistema acredita serão consultados.

Um usuário deve entrar, tipicamente, um termo debusca completo ou consulta para ser apresentado com resulta-dos relevantes. Se uma porção de uma consulta, como os pri-meiros poucos caracteres, for entrada, o usuário é freqüen-temente apresentado com mensagens de erro ou resultados in-corretos. Adicionalmente, se um usuário não tem certeza daconsulta a entrar para receber resultados, o usuário deveentrar individualmente várias consultas e separar atravésdos resultados para encontrar páginas de rede desejáveis,por exemplo. Seria desejável que um usuário entrasse umaporção de uma consulta e recebesse resultados relevantes pa-ra um grupo de consultas iniciando com a porção entrada. A-dicionalmente, à medida que o usuário continua a entrar aconsulta, desse modo estendendo a porção, seria desejávelque os resultados ajustassem automaticamente à medida que aconsulta muda.

Adicionalmente, um tal mecanismo de consultar por-ção seria adicionalmente desejável se recursos fossem pre-servados e as operações concluídas mais rápido por utiliza-ção adicional do cache front-end.

SUMÁRIO

Resultados relacionados para uma porção de umaconsulta são obtidos identificando outras consultas que ini-ciam com a porção da consulta e obtendo os resultados dasoutras consultas. A porção da consulta pode ser atribuída aum servidor front-end que recebe outras consultas iniciandocom a mesma porção da consulta. As outras consultas podemser armazenadas em uma estrutura de dados que inclui um ca-che de servidor e um conjunto comum de consultas. Os resul-tados das outras consultas podem ser armazenados no cache deservidor ou em um banco de dados back-end.

Um conjunto de consultas comuns pode ser formadopor compilar consultas deletadas, deletadas a partir do ca-che de servidor. 0 conjunto de consultas comuns também podeincluir consultas adicionais a partir de uma lista predeter-minada.

Um conjunto atualizado de consultas para o cachede servidor pode ser computado utilizando o conjunto de con-sultas comuns. Uma consulta faltante pode ser uma consultaque pertence ao cache de servidor porém talvez não estejaarmazenado no cache de servidor. A consulta faltante podefazer parte do conjunto de consultas comuns. A conta faltan-te pode ser inserida em uma fila e posteriormente colocadano cache de servidor durante um período de inatividade oubaixa atividade. Similarmente, uma consulta expirada, dele-tada a partir do cache de servidor, também pode ser inseridana fila e posteriormente colocada no cache de servidor.

Esse Sumário é fornecido para introduzir uma sele-ção de conceitos em uma forma simplificada que s~~ao adicio-nalmente descritos abaixo na Descrição Detalhada. Esse Sumá-rio não pretende identificar aspectos chave ou aspectos es-senciais da matéria reivindicada, nem pretende ser utilizadopara limitar o escopo da matéria reivindicada.

BREVE DESCRIÇÃO DOS DESENHOS

O sumário acima e a descrição detalhada a seguirsão entendidos de forma melhor quando lidos em combinaçãocom os desenhos apensos. Modalidades exemplares são mostra-das nos desenhos, entretanto, entende-se que as modalidadesnão são limitadas aos métodos específicos e meios represen-tados nas mesmas. Nos desenhos:

A figura 1 é um diagrama de blocos representandoum dispositivo de computação exemplar;

A figura 2 é um diagrama de blocos representandouma organização de servidor exemplar;

A figura 3 é um diagrama de blocos representandoum sistema de consulta;

A figura 4 é um diagrama de blocos representandoum sistema de construção de consultas;

As figuras 5a e 5b são um diagrama de fluxo ilus-trando uma modalidade de um método de fornecer resultados deconsulta;

A figura 6 é um diagrama de fluxo ilustrando umamodalidade de um método de construir um conjunto de consul-tas comuns; e

A figura 7 é um diagrama de fluxo ilustrando umamodalidade de um método de atualizar um conjunto de consul-tas cache.

DESCRIÇÃO DETALHADA

Com referência à figura 1, um sistema exemplar pa-ra implementar a invenção inclui um dispositivo de computa-ção de propósito geral na forma de um computador 110. Compo-nentes de computador 110 podem incluir, porém não são limi-tados a, uma unidade de processamento 120, uma memória desistema 130, e um barramento de sistema 121 que acopla vá-rios componentes de sistema incluindo a memória de sistema àunidade de processamento 120. O barramento de sistema 121pode ser qualquer um de vários tipos de estruturas de barra-mento incluindo um barramento de memória ou controlador dememória, um barramento periférico, e um barramento local u-tilizando qualquer de uma variedade de arquiteturas de bar-ramento. Como exemplo, e não limitação, tais arquiteturasincluem barramento de Arquitetura Padrão na indústria (ISA),barramento de Arquitetura de Micro canal (MCA), barramentode ISA aperfeiçoada (EISA), barramento local da Video Elec-tronics Standards Association (VESA), e barramento de Inter-conectar Componente Periférico (PCI) (também conhecimentocomo barramento Mezzanine).

O computador 110 inclui, tipicamente, uma varieda-de de meios legíveis por computador. Meios legíveis por com-putador podem ser quaisquer meios disponíveis que podem seracessados pelo computador 110 e incluem meios tanto voláteiscomo não voláteis, meios removíveis e não removíveis. Comoexemplo, e sem limitação, meios legíveis por computador po-dem compreender meios de armazenagem em computador e meiosde comunicação. Meios de armazenagem em computador incluemmeios tanto voláteis como não voláteis, removíveis quantonão removíveis implementados em qualquer método ou tecnolo-gia para armazenagem de informações como instruções legíveispor computador, estruturas de dados, módulos de programa ououtros dados. Meios de armazenagem de computador incluem,porém não são limitados a, RAM, ROM, EEPROM, memória flashou outra tecnologia de memória, CD-ROM, digital versatiledisks (DVD) ou outra armazenagem de disco óptico, cassetesmagnéticos, fita magnética, armazenagem de disco magnéticoou outros dispositivos de armazenagem magnética, ou qualgueroutro meio que possa ser utilizado para armazenar as infor-mações desejadas e que possa ser acessado pelo computador110. Meios de comunicação incorporam, tipicamente, instru-ções legíveis por computador, estruturas de dados, módulosde programa ou outros dados em um sinal de dados moduladocomo uma onda portadora ou outro mecanismo de transporte einclui quaisquer meios de fornecimento de informações. 0termo "sinal de dados modulado" significa um sinal que temuma ou mais de suas características definida ou alterada detal modo a codificar informações no sinal. Como exemplo, enão limitação, meios de comunicação incluem meios com fiocomo uma rede com rio ou conexão de fio direta, e meios semfio como meios sem fio acústicos, RF, infravermelho e ou-tros. Combinações de quaisquer dos acima devem ser incluídastambém no escopo de meios legíveis por computador.

A memória do sistema 130 inclui meios de armazena-gem em computador na forma de memória volátil e/ou não volá-til como ROM 131 e RAM 132. Um sistema de entrada/saída bá-sico 133 (BIOS), contendo as rotinas básicas que ajudam atransferir informações entre elementos no computador 110,como durante partida, é tipicamente armazenado na ROM 131. ARAM 132 contém, tipicamente, módulos de dados e/ou programasque são imediatamente acessíveis a e/ou atualmente sendo o-perados pela unidade de processamento 120. Como exemplo, enão limitação, a figura 1 ilustra o sistema operacional 134,programas de aplicação 135, outros módulos de programa 136 edados de programa 137.

0 computador 110 também pode incluir outros meiosde armazenagem em computador removíveis/não removíveis, vo-láteis/não voláteis. Somente como exemplo, a figura 1 ilus-tra uma unidade de disco rígido 141 que lê a partir de ougrava para meios magnéticos não voláteis, não removíveis,uma unidade de disco magnético 151 que lê a partir de ougrava para um disco magnético não volátil, removível 152, euma unidade de disco óptico 155 que lê a partir de ou gravapara um disco óptico removível, não volátil 156, como um CD-ROM ou outros meios ópticos. Outros meios de armazenagem emcomputador removíveis/não removíveis, voláteis/não voláteisque podem ser utilizados no ambiente operacional exemplarincluem, porém não são limitados a, cassetes de fita magné-tica, cartões de memória flash, digital versatile disks, fi-ta de vídeo digital, RAM de estado sólido, ROM de estado só-lido, e similares. A unidade de disco rígido 141 é tipica-mente conectada ao barramento de sistema 121 através de umainterface de memória não removível como uma interface 14 0, ea unidade de disco magnético 151 e a unidade de disco óptico155 são tipicamente conectadas ao barramento de sistema 121por uma interface de memória removível, como uma interface 150.

As unidades e seus meios de armazenagem em compu-tador associados, discutidos acima e ilustrados na figura 1,fornecem armazenagem de instruções legíveis por computador,estruturas de dados, componentes, módulos de programa e ou-tros dados para o computador 110. Na figura 1, por exemplo,a unidade de disco rígido 141 é ilustrada como armazenandosistema operacional 144, programas de aplicação 145, outrosmódulos de programa 14 6, e dados de programa 147. Observeque esses componentes podem ser iguais ou diferentes do sis-tema operacional 134, programas de aplicação 135, outros mó-dulos de programa 136 e dados de programa 137. O sistema o-peracional 144, programas de aplicação 145, outros módulosde programa 14 6, e dados de programa 147 recebem números di-ferentes aqui para ilustrar que, no mínimo, há cópias dife-rentes. Um usuário pode entrar comandos e informações nocomputador 110 através de dispositivos de entrada como umteclado 162 e um dispositivo de indicação 161, comumentemencionado como um mouse, trackball ou mesa sensível ao to-que. Outros dispositivos de entrada (não mostrados) podemincluir um microfone, manche, bloco de jogo, prato de saté-lite, scanner ou similar. Esses e outros dispositivos de en-trada são freqüentemente conectados à unidade de processa-mento 120 através de uma interface de entrada de usuário 160que é acoplada ao barramento de sistema, porém pode ser co-nectada por outra interface e estruturas de barramento, comouma porta paralela, porta de jogo ou um barramento serialuniversal (USB). Um monitor 191 ou outro tipo de dispositivode exibição também é conectado ao barramento de sistema 121através de uma interface, como uma interface de vídeo 190.

Além do monitor, computadores também podem incluir outrosdispositivos de saída periféricos como alto-falantes 197 euma impressora 196, que podem ser conectados através de umainterface periférica de saída 195.

O computador 110 pode operar em um ambiente ligadoem rede utilizando conexões lógicas a um ou mais computado-res remotos, como computador remoto 180. O computador remoto180 pode ser um computador pessoal, um servidor, um rotea-dor, um PC de rede, um dispositivo par ou outro nó de redecomum, e tipicamente inclui muitos ou todos os elementosdescritos acima em relação ao computador 110, embora somenteum dispositivo de armazenagem de memória 181 tenha sido i-lustrado na figura 1. As conexões lógicas representadas in-cluem uma rede de área local (LAN) 171 e uma rede remota(WAN) 173, porém podem incluir também outras redes. Tais am-bientes de ligação em rede são comuns em escritórios, redesde computador de empresa, intranets e Internet.

Quando utilizado em um ambiente de ligação em redeLAN, o computador 110 é conectado a LAN 171 através de umadaptador ou interface de rede 170. Quando utilizado em umambiente de ligação em rede WAN, o computador 110 inclui,tipicamente, um modem 172 ou outro meio para estabelecer co-municação através da WAN 173, como Internet. O modem 172,que pode ser interno ou externo, pode ser conectado ao bar-ramento de sistema 121 via interface de entrada de usuário160, ou outro mecanismo apropriado. Em um ambiente ligado emrede, módulos de programa representados em relação ao compu-tador 110, ou porções do mesmo, podem ser armazenadas nodispositivo de armazenagem de memória remoto. Como exemplo,e não limitação, a figura 1 ilustra programas de aplicaçãoremotos 185 como residindo no dispositivo de memória 181.Será reconhecido que as conexões de rede mostradas são exem-plares e outros meios de estabelecer um link de comunicaçãoentre os computadores pode ser utilizado.

Toda ou porções dos métodos da presente invençãodescrita acima podem ser incorporadas em hardware, softwareou uma combinação dos dois. Quando incorporado em software,os métodos da presente invenção, ou certos aspectos ou por-ções dos mesmos, podem ser incorporados na forma de códigode programa que quando executado por um sistema de computa-ção fazem com que o sistema de computação execute os métodosda presente invenção. Esse código de programa pode ser arma-zenado em qualquer meio legível por computador, como aqueletermo é definido acima.

A figura 2 representa uma organização de servidor200 que pode ser utilizada para fornecer resultados paraconsultas, como consultas ou porções de consultas inseridasem um motor de busca de internet através, por exemplo, docomputador 110. Uma consulta se origina na Internet 210, on-de um usuário pode inserir uma consulta para a qual desejaobter resultados relevantes, como páginas de rede dirigidasà consulta. A consulta pode ser inserida em um motor de bus-ca, que pode permitir que o usuário insira a consulta de in-teresse e que pode exibir os resultados relevantes para ousuário acessar. A Internet 210 pode ser conectada a um ser-vidor de distribuidor 220, que recebe a consulta a partir daInternet 210. Múltiplos servidores de distribuidor 220 podemser conectados à Internet 210. A figura 2 ilustra três ser-vidores de distribuidor 220 (220a, 220b, e 220c), embora onúmero dos servidores de distribuidor 220 não seja desse mo-do limitado. A consulta pode ser atribuída a um servidor es-pecífico dos servidores de distribuidor 220, por exemplo,por um endereço de protocolo de Internet (IP) de origem daconsulta. Outros esquemas podem ser utilizados para atribuira consulta a um dos servidores de distribuidor 220. Alterna-tivamente, a consulta pode ser aleatoriamente enviada aqualquer um dos servidores de distribuidor 220.

O servidor de distribuidor 220 que recebe a con-sulta pode transmitir a consulta para um servidor front-end230, como um dos servidores front-end 230a, 230b, 230c e230n mostrados na organização de servidor 200 da figura 2. Aorganização de servidor 200 não é limitada a um certo númerodos servidores front-end 230. O servidor front-end 230 querecebe a consulta a partir do servidor de distribuidor 220pode fazer isso com base em um mapeamento que liga a consul-ta ao servidor front-end 230. Por exemplo, a consulta podeser hashed para produzir um valor, que, por sua vez, é uti-lizado em uma função de mapeamento que coloca certas consul-tas em servidores front-end específicos 230 e pode assegurarque a mesma consulta seja sempre, ou quase isso, dirigida aomesmo servidor front-end 230. A função de mapeamento podedeterminar qual dos servidores front-end 230 receberá a con-sulta. O servidor front-end 230 não necessita ser atribuídocom base em uma função de mapeamento e pode em vez disso,por exemplo e não por limitação, receber aleatoriamente aconsulta.Um cache, ou armazenagem local, pode conter con-sultas e seus resultados correspondentes. 0 cache pode fazerparte do servidor front-end 230, e as consultas e resultadosdo cache podem ser um conjunto de consultas e resultados re-centes, como aqueles a partir de um período de tempo prede-terminado, por exemplo três horas. Quando o servidor front-end 230 recebe a consulta a partir do servidor de distribui-dor 220, o servidor front-end 230 pode buscar seu cache paradeterminar se a consulta, e seus resultados correspondentes,já estão armazenados no cache. Se a consulta estiver no ca-che, então o servidor front-end 230 pode retornar os resul-tados a partir do cache. Os resultados podem ser fornecidosao usuário que entrou a consulta.

Os servidores front-end 230 podem estar em comuni-cação com um banco de dados back-end 240, que pode conterresultados existentes, por exemplo páginas de rede. Resulta-dos de consulta podem ser armazenados no banco de dadosback-end 240. Se a consulta entrada não estiver no cache doservidor front-end 230, então o banco de dados back-end 240pode ser consultado para retornar resultados de consulta re-levantes ao us.uário. Como o banco de dados back-end 240 étipicamente muito maior do que o cache dos servidores front-end 230, a consulta com o banco de dados back-end pode demo-rar um período de tempo significativamente mais longo do quea consulta com o cache dos servidores front-end 230. Portan-to, a consulta com o banco de dados back-end 240 pode ocor-rer somente, por exemplo, quando o servidor front-end 230não contiver os resultados solicitados ou quando o servidorfront-end 230 encontra um problema, como uma falha do servidor.

A figura 3 é um diagrama de blocos que representaum sistema de consulta 300, que pode ser utilizado para ob-ter resultados para uma porção de uma consulta. 0 sistema deconsulta 300 pode incluir o servidor de distribuidor 220 pa-ra receber uma porção de uma consulta. A porção da consultapode ser, por exemplo, os três primeiros caracteres de umaconsulta. Um usuário que deseja resultados para a consulta,pode digitar ou entrar a porção da consulta em um motor debusca na Internet. A porção da consulta pode ser dirigida aoservidor de distribuidor 220 com base em um endereço IP docomputador 110 a partir de onde a porção da consulta se ori-gina. A porção da consulta pode ser aleatoriamente dirigidaao servidor de distribuidor 220.

O servidor de distribuidor 220 pode ser responsá-vel por atribuir a porção da consulta ao servidor front-end230. Uma função hash pode ser utilizada pelo servidor dedistribuidor 220 para essa tarefa de atribuição. O servidorde distribuidor 220 pode, por exemplo, atribuir a porção daconsulta ao servidor front-end 230 de modo que outras con-sultas que têm a mesma porção serão atribuídas ao mesmo ser-vidor front-end 230. Após a porção da consulta ser atribuídaao servidor front-end 230, o servidor de distribuidor 220pode transmitir a porção da consulta ao servidor front-endatribuído, 230.

Após o servidor front-end 230 receber a porção daconsulta, o servidor front-end 230 pode ser responsável porexecutar uma busca para obter outras consultas que têm amesma porção que a porção da consulta. Para obter essas con-sultas, o servidor front-end 230 pode consultar uma estrutu-ra de dados 310. A estrutura de dados 310, embora mostradocomo um componente separado na figura 3, pode fazer parte doservidor front-end 230. A estrutura de dados 310 pode inclu-ir um cache de servidor, como consultas cache 320. As con-sulta cache 320 podem incluir consultas anteriores que forammantidas na estrutura de dados 310 por um período de tempopredeterminado. Desse modo, as consultas cache 320 podem,por exemplo, incluir as consultas mais recentes. As consul-tas cache 320 podem ser mantidas na estrutura de dados 310para acesso fácil e rápido a consultas recentes. A estruturade dados 310 pode incluir também um conjunto de consultascomuns 330. A formação do conjunto de consultas comuns édescrita em mais detalhe abaixo.

A estrutura de dados pode ser uma estrutura trieaumentada, que é uma estrutura que facilita recuperação rá-pida de informações relacionadas a uma consulta ou uma por-ção de uma consulta. Por exemplo, possíveis porções de umaconsulta juntamente com informações adicionais relacionadasa cada porção da consulta podem ser armazenadas na estruturatrie. As informações relacionadas a cada porção da consultapodem ser, por exemplo, uma lista de um número predetermina-do de consultas mais freqüentemente solicitadas iniciandocom a porção das consulta. A lista pode ser separada em umaordem de freqüência descendente, de modo que a consulta so-licitada mais comumente iniciando com a porção da consulta éprimeiramente listada.

Quando uma lista de outras consultas, que pode in-cluir a porção da consulta, é obtida a partir da estruturade dados 310, uma estrutura de resultados 340, que pode seruma estrutura cache, é consultada. A estrutura de resultadospode ser uma parte do servidor front-end 230. A estrutura deresultados 340 contém resultados para consultas. Após con-sulta com a estrutura de resultados 340, os resultados paraconsultas que iniciam com a porção da consulta são obtidose fornecidos ao usuário. Esses resultados podem ser, por e-xemplo, uma seleção múltipla de páginas da rede.

O banco de dados back-end 240 também pode ser in-cluído como parte do sistema de consulta 300. O banco de da-dos back-end 240 pode ser consultado se resultados para umaou mais das consultas que incluem a porção da consulta nãoforem localizados na estrutura de resultados 340. Os resul-tados obtidos a partir do banco de dados back-end 240 sãotambém fornecidos ao usuário, como mostrado na figura 3.

Uma representação de diagrama de blocos de um sis-tema de construção de consultas comuns 400 é ilustrada nafigura 4. O sistema 400 pode ser atribuído a tarefa de criaras consultas comuns 330, que podem ser utilizadas para obterconsultas que têm a mesma porção que a porção da consulta. 0sistema de construção de consultas comuns 400 pode incluir oservidor front-end 230, que recebe a porção da consulta apartir do servidor de distribuidor 220. Um cache de servidor410 pode fazer parte do servidor front-end 230. O cache deservidor 410 pode ser uma estrutura de cache do servidorfront-end 230 que armazena consultas anteriores, como con-sultas que foram mantidas por um período de tempo predeter-minado. O cache de servidor 410 do servidor front-end 230pode ser o mesmo componentes que as consultas de cache 320da estrutura de dados 310, que podem fazer parte do servidorfront-end 230.

As consultas podem ser freqüentemente deletadas apartir do cache de servidor 410 do servidor front-end 230.As deleções podem ocorrer devido ao tamanho limitado do ca-che de servidor 410; uma consulta pode necessitar ser dele-tada para criar espaço de armazenagem para uma consulta maisnova (ou porção da consulta). Ou, as deleções podem ocorrerperiodicamente. Quando as consultas são deletadas a partirdo cache de servidor 410, uma entrada Iog 420 pode receber erastrear as consultas deletadas. Após decorrer um período detempo predeterminado, a entrada Iog 420 pode fornecer asconsultas deletadas para um compilador de entrada Iog 430,que compila as entradas deletadas. O compilador de entradaIog 430 pode compilar as entradas deletadas com base em cri-térios anteriormente determinados, como, por exemplo, aque-las entradas que aparecem mais de uma vez durante um períodode uma semana. 0 compilador de entrada Iog 430, após terconcluído a compilação de consultas deletadas, pode fornecera compilação para as consultas comuns 330 da estrutura dedados 310. A estrutura de dados 310 armazena então as con-sultas comuns para uso em fornecer consultas que têm a mesmaporção que a porção da consulta buscada para a estrutura deresultados 340.As consultas comuns 330 podem servir como um su-plemento para as consultas cache 320. As consultas cache 320podem ser consultas mais recentes, enquanto as consultas co-muns 330, que podem não necessariamente ser consultas recen-tes, podem ser consultas freqüentemente solicitadas a partirde um periodo de tempo relativamente longo, predeterminado,como uma semana.

As figuras 5a e 5b ilustram um método de fornecerresultados de consulta. Em 505, uma porção de uma consulta éobtida. A porção da consulta pode ser iniciada por um usuá-rio, que, desejando resultados relacionados à consulta, en-tra a porção da consulta em um motor de busca na Internet,por exemplo. A porção da consulta pode ser obtida no servi-dor de distribuidor 220. Em 510, a porção da consulta é exa-minada para determinar se a porção da consulta casa com umaentrada predeterminada. Se a porção da consulta casar umaentrada predeterminada, então, em 515 caracteres seguintessão atribuídos como a porção da consulta. Como um número deentradas que ocorrem freqüentemente podem existir que o usu-ário não pretende que seja parte da consulta, essa compara-ção pode eliminar a provisão de resultados de consulta paraconsultas indesejáveis. Por exemplo, se um usuário entratais consultas iniciando como "http" e "www", o usuário ti-picamente não deseja buscar essas consultas porém pode, emvez disso, estar interessado nos caracteres que seguem essasentradas que ocorrem freqüentemente. Desse modo, por atribu-ir caracteres seguinte, como três caracteres após "www", co-mo a porção da consulta, a porção adequada da consulta podeser buscada. A porção da consulta pode ser comparada com ou-tras entradas predeterminadas.

Após caracteres seguintes serem atribuídos como aporção da consulta, e se a porção da consulta não casar comuma entrada predeterminada, então o método de fornecer re-sultados de consulta pode prosseguir para 520 a partir de515 e 510, respectivamente. Em 520, uma representação daporção da consulta pode ser computada. Essa representaçãopode ser uma função hash da porção da consulta, por exemplo.Outras representações também são possíveis.

Em 525, após 520, a porção da consulta pode seratribuída a um servidor front-end 230. Como uma'representa-ção da porção da consulta foi computada em 520, então a re-presentação pode ser utilizada para atribuir a porção daconsulta ao servidor front-end 230. Outros critérios de a-tribuição podem ser utilizados para atribuir a porção daconsulta ao servidor front-end. OU a atribuição pode ser umaseleção aleatória. Em 530, a porção da consulta pode ser en-viada para o servidor front-end atribuído 230.

535 determina se uma estrutura de dados, como aestrutura de dados 310 descrita acima com relação à figura 3e figura 4, contém consultas gue iniciam com a porção daconsulta. Se a estrutura de dados 310, gue pode incluir con-sultas cache 320 gue podem incluir consultas anteriores gueforam mantidas na estrutura de dados 310 por um período detempo predeterminado e consultas comuns 330, não contiverconsultas gue iniciam com a porção da consulta, então o usu-ário, em 540, recebe uma lista de resultado vazia. Se, en-tretanto, a estrutura de dados 310 contiver consultas queiniciam com a porção da consulta, então o método prosseguepara 545 (figura 5b) . Em 545, as consultas iniciando com aporção da consulta podem ser obtidas a partir da estruturade dados 310.

Em 550, uma determinação é feita para determinarse, para cada consulta obtida iniciando com a porção da con-sulta, os resultados são armazenados em um cache de servi-dor, como a estrutura de resultados 340, que pode fazer par-te do servidor front-end 230. Em 560, se os resultados parauma consulta obtida iniciando com a porção da consulta nãoestiverem na estrutura de resultados 340, então os resulta-dos são obtidos a partir do banco de dados back-end 240. Em555, se em vez disso os resultados para uma consulta obtidainiciando com a porção da consulta estiverem na estruturade resultados 340, então os resultados são obtidos a partirda estrutura de resultados 340. A determinação em 550 é exe-cutada para cada consulta obtida que inclui a porção da con-sulta. Isso pode assegurar que os resultados são fornecidospara cada consulta que inclui a porção da consulta, quer osresultados sejam do banco de dados back-end 240 ou da estru-tura de resultados 340. 0 método de fornecer consulta termi-na em 565 onde os resultados são fornecidos.

A figura 6 é um diagrama de fluxo ilustrando ummétodo de construir um conjunto de consultas comuns. Em 610,consultas são geradas com base em uma lista predeterminada.A lista predeterminada pode incluir consultas que um admi-nistrador de sistema acredita devam fazer parte do conjuntode consultas comuns 330. Por exemplo, uma consulta predeter-minada pode ser um novo filme que não foi utilizado em bus-cas de consulta por usuários porém que se espera que se tor-ne popular e buscado amplamente no futuro próximo. Pela adi-ção de tais consultas às consultas comuns 330, que é parteda estrutura de dados 310, uma busca para a consulta, ouporção da consulta pode não exigir consulta com o banco dedados back-end 240.

Em 615, consultas deletadas a partir de um cachede um servidor, como o cache de servidor 410 do servidorfront-end 230 ou as consultas cache 320, são compiladas. Asconsultas deletadas podem ser compiladas durante um períodode tempo predeterminado. As consultas deletadas podem serrastreadas pela entrada Iog 420 e compiladas pelo compiladorde entrada Iog 430, como discutido acima com relação ao sis-tema de construção de consulta comum 400 da figura 4.

Em 620, o conjunto de consultas comuns 330 é for-mado. As consultas comuns podem incluir uma combinação oucompilação das consultas predeterminadas, geradas em 610, eas consultas deletadas, geradas em 615. Após formar as con-sultas comuns 330, em 625, as consultas comuns' 330 são dis-tribuídas para os servidores front-end 230. Se as consultasdeletadas forem aquelas deletadas a partir de um servidorfront-end específico, como o servidor front-end 230b da fi-gura 2, então as consultas comuns podem ser distribuídas pa-ra os outros servidores front-end 230a, 230c, e 230n do sis-tema 200.

A figura 7 é um diagrama de fluxo ilustrando ummétodo de atualizar as consultas cache 320 de uma estruturade dados 310 de um servidor front-end, que pode fazer partede um servidor front-end 230. As consultas cache 320 podemincluir consultas recentes. Em 710, um conjunto atualizadode consultas é computado. O conjunto atualizado de consultaspode incluir consultas a partir das consultas comuns 330 queseriam atribuídas ao servidor front-end 230 com base, porexemplo, em uma operação de hashing e mapeamento que operapara orientar as mesmas consultas e as mesmas porções dasconsultas para o mesmo servidor front-end 230. O conjuntoatualizado de consultas pode ser computado pelo servidorfront-end 230. Em 720, o conjunto atualizado de consultaspode ser armazenado na estrutura de dados 310 com as consul-tas cache 320. Isso serve para atualizar as consultas cache320.

Em 730, uma consulta no conjunto atualizado deconsultas porém não nas consultas cache 320 (uma consultafaltante) é determinada. Se nenhuma consulta casar com essecritério, o método prossegue para buscar uma consulta queefetivamente case com os critérios. O método continua de mo-do que a consulta faltante seja adicionada às consultas ca-che 320. Em 740, a consulta faltante é adicionada a uma fi-la.

O método pode prosseguir para 750, onde o sistemaé analisado para determinar se o sistema está levemente car-regado. Cada vez que um servidor front end 230 envia uma so-licitação para o sistema back-end 240, a resposta a partirdo sistema back-end 240 pode incluir realimentação que podeser utilizada para determinar o estado atual do back-end240, que pode incluir carga back-end atual. Por exemplo, arealimentação pode incluir um número médio de solicitaçõesque estão em uma fila esperando para serem processadas peloback-end 240 ou uma qualidade de uma resposta que o back-end240 é capaz de obter durante um limite de tempo de processa-mento de consulta. 0 servidor front-end 230 pode então uti-lizar um algoritmo para determinar se o back-end atual 240deve ser considerado como intensamente ou levemente carrega-do com base na realimentação. Se o sistema estiver levementecarregado, então o método pode prosseguir para 760.

Em 760, a partir de 740 ou 750, a consulta faltan-te é removida da fila. Em 770, a consulta faltante pode serfornecida ao banco de dados back-end 240. Em 780, o banco dedados back-end 240 atualiza as consultas cache 320 com aconsulta faltante. A consulta faltante não mais está " fal-tando" nas consultas cache 320.

Como pode ser reconhecido, as modalidades revela-das podem ser implementadas como um todo ou em parte em umou mais sistemas ou dispositivos de computação. A figura 1ilustra os componentes funcionais de um exemplo de um siste-ma de computação 100, no qual aspectos podem ser incorpora-dos ou postos em prática. Como utilizado aqui, os termos"sistema de computação", "sistema de computador", e "compu-tador" se referem a qualquer máquina, sistema ou dispositivoque compreende um processador capaz de executar ou de outromodo processar código de programa e/ou dados. Os exemplos desistemas de computação incluem, sem nenhuma limitação pre-tendida, computadores pessoais (PCs), minicomputadores, com-putadores de grande porte, clientes finos, PCs de rede, ser-vidores, estações de trabalho, computadores laptop, computa-dores portáteis, eletrônica programável pelo consumidor,consoles de multimeios, consoles de jogos, receptores de sa-télite, set-top boxes, caixas eletrônicos automatizados, ca-sas de jogos, telefones móveis, assistentes pessoais digi-tais (PDAs), e qualquer outro sistema ou máquina baseado emprocessador. Os termos "código de programa" e "código" sereferem a qualquer conjunto de instruções que são executadasou de outro modo processadas por um processador. Código deprograma e/ou dados podem ser implementados na forma de ro-tinas, programas, objetos, módulos, estruturas de dados esimilares que executam funções especificas.

Observa-se que os exemplos acima foram fornecidossimplesmente para fins de explicação e não são de modo algumpara serem interpretados como limitadores. Embora a invençãotenha sido descrita com referência a várias modalidades, en-tende-se que as palavras que foram utilizadas aqui são pala-vras de descrição e ilustração, em vez de palavras de limi-tação. Além disso, embora as modalidades tenham sido descri-tas aqui com referência a meios específicos, materiais e e-xemplos, as modalidades não pretendem ser limitadas aos de-talhes revelados aqui; em vez disso, as modalidades estendema todas as estruturas funcionalmente equivalentes, métodos eusos, como estão compreendidas no escopo das reivindicaçõesapensas.

Claims (20)

1. Método de fornecer resultados de consulta, ométodo sendo CARACTERIZADO por compreender:obter uma porção de uma consulta;atribuir a porção da consulta a um servidor (230);obter outras consultas iniciando com a porção daconsulta; eobter resultados de algumas ou todas as outrasconsultas com base na porção da consulta.

2. Método, de acordo com a reivindicação 1,CARACTERIZADO por compreender ainda:computar uma representação da porção da consulta;em que a atribuição da porção da consulta a umservidor (230) compreende atribuir a porção da consulta a umservidor (230) com base na representação.

3. Método, de acordo com a reivindicação 1,CARACTERIZADO por compreender ainda:determinar se a porção da consulta casa com umaentrada predeterminada; eatribuir caracteres seguintes como a porção daconsulta.

4. Método, de acordo com a reivindicação 1,CARACTERIZADO por compreender ainda:armazenar consultas cache (320) e um conjunto deconsultas comuns (330) em uma estrutura de dados (310);em que a obtenção de outras consultas iniciandocom a porção da consulta compreende obter outras consultasiniciando com a porção da consulta a partir da estrutura dedados (310) .

5. Método, de acordo com a reivindicação 4,CARACTERIZADO por compreender ainda:modificar a estrutura de dados (310) para refletiralterações feitas nas consultas cache (320) e alteraçõesfeitas no conjunto de consultas comuns (330).

6. Método, de acordo com a reivindicação 4,CARACTERIZADO por compreender ainda:armazenar as consultas cache (320) e o conjunto deconsultas comuns (330) de acordo com uma freqüência de uso;eexibir os resultados de cada uma das outras con-sultas iniciando com a porção da consulta em uma ordem des-cendente da freqüência de uso.

7. Método, de acordo com a reivindicação 1,CARACTERIZADO pelo fato de que a obtenção dos resultados decada uma das outras consultas iniciando com a porção da con-sulta compreende obter resultados de cada uma das outrasconsultas a partir de cache (410) do servidor (230).

8. Método, de acordo com a reivindicação 1,CARACTERIZADO pelo fato de que obter resultados de cada umadas outras consultas iniciando com a porção da consulta com-preende obter resultados de cada uma das outras consultas apartir de um servidor back-end (240) .

9. Método, de acordo com a reivindicação 1,CARACTERIZADO por compreender ainda:fornecer um resultado vazio se as outras consultasiniciando com a porção da consulta não puderem ser obtidas.

10. Sistema de consulta (300), CARACTERIZADO porcompreender:um servidor de distribuidor (220) que recebe umaporção de uma consulta;uma estrutura de dados (310) que armazena consul-tas cache (320) e um conjunto de consultas comuns (330);uma estrutura de resultados (340) que provê resul-tados para as consultas cache (320) e o conjunto de consul-tas comuns (330); eum servidor front-end (230) que consulta a estru-tura de dados (310) e a estrutura de resultados (340) parafornecer resultados relacionados com base na porção da con-sulta .

11. Sistema, de acordo com a reivindicação 10,CARACTERIZADO por compreender ainda um banco de dados back-end (240).

12. Sistema, de acordo com a reivindicação 10,CARACTERIZADO pelo fato de que o servidor de distribuidor(220) atribui a porção da consulta ao servidor front-end(230).

13. Sistema, de acordo com a reivindicação 10,CARACTERIZADO pelo fato de que a porção da consulta é umprefixo da consulta.

14. Método de construir um conjunto de consultascomuns (330), o método sendo CARACTERIZADO por compreender:compilar entradas deletadas a partir de um cache(410) de um servidor front-end (230);formar um conjunto de consultas comuns (330) com-preendidas das entradas deletadas, em que as entradas dele-tadas são a partir de uma faixa de tempo predeterminada; edistribuir o conjunto de consultas comuns (330)para outro servidor front-end (230) .

15. Método, de acordo com a reivindicação 14,CARACTERIZADO pelo fato de que a distribuição do conjunto deconsultas comuns (330) para outro servidor front-end (230)compreende distribuir o conjunto de consultas comuns (330)para múltiplos servidores front-end (230).

16. Método, de acordo com a reivindicação 14,CARACTERIZADO por compreender ainda:gerar consultas adicionais baseadas em uma listapredeterminada; eadicionar as consultas adicionais ao conjunto deconsultas comuns (330).

17. Método, de acordo com a reivindicação 14,CARACTERIZADO por compreender ainda:computar um conjunto atualizado de consultas paraum servidor front-end (230), em que o conjunto atualizado deconsultas é compreendido de consultas atribuídas no conjuntode consultas comuns (330) que são atribuídas ao servidorfront-end (230) ; econstruir uma estrutura de dados (310) para o ser-vidor front-end (230), em que o conteúdo da estrutura de da-dos é compreendido do conjunto atualizado de consultas econsultas cache (320).

18. Método, de acordo com a reivindicação 17,CARACTERIZADO por compreender ainda:computar consultas faltantes, em que as consultasfaltantes pertencem em um cache (410) do servidor front-end(230); einserir as consultas faltantes em uma fila.

19. Método, de acordo com a reivindicação 18,CARACTERIZADO por compreender ainda:remover as consultas faltantes da fila;enviar as consultas faltantes a partir da fila pa-ra um banco de dados back-end (240); einserir as consultas faltantes no cache (410) doservidor front-end (230).

20. Método, de acordo com a reivindicação 17,CARACTERIZADO por compreender ainda:determinar se uma consulta expirada que expirou apartir do cache (410) do servidor (230) pertence ao conjuntoatualizado de consultas;inserir a consulta expirada em uma fila,remover a consulta expirada a partir da fila,enviar a consulta expirada a partir da fila paraum banco de dados back-end (240); einserir a consulta expirada no cache (410) do ser-vidor front-end (230).