KR20130132757A

KR20130132757A - 예측 쿼리 제안 캐싱

Info

Publication number: KR20130132757A
Application number: KR1020137004430A
Authority: KR
Inventors: 스티븐 티. 카네프스키
Original assignee: 구글 인코포레이티드
Priority date: 2010-07-22
Filing date: 2011-07-19
Publication date: 2013-12-05
Anticipated expiration: 2031-07-19
Also published as: AU2011282258B2; WO2012012396A3; JP2013535729A; US9323808B1; AU2011282258A1; CN103221951A; US8560562B2; WO2012012396A2; KR101708448B1; US20120023120A1; CN103221951B; JP5745627B2; EP2596441A2

Abstract

사전-캐싱 쿼리 제안들을 위한, 방법들, 시스템들, 장치, 및 컴퓨터 프로그램 제품들이 개시된다. 일 양태에서, 방법은 탐색 리소스에 대한 요청을 클라이언트 디바이스로부터 수신하는 단계; 상기 요청에 응답하여 상기 탐색 리소스를 상기 클라이언트 디바이스에 제공하는 단계를 포함하고, 상기 탐색 리소스는 상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 하는 제1 명령어들; 초기 쿼리 제안들; 및 제2 명령어들을 포함하며, 상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금 클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고; 상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고; 상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고; 및 상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 한다.

Description

예측 쿼리 제안 캐싱{PREDICTIVE QUERY SUGGESTION CACHING}

본 명세서는 쿼리 제안(query suggestion)들에 관한 것이다.

인터넷은 광범위한 리소스들로의 액세스를 제공한다. 리소스로는 예를 들어, 비디오 파일, 이미지 파일, 오디오 파일, 또는 특정 주제들, 도서 기사, 또는 뉴스 기사를 위한 콘텐츠를 포함하는 웹 페이지가 있다. 탐색 시스템은 탐색 쿼리의 수신에 응답하여 하나 이상의 리소스를 선택할 수 있다. 탐색 쿼리는 데이터로서, 사용자의 정보 요구를 충족하기 위해 사용자가 탐색 쿼리에 제출한 것이다. 탐색 시스템은 선택된 리소스들로 링크시키는 탐색 쿼리를 제공하기 위해, 그 탐색 쿼리의 관련성(relevance)과 다른 리소스들에 관련된 자신의 중요도(importance)에 기초하여, 리소스들을 선택하여 점수화한다. 탐색 결과는 일반적으로 그 점수에 따라 순서가 부여되어, 탐색 결과 페이지에 제공된다.

탐색 시스템들은 사용자가 자신의 정보 요구를 충족시키는 것을 돕기 위하여 사용자들에게 탐색 제안들을 제공할 수 있다. 본 명세서에서 사용되는 것에 따르면, 용어 "쿼리 제안(query suggestion)"은 제안되는 데이터로서, 탐색을 정제(refine)하거나 탐색 전략(search strategy)을 정제하는데 사용될 수 있다. 쿼리 제안은 다른 탐색 쿼리, 키워드들, 또는 탐색 쿼리 또는 키워드가 속하는 토픽(topic)일 수 있다. 쿼리 제안은 주로 추가 쿼리로서 사용되며, 예를 들어 쿼리 제안은 쿼리 제안에 대한 사용자 선택에 응답하여, 쿼리로서 탐색 시스템에 의해 처리될 수 있다.

일부 탐색 시스템들은 사용자가 타이핑하는 동안 쿼리 제안들을 제공하여, 사용자가 전체 쿼리(entire qurry)를 타이핑하지 않고 쿼리 제안을 선택할 수 있게 한다. 이러한 시스템들은 일반적으로 각 키스트로크(keystroke)로 탐색 엔진에 제안 요청들을 송신하고, 탐색 엔진은 입력된 문자들에 매치하는 접두사(prefix)로 된 쿼리 제안들을 제공한다. 제안 서비스는 또한 모바일 디바이스 상에서도 제공된다. 그러나 모바일 디바이스는 종종 더 높은 네트워크 지연(much higher network latency)을 처리할 필요가 있고, 제안 서비스의 성능은 지연이 증가함에 따라 악화될 수 있다. 종종 지연에 의해 수신된 제안들이 입력된 현재 쿼리 접두사와 매치되지 않을 수도 있으며, 이로써 사용자 경험을 향상시키기 보다는 오히려 악화시키는 경향이 있다.

일반적으로, 본 명세서에서 설명되는 주제의 혁신적인 양태는 방법들로 구현될 수 있는데, 이 방법들은 탐색 리소스에 대한 요청을 클라이언트 디바이스로부터 수신하는 동작; 및 상기 요청에 응답하여 상기 탐색 리소스를 상기 클라이언트 디바이스에 제공하는 동작을 포함하고, 상기 탐색 리소스는 제1 명령어들, 초기 쿼리 제안들, 및 제2 명령어들을 포함하며, 상기 제1 명령어들은 상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 하고, 상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금 클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고, 상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고, 상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고, 및 상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 한다. 이 양태의 다른 실시예들은 상응하는 시스템, 장치, 및 컴퓨터 스토리지 디바이스상에 인코딩되어, 상기 방법들의 동작들을 수행하도록 구성된 컴퓨터 프로그램을 포함한다.

일반적으로, 본 명세서에서 설명되는 주제의 또 다른 양태는 방법들로 구현될 수 있는데, 이 방법들은 탐색 엔진으로부터 탐색 리소스에 대한 요청을 제공하는 동작; 및 상기 요청에 응답하여 상기 탐색 리소스를 수신하는 동작을 포함하고, 상기 탐색 리소스는 제1 명령어들, 초기 쿼리 제안들, 및 제2 명령어들을 포함하며, 상기 제1 명령어들은 상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하게 하고, 상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금 클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고, 상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고, 상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고, 및 상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 한다. 이 양태의 다른 실시예들은 상응하는 시스템, 장치, 및 컴퓨터 스토리지 디바이스상에 인코딩되어, 상기 방법들의 동작들을 수행하도록 구성된 컴퓨터 프로그램을 포함한다.

본 명세서에서 설명된 주제의 하나 이상의 실시예에 대한 상세 내용은 첨부도면들 및 이하 상세한 설명에서 개시된다. 본 주제의 다른 특징, 양태, 및 이점들은 상세한 설명과 도면, 및 청구범위로부터 명백해질 것이다.

도 1은 클라이언트 디바이스와의 데이터 통신하는 쿼리 제안 시스템의 블록도이다.
도 2는 탐색 인터페이스 리소스를 제공받을 초기 쿼리 제안들을 결정하기 위한 예시적 프로세서의 순서도이다.
도 3은 탐색 엔진 인터페이스와 함께 초기 쿼리 제안들을 제공하는 예시적 프로세스의 순서도이다.
도 4는 클라이언트 디바이스로부터 쿼리 제안들을 수신하고 요청하기 위한 예시적 프로세스의 순서도이다.
도 5는 클라이언트 디바이스로부터의 쿼리 제안 요청들을 탐색 엔진에 제공하고, 수신된 쿼리 제안들을 처리하기 위한 예시적 프로세스의 순서도이다.
여러 도면에서 유사한 참조 번호들 및 명칭들은 유사한 요소들을 가리킨다.

§ 1.0 개관( Overview )

도 1은 클라이언트 디바이스(106)와 데이터 통신을 하는 쿼리 제안 시스템(100)의 블록도이다. 로컬 영역 네트워크(LAN), 광역 네트워크(WAN), 인터넷 또는 이것들의 조합과 같은 컴퓨터 네트워크(102)는 퍼블리셔(104), 클라이언트 디바이스(106), 및 탐색 시스템(110)을 연결시킨다.

퍼블리셔(104)는 네트워크(102)를 사용하여 리소스로의 전자적 액세스를 서비스하고 제공하는 모든 웹 사이트이다. 웹 사이트는 도메인 이름과 연관된 하나 이상의 리소스(105)의 집합일 수 있다. 예시적 웹 사이트는 텍스트, 그래픽 이미지, 멀티미디어 콘텐츠, 및 스크립트와 같은 프로그래밍 요소들을 포함할 수 있는, HTML(Hypertext Markup Language)로 포맷된 웹 페이지들의 집합이다.

리소스는 네트워크(102)를 통해 퍼블리셔(104)에 의해 제공될 수 있고, 리소스 어드레스에 의해 주소가 지정되는 모든 데이터이다. 리소스들은 HTML 페이지, 워드 프로세싱 문서, PDF(Portable Document Format)문서, 이미지, 비디오, 및 피드 소스(feed source) 등을 포함한다. 리소스들은 단어(word), 구(phrase), 사진 등을 포함할 수 있고, 메타(또는 메타데이터) 정보와 같은 내장된 정보, 및 하이퍼링드 및/또는 내장된 명령어(예컨대, 자바스크립트 스크립트)들을 포함할 수 있다.

각 리소스는 고유하게 식별될 수 있는 주소지정이 가능한 저장소 위치를 갖는다. 주소지정이 가능한 위치는 예컨대, URL(Universal Resource Locator)과 같은 리소스 로케이터(resource locator)에 의해 주소지정된다.

클라이언트 디바이스(106)는 사용자의 제어하에 있고, 네트워크(102)를 통해 리소스들을 요청하여 수신할 수 있는 전자 디바이스이다. 예시적 클라이언트 디바이스(106)는 개인 컴퓨터, 랩탑 컴퓨터, 모바일 통신 디바이스, 및 네트워크(102)를 통해 데이터를 송신 및 수신할 수 있는 다른 디바이스들을 포함한다. 클라이언트 디바이스(106)는 통상적으로 네트워크(102)를 통해 데이터의 송신과 수신을 용이하게 하는, 웹 브라우저와 같은 사용자 애플리케이션을 포함한다.

탐색 시스템(110)은 리소스들을 탐색하는 탐색 엔진(118)을 포함한다. 수많은 퍼블리셔들이 존재하기 때문에, 네트워크(102)를 통해 이용가능한 수많은 리소스들이 존재한다. 이러한 리소스들의 탐색을 용이하게 하기 위해, 탐색 엔진(118)은 퍼블리셔들(104)을 크롤링(crawing)하고, 퍼블리셔들(104)에 의해 제공되는 리소스(105)를 인덱싱함으로써 리소스들을 식별한다. 인덱스되고, 선택적으로, 리소스(105)의 캐시된 카피본들은 리소스 인덱스(112)에 저장된다. 일반적으로, 리소스 인덱스(112)는 키워드-기반 인덱스들, 위치-기반 인덱스들, 및 다른 인덱스들을 포함하는 다양한 유형의 리소스(105)를 포함할 수 있다.

클라이언트 디바이스(106)는 탐색 엔진(118)에 탐색 쿼리들을 제출한다. 응답으로, 탐색 엔진(118)은 그 쿼리들에 관련된 리소스들을 식별하기 위해 리소스 인덱스(112)를 사용한다. 탐색 엔진(118)은 리소스들을 식별하고, 그 리소스들을 식별하는 탐색 결과를 생성하여, 그 탐색 결과를 클라이언트 디바이스(106)에 제공한다. 탐색 결과(111)는 쿼리에 응답하는 리소스를 식별하고, 그 리소스에 대한 리소스 로케이터를 포함한다. 예시적 탐색 결과(111)는 웹 페이지 제목, 웹 페이지로부터 추출된 텍스트의 스니핏(또는 일부), 및 웹 페이지의 URL을 포함할 수 있다.

탐색 결과는 정보 검색(IR: Information retrival) 점수와 같은 탐색 결과에 의해 식별된 리소스들(105)에 관련된 점수에 기초하여 순위가 부여되는데, 선택적으로(optional) 다른 리소스들과 관련되는 각 리소스의 품질 점수(qulity score)에도 기초한다. 일부 구현예들에서, IR 점수는 탐색 쿼리 및 리소스(105)에 상응하는 특징 벡터(feature vector)들의 내적(dot product)으로부터 계산되고, 탐색 결과에 대한 순위 매김은 IR 점수와 품질 점수의 조합인 초기 관련성 점수(initial relevance scores)에 기초한다. 탐색 결과는 이 초기 관련성 점수들에 따라 순서가 정해지고, 그 순서에 따라서 클라이언트 디바이스(106)에 제공된다.

클라이언트 디바이스(106)는 탐색 결과 페이지들을 수신하고, 사용자들(예컨대, 사용자들의 브라우저들)에게 제시하기 위해 그 페이지들을 랜더링한다. 사용자가 클라이언트 디바이스(106)에서 탐색 결과를 선택하는 것에 응답하여, 탐색 결과(111)가 참조하는 리소스(105)가 요청한 클라이언트 디바이스(106)에 제공된다.

클라이언트 디바이스들로부터 제출된 쿼리들은 쿼리 로그들(114)에 저장된다. 탐색 결과들에 의해 참조된 웹 페이지들과 쿼리들에 대한 클릭 데이터는 클릭 로그들(116)에 저장된다. 클릭 데이터는 탐색 엔진(118)에 의해 제공된 탐색 결과에 응답하여 취해진 액션들을 정의한다. 쿼리 로그들(114)과 클릭 로그들(116)은 클라이언트 디바이스에 의해 제출된 쿼리들을, 탐색 결과에서 식별된 웹 페이지들 및 사용자에 의해 취해진 액션들과 매칭시키는데 사용될 수 있다(즉, 각 식별자에 대한 탐색 이력이 액세스될 수 있도록, 탐색 요청들로부터의 식별자들과 연관된 데이터). 만약 시간 데이터도 저장된다면, 이 액션들이 취해지고, 쿼리들이 제출된 관련 시간도 결정될 수 있다. 따라서 클릭 로그들(116) 및 쿼리 로그들(114)은 클라이언트 디바이스에 의해 제출된 쿼리들의 시퀀스, 그 쿼리들에 응답하여 취해진 액션들(예컨대, 사용자에 의해), 및 상기 쿼리들이 얼마나 자주 제출되었는지를 추적하기 위해 탐색 엔진에 의해 사용될 수 있다.

일부 구현예들에서, 탐색 시스템(110)은 사용자가 쿼리를 타이핑하는 동안 쿼리 제안들을 결정하여 제공할 수 있다. 예시로서, 클라이언트 디바이스(106)의 사용자는 "new y…"로 시작하는 쿼리를 입력할 수 있다. 탐색 시스템(110)은 제안된 쿼리 완성, 또는 예컨대, "new york", "new york city", "new york time" 등과 같은 제안들을 제공할 수 있다. 이 제안들은 예를 들어, 사용자의 웹 브라우저 내에 있는 제안 박스(suggestions box)에 보여질 수 있는데, 예를 들어 이 제안 박스는 사용자가 쿼리를 타이핑하고 있는 탐색 박스(search box)에 인접해 있다. 제안 박스가 사용자가 의도했던 쿼리를 포함하고 있고, 사용자로 확인된다면, 사용자는 제안을 선택(예컨대, 클릭 온)할 수 있으며, 그 제안이 탐색 박스에 있는 사용자의 부분 쿼리(partical query)를 대체할 수 있다. 결과적으로, 사용자는 전체 쿼리를 입력할 필요가 없다.

쿼리 제안들의 프로세스는 사용자의 개인 컴퓨터 또는 상대적으로 빠르게 쿼리 제안들을 처리하는 네트워크 대역을 갖는 다른 컴퓨팅 디바이스에서 잘 동작할 수 있다. 그러나 일부 모바일 통신 디바이스(예컨대, 모바일 폰 및 스마트 폰)는 데스크탑 PC에 대한 유선 접속의 지연과 비교하여 높은 네트워크 지연을 가질 수 있다. 결과적으로, 제안 프로세스가 너무 느려서 이것이 사용자가 쿼리를 타이핑하는 프로세스를 방해할 수 있다. 이것의 원인 중의 하나는, 제안들이 사용자가 추가 키스트로크들을 타이핑한 후에 도달할 때, 이 지연은 현재 입력된 쿼리에 사용할 수 없는 일부 제안들을 만든느 결과를 가져올 수 있다.

일부 컴퓨팅 디바이스 접속(예컨대, 모바일 통신 디바이스 접속)에 내재하는 네트워크 지연을 극복하기 위해, 탐색 시스템(110)은 제안들은 부분적으로 입력된 쿼리(partially-entered query)들 만으로 다르게 예측되기 전에 제안들을 양호하게 예측할 수 있다. 예를 들어, 탐색 시스템(110)은 사용자의 클라이언트 디바이스(106)에 제안들을 디스플레이하기 전에 가능성 있는 제안들을 결정하기 위해 사용자의 쿼리 이력을 사용할 수 있다. 탐색 시스템(110)에 의해 제공된 제안들은 클라이언트 디바이스(106)에 제공되어, 그것들이 필요해지기 전에 클라이언트 디바이스(106) 상에서 이용가능한 제안들을 만들기 위해 캐싱 및 로컬 저장소를 사용할 수 있다.

다시 도 1을 참조하면, 탐색 시스템(110)은 제안 수집기(127) 및 제안 서버(128)를 포함한다. 제안 수집기(127)는 사용자가 타이프했거나 타이프할 가능성이 가장 높은 것에 기초하여 부분 쿼리들에 대한 제안들의 수집된 세트들을 생성할 수 있다. 제안 서버(128)는 하나의 특정 부분 쿼리(specific partial query)에 대한 완전 제안 쿼리(complete suggested query)들을 제공할 수 있는 서버측-코드 모듈(server-side code module)이다. 제안 수집기(127)와 제안 서버(128)는 개별적 제안 요청/응답 인터페이스(129)를 사용하여 통신할 수 있다. 예를 들어, 제안 수집기(127)는 제안 서버(128)에 요청(예컨대, 부분 쿼리)을 송신하고, 이에 응답하여, 제안 서버(128)는 상응하는 응답(예컨대, 상기 부분 쿼리에 매칭하는 제안들)을 제공한다. 일부 구현예들에서, 제안 수집기(127)와 제안 서버(128)는 하나의 구성요소 내에 결합될 수 있다.

또한, 제안 수집기(127)는 탐색 엔진(118)과 통신할 수 있다. 예를 들어, 탐색 엔진(118)이 수신한(예컨대, 사용자의 브라우저(130)로부터) 쿼리들에 기초하여, 탐색 엔진(118)은 공통/관련 제안들(131)에 대한 요청을 제안 수집기(127)에 송신한다. 이에 응답하여, 제안 수집기(127)는 제안들을 식별(예컨대, 제안 서버(128)와 인터페이싱함으로써)하고, 수집된 제안들(132)을 탐색 엔진(118)에 송신할 수 있다. 결과적으로, 사전-캐시된 제안들이 탐색 엔진(118)이 브라우저(130)에서의 사용을 위해 클라이언트 디바이스(106)에 제공하는 탐색 페이지에 포함될 수 있다. 함께 동작하면서, 탐색 엔진(118), 제안 수집기(127), 및 제안 서버(128)는 시스템(100) 내에서 제안들을 생성하기 위해 사용되는 서버측 프로세싱을 제공한다.

부분 쿼리들과 그 결과인 제안들의 예시로서, 전형적인 흐름은 후술되는 것과 같을 수 있다. 클라이언트 디바이스(106) 상에서 브라우저(130)를 실행하고 있는 사용자는 HTML 탐색 페이지를 요청할 수 있다. 사용자는 처음(예컨대, 새로운 모바일 통신 디바이스에서)으로 브라우저(130)를 사용하거나, 또는 사용자가 자신의 클라이언트 디바이스(106) 상에서 이전에 여러 번 브라우징하여, 새로운 브라우징 세션(browsing session)이 간단하게 시작할 수 있다. 일부 구현예들에서, 제공되는 탐색 페이지는 초기 쿼리 제안(initial query suggestion)들을 포함한다. 예를 들어, 제안들은 쿼리 로그들(114)에 저장된 정보를 사용하여, 모든 사용자들의 과거 쿼리들에 기초할 수 있다. 이러한 제안들을 사용하여, 탐색 시스템(110)은 사용자가 쿼리 입력을 시작하기 전에 사용자의 브라우저(130)에 대한 사전-캐시된 제안들(136)을 탐색 페이지를 제공할 수 있다.

클라이언트 디바이스(106)는 사전-캐시된 제안들(136)을 갖는 탐색 페이지를 수신한다. 탐색 페이지의 일반 HTML 코드 외에, 탐색 페이지는 탐색 이력과 많은 부분 쿼리들의 캐시, 및 연관된 제안들을 관리할 수 있는 추가 명령어들(예컨대, 자바 스크립트 코드(140))를 포함한다. 또한 탐색 페이지는 사용자가 자신의 쿼리에 타이핑할 가능성이 있는 처음 몇 문자에 기초하여 가능성이 가장 높은 제안들의 세트를 포함한다. 탐색 시스템(110)으로부터 수신된 제안들은 브라우저(130) 내의 로컬 저장소(142)에 저장된다.

사용자가 브라우저(130) 내에 있는 탐색 필드에 문자(예를 들어, "ne")를 타이핑하는 동안, 로컬 저장소(142)에 있는 제안 캐시는 부분 쿼리를 포함하고 있는지를 확인하기 위해 체크된다. 만약, 제안 캐시가 부분 쿼리를 포함하고 있으면, 그 부분 쿼리에 대한 제안들이 브라우저(130)에서 사용자에게 즉시 디스플레이될 수 있다. 일부 구현예들에서, 요청(예컨대, 미리 보기(134)를 갖는 제안들에 대한 요청)이 제안 수집기(127)에 송신되어, 사용자가 그때까지 타이핑한 것과 다음으로 타이핑할 가능성이 가장 높은 것에 기초하여 추가 부분 쿼리들에 대한 수집된 제안들(135)을 얻는다. 이 방식에서는, 시스템(100)이 흔히 사용자보다 빠른 상태를 유지하여, 사용자가 임의의 부분 쿼리를 타이핑하기 전에 임의 부분 쿼리를 이용할 수 있는 제안들을 가질 수 있다. 성능(performance)은 캐시가 커질수록 시간이 지남에 따라 향상될 수 있는데, 이는 특히 많은 사용자가 시간이 지날수록 유사한(또는 심지어 동일한) 쿼리를 실행하려는 경향이 있기 때문이다.

통신이 높은 지연을 경험하더라도, 사전-캐시된 제안들의 존재는 추가 제안들이 탐색 시스템(110)으로부터 적시에 수신되지 않더라도, 쿼리 제안들을 생성할 수 있게 한다. 만약 추가 제안들이 적시에 수신되면(즉, 수신되는 시점에 그 제안들이 입력되고 있는 부분 쿼리에 여전히 상관될 때, 예를 들어, 제안들이 부분 쿼리에 매칭되는 접두사들을 갖음), 그 추가 제안들은 제안들로서 디스플레이될 수 있다. 그러나 만약 추가 제안들이 적시에 수신되지 않으면(즉, 수신되는 시점에 그 제안들이 입력되고 있는 부분 쿼리에 더이상 상관되지 않을 때, 예를 들어, 제안들이 부분 쿼리에 매칭하지 않는 접두사들을 갖음), 제안들은 가능한 제안들로서 나중에 사용하기 위해 로컬 저장수(142)에 저장될 수 있다.

일부 구현예들에서, 탐색 엔진(118)은 또한 탐색 결과에 추가 사전-캐시된 제안들(144)을 제공할 수 있는데, 사전-캐시된 제안들은 사용자들이 입력했던 이전 관련 쿼리들에 기초한다. 예를 들어, 이전 쿼리는 탐색 결과 페이지를 제공받은 탐색 결과를 식별하는데 사용되는 쿼리일 수 있다. 상응하는 탐색 쿼리(예컨대, 쿼리 "new york times"에 응답하는)를 동반하는 이 쿼리(예컨대, "new york times")에 기초하여, 탐색 엔진(118)은 관련 제안들(예컨대, "LA times", "New York Post" 등)을 제공한다.

관련 제안들을 식별하기 위해, 탐색 엔진(118)은 쿼리 로그들(114)로부터의 과거 사용자 쿼리들에 대한 정보와, 클릭 로그들(116)로부터 상응하는 웹 페이지와의 사용자 상호동작들에 대한 이력을 사용할 수 있다. 추가 사전-캐시된 제안들(144)을 갖는 탐색 결과가 브라우저(130)에 의해 이전 쿼리들(146)에 기초하여 추가 제안들을 갖는 HTML 탐색 쿼리 페이지로서 저장될 수 있다.

사전-캐싱 제안들의 프로세스는 사용자가 쿼리의 문자들을 입력하는 동안 계속될 수 있다. 로컬 저장소(142)에 가능성이 가장 높은 제안들을 업데이트하고 캐싱함으로써, 높은 네트워크 지연을 갖는 모바일 통신 디바이스라 하더라도, 브라우저(130)가 사용자가 타이핑하는 것보다 먼저 있을 수 있다. 결과적으로, 캐시된 제안들은 사용자보다 먼저 몇 개의 키스트로크(예컨대, 둘 이상)를 남겨둘 수 있다. 이것은 "오래된(stale)" 제안들, 또는 달리 말해서, 더 이상 이용할 수 없는 이전 사용자의 부분 쿼리 2개 또는 3개의 키스트로크에 기초한 제안들이 디스플레이되는 것을 방지할 수 있다. 예를 들어, 만약 사용자가 다른 문자(예컨대, "b"가 아니라 "w")를 입력하여, 부분 쿼리가 "new"로 되면, 부분 쿼리 "ne"에 기초하여 처음에 캐시되었던(그 시점에) "Nebraska"로 시작하는 제안들은 "오래된" 것이 된다.

로컬 저장소(142)는 클라이언트 디바이스(106) 상에 필요할 수 있는 모든 종류의 제안-관련 데이터를 저장할 수 있다. 예를 들어, 로컬 저장소(142)는 HTML, HTML5, Google Gears, 간단한 자바 스크립트 객체, 또는 사용자의 브라우저(130) 상에 대한 제안들을 지원하고 표시할 필요가 있는 다른 캐시된 정보를 포함할 수 있다.

일부 구현예들에서는, 탐색 시스템(110)에 의해 제공된 제안들이 키 값 쌍(key vaule pairs)의 형태로 되어 있으며, 로컬 저장소(142)에 저장되어 있는 사전-캐시된 제안들은 키 값 쌍으로 저장된다. 키 값 쌍은 쿼리 입력 시퀀스(예를 들어, 부분 쿼리) 및 쿼리 입력 시퀀스와 매칭되는 초기 쿼리 문자를 갖는 쿼리 제안들일 수 있다. 예를 들어, 하나의 키 값 쌍은 입력 시퀀스 "ne"와, 쿼리 제안들(예컨대, "new york", "new york city", "new york times", "Nebraska football" 등)일 수 있다. 예를 들어, 이런 방식으로 사전-캐시된 제안들을 저장하면 브라우저(130)가 사용자의 현재 부분 쿼리에 기초하여 제안들을 액세스하고 표시하는 프로세스를 신속하게 처리할 수 있다.

§ 2.0은 초기 쿼리 제안들 결정( Determining Initial Query Suggestions )

도 2는 탐색 인터페이스 리소스를 제공받을 초기 쿼리 제안들을 결정하기 위한 예시적 프로세스(200)의 순서도이다. 탐색 인터페이스 리소스는 사용자가 탐색 쿼리를 입력하는 페이지(예컨대, 탐색 엔진 호스트에 대한 홈 페이지)이다. 탐색 시스템(110)은 즉 사용자들에 의한 사용자 쿼리들을 처리하는 프로세스와는 별개인 백-앤드 프로세스(back-end process)에서, 바람직하게 쿼리 시간(query time) 이전에 프로세스(200)의 단계들을 수행한다. 초기 쿼리 제안들이 결정되면, 초기 제안들은 탐색 인터페이스 리소스를 제공받는다.

사용자에 의해 제출된 쿼리들을 포함하는 쿼리 로그 데이터와 각 쿼리가 제출된 빈도(frequency)가 액세스된다(202). 예를 들어, 탐색 시스템(110)은 쿼리 로그들(114)을 액세스할 수 있다. 액세스된 정보는 복수의 사용자들에 의해 이전에 입력된 특정 쿼리들, 탐색 결과의 선택들, 및 쿼리가 입력된 빈도를 포함한다.

초기 쿼리 문자의 가능성이 가장 높은 시퀀스는 쿼리 로그 데이터로부터 결정된다(204). 결정은 쿼리 로그들(114)에 저장되어 있는 완전한 이전 쿼리(complete previous query)들과 그것들의 빈도에 기초할 수 있다. 일부 구현예들에서, 가능성이 가장 높은 시퀀스들은 결정하는데 사용되는 쿼리 빈도(query frequency)는 특정 시간 기간(예컨대, 전년 또는 전월)으로 제한된다.

가능성이 가장 높은 시퀀스 각각에 대하여, 가능성이 가장 높은 쿼리들이 가능성이 가장 높은 시퀀스 및 쿼리 로그 데이터로부터 결정된다(206). 예를 들어, "new"의 가능성 있는 시퀀스에 대해서, 탐색 시스템(110)은, 각각이 아주 높은 상대 빈도로 입력된 퀴리들 "new york times"와 "new york city"이 가능성이 가장 높은 쿼리라고 결정할 수 있다. 그에 비해, 탐색 시스템(110)은, 상대적으로 낮은 빈도로 이전에 입력되었던 쿼리 "new day rising"이 시퀀스 "new"에 대해 가능성이 가장 쿼리라고 결정할 수 있다. 이 프로세스는 다른 가능성이 가장 높은 시퀀스(예를 들어, "abc", "xyz" 등)에 대해 반복된다.

일부 구현예들에서는, 쿼리 빈도 분석(query frequency analysis)이 사용자의 국가 및 언어에서 이력 쿼리들을 관찰하고, 문자들의 가능성이 가장 높은 초기 시퀀스를 계산함으로써 가능성이 가장 높은 시퀀스와 가능성이 가장 높은 쿼리들을 결정하는데 사용될 수 있다. 대형 캐시 히트 비율(cache hit ratio)은 단지 소량의 사전-캐시된 데이터로 처음 몇 문자들에 대해 달성될 수 있다.

초기 쿼리 문자들의 가능성이 가장 높은 시퀀스 각각에 대해 결정된 가능성이 가장 높은 쿼리들이 초기 쿼리 제안들로 지정된다(208). 예를 들어, 가능성이 가장 높은 쿼리는 탐색 페이지(140)를 제공받는 사전-캐시된 제안들(136)을 생성하는데 사용될 수 있다.

일부 구현예들에서는, 가능성이 가장 높은 시퀀스 각각에 대해 결정된 가능성이 가장 높은 쿼리들이 함께 그룹화된다. 예를 들어, 쿼리들은 자신에게 할당된 가능성 점수(likelihood score)를 가질 수 있고, 그 점수들은 가능성에 대해 내림차순으로 제안들을 순서화하는데 사용할 수 있다. 결과적으로, 탐색 시스템(110)에 의해 제공되는 제안들의 목록은 먼저 가능성이 가장 높은 제안(예컨대, "new york times)을 제시하고, 이어서 두 번째로 가능성이 높은 제안(예를 들어, "new york yankees")을 제시한다. 일부 구현예들에서는, 브라우저(130)는 제안들이 사용자가 의도했던 것일 가능성의 순서대로 그 제안들을 디스플레이한다. 다른 구현예들에서는, 제안들이 다른 순서(예컨대, 알파벳)으로 디스플레이될 수도 있다.

§ 2.1 추가 쿼리 제안들을 결정( Providing Pre - Cached Query Suggestions )

이 프로세스(200)는 또한 사용자 디바이스로부터 수신된 부분 쿼리들에 기초하여 추가 제안들을 생성하기 위한 탐색 시스템(110)에 의해 사용될 수 있다. 추가 제안들은 초기 제안(예를 들어, 탐색 결과 페이지로)에 이어서 제공된다. 탐색 시스템(110)은 상술된 것과 같은 쿼리 빈도 분석, 접두사 분석(prefix analysis), 및 글자 빈도 분석(letter frequency analysis)을 포함하는, 부분 쿼리들을 처리하기 위한 다양한 기술을 사용할 수 있다. 접두사 분석은 부분 쿼리를 검사(examine)하고, 이력 쿼리 데이터를 분석하는 것에 기초하여 가능성이 가장 높은 완전 쿼리(complete query)를 결정할 수 있다. 이 기술은 사용자가 타이핑하는 각 문자를 위해 네트워크 요청을 할 필요없이 이것들의 부분 쿼리들에 대해 사전-캐시된 제안들을 생성하기 위해, 가능성이 가장 높은 중간 부분 쿼리(intermediate partial query)(예를 들어, "new" 또는 "new york")를 예측할 수 있다.

글자 빈도 분석은 예를 들어, 부분 쿼리의 마지막 글자(예컨대, 최종-입력된)에 기초하여 이력 쿼리들을 처리함으로써 가능성이 가장 높은 다음 글자를 예측하는데 사용할 수 있다. 예를 들어, 영어 사용자가 "q"를 타이핑할 때마다, 쿼리의 나머지가 고유하고 그 자신이 접두사 분석되지 않더라도, 이어지는 글자가 "u"가 될 가능성이 높을 수 있다. 따라서 "q"로 끝나는 부분 쿼리에 대한 응답은 글자 "u"를 포함하는 다른 요청들을 요청하지 않고, 다음으로 " u"가 이어지는 동일한 부분 쿼리에 대한 제안들을 포함할 수 있다.

이에 더하여, 탐색 시스템(110)은 추가 쿼리 제안들을 제공하기 위해 사용자로부터 수신한 완전 쿼리를 처리할 수 있다. 예를 들어, 탐색 시스템(110)은 쿼리 제안들을 식별하기 위해 관련 탐색 분석을 사용할 수 있다. 관련 탐색 분석은, 사용자에 의해 실행된 전체 쿼리가 주어졌을 때, 사용자가 타이프할 가능성이 있는 다른 쿼리들을 예측할 수 있다. 그 쿼리들은 이러한 쿼리들에 대한 사전-캐시된 제안들로서 HTML 탐색 결과 페이지에 포함되어, 사용자가 네트워크 요청을 요청하지 않고 이러한 쿼리들을 타이프하는 경우, 그 쿼리들이 이용될 수 있다.

마지막으로, 클라이언트 디바이스는 또한 클라이언트 상에 쿼리 제안들을 생성하기 위해 쿼리 이력을 사용할 수 있다. 쿼리 이력은 사용자가 이전 쿼리들을 반복 할 가능성이 높다는 가능성에 기초하여 제안들을 생성하는데 사용될 수 있다. 예를 들어, 사용자의 이전 쿼리들은 로컬적으로(예를 들어, 로컬 저장소(142)에) 캐시될 수 있어, 네트워크 요청이 없이도 디스플레이될 수 있다. 일부 구현예들에서, 로컬적으로 캐시된 쿼리들은 타임스탬프 및 빈도를 포함할 수 있고, 낮은 빈도수 또는 최근(예컨대, 전년 또는 전월 등)에 사용되지 않은 쿼리들은 캐시 공간을 확보하기 위해 제거될 수 있다.

§ 3.0 사전- 캐시된 쿼리 제안들을 제공( Providing Pre - Cached Query Suggestions)

도 3은 초기 쿼리 제안들에 탐색 엔진 인터페이스 리소스를 제공하기 위한 예시적 프로세스(300)의 순서도이다. 탐색 시스템(110)은, 예를 들어, 서버-중심 프로세스(server-oriented process)인 프로세스(300)의 단계들을 수행할 수 있다. 프로세스(300)는 탐색 시스템(110)이 사전 캐시된 쿼리들의 초기 세트를 어떻게 클라이언트 디바이스에 제공하는지와, 탐색 시스템(110)이 사전-캐시된 쿼리들의 추가 세트들을 어떻게 클라이언트 디바이스에 제공하는지를 설명한다.

탐색 리소스에 대한 요청이 클라이언트 디바이스로부터 수신된다(302). 예시로서, 탐색 시스템(110)은 클라이언트 디바이스(106)로부터 탐색 리소스 페이지에 대한 요청을 수신한다. 예를 들어, 사용자가 브라우저 애플리케이션을 기동시키고 탐색 시스템(110)의 홈 페이지로 이동할 때, 요청이 클라이언트 디바이스(106)에서 구동중인 사용자의 브라우저(130)로부터 송신될 수 있다.

탐색 리소스가 탐색 리소스의 요청에 대한 응답으로 클라이언트 디바이스에 제공된다(304). 탐색 리소스에는 제1 명령어 및 초기 탐색 제안들이 포함되는데, 제1 명령어는 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 한다. 예시로서, 탐색 시스템(110)은 클라이언트 디바이스(106)에 사전-캐시된 제안들(136)을 갖는 탐색 페이지를 송신할 수 있다. 이 탐색 페이지는 사용자의 브라우저(130)에서 실행가능한 HTML 코드의 형태일 수 있다. 제안들은 상술되어진 프로세스(200)에 의해 결정된 제안들일 수 있다. 또한 탐색 리소스는 클라이언트 디바이스로 하여금 클라이언트 디바이스에 있는 제안 저장소에 초기 쿼리 제안들을 저장하도록 하는 제2 명령어(예컨대, 자바 스크립트 코드)들을 포함한다.

탐색 리소스가 클라이언트 디바이스상에서 랜더링된 후에, 사용자가 쿼리를 입력하는 동안, 제2 명령어들은 또한 클라이언트 디바이스로 하여금 쿼리 입력 필드에 있는 쿼리 문자 입력을, 제안 저장소에 저장된 쿼리 제안들과 비교하고, 그 비교 결과에 기초하여 제1 쿼리 문자 입력 필드에 있는 쿼리 문자 입력들과 매치하는 쿼리 제안들을 선택하게 한다. 제2 명령어들을 실행 중인 클라이언트 디바이스는 이어서 제1 쿼리 입력 필드에 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 선택된 쿼리 제안들을 디스플레이한다. 사용자는 제안된 쿼리 중 하나를 선택하거나, 쿼리를 계속해서 입력할 수 있다. 결국 사용자는 쿼리를 입력할 것이고(제안들 중 하나를 선택하거나, 그 쿼리를 타이핑함으로써) 클라이언트 디바이스로 하여금 그 쿼리를 탐색 시스템(110)에 송신하게 한다.

비교 동작에 관하여, 제안 저장 로컬 저장소(142)에 저장된 사전-캐시된 쿼리들이 즉시 사용가능하기 때문에, 클라이언트 디바이스(106)는 탐색 시스템(110)으로부터 추가 제안들을 요청하여 그 추가 제안들의 수신을 대기할 필요가 없다. 상술되어진 바와 같이, 일부 구현예들에서는, 요청(예를 들어, 미리 보기(134)가 있는 제안들에 대한 요청)이 또한 제안 수집기(127)로 송신되어, 지금까지 사용자가 타이핑한 것과 이어서 타이핑할 가능성이 가장 높은 것들에 기초하여 추가 부분 쿼리들에 대한 추가 수집 제안들(135)을 획득한다. 만약 추가 제안들이 적시에 수신되면, 그 제안들은 제안들로서 디스플레이될 수 있고, 만약 추가 제안들이 적시에 수신되지 않으면, 그 제안들은 가능한 제안들로서 추후 사용하기 위해 로컬 저장소(142)에 저장될 수 있다.

쿼리는 클라이언트 디바이스로부터 수신된다(306). 예를 들어, 탐색 시스템(110)은 클라이언트 디바이스(106)로부터 쿼리를 수신할 수 있다. 쿼리는 사용자가 타이프하였거나 제안들로부터 선택되거나, 이 둘이 일부 조합된 완전 쿼리일 수 있다.

탐색 결과 리소스는 클라이언트 디바이스로부터 수신된 쿼리에 응답으로 제공된다(308). 탐색 결과 리소스는 클라이언트 디바이스로 하여금 쿼리에 응답하기로 결정된 리소스들을 참조하는 탐색 결과와 추가 쿼리 제안들을 디스플레이하는 탐색 결과 페이지를 생성하게 하는 제3 명령어들을 포함한다. 예시로서, 도 1을 참조하면, 탐색 시스템(110)이 추가 사전-캐시된 제안들(144)을 갖는 탐색 결과의 형태로, 그 탐색 결과 리소스를 클라이언트 디바이스(106)에 제공할 수 있다.

탐색 결과 리소스는 클라이언트 디바이스(106)가 브라우저(130)에 탐색 결과를 디스플레이하는데 사용할 수 있는 HTML 코드를 포함한다. 또한, 탐색 결과 리소스는 추가 쿼리 제안들을 포함할 수 있고, 탐색 시스템(110)은 쿼리 로그들(114)로부터 또는 다른 쿼리 제안 서비스들로부터의 정보를 사용하여 획득할 수 있다. 일부 구현예들에서, 추가 사전-캐시된 제안들은 탐색 결과 리소스에 대한 탐색 결과를 식별하기 위해 선택되고 사용된 쿼리에 기초한 것이다. 탐색 결과 리소스는 또한 클라이언트 디바이스로 하여금 클라이언트 디바이스의 제안 저장소에 추가 쿼리 제안들을 저장하게 하는 제4 명령어(예컨대, 자바 스크립트 코드)들을 포함한다. 결과적으로, 사전-캐시된 제안들은 사용자의 관심에 더욱 관련되는 쿼리 제안들을 포함하기 시작하고, 사용자의 브라우저(130)는 개인화된 사전-캐시된 제안들을 디스플레이하기 시작한다.

탐색 결과 리소스가 클라이언트 디바이스상에서 랜더링된 후에, 사용자는 다시 탐색 결과 리소스 상의 쿼리 입력 필드에 다른 쿼리를 입력할 수 있다. 제4 명령어들은 또한 클라이언트 디바이스로 하여금 쿼리 입력 필드에 있는 쿼리 문자 입력을, 제안 저장소에 저장된 쿼리 제안들과 비교하고, 그 비교 결과에 기초하여 제1 쿼리 문자 입력 필드에 있는 쿼리 문자 입력들과 매치하는 쿼리 제안들을 선택하게 한다. 제4 명령어들을 실행 중인 클라이언트 디바이스는, 이어서 상기 선택된 쿼리 제안들을 쿼리 문자 입력에 대한 쿼리 제안들로서 제1 쿼리 입력 필드에 디스플레이한다.

§4.0 사전- 캐시된 제안들의 클라이언트측 프로세싱( Client Side Processing Of Pre - Cached Suggestions )

도 4는 클라이언트 디바이스로부터 쿼리 제안들을 수신하고 요청하기 위한 예시적 프로세스(400)의 순서도이다. 클라이언트 디바이스(106)는 프로세스(400)의 단계들을 수행하고, 예를 들어, 일부 단계들을 위해 탐색 시스템(110)과 상호동작한다.

탐색 엔진으로부터 탐색 리소스에 대한 요청이 제공된다(402). 예시로서, 클라이언트 디바이스(106)는 탐색 리소스에 대한 요청을 탐색 시스템(110)에 제공할 수 있다. 요청은 예를 들어, 사용자가 브라우저 애플리케이션을 시작하고, 탐색 시스템(110)의 홈 페이지로 이동할 때, 클라이언트 디바이스(106)에서 실행 중인 사용자의 브라우저(130)로부터 송신될 수 있다.

탐색 리소스는 탐색 리소스에 대한 요청에 응답하여 수신된다(404). 예시로서, 클라이언트 디바이스(106)는 탐색 시스템(110)으로부터 사전-캐시된 제안들(136)을 갖는 탐색 페이지를 수신할 수 있다. 탐색 페이지는 클라이언트 디바이스가 쿼리 입력 필드와 초기 쿼리 제안들을 포함하는 탐색 인터페이스를 생성할 수 있게 하는 명령어들을 포함할 수 있다. 탐색 페이지는 사용자의 브라우저(130)에서 실행가능한 HTML 코드의 형태일 수 있다. 탐색 페이지는 또한 상술되어진 사전-캐시된 제안들을 처리할 수 있는 제2 명령어(예컨대, 자바 스크립트 코드)들을 포함할 수 있다.

초기 쿼리 제안들이 클라이언트 디바이스의 제안 저장소에 저장된다(406). 예를 들어, 제2 명령어들을 실행 중인 클라이언트 디바이스(106)는 로컬 저장소(142)에 초기 쿼리 제안들을 저장한다. 이러한 방식으로, 사용자가 제안들로부터 선택할 가능성이 있는 쿼리들은 클라이언트 디바이스(106)상에서 이용가능하고 사전-캐시된다.

제1 쿼리 입력 필드에 있는 쿼리 문자 입력은 쿼리 저장소에 저장된 쿼리 제안들과 비교된다(408). 예시로서, 사용자가 쿼리 입력 필드에 입력하는 쿼리 문자들은 로컬 저장소(142)에 저장된 쿼리 제안들과 비교된다. 예를 들어, 사용자의 일부 쿼리 "ne"가 로컬 저장소(142)에 저장된 제안들(예를 들어, "new york times" 등)과 비교될 수 있다.

상기 비교 결과에 기초하여, 제1 쿼리 입력 필드에 있는 쿼리 문자 입력들과 매치하는 쿼리 제안들이 선택된다(410). 예를 들어, 클라이언트 디바이스(106)는 그 비교 결과에 기초하여 제1 쿼리 입력 필드에 있는 쿼리 문자와 매치하는 쿼리 제안들을 선택할 수 있다. 이 경우, 제안 "new york times"와 "ne"로 시작하는 다른 제안들이 선택되는데, 이는 이것들이 부분 쿼리 "ne"와 매치하기 때문이다.

선택된 쿼리 제안들은 쿼리 문자 입력에 대한 쿼리 제안들로서 제1 쿼리 입력 필드 내에 디스플레이된다(412). 선택된 쿼리 제안들은 제1 쿼리 입력 필드에 인접해 있는 제안 박스에 디스플레이될 수 있다. 예시로서, 사용자가 제1 쿼리 입력 필드에 "ne"를 입력한 시점에, 사용자의 브라우저(130)는 또한 부분 쿼리에 매치하는 제안들(예컨대, "new york times" 등)을 디스플레이할 수 있다. 브라우저는 로컬 저장소(142)로부터 제안들을 획득할 수 있다. 사용자가 쿼리에 추가 문자들을 타이핑하면, 로컬 저장소로부터 취득된 제안들이 현재 부분 쿼리와 일치하도록 변할 수 있다.

일부 구현예들에서는, 최근에 사전-캐시된(예를 들어, 사용자의 현재 사용자 세션 및 부분 쿼리에 기초하여) 쿼리 제안들을 포함하는 로컬 저장소(142) 외에, 예를 들어, 브라우저에 최근(예컨대, 미리-결정된 시간 기간(예컨대, 전월 내))에 입력된 쿼리들에 기초하여 저장된 쿼리 제안들을 포함할 수 있다.

프로세스(400)는 탐색 리소스(예를 들어, 탐색 시스템의 홈 페이지)를 수신하는 상황(context)으로 설명되었지만, 프로세스(400)는 또한 추가 쿼리 제안들을 포함하는 탐색 결과 페이지를 수신하는 상황에 적용될 수도 있다.

§ 5.0 탐색 시스템로의 클라이언트측 탐색 제안 요청( Client Side Search Suggestion Requests To The Search System )

도 5는 클라이언트 디바이스로부터의 쿼리 제안 요청을 탐색 엔진에 제공하고, 수신된 쿼리 제안들을 처리하기 위한 예시적 프로세스(500)의 순서도이다. 클라이언트 디바이스(106)는 예를 들어, 프로세스(500)의 단계들을 수행할 수 있다.

제1 쿼리 입력 필드에 있는 입력인 쿼리 문자들은 쿼리 제안 요청으로서 탐색 시스템(110)에 제공된다(502). 예를 들어, 사용자가 탐색 리소스 또는 탐색 결과 리소스의 쿼리 입력 필드(예컨대, 탐색 페이지 또는 탐색 결과 페이지상의 탐색 상자)에 일부 쿼리 "ne"를 입력할 수 있다. 클라이언트 디바이스(106)는 미리 보기(134)를 갖는 제안에 대한 요청으로서 그 입력을 탐색 시스템(110)에 송신할 수 있다. 이 요청이 송신될 때, 클라이언트 디바이스(106)는 로컬 저장소(142)에 저장되고, 그 중 일부가 사용자의 현재 부분 쿼리에 관련될 수 있는 사전-캐시된 제안들을 이미 가지고 있을 수 있고, 사용자에게 제시할 쿼리 제안들을 결정하기 위해 이 사전-캐시된 제안들을 처리할 수 있다.

이 요청에 응답하여, 추가 쿼리 제안들이 데이터 처리 장치로부터 수신된다(504). 예를 들어, 클라이언트 디바이스(106)는 탐색 시스템(110)으로부터 수집된 제안들(135)을 수신할 수 있다. 수신된 제안들은 상술된 바와 같이, 예를 들어 쿼리 로그들(114)과 클릭 로그들(116)을 사용하여 탐색 시스템(110)에 의해 생성되거나, 또는 별도의 제안 서비스로부터 수신될 수도 있다. 만약 추가 제안들이 적시에 수신되면(즉, 수신되는 시점에 그 제안들이 입력되고 있는 부분 쿼리에 여전히 상관될 때, 예를 들어, 제안들이 부분 쿼리에 매칭되는 접두사들을 갖음), 그 제안들은 제안들로서 디스플레이될 수 있다. 그러나 추가 제안들이 적시에 수신되지 않으면(즉, 수신되는 시점에 그 제안들이 입력되고 있는 부분 쿼리에 더이상 상관되지 않을 때, 예를 들어, 제안들이 부분 쿼리에 매칭하지 않는 접두사들을 갖음), 그 제안들은 가능한 제안들로서 추후 사용하기 위해 로컬 저장소(142)에 저장될 수 있다.

추가 쿼리 제안들은 제안 저장소에 저장된다(506). 예를 들어, 클라이언트 디바이스(106)가 수신한 제안들의 소스와 관계없이, 제안들은 로컬 저장소(142)에 캐시될 수 있다. 해당 시점부터, 로컬 저장소(142)에 저장되어 있는 사전-캐시된 제안들은, 사용자의 현재 부분 쿼리와 매치하는 제안들을 디스플레이하기 위해 브라우저(130)에 의해 사용될 수 있다. 또한, 제안들은 쿼리 제안들의 후속 처리를 위하여 클라이언트 디바이스(106)에서 이용가능할 수 있다.

§ 6.0 사전-캐싱 위치 특정 제안( Pre - Caching Location Specific Suggestions)

일부 구현예들에서는, 제안 수집기(127)는 클라이언트 디바이스(106)의 위치를 나타내는 위치 데이터를 확인하고, 그 위치 데이터를 이용하여 캐싱을 위한 위치 특정 쿼리 제안들을 제공한다. 일부 구현예들에서, 로컬 저장소(142)는 자신의 위치(예컨대, L1, L2 ..., Ln)로 위치 특정 쿼리 제안들을 연관시킨다. 위치 특정 쿼리 제안들이 상기에서 제공된 쿼리 제안들(위치 특정일 필요가 없는)을 증가시키는데 이용될 수 있는데, 즉 위치 특정 쿼리 제안들이 위치 독립 쿼리 제안들을 증가시키는데 사용된다.

예를 들어, 일부 구현예들에서, 탐색 페이지를 제공받는 사전-캐시된 제안들(136), 및 탐색 결과 페이지를 제공받는 추가 제안들은, 위치 독립적 쿼리 제안(location independent query suggestion)들 및 위치 특정 쿼리 제안(location specific query suggestion)들을 포함한다. 본 명세서에서 사용되는 것처럼, 위치 독립 쿼리 제안은 클라이언트 디바이스의 위치에 상관없는 쿼리 제안으로서 디스플레이될 수 있는 쿼리 제안이다. 반대로, 위치 특정 쿼리 제안은 위치 또는 영역에 연관되고, 클라이언트 디바이스가 그 위치 또는 영역 내에 있을 때만 쿼리 제안으로서 디스플레이될 수 있는 쿼리 제안이다.

위치 특정 쿼리 제안들은, 위치 특정 쿼리 제안들이 특정 위치에 특정되는 점을 제외하고는, 상술되어진 것과 유사한 방식으로 생성된다. 예를 들어, 위치 특정 쿼리 제안들의 초기 세트를 결정하고, 추가 위치 특정 쿼리 제안들을 결정하는 프로세스는, 처리되는 쿼리들이 특정 위치 내에 있는 디바이스들로부터 수신된 쿼리들로 제한된다는 점을 제외하고는, 도 2에서 설명된 단계들과 유사한 단계들을 수행한다.

쿼리 제안들에 대한 관련 위치 정보는 클라이언트 디바이스에 의해 제공된 위치 데이터(예컨대, GPS 좌표), 특정 지역 영역에 할당된 IP 어드레스들 등으로부터 제공된다. 예를 들어, 클라이언트 디바이스의 사용자가 캘리포니아주의 마운틴뷰에 거주하고 있다고 가정한다. 결과적으로, 사용자 디바이스는 위치 독립 쿼리 제안들과 캘리포니아 지역 마운틴뷰(위치 L1으로 지시됨)에 특정되는 위치 특정 쿼리 제안들을 포함할 것이다. 또한, 사용자가 바베큐(barbecue) 음식점에서 식사하는 것을 좋아하고, 마운틴뷰에 있는 동안, 텍스트 "barbecue"를 쿼리로 입력하기 시작한다고 가정한다. 텍스트가 입력되는 동안, 입력된 문자열에 매칭되는 쿼리 제안들이 위치 독립 쿼리 제안들과 쿼리 제안(즉, 위치 L1에 연관된 쿼리 제안)들의 단 하나의 위치 특정 세트로부터 제공될 것이다. 후자의 쿼리 제안들은 예를 들어, 캘리포니아 지역의 마운틴 뷰에 있는 음식점의 이름들과, 켈리포니아의 마운틴 뷰의 위치를 특정하는 다른 매칭 쿼리들을 포함한다.

나중에, 사용자가 조지아주의 애틀랜타(위치 L2로 표시됨)를 여행한다. 사용자가 조지아 지역의 애틀랜타에서 처음으로 클라이언트 디바이스(106)를 사용할 때, 사용자는 탐색 페이지와 함께 애틀랜타 특정 초기 쿼리 제안들의 세트를 제공받을 것이고, 제공된 각 탐색 페이지와 함께 추가 애틀랜타 쿼리 제안들을 제공받을 것이다. 위치 독립 쿼리 제안들도 또한 함께 제공될 수 있다. 따라서 사용자가 애틀랜타에 있는 동안 탐색 쿼리 "barbecue"을 입력하기 시작하면, 입력된 문자열에 매치하는 쿼리 제안들이 위치 독립 쿼리 제안들과 쿼리 제안들의 오직 하나의 위치 특정 세트(즉, 위치 L2에 연관된 쿼리 제안들)로부터 제공될 것이다. 후자인 쿼리 제안들은 예를 들어, 조지아 지역의 애틀랜타에 있는 음식점의 이름, 및 조지아주 애틀랜타의 위치에 특정되는 다른 매칭 쿼리들을 포함한다.

일부 구현예들에서, 사용자에게 디스플레이하기 위하여 위치 특정 쿼리 제안들의 프로세스는 필터링 프로세스에 따라서 완료된다. 예를 들어, 탐색 리소스에 대한 요청이 클라이언트 디바이스(106)의 현재 위치를 식별하는 위치 데이터를 포함한다고 가정한다. 위치 독립 쿼리 제안들 외에, 클라이언트 디바이스의 현재 위치에 특정하는 위치 특정 쿼리 제안들을 포함하는 초기 쿼리 제안들의 세트도 제공된다. 마찬가지로, 탐색 결과 페이지를 제공받는 쿼리 제안들은 또한 클라이언트 디바이스의 현재 위치에 특정하는 위치 특정 쿼리 제안들을 포함한다. 사용자에게 디스플레이하기 위하여 쿼리 제안들을 선택할 때, 브라우저에서 명령어들을 실행하고 있는 클라이언트 디바이스는 클라이언트 디바이스의 현재 위치에 특정되지 않는 위치 특정 쿼리 제안들을 제외한다. 따라서 상술된 바와 같이, 사용자가 조지아 지역의 애틀랜타에 있을 때, 캘리포니아주의 마운틴 뷰에 대한 위치 특정 쿼리 제안들은 제공되지 않는데, 이는 조지아주 애틀랜타의 현재 위치에 특정되지 않기 때문이다.

위치 특정 쿼리 제안들을 필터링하여 제공하는 다른 방식들이 또한 사용될 수 있다.

§ 7.0 추가 구현 세부 정보( Additional Implementation Details )

본 명세서에 기재된 요지와 기능적 동작들의 실시예들은 디지털 전자 회로로 구현되거나, 또는 상세한 설명에 기재된 구조 및 그들의 구조적 등가물을 포함하는 컴퓨터 소프트웨어, 펌웨어, 또는 하드웨어로 구현되거나, 또는 이들 중 하나 이상의 조합으로 구현될 수 있다. 본 명세서에 기재된 요지의 실시예들은 하나 이상의 컴퓨터 프로그램 제품, 즉, 데이터 프로세싱 장치에 의해 실행되거나 또는 그 장치의 동작을 제어하도록, 컴퓨터 저장 매체에 부호화된 컴퓨터 프로그램 명령의 하나 이상의 모듈로서 구현될 수 있다. 대안적 또는 부가적으로, 프로그램 명령들은 인공적으로 생성된 전파되는(propagated) 신호(예를 들어, 기계-생성 전기, 광 또는 전자기 신호)로서, 데이터 처리 장치에 의한 실행을 위하여 적절한 수신 장치로 전송하기 위한 정보를 인코딩하기 위해 생성된다. 컴퓨터 저장 매체는 컴퓨터-판독가능 저장 디바이스, 컴퓨터 판독가능 저장 기판(substrate), 랜덤 또는 시리얼 액세스 메모리 어레이 또는 디바이스, 이들 중 하나 이상의 조합일 수 있다. 또한, 컴퓨터 저장 매체는 전파되는 신호는 아니지만, 컴퓨터 저장 매체는 인공적으로 생성된 전파되는 신호로 부호화된 컴퓨터 프로그램 명령들의 소스 또는 전용일 수 있다. 컴퓨터 저장 매체는 또한 하나 이상의 분리된 물리적 구성요소 또는 미디어(예컨대, 복수의 CD, 디스크들, 또는 다른 저장 디바이스들)이거나, 그 물리적 구성요소 또는 미디어에 포함될 수 있다.

본 명세서에서 설명된 동작들은 하나 이상의 컴퓨터 판독가능 매체 디바이스에 저장되거나 다른 소스로부터 수신된 데이터에 대해 데이터 처리 장치에 의해 동작들이 실행됨으로써 구현될 수 있다.

"데이터 프로세싱 장치"라는 용어는 데이터를 처리하기 위한 모든 종류의 장치, 디바이스 및 기계를 포괄하며, 예를 들어, 프로그래머블 프로세서, 컴퓨터, 칩상의 시스템, 또는 다중의 것(multiple ones), 또는 이들의 조합을 포함한다. 장치는 FPGA(field programmable gate array) 또는 ASIC(application specific integrated circuit)과 같은 전용 논리 회로가 프로세스를 포함할 수 있다. 장치는 또한 하드웨어 외에도, 당해 컴퓨터 프로그램에 대한 실행 환경을 생성하는 코드를 포함하고, 코드는 예를 들어, 프로세서 펌웨어, 프로토콜 스택, 데이터베이스 관리 시스템, 운영 시스템, 교차-플랫폼 런타임 환경, 가상 기계, 또는 이들 중 하나 이상의 조합을 구성한다. 장치와 실행 환경은 예를 들어 웹 서비스, 분산된 컴퓨팅 구조, 및 그리드 컴퓨팅 구조와 같이, 다양한 다른 컴퓨팅 모델 구조로 구현될 수 있다.

컴퓨터 프로그램(프로그램, 소프트웨어, 소프트웨어 애플리케이션, 스크립트 또는 코드로도 알려짐)은 컴파일 또는 인터프리터 언어나 선언적 또는 절차적 언어를 포함하는 모든 형태의 프로그래밍 언어로 작성될 수 있으며, 독립형 프로그램이나 모듈, 컴포넌트, 서브루틴, 객체 또는 컴퓨터 환경에서 사용하기에 적합한 그 밖의 유닛을 포함하는 임의의 형태로도 배치될 수 있다. 컴퓨터 프로그램은 파일 시스템의 파일에 반드시 상응해야 하는 것은 아니다. 프로그램은 다른 프로그램 또는 데이터를 보유하는 파일의 일부에 저장되거나(예를 들어, 마크업 언어 문서 내에 저장되는 하나 이상의 스크립트), 당해 프로그램 전용의 단일 파일에 저장되거나, 또는 다수의 조화된(coordinated) 파일들(예를 들어, 하나 이상의 모듈, 서브프로그램, 코드의 부분을 저장하는 파일)에 저장될 수 있다. 컴퓨터 프로그램은 하나의 컴퓨터에서, 또는 한 위치에 배치되거나 또는 다수의 위치에 걸쳐서 분산되고 통신 네트워크에 의해 접속된 다수의 컴퓨터에서 실행되도록 배치될 수 있다.

본 명세서에 설명된 프로세스와 논리 흐름은 하나 이상의 프로그래머블 프로세서에 의해 수행될 수 있고, 이 프로그래머블 프로세서는 입력 데이터에 작용하여 출력을 생성함으로써 동작들을 수행하는 하나 이상의 컴퓨터 프로그램들을 실행한다. 예를 들어, FPGA(field programmable gate array) 또는 ASIC(application specific integrated circuit)과 같은 전용 논리 회로가 프로세스와 논리 흐름을 수행하거나, 장치를 구현할 수 있다.

컴퓨터 프로그램의 실행에 적합한 프로세서에는, 예를 들어, 범용 및 전용 마이크로프로세서, 및 임의 종류의 디지털 컴퓨터 중 하나 이상의 프로세서가 있다. 일반적으로, 프로세서는 판독 전용 메모리(ROM), 또는 랜덤 액세스 메모리(RAM), 또는 양자로부터 명령과 데이터를 수신한다. 컴퓨터의 필수 구성요소는 명령들에 따라 동작들을 실행하는 프로세서, 및 명령과 데이터를 저장하는 하나 이상의 메모리 디바이스이다. 일반적으로, 컴퓨터는 데이터를 저장하기 위한 하나 이상의 대용량 저장 디바이스(예를 들어, 자기 디스크, 광자기 디스크, 또는 광디스크)를 포함하거나, 또는 이 디바이스와 데이터를 송수신하기 위하여 동작적으로(operatively) 결합될 수 있다. 하지만 컴퓨터는 이러한 디바이스를 반드시 구비할 필요는 없다. 더욱이, 컴퓨터는 예를 들어, 모바일 전화기, 개인 정보 단말(PDA), 모바일 오디오 또는 비디오 재생기, 게임 콘솔, GPS(global positioning system) 수신기, 또는 휴대용 저장 디바이스(예컨대, USB(universal serial bus) 플래쉬 드라이버) 등과 같은 다른 디바이스에 내장될 수 있다. 컴퓨터 프로그램 명령어와 데이터를 저장하기 적합한 디바이스에는, 예를 들어, 반도체 메모리 디바이스(예를 들어, EPROM, EEPROM, 플래시 메모리 디바이스); 자기 디스크(예를 들어, 내부 하드디스크, 착탈식 디스크); 광자기 디스크; 및 CD ROM과 DVD-ROM 디스크를 포함하는 모든 형태의 비휘발성 메모리, 매체 및 메모리 디바이스가 포함된다. 프로세서와 메모리는 전용 논리 회로에 의해 보완되거나 또는 전용 논리 회로에 통합될 수 있다.

사용자와의 상호작용을 제공하기 위하여, 본 명세서에 기술된 요지의 실시예는, 정보를 사용자에게 디스플레이하기 위한 디스플레이 디바이스(예를 들어, CRT(cathode ray tube) 또는 LCD(liquid crystal display) 모니터), 키보드 및 포인팅 디바이스(예를 들어, 마우스 또는 트랙볼)를 구비한 컴퓨터에 구현될 수 있다. 사용자는 키보드와 포인팅 디바이스를 이용하여 컴퓨터에 입력을 제공할 수 있다. 사용자와의 상호작용을 제공하기 위하여 다른 종류의 디바이스가 또한 사용될 수 있다. 예를 들어, 사용자에게 제공되는 피드백(feedback)은 예를 들어, 시각 피드백, 청각 피드백 또는 촉각 피드백인 임의 형태의 감각 피드백일 수 있고, 사용자로부터의 입력은 음향, 음성 또는 촉각 입력을 포함하는 임의의 형태로 수신될 수 있다. 또한, 컴퓨터는 사용자에 의해 이용되는 디바이스로 문서들을 송신하고, 그 디바이스로부터 문서들을 수신함으로써(예컨대, 웹 브라우저로부터 수신된 요청에 응답하여 사용자의 클라이언트 디바이스의 웹 브라우저에 웹 페이지를 송신함으로써) 사용자와 상호작용할 수 있다.

본 명세서에 기술된 요지의 실시예는, 예를 들어, 데이터 서버와 같은 백엔드(back-end) 구성요소를 구비하는 컴퓨팅 시스템; 또는 예를 들어, 애플리케이션 서버와 같은 미들웨어 구성요소를 구비하는 컴퓨팅 시스템; 또는 예를 들어, 사용자가 본 명세서에 기술된 요지의 구현예와 상호작용할 수 있는 그래픽 사용자 인터페이스 또는 웹브라우저를 구비한 클라이언트 컴퓨터와 같은 프론트엔드(front-end) 구성요소를 구비하는 컴퓨터 시스템; 또는 이러한 백엔드, 미들웨어 또는 프론트엔드 구성요소들의 임의 조합을 구비하는 컴퓨팅 시스템으로 구현될 수 있다. 시스템의 구성요소는 디지털 데이터 통신의 임의 형태 또는 매체(예를 들어, 통신 네트워크)에 의해 상호접속될 수 있다. 통신 네트워크의 예에는 로컬 영역 네트워크(LAN)와 인터넷과 같은 광역 네트워크(WAN), 인터-넷(예컨대, 인터넷), 및 피어-투-피어 네트워크들(예컨대, 애드 혹 피어-투-피어 네트워크(ad hoc peer-to-peer network)들)가 포함된다.

컴퓨팅 시스템은 클라이언트와 서버를 포함할 수 있다. 클라이언트와 서버는 보통 서로 떨어져 있으며, 일반적으로는 통신 네트워크를 통하여 상호작용한다. 클라이언트와 서버의 관계는 각각의 컴퓨터상에서 실행되고 상호 클라이언트-서버 관계를 갖는 컴퓨터 프로그램에 의하여 발생한다. 일부 실시예들에서, 서버는 데이터(예컨대, HTML 페이지)를 클라이언트 디바이스(예컨대, 클라이언트 디바이스와 상호작용하기 위하여 사용자에게 데이터를 디스플레이하고 그 사용자로부터 사용자 입력을 수신하기 위한 목적임)로 전송한다. 클라이언트 디바이스에서 생성된 데이터(예컨대, 사용자 상호작용의 결과)는 서버에 있는 클라이언트 서버로부터 수신될 수 있다.

본 명세서가 다수의 특정한 구현 세부사항을 포함하고 있지만, 이는 임의 발명의 범위나 청구할 사항의 범위에 대한 어떠한 제약으로서도 이해되어서는 안 되며, 특정 발명들의 특정한 실시예에 고유한 특징의 설명으로서 이해되어야 한다. 별개의 실시예의 문맥으로 본 명세서에서 설명된 소정 특징은 조합되어 단일 실시예로 구현될 수 있다. 반대로, 단일 실시예의 문맥에서 설명한 다양한 특징은 복수의 실시예에서 별개로 구현되거나 어떤 적당한 하위 조합으로서도 구현 가능하다. 또한, 앞에서 특징이 소정 조합에서 동작하는 것으로서 설명되고 그와 같이 청구되었지만, 청구된 조합으로부터의 하나 이상의 특징은 일부 경우에 해당 조합으로부터 삭제될 수 있으며, 청구된 조합은 하위 조합이나 하위 조합의 변형으로 될 수 있다.

마찬가지로, 도면에서 특정한 순서로 동작을 묘사하고 있지만, 그러한 동작이 바람직한 결과를 얻기 위해, 도시한 특정 순서나 순차적인 순서로 수행되어야 한다거나, 설명한 모든 동작이 수행되어야 한다는 것을 의미하는 것은 아니다. 소정 환경에서, 멀티태스킹 및 병렬 프로세싱이 바람직할 수 있다. 또한, 상술한 실시예에 있어서 다양한 시스템 구성요소의 분리는 모든 실시예에서 그러한 분리를 요구하는 것으로 이해되어서는 안 되며, 설명한 프로그램 구성요소와 시스템은 단일 소프트웨어 제품으로 통합되거나 또는 복수의 소프트웨어 제품으로 패키지될 수 있다는 점을 이해되어야 한다.

따라서 요지의 특정 실시예들이 설명되었다. 그 밖의 구현예들은 후술하는 청구범위 내에 범위에 속한다. 일부 경우에는, 청구 범위에 인용된 동작들은 상이한 순서로 수행될 수 있지만, 여전히 바람직한 결과를 달성할 수 있다. 또한, 첨부 도면에서 묘사된 프로세스들은 바람직한 결과를 달성하기 위해, 도시된 특정 순서, 또는 순차적 순서를 요구할 필요는 없다. 특정 구현예들에서는, 멀티태스팅 뽀는 병렬 프로세싱이 유리할 수 있다.

102: 네트워크
104: 퍼블리셔들
105: 리소스(들)
106: 클라이언트 디바이스
110: 탐색 시스템
112: 리소스 인덱스
114: 쿼리 로그들
116: 클릭 로그들
118: 탐색 엔진
127: 제안 수집기
128: 제안 서버
130: 브라우저
142: 로컬 저장소

Claims

데이터 처리 장치; 및
상기 데이터 처리 장치와 데이터 통신을 하고, 서버 명령어들을 저장하는 메모리 저장 장치를 포함하고, 상기 서버 명령어들은 상기 데이터 처리 장치에 의해 실행되었을 때, 상기 데이터 처리 장치로 하여금
탐색 리소스에 대한 요청을 클라이언트 디바이스로부터 수신하는 동작;
상기 요청에 응답하여 상기 탐색 리소스를 상기 클라이언트 디바이스에 제공하는 동작을 수행하도록 하고,
상기 탐색 리소스는
상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 하는 제1 명령어들;
초기 쿼리 제안들; 및
제2 명령어들을 포함하며,
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고;
상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고;
상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고; 및
상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 하는 시스템.
청구항 1에 있어서,
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자들을 쿼리 제안 요청으로서 상기 데이터 처리 장치에 제공하고;
상기 요청에 응답하여, 상기 데이터 처리 장치로부터 추가 쿼리 요청들을 수신하고;
상기 제안 저장소에 상기 추가 쿼리 제안들을 저장하게 하고,
상기 서버 명령어들은 상기 데이터 처리 장치로 하여금 상기 쿼리 제안 요청에 응답하여 상기 클라이언트 디바이스에 상기 추가 쿼리 제안들을 제공하게 하는 시스템.
청구항 2에 있어서, 상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금 쿼리 문자의 각 입력에 대한 별개의 쿼리 제안 요청을 상기 쿼리 입력 필드에 제공하게 하는 시스템.
청구항 1에 있어서,
상기 서버 명령어들은 추가로 상기 데이터 처리 장치로 하여금 상기 클라이언트 디바이스로부터 수신된 상기 쿼리에 응답하여 탐색 결과 리소스를 제공하게 하고, 상기 탐색 결과 리소스는
상기 클라이언트 디바이스로 하여금 상기 쿼리에 응답하는 것으로 결정된 탐색 결과 참조 리소스들을 디스플레이하는 탐색 결과 페이지를 생성하게 하는 제3 명령어들과;
추가 쿼리 제안들과;
상기 클라이언트 디바이스로 하여금 상기 클라이언트 디바이스의 상기 제안 저장소에 상기 추가 쿼리 제안들을 저장하게 하는 제4 명령어들을 포함하는 시스템.
청구항 4에 있어서,
상기 탐색 결과 페이지는 제2 쿼리 입력 필드를 포함하고; 및
상기 제4 명령어들은 상기 클라이언트 디바이스로 하여금
상기 제2 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고;
상기 비교 결과에 기초하여 상기 제2 쿼리 입력 필드에 있는 상기 쿼리 문자들에 매치하는 제안들을 선택하고;
상기 쿼리 문자에 대한 쿼리 제안들로서 상기 선택된 쿼리 제안들을 상기 제2 쿼리 입력 필드에 디스플레이하게 하는 시스템.
청구항 1에 있어서, 상기 서버 명령어들은 상기 데이터 처리 장치들로 하여금
사용자들에 의해 제출된 쿼리들과 각 쿼리가 제출된 빈도(frequency)를 포함하는 쿼리 로그 데이터에 액세스하는 동작;
상기 쿼리 로그 데이터로부터 초기 쿼리 문자의 가능성이 가능 높은 시퀀스들을 결정하는 동작;
가능성이 가장 높은 시퀀스들 각각에 대하여, 가능성이 가장 높은 시퀀스와 상기 쿼리 로그 데이터로부터 가능성이 가장 높은 쿼리들을 결정하는 동작―가능성이 가장 높은 쿼리 각각은 초기 쿼리 문자의 가능성이 가장 높은 시퀀스에 매치하는 쿼리 문자의 초기 시퀀스를 가짐―; 및
초기 쿼리 문자의 가능성이 가장 높은 시퀀스 각각에 대해 결정된 상기 가능성이 가장 높은 쿼리들을, 상기 초기 쿼리 제안들로 지정하는 동작을 수행하도록 더 동작가능한 시스템.
청구항 6에 있어서,
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
쿼리 제안 요청으로서 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자들을 상기 데이터 처리 장치에 제공하고;
상기 요청에 응답하여, 상기 데이터 처리 장치로부터 추가 쿼리 제안들을 수신하고; 및
상기 제안 저장소에 상기 추가 쿼리 제안들을 저장하게 하고;
상기 서버 명령어들은 상기 데이터 처리 장치로 하여금
상기 클라이언트 디바이스로부터 상기 쿼리 문자를 수신하고; 및
상기 쿼리 로그 데이터로부터 후속 쿼리 문자(subsequent query characters)의 가능성이 가장 높은 시퀀스를 결정하게 하고―상기 후속 쿼리 문자는 상기 클라이언트 디바이스로부터 수신된 상기 쿼리 문자들에 대한 시퀀스에서 후속하는 쿼리 문자임―;
후속 쿼리 문자의 가능성이 가장 높은 시퀀스 각각에 대하여, 후속 쿼리 문자의 가능성이 가장 높은 시퀀스와 상기 쿼리 로그 데이터로부터 가능성이 가장 높은 추가 쿼리들을 결정하고―가장 가능성이 높은 쿼리는 클라이언트 디바이스로부터 수신된 상기 쿼리 문자에 매칭되는 쿼리 문자의 초기 시퀀스와 후속 쿼리 문자의 가능성이 가장 높은 시퀀스를 가짐―;
후속 쿼리 문자의 가능성이 가장 높은 시퀀스들 각각에 대해 결정된 가능성이 가장 높은 쿼리들을, 상기 추가 쿼리 제안들로 지정하고; 및
상기 쿼리 제안 요청에 응답하여 상기 클라이언트 디바이스에 상기 추가 쿼리 제안들을 제공하는 시스템.
청구항 7에 있어서,
상기 서버 명령어들은 상기 데이터 처리 장치로 하여금
키 값 쌍의 형태로 상기 초기 쿼리 제안들과 상기 추가 제안 쿼리들을 제공하게 하고―상기 키 값 쌍은 쿼리 입력 시퀀스와 상기 쿼리 입력 시퀀스들에 매치하는 초기 쿼리 문자들을 가지는 쿼리 제안들임―; 및
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자가 상기 키 값 쌍 중 어느 쿼리 입력 시퀀스에도 매칭되지 않는다는 결정에만 응답하여, 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력을 상기 데이터 처리 장치에 쿼리 제안 요청으로서 제공하게 하는 시스템.
청구항 1에 있어서,
상기 탐색 리소스에 대한 요청은 상기 클라이언트 디바이스의 현재 위치를 식별하는 위치 데이터를 포함하고;
상기 초기 쿼리 제안들은 상기 클라이언트 디바이스의 현재 위치에 특정하는 위치 특정 쿼리 제안들을 포함하고; 및
상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하는 동작은, 상기 클라이언트 디바이스의 상기 현재 위치에 특정하지 않는 위치 특정 쿼리 제안들을 제외시키는 동작을 더 포함하는 시스템.
프로세싱 시스템;
상기 프로세싱 시스템과 데이터 통신을 하고, 브라우저 명령어들을 저장하고 있는 메모리 저장 장치를 포함하고, 상기 브라우저 명령어들은 상기 프로세싱 시스템에 의해 실행되었을 때 상기 클라이언트 디바이스로 하여금 탐색 엔진으로부터 탐색 리소스에 대한 요청을 제공하는 동작; 및 상기 요청에 응답하여 상기 탐색 리소스를 수신하는 동작을 수행하도록 하고,
상기 탐색 리소스는
상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 하는 제1 명령어;
초기 쿼리 제안들; 및
제2 명령어들을 포함하고;
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
상기 클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고;
상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고;
상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고; 및
상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 하는 클라이언트 디바이스.
청구항 10에 있어서,
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자들을 쿼리 제안 요청으로서 상기 데이터 처리 장치에 제공하고;
상기 요청에 응답하여, 상기 데이터 처리 장치로부터 추가 쿼리 요청들을 수신하고;
상기 제안 저장소에 상기 추가 쿼리 제안들을 저장하게 하는 클라이언트 디바이스.
청구항 11에 있어서, 상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금 쿼리 문자의 각 입력에 대한 별개의 쿼리 제안 요청을 상기 쿼리 입력 필드에 제공하게 하는 클라이언트 디바이스.
청구항 11에 있어서,
상기 클라이언트 디바이스는 상기 클라이언트 디바이스로부터 수신된 상기 쿼리에 응답으로 탐색 결과 리소스를 수신하고, 상기 탐색 결과 리소스는
상기 클라이언트 디바이스로 하여금 상기 쿼리에 응답하는 것으로 결정된 탐색 결과 참조 리소스들을 디스플레이하는 탐색 결과 페이지를 생성하게 하는 제3 명령어들과;
추가 쿼리 제안들과;
상기 클라이언트 디바이스로 하여금 상기 클라이언트 디바이스의 상기 제안 저장소에 상기 추가 쿼리 제안들을 저장하게 하는 제4 명령어들을 포함하는 클라이언트 디바이스.
청구항 13에 있어서,
상기 탐색 결과 페이지는 제2 쿼리 입력 필드를 포함하고; 및
상기 제4 명령어들은 상기 클라이언트 디바이스로 하여금
상기 제2 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고;
상기 비교 결과에 기초하여 상기 제2 쿼리 입력 필드에 있는 상기 쿼리 문자들에 매치하는 제안들을 선택하고;
상기 쿼리 문자에 대한 쿼리 제안들로서 상기 선택된 쿼리 제안들을 상기 제2 쿼리 입력 필드에 디스플레이하게 하는 클라이언트 디바이스.
청구항 14에 있어서,
상기 초기 쿼리 제안들과 상기 추가 제안 쿼리들은 키 값 쌍으로 제공되고―상기 키 값 쌍은 쿼리 입력 시퀀스와 상기 쿼리 입력 시퀀스들에 매치하는 초기 쿼리 문자들을 가지는 쿼리 제안들임―; 및
상기 제2 명령어들과 상기 제 명령어들은 상기 클라이언트 디바이스로 하여금
상기 제1 쿼리 입력 필드 또는 제2 쿼리 입력 필드 각각에 있는 상기 쿼리 문자가 상기 키 값 쌍 중 어느 쿼리 입력 시퀀스에도 매칭되지 않는다는 결정에만 응답하여, 상기 제1 쿼리 입력 필드와 상기 제2 쿼리 입력 필드 각각에 있는 상기 쿼리 문자 입력을 상기 데이터 처리 장치에 쿼리 제안 요청으로서 제공하게 하는 클라이언트 디바이스.
청구항 15에 있어서,
상기 탐색 리소스에 대한 요청은 상기 클라이언트 디바이스의 현재 위치를 식별하는 위치 데이터를 포함하고;
상기 초기 쿼리 제안들은 상기 클라이언트 디바이스의 현재 위치에 특정하는 위치 특정 쿼리 제안들을 포함하고; 및
상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하는 동작은, 상기 클라이언트 디바이스의 상기 현재 위치에 특정하지 않는 위치 특정 쿼리 제안들을 제외시키는 동작을 더 포함하는 클라이언트 디바이스.
데이터 처리 장치에 의해 수행되는 컴퓨터 구현 방법으로서,
탐색 리소스에 대한 요청을 클라이언트 디바이스로부터 수신하는 단계; 및
상기 요청에 응답하여 상기 탐색 리소스를 상기 클라이언트 디바이스에 제공하는 단계를 포함하고,
상기 탐색 리소스는
상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 하는 제1 명령어들;
초기 쿼리 제안들; 및
제2 명령어들을 포함하며,
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고;
상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고;
상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고; 및
상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 하는 방법.
청구항 17에 있어서,
사용자들에 의해 제출된 쿼리들과 각 쿼리가 제출된 빈도를 포함하는 쿼리 로그 데이터에 액세스하는 단계;
상기 쿼리 로그 데이터로부터 초기 쿼리 문자의 가능성이 가능 높은 시퀀스들을 결정하는 단계;
가능성이 가장 높은 시퀀스들 각각에 대하여, 가능성이 가장 높은 시퀀스와 상기 쿼리 로그 데이터로부터 가능성이 가장 높은 쿼리들을 결정하는 단계―가능성이 가장 높은 쿼리 각각은 초기 쿼리 문자의 가능성이 가장 높은 시퀀스에 매치하는 쿼리 문자의 초기 시퀀스를 가짐―; 및
초기 쿼리 문자의 가능성이 가장 높은 시퀀스 각각에 대해 결정된 상기 가능성이 가장 높은 쿼리들을, 상기 초기 쿼리 문자들로 지정하는 단계를 포함하는 방법.
청구항 18에 있어서,
상기 클라이언트 디바이스로부터 상기 제1 쿼리 입력 필드에 쿼리 문자를 수신하는 단계; 및
상기 쿼리 로그 데이터로부터 후속 쿼리 문자(subsequent query characters)의 가능성이 가장 높은 시퀀스를 결정하는 단계―상기 후속 쿼리 문자는 상기 클라이언트 디바이스로부터 수신된 상기 쿼리 문자들에 대한 시퀀스에서 후속하는 쿼리 문자임―;
후속 쿼리 문자의 가능성이 가장 높은 시퀀스 각각에 대하여, 후속 쿼리 문자의 가능성이 가장 높은 시퀀스와 상기 쿼리 로그 데이터로부터 가능성이 가장 높은 추가 쿼리들을 결정하고―가장 가능성이 높은 쿼리는 클라이언트 디바이스로부터 수신된 상기 쿼리 문자에 매칭되는 쿼리 문자의 초기 시퀀스와 후속 쿼리 문자의 가능성이 가장 높은 시퀀스를 가짐―;
후속 쿼리 문자의 가능성이 가장 높은 시퀀스들 각각에 대해 결정된 가능성이 가장 높은 쿼리들을, 추가 쿼리 제안들로 지정하는 단계; 및
상기 쿼리 제안 요청에 응답하여 상기 클라이언트 디바이스에 상기 추가 쿼리 제안들을 제공하는 방법.
청구항 19에 있어서,
상기 초기 쿼리 제안들과 상기 추가 제안 쿼리들은 키 값 쌍의 형태이고―상기 키 값 쌍은 쿼리 입력 시퀀스와 상기 쿼리 입력 시퀀스들에 매치하는 초기 쿼리 문자들을 가지는 쿼리 제안들임―; 및
상기 제1 쿼리 입력 필드 또는 제2 입력 필드에 있는 상기 쿼리 문자가 상기 키 값 쌍 중 어느 쿼리 입력 시퀀스에도 매칭되지 않는다는 결정에만 응답하여, 상기 제1 쿼리 입력 필드 또는 상기 제2 입력 필드에 있는 상기 쿼리 문자 입력가 쿼리 제안 요청으로서 제공되는 방법.
명령어들을 포함하는 컴퓨터 프로그램으로 인코딩된 컴퓨터 저장 매체로서, 상기 명령어들은 데이터 처리 장치에 의해 실행되었을 때, 상기 데이터 처리 장치로 하여금
탐색 리소스에 대한 요청을 클라이언트 디바이스로부터 수신하는 동작; 및
상기 요청에 응답하여 상기 탐색 리소스를 상기 클라이언트 디바이스에 제공하는 동작을 수행하게 하고,
상기 탐색 리소스는
상기 클라이언트 디바이스로 하여금 제1 쿼리 입력 필드를 포함하는 탐색 인터페이스를 생성하도록 하는 제1 명령어들;
초기 쿼리 제안들; 및
제2 명령어들을 포함하며,
상기 제2 명령어들은 상기 클라이언트 디바이스로 하여금
클라이언트 디바이스의 제안 저장소에 상기 초기 쿼리 제안들을 저장하고;
상기 제1 쿼리 입력 필드에 있는 쿼리 문자 입력을 상기 제안 저장소에 저장된 상기 쿼리 제안들과 비교하고;
상기 비교 결과에 기초하여 상기 제1 쿼리 입력 필드에 있는 상기 쿼리 문자 입력에 매치하는 쿼리 제안들을 선택하고; 및
상기 선택된 쿼리 제안들을 상기 쿼리 문자 입력에 대한 쿼리 제안들로서 상기 제1 쿼리 입력 필드에 디스플레이하게 하는 컴퓨터 저장 매체.