TL;DR;

Query Autocompletionはユーザの検索体験を改善するために広く導入されていますが、効果的に提供するにはシステム要求を理解しておくとよいとおもいます

そこでQuery Autocompletionの概要と歴史的経緯を説明したうえで一般的なシステム構成について解説してみます
Query Autocompletionを担当することになった（ニッチな）エンジニアの方に参考になればうれしいです
※英語がOKなら参考文献を読んだ方が良いです

Query Autocompletionとは

Query Autocompletionは検索支援機能の一つです

Query Autocompletionの例
検索ボックスでユーザの検索したいクエリを予測し提示することで、少ないキーストロークで検索行動を完了させることを目的としています
GoogleのようなWeb検索、Amazonのようなeコマース、twitterのようなSNSアプリにおいてPC/モバイル問わず提供されています。

サジェスト、QAC、QuerySuggestなどと呼ばれています

Query Autocompletionシステムに要求されること

Query Autocompletionシステムには高スループットかつ低レイテンシーが要求されます

要求	要求される性能
スループット	検索ボックスの検索数の数倍のリクエストを処理する
Latency	ユーザの入力から100ミリ秒以内に表示が完了する

高スループット

Query Autocompletionシステムでは検索ボックスの入力が変更される単位で検索が実行されます
つまり１文字増えるごとに検索が実行されるため１つの検索クエリで数倍のAPIの呼び出しが発生します
たとえば”ラーメン”と検索する場合Query Autocompletionでは”ラ"、"ラー"､"ラーメ"､”ラーメン”と呼び出されると考えられます。日本語入力の場合”R”、"RA"といったローマ字入力の場合はより多くの検索が実行されるかもしれません

低レイテンシー

Query Autocompletionシステムは、PC・モバイルに搭載されている日本語入力用のIMEと同様の応答をユーザに期待されています
人間は応答速度が50ミリ秒以内であればリアルタイムで処理されていると感じますが、100ミリ秒を超えるとユーザの行動とは関係ないアクションだと感じてしまいます
そのことからサーバーサイドで50ミリ秒以内の応答が望ましいと考えられています

Query Autocompletionの歴史

Autocompletionの歴史

Query Autocompletionの歴史は1960年代まで遡ることが、コマンド入力支援として継続的に研究対象となっています
当時はインクリメントサーチと呼ばれクエリの予測ではなく事前に登録されていた”単語”や"コ
マンド"といったコンテンツ予測が主なタスクでした

Query AutocompletionとWeb検索

2000年代には、利用者の履歴をベースとしたQuery AutocompletionがOSやブラウザ・メールなどに組み込まれています
Web検索への適用は2004年にラボ機能としてGoogle Suggestがリリースとなります
Google Suggestは2008年にGoogle検索に統合され、いまではWeb検索の必須な補助機能となっています

Query Autocompletionの効果

Query Autocompletionは、ユーザ検索体験とシステムリソース両方への効果があります

ユーザ検索体験への効果

ユーザのクエリの⼊力時間を節約
- Yahoo!(2014)の英語/PCユーザのキーストロークが50％以上節約
- Google(2006)のモバイルユーザで最大46%以上節約すると発表
スペルミスを回避
関連する検索⽤語を見つける

システムリソースへの効果

適切なクエリを作成することができればユーザの検索時間が減るので、検索エンジンへの負荷が下がります

Query Autocompletionのフローについて

一般的なQuery Autocompletionのフローをしまします

検索ボックスの入力が変更された文字”Prefex”をQuery Autocompletionに問い合わせを行う
文字”Prefex”からユーザの完成した検索クエリ候補を取り出す(検索処理)
検索結果候補から時間・位置情報・ユーザの行動履歴などを用いてランキングを行う(ランキング)
検索ボックスの下などに検索クエリ候補を表示する（表示）

”検索処理”、”ランキング”、”表示”各処理で様々な改善手法が提案されています

まとめ

Query Autocompletionはユーザの検索体験を改善するためにだけでなく検索システムへの負荷を低減するなどのメリットがあるため広く導入されています
ただし効果的に提供するには低latencyで高スループットな検索システムが必要になります

フィードバックのお願い

Query Autocompletionは中規模以上になると検索エンジンとは別のシステムアーキテクチャーやデータ構造が必要になるといわれております
今後も自分の理解を深める目的でQuery Autocompletionの詳細についてまとめる予定です、記事のへのフィードバックや間違いへの指摘をいただければと思います