压缩完美嵌入式跳过列表加速倒排索引查找
40 浏览量
更新于2024-07-14
收藏 174KB PDF 举报
"Compressed Perfect Embedded Skip Lists for Quick Inverted-Index Lookups-计算机科学"
本文主要探讨了在大规模倒排索引（inverted index）中提高搜索效率的技术，特别是压缩完美嵌入式跳过列表（Compressed Perfect Embedded Skip Lists）。倒排索引是构建大型搜索引擎的关键组成部分，它允许快速定位到包含特定关键词的文档。为了加速查找过程，通常会在索引内部建立跳过机制，以便快速跳过无关文档。
传统的跳过策略是在每平方根f个文档指针处设置一个跳过节点，其中f表示该关键词出现的总文档数。然而，随着互联网规模的扩大，这种方法可能不再足够高效。作者Paolo Boldi和Sebastiano Vigna提出了更精细的技术——压缩完美嵌入式跳过列表，这种技术旨在直接在倒排列表中嵌入压缩的跳过结构。
文章提供了统计模型来解释他们在实验中观察到的跳过数据的分布，并基于这些模型设计了有效的压缩技术。这些技术的目标是在节省空间的同时，允许以较高的粒度对指针进行索引，从而增加整体索引大小只有几个百分点，但仍然能实现快速查找。
介绍部分还强调了倒排索引的重要性，它们是搜索引擎快速响应查询的基础。倒排索引将词汇表中的每个词关联到包含这个词的文档列表，而跳过列表则进一步提高了搜索速度。通过压缩技术优化这一结构，可以平衡存储开销和检索性能。
论文详细讨论了如何实现这种压缩的完美跳过列表，包括其设计原理、压缩算法以及如何在实际应用中有效利用这些方法。此外，文章可能还包含了实验结果，展示了新方法相对于传统跳过策略的性能提升和空间效率。
这篇计算机科学论文提供了一种创新的解决方案，用于优化大规模搜索引擎的索引结构，以适应不断增长的网络数据量，同时保持高效的查询性能。
f
t
p
0
DATA
p
1
DATA
p
2
DATA
p
3
DATA
p
4
DATA
· · ·
c o
0
o
1
o
2
o
3
· · ·
Figure 1: An inverted list without skips.
the document), plus possibly some additional data, such as
• the count, that is, the number of occurrences of term t in document p;
• the positions, that is, the list of integers representing the positions where the term t appears
in document p.
The number of items contained in the inverted index for term t (i.e., the number of documents
where t occurs) is called the frequency f
t
of t, and it is usually written at the beginning of the
inverted list. A graphical example is shown in Figure 1.
Inverted lists are accessed sequentially, as their purpose is exactly to retrieve a sequence of
documents containing a term; usually, when trying to match a query, several inverted lists are
read and merged. Introducing skips in these lists, as suggested in [6], may allow one to save
time because in conjunctive queries one can skip over useless postings.
When a skip structure is embedded in an inverted list, we can tell how quickly a skip can be
performed by counting the number of record read, the number of integer read, and the number
of jumps, that is, low-level (usually, filesystem-level) calls that skip over a given number of
bits. In the rest of this paper, we shall describe a data structure that is the natural evolution of
the one-level skip described in [6], and show how this structure can be compressed and used
efficiently.
Perfect skip lists. Skip lists [9] are a data structure in which elements are organised as in an
ordered list, but with additional references
1
that allow one to skip forward in the list as needed.
More precisely, a skip list is a singly linked list of items hx
0
, x
1
, . . . , x
n−1
i, such that:
• items in the list are increasingly ordered w.r.t. some fixed order relation, that is, x
0
≤ x
1
≤
··· ≤ x
n−1
;
• every item x
i
appearing in the list contains a reference to the next item x
i+1
(as in any
linked list);
• moreover, item x
i
contains a certain number h
i
≥ 0 of extra references, that are called the
skip tower of the item; the t-th reference in this tower addresses the first item j > i such
that h
j
≥ t.
1
The term reference used here can be taken to mean “memory address”; in the data structure and programming
literature this is usually called pointer. Unfortunately, in the papers on inverted indices, pointer is used for “document
number”, and we shall adhere to this tradition.
3
剩余14页未读，继续阅读
点击了解资源详情
点击了解资源详情
点击了解资源详情
2021-02-10 上传
2021-04-22 上传
2021-06-08 上传
2021-04-22 上传
2021-05-26 上传
2021-04-22 上传
weixin_38637665
- 粉丝: 4
- 资源: 951
我的内容管理
展开
最新资源
- Java毕业设计项目：校园二手交易网站开发指南
- Blaseball Plus插件开发与构建教程
- Deno Express：模仿Node.js Express的Deno Web服务器解决方案
- coc-snippets: 强化coc.nvim代码片段体验
- Java面向对象编程语言特性解析与学生信息管理系统开发
- 掌握Java实现硬盘链接技术：LinkDisks深度解析
- 基于Springboot和Vue的Java网盘系统开发
- jMonkeyEngine3 SDK：Netbeans集成的3D应用开发利器
- Python家庭作业指南与实践技巧
- Java企业级Web项目实践指南
- Eureka注册中心与Go客户端使用指南
- TsinghuaNet客户端：跨平台校园网联网解决方案
- 掌握lazycsv：C++中高效解析CSV文件的单头库
- FSDAF遥感影像时空融合python实现教程
- Envato Markets分析工具扩展：监控销售与评论
- Kotlin实现NumPy绑定：提升数组数据处理性能
