查询引导的位置敏感哈希

Approximate Nearest Neighbor Search is a fundamental problem in processing complex data objects and has extensive applications in various domains, such as database, data mining and computational geometry. Locality-Sensitive Hashing (LSH) and its variants are the most influential solution of the Approximate Nearest Neighbor Search problem in high-dimensional space. Traditionally, an LSH scheme partitions data objects into buckets before any query arrives, and hence a query object and its real neighbor can be partitioned into different buckets. To overcome this limitation, we have newly developed a query-aware LSH scheme named QALSH. In this project, based on our current research progresses, on the one hand we plan to conduct further studies on query-aware LSH from both theoretical and algorithmic perspectives , using the Approximate Nearest Neighbor Search problem as the underlying motivation. On the other hand, we plan to leverage query-aware LSH to solve the Approximate Furthest Neighbor Search and Approximate Closest Pair Search problems, which are closely related to the Approximate Nearest Neighbor Search. In addition, we will study how to effectively implement distributed computing of LSH so that we can easily handle similarity search over massive high-dimensional data. Studies on LSH schemes not only hold great scientific significance in basic theories of computer science, data science and high-dimensional computational geometry, but also enjoy substantial potential in advancing intelligent applications of big data in China.

近似最近邻检索是复杂数据对象处理中的一个基本问题，在数据库、数据挖掘以及高维计算几何等领域有着广泛的应用。位置敏感哈希及其变体是目前最有影响的高维近似最近邻检索机制。传统上，位置敏感哈希在任何查询到来之前已经将数据对象分桶，因此可能将查询对象与它的近邻分进不同的桶。为了克服这一局限，我们新近发展了查询引导的位置敏感哈希机制QALSH。本项目就是希望在我们的现有研究基础上，一方面，针对近似最近邻检索，对查询引导的位置敏感哈希理论与算法开展更深入的研究。另一方面，将查询引导的位置敏感哈希机制用来解决密切相关的近似最远邻检索与近似最近对检索。此外，我们还将研究如何高效地实现位置敏感哈希的分布式计算，以便支持海量高维数据的相似性检索。研究位置敏感哈希技术，不仅在计算机科学，数据科学，高维计算几何等等学科的基础理论方面具有重大科学意义，而且在推动中国大数据智能应用方面具有极其广阔的发展前景。

近似最近邻检索是复杂数据对象处理中的一个基本问题，在数据库、数据挖掘以及高维计算几何等领域有着广泛的应用。位置敏感哈希及其变体是目前最有影响的高维近似最近邻检索机制。传统上，位置敏感哈希在任何查询到来之前已经将数据对象分桶，因此可能将查询对象与它的近邻分进不同的桶。为了克服这一局限，我们新近发展了查询引导的位置敏感哈希机制QALSH: 以查询为锚点动态地进行分桶。本项目在原始QALSH的基础上，一方面，针对近似最近邻检索问题，对查询引导的位置敏感哈希理论与算法开展了更深入的研究。另一方面，将查询引导的位置敏感哈希机制用来解决密切相关的高维相似性检索问题。目前我们在以下方面取得重要研究进展：.1. 将仅仅针对欧式距离(即l2距离）的原始QALSH扩展到解决任意lp距离（0 < p ≤ 2）下的近似最近邻检索问题；.2. 将QALSH用来解决高维欧式空间中的近似最远邻检索问题；.3. 将QALSH用来解决高维欧式空间中的近似最大内积检索问题；.4. 将QALSH与关系数据库系统(PostgreSQL)内核进行耦合；.5. 将QALSH基于非易失性内存进行优化实现；.6. 将QALSH进行单机多核并行化。