For some time, the networking community has assumed that it is impossible to do IP routing
lookups in software fast enough to support gigabit speeds. IP routing lookups must find the …

In representing a subset of a large finite set, or an index for text search, one is faced with the
need for both time and space efficiency. In this paper, we look at some approaches that have …

The growth of the Internet and its acceptance has sparkled keen interest in the research
community in respect to many apparent scaling problems for a large infrastructure based on …

A static dictionary is a data structure storing subsets of a finite universe U, answering
membership queries. We show that on a unit cost RAM with word size Θ(\log|U|), a static …

We consider the implementation of abstract data types for the static objects: binary tree,
rooted ordered tree and balanced parenthesis expression. Our representations use an …

This paper deals with the problem of storing a subset of elements from the bounded
universe M={0,...,M-1\} so that membership queries can be performed efficiently. In …

We study the static membership problem: Given a set S of at most n keys drawn from a
universe of size m, store it so that queries of the form" Is x in S?" can be answered quickly …

Membership (membership query/membership testing) is a fundamental problem across
databases, networks and security. However, previous research has primarily focused on …

A static dictionary is a data structure for storing subsets of a finite universe U, so that
membership queries can be answered efficiently. We study this problem in a unit cost RAM …

We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but
no multiplication, there is a transdichotomous solution to the static dictionary problem using …