压缩完美嵌入式跳过列表加速倒排索引查找

93 浏览量更新于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提出了更精细的技术——压缩完美嵌入式跳过列表，这种技术旨在直接在倒排列表中嵌入压缩的跳过结构。文章提供了统计模型来解释他们在实验中观察到的跳过数据的分布，并基于这些模型设计了有效的压缩技术。这些技术的目标是在节省空间的同时，允许以较高的粒度对指针进行索引，从而增加整体索引大小只有几个百分点，但仍然能实现快速查找。介绍部分还强调了倒排索引的重要性，它们是搜索引擎快速响应查询的基础。倒排索引将词汇表中的每个词关联到包含这个词的文档列表，而跳过列表则进一步提高了搜索速度。通过压缩技术优化这一结构，可以平衡存储开销和检索性能。论文详细讨论了如何实现这种压缩的完美跳过列表，包括其设计原理、压缩算法以及如何在实际应用中有效利用这些方法。此外，文章可能还包含了实验结果，展示了新方法相对于传统跳过策略的性能提升和空间效率。这篇计算机科学论文提供了一种创新的解决方案，用于优化大规模搜索引擎的索引结构，以适应不断增长的网络数据量，同时保持高效的查询性能。

DATA

· · ·

c o

· · ·

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

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, ﬁlesystem-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

efﬁciently.

Perfect skip lists. Skip lists [9] are a data structure in which elements are organised as in an

ordered list, but with additional references

that allow one to skip forward in the list as needed.

More precisely, a skip list is a singly linked list of items hx

, x

, . . . , x

n−1

i, such that:

• items in the list are increasingly ordered w.r.t. some ﬁxed order relation, that is, x

≤ x

≤

··· ≤ x

n−1

;

• every item x

appearing in the list contains a reference to the next item x

i+1

(as in any

linked list);

• moreover, item x

contains a certain number h

≥ 0 of extra references, that are called the

skip tower of the item; the t-th reference in this tower addresses the ﬁrst item j > i such

that h

≥ t.

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.

剩余14页未读，继续阅读

weixin_38637665

粉丝: 4
资源: 951

压缩完美嵌入式跳过列表加速倒排索引查找

Adapted compressed sensing for effective hardware implementations-2018

Compiling kernel for Multi-VM(host-vm)

curl --help

U-Shaped Transformer for Image Restoration

最新资源