Indexable dictionaries, supporting rank and select queries, are used as building blocks for many algorithms. For a universe U = {0, ..., |U| - 1} and an ordered set S = {s0, ..., sn-1} ⊆ U, an indexable dictionary supports rank and select queries in addition to membership queries, Select(j) query is used to get the j'th ranked element, and Rank(x) is used to retrieve the rank of x among all elements in S. In this work, we give two time-linear, one-pass practical constructions of static succinct indexable dictionaries, both are deterministic in query time, but they differ by construction method and Rank(x) query time. The first supports Rank and Select queries in constant time and has expected linear construction time. The second supports Select queries in constant time, and Rank(x) queries in O(log log |U|/n) time, has worst-case linear construction time, and uses only o(n) additional bits during construction. The latter one is fully indexable dictionary supporting Rank(x) queries on arbitrary x. These indexable dictionaries can be used where construction bounds matter, as in a dynamic algorithm that uses them as a building block, we exemplify this by showing how to utilize them to improve the query time of a dynamic dictionary matching algorithm.

In this paper we introduce a general framework that exponentially improves the space, the degree of independence, and the time needed by min-wise based algorithms. The authors, in SODA 2011, we introduced an exponential time improvement for min-wise based algorithms by defining and constructing an almost k-min-wise independent family of hash functions. Here we develop an alternative approach that achieves both exponential time and exponential space improvement. The new approach relaxes the need for approximately min-wise hash functions, hence gets around the Omega(log(1/epsilon)) independence lower bound in [Patrascu 2010]. This is done by defining and constructing a d-k-min-wise independent family of hash functions. Surprisingly, for most cases only 8-wise independence is needed for the additional improvement. Moreover, as the degree of independence is a small constant, our function can be implemented efficiently. Informally, under this definition, all subsets of size d of any fixed set X have an equal probability to have hash values among the minimal k values in X, where the probability is over the random choice of hash function from the family. This property measures the randomness of the family, as choosing a truly random function, obviously, satisfies the definition for d=k=|X|. We define and give an efficient time and space construction of approximately d-k-min-wise independent family of hash functions for the case where d=2, as this is sufficient for the additional exponential improvement. We discuss how this construction can be used to improve many min-wise based algorithms. To our knowledge such definitions, for hash functions, were never studied and no construction was given before. As an example we show how to apply it for similarity and rarity estimation over data streams. Other min-wise based algorithms, can be adjusted in the same way.

In this paper we extend the notion of min-wise independent family of hash functions by defining a k-min-wise independent family of hash functions. Informally under this definition, all subsets of size k of any fixed set X have an equal chance to have the minimal hash values among all the elements in X, when the probability is over the random choice of hash function from the family. This property measures the randomness of the family as choosing a truly random function, obviously satisfies the definition for k = |X|. We define and give an efficient time and space construction of approximately k-min-wise independent family of hash functions by extending Indyk's construction of approximately min-wise independent [1]. The number of words needed to represent each function is , which is only suboptimal by a factor of , where ε ∊ (0, 1) is the desired error bound. This construction is the first applicable for sampling bottom-k sketches [2, 3] out of the universe. In addition, we introduce a general and novel technique that utilizes our construction, and can be used to improve many min-wise based algorithms, such as [4, 5, 6, 7, 3, 2, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]. As an example we show how to apply it for similarity estimation over data streams, and reduce exponentially the run time of the current known result [5]. In addition, we also discuss improvements of known algorithms for estimating rarity and entropy of random walk over graphs (from SODA07 [20]).