PISA: 学术界的高性能索引和搜索
加入我们的Slack
概述
PISA是一个能够在大规模文档集合上运行的文本搜索引擎。它允许研究人员使用最先进的技术进行实验,为快速开发提供了理想的环境。
以下列出了PISA的一些特点:
- 使用C++编写以提高性能;
- 具备解析、索引和分片能力;
- 实现了多种索引压缩方法;
- 实现了多种查询处理算法;
- 实现了文档重排序;
- 免费开源,采用宽松许可证;
关于PISA
PISA是什么?
PISA是一个文本搜索引擎,而"PISA项目"是一套帮助进行索引和查询处理实验的工具集。 给定一个文本集合,PISA可以在这个语料库上构建一个倒排索引, 使得可以对该语料库进行搜索。简单来说,倒排索引是一种高效的 数据结构,它通过为每个唯一词条存储文档列表来表示文档语料库 (参见这里)。 在查询时,PISA将其索引存储在主内存中以实现快速检索。
这一切意味着什么?
简单来说,PISA是一个文本搜索引擎。从一个文档语料库开始,
例如维基百科,PISA可以构建一个倒排索引,使我们能够
快速搜索维基百科集合。在最基本的层面上,支持布尔
AND
和OR
查询。想象我们想要找到所有匹配查询*"乌龙茶"的
维基百科文档 - 我们可以运行一个布尔合取查询(乌龙 AND
茶)。
我们也可能对找到包含乌龙或茶*(或两者)的文档感兴趣,在这种情况下
我们可以运行一个布尔析取查询(乌龙 OR
茶)。
除了上面讨论的简单布尔匹配之外,我们实际上可以对文档进行排序。 简单来说,文档是通过假设词语越罕见就越重要的函数来排序的。 这些排序器还假设一个词在文档中出现的次数越多,该文档就越有可能是关于那个词的。 最后,较长的文档包含更多的词,因此比较短的文档更有可能获得更高的分数, 所以会进行归一化处理以确保所有文档得到平等对待。感兴趣的读者可能希望 查看TF/IDF维基百科文章以了解更多关于这种排序方法的信息。
搜索与模式匹配
这与grep
这类搜索不同。这更接近流行的Lucene搜索引擎,尽管我们目前
不支持像Lucene那么多的查询类型。如前所述,PISA中的主要底层数据
结构是倒排索引。倒排索引为每个词条存储包含该词条的文档列表。
可以快速遍历这些列表以找到匹配查询词的文档,然后对这些文档进行
评分、排序并返回给用户。
谁应该使用PISA?
PISA的主要用途是进行实验,以进一步理解信息检索(IR)领域。在IR领域中,有各种重要的研究方向,从改善结果质量(有效性)到提高搜索系统的可扩展性和效率。PISA主要关注IR研究的可扩展性和效率方面,这也是PISA代表"学术界高性能索引和搜索"的原因。简而言之,PISA是一个用于开发高效搜索新创新的平台。
如果我只是想玩玩搜索引擎呢?
虽然PISA专注于作为实验的基础,但它也非常适合用作简单的通用索引和搜索系统。
PISA能处理什么规模的数据?
PISA可以处理大型文本集合。例如,PISA可以轻松索引ClueWeb09B或ClueWeb12B语料库,每个语料库包含超过5000万个网页文档和接近500 GiB的压缩文本数据,生成的索引大小在10-40 GiB之间,具体取决于所使用的压缩编解码器。根据具体情况,这些索引可以在大约10-20小时内从头开始构建。此外,可以通过索引分片来处理更大的集合,将大型语料库分解为较小的子集(分片)。但是,我们需要注意,PISA是一个内存中系统,旨在基于完全驻留在主内存中的索引来服务查询。因此,可能的规模将受到主内存的限制。
PISA到底有多快?
最近有几项工作对PISA进行了基准测试。例如,Antonio Mallia、Michal Siedlaczek和Torsten Suel在ECIR 2019上发表的索引压缩和DAAT查询处理方法的实验研究显示,PISA能够在包含5000万个网页文档的集合上,以10-40和20-50毫秒的平均延迟分别返回前10和前1000个文档。
PISA还包含在Tantivy的搜索引擎基准游戏中,该游戏还有Tantivy、Lucene和Rucene作为竞争对手。
PISA是如何开始的?
PISA是Giuseppe Ottaviano发起的ds2i项目的一个分支。ds2i项目包含了IR领域中许多重要效率创新的源代码,包括"分区Elias-Fano"压缩方法。
入门
对于那些有兴趣使用PISA的人,我们建议查看以下资源:
- 描述PISA的开源信息检索可复现性挑战(OSIRRC)论文,包括端到端实验。
- 附带的Docker镜像,可用于复现上述实验。
- 文档。
- 加入我们的Slack频道打个招呼!
贡献
如果你想参与PISA,请查看我们的贡献页面。
引用
如果你在研究论文中使用PISA,请引用以下参考文献:
@inproceedings{MSMS2019,
author = {Antonio Mallia and Michal Siedlaczek and Joel Mackenzie and Torsten Suel},
title = {{PISA:} Performant Indexes and Search for Academia},
booktitle = {Proceedings of the Open-Source {IR} Replicability Challenge co-located
with 42nd International {ACM} {SIGIR} Conference on Research and Development
in Information Retrieval, OSIRRC@SIGIR 2019, Paris, France, July 25,
2019.},
pages = {50--56},
year = {2019},
url = {http://ceur-ws.org/Vol-2409/docker08.pdf}
}