Google Summer of Code 2023 - Polygon Geo Filter for Qdrant Vector Database
TL;DR · AI 摘要
Qdrant 在 2023 年 Google Summer of Code 中新增了多边形地理过滤功能，提升向量数据库的地理查询能力。
核心要点
- Qdrant 新增多边形地理过滤功能，提升查询灵活性。
- 使用 GeoHash 分层结构优化地理查询性能。
- 采用 Ray Casting 算法判断点与多边形关系。
结构提纲
按章节快速跳转。
介绍作者参与 Google Summer of Code 项目，开发 Qdrant 多边形地理过滤功能。
说明地理过滤功能的使用场景和 Qdrant 当前功能的局限性。
解释 Qdrant 内部使用 GeoHash 分层结构进行地理计算的原理。
描述对 GeoHash 算法进行测试和验证的过程，包括 Ray Casting 算法的使用。
介绍在项目中对 Proto 和 JSON 格式设计的深入研究和优化。
思维导图
用一张图看清主题之间的关系。
查看大纲文本（无障碍 / 无 JS 友好）
- Qdrant 多边形地理过滤功能
- 技术挑战
- GeoHash 分层结构
- 多边形与矩形相交判断
- 点在多边形内判断
- 实现方法
- 使用 Ray Casting 算法
- Proto 和 JSON 格式设计
金句 / Highlights
值得收藏与分享的关键句。
Qdrant 使用 GeoHash 分层结构，将世界划分为矩形，提升查询效率。
采用 Ray Casting 算法判断点是否在多边形内，提高地理查询准确性。
通过深入测试和可视化验证，确保 GeoHash 和多边形计算算法的准确性。
Google Summer of Code 2023 - Qdrant 向量数据库的多边形地理过滤器
返回 Qdrant 文章
·
2023 年 10 月 12 日
介绍
大家好，我是 Zein Wen，我是 Qdrant 的 Google Summer of Code 2023 参与者。我有幸与一位非常优秀的导师 Arnaud Gourlay 合作，共同增强 Qdrant 的地理多边形过滤器功能。这个新功能允许用户使用多边形来进一步细化查询结果。作为地理过滤器家族中半径和矩形过滤器的最新补充，这一增强功能为查询地理数据提供了更大的灵活性，开启了有趣的全新使用场景。
项目概述
地理过滤器的使用案例（https://traveltime.com/blog/map-postcode-data-catchment-area）
由于 Qdrant 是一个功能强大的向量查询数据库，它为机器学习驱动的应用程序（如推荐系统）提供了巨大的潜力。然而，仅靠向量查询的范围可能并不总是能满足用户的需求。设想一下，当你寻找餐厅推荐时，你不仅仅想要一份餐厅列表，而是那些位于你社区内的餐厅。这就是地理过滤器发挥作用的地方，通过引入额外的过滤条件来增强查询。在此之前，Qdrant 的地理过滤选项仅限于圆形和矩形，这可能无法与现实世界中多样的边界相匹配。这种场景正是用户提出功能请求的原因，我们决定解决这个问题，因为它为与地理相关的查询引入了更大的能力。
技术挑战
- 地理几何计算
地理空间基本概念
内部的地理过滤器不会从测试每个单独的地理位置开始，因为这在计算上会非常昂贵。相反，我们创建了一个地理哈希层，将世界划分为矩形。当为 Qdrant 条目创建空间索引时，它会将条目分配给其位置的地理哈希。
在查询过程中，我们首先识别所有满足过滤条件的潜在地理哈希，然后在这些哈希中检查位置候选者。完成此搜索涉及两个关键的几何计算：
- 确定多边形是否与矩形相交
- 确定一个点是否位于多边形内。
几何计算测试
虽然我们有一个 geo crate（一个 Rust 库），它为这些计算提供了 API，但我们深入研究了底层算法并验证了它们的准确性。这引导我们进行了广泛的测试和可视化以确定正确性。除了评估当前的 crate，我们还发现有多种算法可用于这些计算。我们投入时间探索了不同的方法，如 winding windows 和 ray casting，以理解它们的区别，并为未来的改进铺平道路。
通过这个过程，我享受到了快速掌握陌生概念的能力。此外，我还需要开发分析策略，以剖析并从中得出有意义的结论。这种经验对扩展我的问题解决工具包非常宝贵。
- Proto 和 JSON 格式设计
为这个新功能设计 ProtoBuf 和 JSON 接口投入了大量努力。这个组件直接暴露给用户，需要一个一致且用户友好的接口，这反过来有助于提升用户体验并减少未来代码的修改。
最初，我们考虑将接口与 GeoJSON 规范对齐，因为它是许多与地理相关的 API 的标准。然而，我们很快意识到 GeoJSON 定义几何的方式与我们当前用于点半径和矩形过滤器的 JSON 和 ProtoBuf 坐标定义存在显著差异。因此，我们优先考虑 API 层面的一致性和用户体验，选择将新的多边形定义与我们现有的所有定义保持一致。
此外，我们原本计划除了多边形之外，再开发一个独立的多边形过滤器。然而，经过仔细考虑后，我们认识到，对于我们的使用场景，多边形过滤器可以实现与多边形过滤器相同的效果。这种关系与我们目前处理多个圆形或矩形的方式类似。因此，我们认为多边形过滤器是多余的，会为 API 增加不必要的复杂性。
完成这项工作让我认识到，在现实世界中寻找解决方案时，要在遵循既定标准和优先考虑用户体验之间找到平衡是一项挑战。同时，这也让我更加理解了专注于开发用户真正需要的功能的重要性，而不是过度扩展我们的努力。
成果
- 深入探索的能力
能够在不熟悉的代码库、概念、API 和技术中深入探索，是开发人员常见的挑战。参与 GSoC 对我来说就像从游泳池的安全区域直接跳入了广阔的海洋。在这个转变过程中，导师的支持是无价的。他为我提供了许多独立探索之前从未接触过的领域的机会。我逐渐不再害怕未知的技术领域，无论是不熟悉的代码、特定领域中的技术还是概念。我对自己逐步学习并运用它们来实现自己设想的能力充满了信心。
- 始终以用户为中心
我学到的另一个重要教训是，考虑用户体验及其具体使用场景的重要性。虽然开发过程中可能涉及迭代过程，但所有直接影响用户的功能都必须以同理心来处理和执行。忽视这一点不仅可能导致功能错误，还可能因为不一致和困惑而削弱用户的信任，最终导致他们不再使用我的工作成果。
- 勇于表达并有效沟通
最后，在开发过程中，遇到不同意见是常见的事情。保持对他人想法的开放态度，同时也要有清晰表达自己观点的决心，这是至关重要的。这有助于促进富有成效的讨论，最终提升开发过程的质量。
总结
被选中参与 Google Summer of Code 2023，并与 Arnaud 和其他 Qdrant 工程师以及所有社区成员合作，是一次真正的荣幸。我非常感激那些花时间审查我的代码、讨论替代方案和设计选择、并在需要时提供帮助的人。通过这些互动，我亲身经历了开源的本质和鼓励协作的文化。这次经历不仅让我第一次为真实产品编写了 Rust 代码，也让我打开了通往开源世界的大门。
毫无疑问，我渴望继续与这个社区一同成长，并为提升产品的功能和改进做出贡献。我也成为了 Qdrant 的倡导者，向许多同事和科技行业的朋友们介绍了这个项目。我非常期待看到在我的社交圈中涌现出新的用户和贡献者！
如果你想尝试我的工作，请阅读文档，然后注册一个免费的云账户或下载 Docker 镜像。我期待看到人们如何在自己的应用中使用我的工作！