SuRF:PracticalRangeQueryFilteringwithFastSuccinctTries原文资源-CSDN文库

5星 · 超过95%的资源需积分: 16 113 浏览量 2018-09-12 11:06:48 上传评论收藏 2.63MB PDF 举报

《SuRF: 实践性范围查询过滤与快速简洁的Trie》是关于一种新的数据结构SuRF（Succinct Range Filter）的研究论文。SuRF旨在解决传统Bloom Filter无法同时高效处理单键查找和范围查询的问题。文章由来自卡内基梅隆大学、慕尼黑工业大学、英特尔实验室和惠普企业实验室的研究人员共同撰写。SuRF基于一个名为Fast Succinct Trie（FST）的新型数据结构，能够在保持点查询和范围查询性能的同时，将每个trie节点的存储消耗降低到10比特。在数据结构中，Bloom Filter是一种使用位数组进行成员测试的数据结构，它可以快速判断一个元素是否在一个集合中，但无法处理范围查询。SuRF的提出，解决了这一局限性，它可以用于近似成员测试，支持单键查找和常见的范围查询，包括开放范围查询、封闭范围查询和范围计数。文章通过在RocksDB数据库中替换其原有的Bloom Filter来评估SuRF的性能。RocksDB是一个高性能的嵌入式数据库，广泛用于处理大规模数据存储，它通过将写操作记录在一个写优化的日志结构合并树（LSM树）中来提供快速的写入性能。SuRF作为其Bloom Filter的替代品，可以减少因I/O导致的延迟，从而加速数据库查询的响应时间。 SuRF通过调整其内部参数来实现对点查询和范围查询的错误率进行调节，以适应不同应用需求。在实验中，研究人员使用了一个100GB的大型数据集对SuRF和Bloom Filter进行了比较测试。结果显示，使用SuRF替换RocksDB的Bloom Filter后，无上限的开放范围查询（open-seek）以及有上限的封闭范围查询（closed-seek）速度提高了1.5倍和5倍。尽管在最坏情况（所有查找都缺失）的点查询吞吐量上，由于错误率略高而有一定的损失，但整体而言，SuRF提供了一个具有吸引力的解决方案，尤其是在需要高速数据检索的应用场景中。 SuRF数据结构的创新点在于它不仅能有效减少存储空间消耗，还能保持高速的查询性能，从而在不牺牲太多准确性的前提下，提高大规模数据集的处理能力。对于存储系统设计者和数据库管理员而言，SuRF提供了一种新的优化工具，能够帮助他们更好地平衡存储效率和查询速度，以适应不同的应用场景。

资源推荐

资源详情

资源评论

SuRF: Practical Range ery Filtering with Fast Succinct Tries

Huanchen Zhang

Carnegie Mellon University

huanche1@cs.cmu.edu

Hyeontaek Lim

Carnegie Mellon University

hl@cs.cmu.edu

Viktor Leis

TU München

leis@in.tum.de

David G. Andersen

Carnegie Mellon University

dga@cs.cmu.edu

Michael Kaminsky

Intel Labs

michael.e.kaminsky@intel.com

Kimberly Keeton

Hewlett Packard Enterprise

kimberly.keeton@hpe.com

Andrew Pavlo

Carnegie Mellon University

pavlo@cs.cmu.edu

ABSTRACT

We present the Succinct Range Filter (SuRF), a fast and compact data

structure for approximate membership tests. Unlike traditional

Bloom lters, SuRF supports both single-key lookups and common

range queries: open-range queries, closed-range queries, and range

counts. SuRF is based on a new data structure called the Fast Succinct

Trie (FST) that matches the point and range query performance of

state-of-the-art order-preserving indexes, while consuming only

10 bits per trie node. The false positive rates in SuRF for both point

and range queries are tunable to satisfy dierent application needs.

We evaluate SuRF in RocksDB as a replacement for its Bloom lters

to reduce I/O by ltering requests before they access on-disk data

structures. Our experiments on a 100 GB dataset show that replacing

RocksDB’s Bloom lters with SuRFs speeds up open-seek (without

upper-bound) and closed-seek (with upper-bound) queries by up

to 1.5

and 5

with a modest cost on the worst-case (all-missing)

point query throughput due to slightly higher false positive rate.

ACM Reference Format:

Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. Andersen, Michael

Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical Range

Query Filtering with Fast Succinct Tries. In Proceedings of 2018 International

Conference on Management of Data (SIGMOD’18). ACM, New York, NY, USA,

14 pages. https://doi.org/10.1145/3183713.3196931

1 INTRODUCTION

Write-optimized log-structured merge (LSM) trees [

] are popu-

lar low-level storage engines for general-purpose databases that

provide fast writes [

] and ingest-abundant DBMSs such as time-

series databases [

]. One of their main challenges for fast query

processing is that items could reside in immutable les (SSTables)

from all levels [

]. Item retrieval in an LSM tree-based design

may therefore incur multiple expensive disk I/Os [

]. This

challenge calls for in-memory data structures that can help locate

query items. Bloom lters are a good match for this task [

]

because they are small enough to reside in memory, and they have

only “one-sided” errors—if the key is present, then the Bloom lter

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than the

author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or

republish, to post on servers or to redistribute to lists, requires prior specic permission

and/or a fee. Request permissions from permissions@acm.org.

SIGMOD’18, June 10–15, 2018, Houston, TX, USA

2018 Copyright held by the owner/author(s). Publication rights licensed to the

Association for Computing Machinery.

ACM ISBN 978-1-4503-4703-7/18/06... $15.00

https://doi.org/10.1145/3183713.3196931

returns true; if the key is absent, then the lter will likely return

false, but might incur a false positive.

Although Bloom lters are useful for single-key lookups (“Is key

42 in the SSTable?”), they cannot handle range queries (“Are there

keys between 42 and 1000 in the SSTable?”). With only Bloom lters,

an LSM tree-based storage engine must read additional table blocks

from disk for range queries. Alternatively, one could maintain an

auxiliary index, such as a B+Tree, to support such range queries.

The I/O cost of range queries is high enough that LSM tree-based

designs often use prex Bloom lters to optimize certain xed-prex

queries (e.g., “where email starts with com.foo@”) [

], despite

their inexibility for more general range queries. The designers

of RocksDB [

] have expressed a desire to have a more exible

data structure for this purpose [

]. A handful of approximate data

structures, including the prex Bloom lter, exist that accelerate

specic categories of range queries, but none is general purpose.

This paper presents the

Succinct Range Filter

(SuRF), a fast

and compact lter that provides exact-match ltering, range l-

tering, and approximate range counts. Like Bloom lters, SuRF

guarantees one-sided errors for point and range membership tests.

SuRF can trade between false positive rate and memory consump-

tion, and this trade-o is tunable for point and range queries semi-

independently. SuRF is built upon a new space-ecient (succinct)

data structure called the Fast Succinct Trie (FST). It performs compa-

rably to or better than state-of-the-art uncompressed index struc-

tures (e.g., B+tree [

], ART [

]) for both integer and string work-

loads. FST consumes only 10 bits per trie node, which is close to

the information-theoretic lower bound.

The key insight in SuRF is to transform the FST into an approxi-

mate (range) membership lter by removing levels of the trie and

replacing them with some number of sux bits. The number of

such bits (either from the key itself or from a hash of the key—as we

discuss later in the paper) trades space for decreased false positives.

We evaluate SuRF via micro-benchmarks and as a Bloom lter

replacement in RocksDB. Our experiments on a 100 GB time-series

dataset show that replacing the Bloom lters with SuRFs of the same

lter size reduces I/O. This speeds up open-range queries (without

upper-bound) by 1.5

and closed-range queries (with upper-bound)

by up to 5

compared to the original implementation. For point

queries, the worst-case workload is when none of the query keys

exist in the dataset. In this case, RocksDB is up to 40% slower using

SuRFs instead of Bloom lters because they have higher (0.2% vs.

0.1%) false positive rates. One can eliminate this performance gap

by increasing the size of SuRFs by a few bits per key.

This paper makes three primary contributions. First, we describe

in Section 2 our FST data structure whose space consumption is

Research 4: Query Processing

SIGMOD’18, June 10-15, 2018, Houston, TX, USA

323

SIGMOD’18, June 10–15, 2018, Houston, TX, USA Huanchen Zhang et al.

(

)

""!00"!00""!00"""!00""!00""!00!00"!00!00!00!00"!00!00!00!

! " # $ % &

' ( ) + , - . *

LOUDS1

Figure 1: An example ordinal tree encoded using LOUDS

close to the minimum number of bits required by information theory

yet has performance equivalent to uncompressed order-preserving

indexes. Second, in Section 3 we describe how to use the FST to

build SuRF, an approximate membership test that supports both

single-key and range queries. Finally, we replace the Bloom lters

with size-matching SuRFs in RocksDB and show that it improves

range query performance with a modest cost on the worst-case

point query throughput due to a slightly higher false positive rate.

2 FAST SUCCINCT TRIES

The core data structure in SuRF is the FST. It is a space-ecient,

static trie that answers point and range queries. FST is 4–15

faster

than earlier succinct tries using other tree representations [

], achieving performance comparable to or

better than the state-of-the-art pointer-based indexes.

FST’s design is based on the observation that the upper levels

of a trie comprise few nodes but incur many accesses. The lower

levels comprise the majority of nodes, but are relatively “colder”.

We therefore encode the upper levels using a fast bitmap-based

encoding scheme (

LOUDS-Dense

) in which a child node search re-

quires only one array lookup, choosing performance over space. We

encode the lower levels using the space-ecient

LOUDS-Sparse

scheme, so that the overall size of the encoded trie is bounded.

The contribution of FST is two-fold. Although the algorithmic

designs of LOUDS-Dense and LOUDS-Sparse are not new, the com-

bination (we call the hybrid encoding scheme

LOUDS-DS

) within

the same data structure is. As shown in Section 4.1, LOUDS-DS

is key to achieving high performance while remaining succinct.

Second, to the best of our knowledge, FST is the rst succinct trie

that matches the performance of the state-of-the-art pointer-based

index structures (existing succinct trie implementations are usually

at least an order of magnitude slower). This performance improve-

ment allows succinct tries to meet the requirements of a much

wider range of real-world applications.

For the rest of the section, we assume that the trie maps the keys

to xed-length values. We also assume that the trie has a fanout of

256 (i.e., one byte per level).

2.1 Background

A tree representation is “succinct” if the space taken by the repre-

sentation is close

to the information-theoretic lower bound, which

is the minimum number of bits needed to distinguish any object

in a class. A class of size

requires at least

log

bits to encode

There are three ways to dene “close” [

]. Suppose the information-theoretic lower

bound is

bits. A representation that uses

O (1)

o(L)

, and

O (L)

bits is called

implicit, succinct, and compact, respectively. All are considered succinct, in general.

r s

o r

LOUDS-Dense

LOUDS-Sparse

S-Labels:

S-HasChild:

S-LOUDS:

D-Labels:

D-HasChild:

D-IsPrefixKey:

r s t p y i y $ t e p

1 0 0 0 1 0 0

0 0 0

a o

D-Values:

v10

v11

S-Values:

v6 v7

v10

v11

1 0 0 1 0 1 0 1

0 1 0

Keys stored: f, far, fas, fast, fat, s, top, toy, trie, trip, try

Level

Figure 2: LOUDS-DS Encoded Trie

– The

symbol represents the char-

acter whose ASCII number is

0xFF

. It is used to indicate the situation where

a prex string leading to a node is also a valid key.

each object. A trie of degree

is a rooted tree where each node

can have at most

children with unique labels selected from set

{

, . . . , k −

}

. Since there are



kn+1



/kn +

-node tries of de-

gree

, the information-theoretic lower bound is approximately

n(k log

k − (k −

) log

(k −

))

bits [

]. An ordinal tree is a rooted

tree where each node can have an arbitrary number of children in

order. Thus, succinctly encoding ordinal trees is a necessary step

towards succinct tries.

Jacobson [

] pioneered research on succinct tree representa-

tions and introduced the

evel-

rdered

nary

egree

equence

(LOUDS) to encode an ordinal tree. As the name suggests, LOUDS

traverses the nodes in a breadth-rst order and encodes each node’s

degree using the unary code. For example, node 3 in Figure 1 has

three children and is thus encoded as ‘1110’.

Navigating a tree encoded with LOUDS uses the rank & select

primitives. Given a bit vector,

rank

(i)

counts the number of 1’s

up to position

(

rank

(i)

counts 0’s), while

select

(i)

returns the

position of the

-th 1 (

select

(i)

selects 0’s). Modern rank & select

implementations [

] achieve constant time by using

look-up tables (LUTs) to store a sampling of precomputed results

so that they only need to count between the samples.

With proper rank & select support, LOUDS performs tree nav-

igation operations that are sucient to implement the point and

range queries required in SuRF in constant time. We assume that

both node/child numbers and bit positions are zero-based:

• Position of the i-th node = select

(i) + 1

•

Position of the k-th child of the node started at p =

select

(rank

(p + k)) + 1

•

Position of the parent of the node started at p =

select

(rank

(p))

2.2 LOUDS-Dense

LOUDS-Dense encodes each trie node using three bitmaps of size

256 (because the node fanout is 256) and a byte-sequence for the

values as shown in the top half of Figure 2. The encoding follows

level-order (i.e., breadth-rst order).

The rst bitmap (D-Labels) records the branching labels for each

node. Specically, the

-th bit in the bitmap, where 0

≤ i ≤

255,

indicates whether the node has a branch with label

. For example,

the root node in Figure 2 has three outgoing branches labeled

and

. The D-Labels bitmap sets the 102nd (

), 115th (

) and 116th

(t) bits and clears the rest.

Research 4: Query Processing

SIGMOD’18, June 10-15, 2018, Houston, TX, USA

324

SuRF: Practical Range ery Filtering with Fast Succinct Tries SIGMOD’18, June 10–15, 2018, Houston, TX, USA

The second bitmap (D-HasChild) indicates whether a branch

points to a sub-trie or terminates (i.e., points to the value or the

branch does not exist). Taking the root node in Figure 2 as an

example, the

and the

branches continue with sub-tries while

the

branch terminates with a value. In this case, the D-HasChild

bitmap only sets the 102nd (f) and 116th (t) bits for the node.

The third bitmap (D-IsPrexKey) includes only one bit per node.

The bit indicates whether the prex that leads to the node is also a

valid key. For example, in Figure 2, the rst node at level 1 has

its prex. Meanwhile,

‘f’

is also a key stored in the trie. To denote

this situation, the D-IsPrexKey bit for this child node must be set.

The nal byte-sequence (D-Values) stores the xed-length values

(e.g., pointers) mapped by the keys. The values are concatenated in

level order: same as the three bitmaps.

Tree navigation uses array lookups and rank & select operations.

We denote

rank

select

over bit sequence bs on position pos to be

rank

select

(bs, pos). Let pos be the current bit position in D-Labels.

To traverse down the trie, given pos where D-HasChild[pos] = 1,

D-ChildNodePos

(pos) = 256

×rank

(D-HasChild, pos) computes

the bit position of the rst child node. To move up the trie,

D-

ParentNodePos

(pos) = 256

×se lect

(D-HasChild,

⌊

pos/256

⌋

) com-

putes the bit position of the parent node. To access values, given

pos where D-HasChild[pos] = 0,

D-ValuePos

(pos) =

rank

(D-Labels,

pos) -

rank

(D-HasChild, pos) +

rank

(D-IsPrexKey,

⌊

pos/256

⌋

)-1

gives the lookup position.

2.3 LOUDS-Sparse

As shown in the lower half of Figure 2, LOUDS-Sparse encodes a

trie node using four byte or bit-sequences. The encoded nodes are

then concatenated in level-order.

The rst byte-sequence, S-Labels, records all the branching labels

for each trie node. As an example, the rst non-value node at level 2

in Figure 2 has three branches. S-Labels includes their labels

, and

in order. We denote the case where the prex leading to a node is

also a valid key using the special byte

0xFF

at the beginning of the

node (this case is handled by D-IsPrexKey in LOUDS-Dense). For

example, in Figure 2, the rst non-value node at level 3 has

‘fas’

its incoming prex. Since

‘fas’

itself is also a stored key, the node

adds

0xFF

to S-Labels as the rst byte. Because the special byte

always appears at the beginning of a node, it can be distinguished

from the real 0xFF label.

The second bit-sequence (S-HasChild) includes one bit for each

byte in S-Labels to indicate whether a child branch continues (i.e.,

points to a sub-trie) or terminates (i.e., points to a value). Taking

the rightmost node at level 2 in Figure 2 as an example, because

the branch labeled

points to a sub-trie, the corresponding bit in

S-HasChild is set. The branch labeled

, on the other hand, points

to a value. Its S-HasChild bit is cleared.

The third bit-sequence (S-LOUDS) also includes one bit for each

byte in S-Labels. S-LOUDS denotes node boundaries: if a label is the

rst in a node, its S-LOUDS bit is set. Otherwise, the bit is cleared.

For example, in Figure 2, the rst non-value node at level 2 has

three branches and is encoded as 100 in the S-LOUDS sequence.

The nal byte-sequence (S-Values) is organized the same way as

D-Values in LOUDS-Dense.

Tree navigation on LOUDS-Sparse is as follows: to move

down the trie, S-ChildNodePos(pos) = select

(S-LOUDS, rank

(S-

HasChild, pos) + 1); to move up,

S-ParentNodePos

(pos) =

select

(S-

HasChild,

rank

(S-LOUDS, pos) - 1); to access a value,

S-ValuePos

(pos) = pos - rank

(S-HasChild, pos) - 1.

2.4 LOUDS-DS and Operations

LOUDS-DS is a hybrid trie in which the upper levels are encoded

with LOUDS-Dense and the lower levels with LOUDS-Sparse. The

dividing point between the upper and lower levels is tunable to

trade performance and space. FST keeps the number of upper levels

small in favor of the space eciency provided by LOUDS-Sparse.

We maintain a size ratio

between LOUDS-Sparse and LOUDS-

Dense to determine the dividing point among levels. Suppose the

trie has

levels. Let

LOUDS-Dense-Size(l)

, 0

≤ l ≤ H

denote the

size of LOUDS-Dense-encoded levels up to

(non-inclusive). Let

LOUDS-Sparse-Size(l)

, represent the size of LOUDS-Sparse encoded

levels from

(inclusive) to

. The cuto level is dened as the largest

such that

LOUDS-Dense-Size(l) × R ≤ LOUDS-Sparse-Size(l )

. Re-

ducing

leads to more levels, favoring performance over space. We

use R=64 as the default.

LOUDS-DS supports three basic operations eciently:

• ExactKeySearch

(key): Return the value of key if key exists (or

NULL otherwise).

• LowerBound

(key): Return an iterator pointing to the key-value

pair

(k, v)

where

is the smallest in lexicographical order satis-

fying k ≥ key.

• MoveToNext(iter): Move the iterator to the next key-value.

A point query on LOUDS-DS works by rst searching the

LOUDS-Dense levels. If the search does not terminate, it continues

into the LOUDS-Sparse levels. The high-level searching steps at

each level are similar regardless of the encoding mechanism: First,

search the current node’s range in the label sequence for the tar-

get key byte. If the key byte does not exist, terminate and return

NULL. Otherwise, check the corresponding bit in the HasChild bit-

sequence. If the bit is

(i.e., the branch points to a child node),

compute the child node’s starting position in the label sequence

and continue to the next level. Otherwise, return the corresponding

value in the value sequence. We precompute two aggregate values

based on the LOUDS-Dense levels: the node count and the number

of HasChild bits set. Using these two values, LOUDS-Sparse can

operate as if the entire trie is encoded with LOUDS-Sparse.

Range queries use a high-level algorithm similar to the point

query implementation. When performing LowerBound, instead of

doing an exact search in the label sequence, the algorithm searches

for the smallest label ≥ the target label. When moving to the next

key, the cursor starts at the current leaf label position and moves

forward. If another valid label

is found within the node, the algo-

rithm nds the left-most leaf key in the subtree rooted at

. If the

cursor hits node boundary instead, the algorithm moves the cursor

up to the corresponding position in the parent node.

We include per-level cursors in the iterator to minimize the

relatively expensive “move-to-parent” and “move-to-child” calls,

which require rank & select operations. These cursors record a trace

from root to leaf (i.e., the per-level positions in the label sequence)

for the current key. Because of the level-order layout of LOUDS-DS,

Research 4: Query Processing

SIGMOD’18, June 10-15, 2018, Houston, TX, USA

325

剩余13页未读，继续阅读

评论收藏

内容反馈

隔壁Uncle_Wang

2019-04-22

很不错的资源！

qq_28488285

粉丝: 4
资源: 22

SuRF: Practical Range Query Filtering with Fast Succinct Tries原文

最新资源

SuRF: Practical Range Query Filtering with Fast Succinct Tries原文

SURF算法原文 请拜读

go-succinct-data-structure-trie：Trie的简洁数据结构，用Go编写

surf算法的原文翻译

SURF算法原论文中文翻译

SURF算法原文翻译

一篇基于SURF翻译

SURF算法学习

SURF: Speeded Up Robust Features

SURF: Detecting and Measuring Search Poisoning

surf：用于异步Rust的快速友好的HTTP客户端框架

exwm-surf:exwm下的Surf接口

surf:冲浪和冲浪-PI

points2surf:从点云学习隐式曲面（ECCV 2020）

SIFT和SURF、FAST等几十种特征算法源程序

repository.surf::person_surfing:

SURF:SURF Project Trinity College都柏林

Surf：简单而强大PHP部署工具

surf:Go中的状态化程序化Web浏览

matlab代码影响-SURF:冲浪

surf：使用VS Code浏览GitHub代码。 （带有CLI，chrome扩展名，也适用于Gitlab）

Surf:我们项目的冲浪部署

surf:mysql,linux shell学习进阶

SURF算法及源码详解

Mastering OpenCV with Practical Computer Vision Projects 电子书及源代码

github.surf：使用VS Code浏览GitHub代码

BB-surf：BB冲浪地图

sift和surf特征原文翻译

最新资源

SURF算法原文请拜读

surf：使用VS Code浏览GitHub代码。（带有CLI，chrome扩展名，也适用于Gitlab）