Nearest Neighbor Search in Google Correlate
Nearest Neighbor Search in Google Correlate
复制标题
Google Correlate 中的最近邻搜索
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Sanjiv Kumar
中科院分区：
文献类型：
--
作者：
D. Vanderkam;Robert B Schonberger;H. Rowley;Sanjiv Kumar
本文介绍了为 Google Correlate[8] 提供支持的算法，该工具可查找随时间推移的流行度与用户提供的时间序列最匹配的网络搜索词。 Correlate 的开发是为了推广 Google Flu Trends 首创的基于查询的建模技术，并将其提供给最终用户。将数百万个候选查询时间序列中的搜索关联起来，以找到最佳匹配，并在不到 200 毫秒的时间内返回结果。其功能集和要求对近似最近邻 (ANN) 搜索技术提出了独特的挑战。在本文中，我们介绍了 Correlate 使用的非对称哈希 (AH) 技术，并展示了如何对其进行调整以满足产品的特定需求。然后，我们开发实验来测试非对称哈希与暴力搜索的吞吐量和召回率。对于“完整”搜索向量，我们实现了比暴力搜索快 10 倍的速度，同时保持 97% 的召回率。对于包含保留期的搜索向量，我们实现了比暴力搜索快 4 倍的速度，并且召回率也达到 97%。
This paper presents the algorithms which power Google Correlate[8], a tool which finds web search terms whose popularity over time best matches a user-provided time series. Correlate was developed to generalize the query-based modeling techniques pioneered by Google Flu Trends and make them available to end users. Correlate searches across millions of candidate query time series to find the best matches, returning results in less than 200 milliseconds. Its feature set and requirements present unique challenges for Approximate Nearest Neighbor (ANN) search techniques. In this paper, we present Asymmetric Hashing (AH), the technique used by Correlate, and show how it can be adapted to fit the specific needs of the product. We then develop experiments to test the throughput and recall of Asymmetric Hashing as compared to a brute-force search. For “full” search vectors, we achieve a 10x speedup over brute force search while maintaining 97% recall. For search vectors which contain holdout periods, we achieve a 4x speedup over brute force search, also with 97% recall.