压缩完美嵌入式跳过列表加速倒排索引查找
PDF格式 | 174KB |
更新于2024-07-14
| 21 浏览量 | 举报
"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页未读，继续阅读
相关推荐
weixin_38637665
- 粉丝: 4
我的内容管理
展开
最新资源
- 安装Oracle必备：unixODBC-2.2.11-7.1.x86_64.rpm
- Spring Boot与Camel XML聚合快速入门教程
- React开发新工具：可拖动、可调整大小的窗口组件
- vlfeat-0.9.14 图像处理库深度解析
- Selenium自动化测试工具深度解析
- ASP.NET房产中介系统：房源信息发布与查询平台
- SuperScan4.1扫描工具深度解析
- 深入解析dede 3.5 Delphi反编译技术
- 深入理解ARM体系结构及编程技巧
- TcpEngine_0_8_0：网络协议模拟与单元测试工具
- Java EE实践项目：在线商城系统演示
- 打造苹果风格的Android ListView实现与下拉刷新
- 黑色质感个人徒步旅行HTML5项目源代码包
- Nuxt.js集成Vuetify模块教程
- ASP.NET+SQL多媒体教室管理系统设计实现
- 西北工业大学嵌入式系统课程PPT汇总
