We consider the problem of querying the existence of hyperedges in hypergraphs. More formally, given a hypergraph, we need to answer queries of the form "does the following set of vertices form a hyperedge in the given hypergraph?". Our aim is to set up data structures based on hashing to answer these queries as fast as possible. We propose an adaptation of a well-known perfect hashing approach for the problem at hand. We analyze the space and run time complexity of the proposed approach, and experimentally compare it with the state-of-the-art hashing-based solutions. Experiments demonstrate the efficiency of the proposed approach with respect to the state-of-the-art. name d size in each dimension n

Introduction

Let H = (V, E) be a hypergraph, where V is the set of vertices, and E is the set of hyperedges. Our aim is to answer queries of the form "is h ⊆ V a member of E?". We are interested in data structures and algorithms enabling constant time response per query in the worst-case with small memory requirements and construction/preprocessing time. We focus on d-uniform, d-partite hypergraphs, where the vertex set is a union of d disjoint parts V = d-1 i=0 V (i) , and each hyperedge has exactly one vertex from each part V (i) .

We are motivated by a tensor decomposition method proposed by Kolda and Hong [START_REF] Kolda | Stochastic gradients for large-scale tensor decomposition[END_REF]. This is a stochastic, iterative method targeting efficient decomposition of both dense and sparse tensors, or multidimensional arrays. Our focus is on the sparse case. For this case, Kolda and Hong propose a sampling approach, called stratified sampling, in which the nonzeros and the zeros of a sparse tensor are sampled separately at each iteration for accelerating the convergence of the decomposition method. The stratified sampling approach works as follows. The nonzeros of the input tensor are sampled uniformly at random. For sampling zeros in a d-dimensional tensor, a d-tuple of indices is generated randomly and tested to see if the input tensor contains a nonzero at that position. If the position is nonzero, the d-tuple is rejected and a new one is generated, until a desired number of indices corresponding to zeros of the input tensor are sampled. Sampling nonzeros is a straightforward task, as the nonzeros of a tensor are available, usually, in an array. To sample from the zeros of a tensor, Kolda and Hong propose a method based on sorting the nonzeros and then using binary search during query time to see if the tuple exists or not. They report that this approach is more efficient than other alternatives based on hashing in their tests-which are carried out in Matlab. Since the above implementation of sampling for zeros can be time consuming, Kolda and Hong propose and investigate other sampling approaches for their stochastic tensor decomposition method. Among the alternatives, the stratified sampling approach is demonstrated to be more useful numerically. That is why we are motivated to increase efficiency of the stratified sampling approach by developing data structures and algorithms for quickly detecting whether a given position in a tensor is zero or not.

A data structure that answers hyperedge queries can be used as a building block in a more general setting. For example, one can compute the number of edges or hyperedges contained in a given set of vertices in time polynomial in the size of the given vertex set, rather than in time proportional to the sum of the vertex degrees. For vertex sets of small cardinality with high vertex degrees, this becomes tangible.

Let T be a d-dimensional tensor of size s 0 × • • • × s d-1 , where s i is the size of the corresponding dimension. An entry in the tensor is indexed by a d-tuple, e.g., T [i 0 , . . . , i d-1 ]. One can associate a d-uniform, d-partite hypergraph H = (V, E) with a tensor T as follows. In H, the vertex set is V = d-1 i=0 V (i) where

V (i) = {v (i) 0 , . . . , v (i)
s i -1 }. Furthermore, there is a hyperedge h ∈ E of the form h = [v (0) i 0 , . . . , v (d-1) i d-1 ] for each nonzero T [i 0 , . . . , i d-1 ]. From this correspondence, we see that the problem of testing if a given position in a tensor is zero can be cast as the problem of testing the existence of a hyperedge in the associated d-uniform, d-partite hypergraph.

We design and implement a perfect hashing based approach by building on the celebrated method by Fredman, Komlós, and Szemerédi [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF] (FKS method). The FKS method stores a given set S of n elements with O(n) space in such a way that it takes constant time to answer a membership query in the worst-case. The FKS method thus promises an asymptotically optimal solution to our problem of answering hyperedge queries. After reviewing the original FKS method in Section 2, we discuss the necessary changes to adapt it to answer hyperedge queries in Section 3. We first list some theoretical properties of the proposed method that are inherited from FKS in Section 3.1, for which the proofs are given in Appendix. We then present an approach to improve space utilization in Section 3.2; while our approach can also be used in the original FKS method, its effects are much more tangible in our use case. We note that since each element in our case is of size d, a lookup takes O(d) time-which is not constant if d is part of the input. Since the queries are of size d, a query response time of O(d) is optimal.

We restrict our attention to d-uniform, d-partite hypergraphs both in describing the proposed method and experimenting with it. This is so, as it covers the tensor decomposition application. Furthermore, as we discuss in Section 3.3.1, this is without loss of generality-the method is applicable to general hypergraphs.

To the best of our knowledge, the hyperedge query problem is first addressed by Kolda and Hong. The underlying problem is that of static hashing and hence existing perfect hashing methods can be used. Minimal perfect hash functions (MPHFs) are static data structures that map a given set with n elements to {0, . . . , n -1}. By using MPHFs, one can store the ids of hyperedges in a space of size n and answer queries in constant time in the worst case. There are a number of publicly available MPHF implementations [START_REF] Esposito | RecSplit: Minimal perfect hashing via recursive splitting[END_REF][START_REF] Genuzio | Fast scalable construction of minimal perfect hash functions[END_REF][START_REF] Limasset | Fast and Scalable Minimal Perfect Hashing for Massive Key Sets[END_REF][START_REF] Müller | Retrieval and perfect hashing using fingerprinting[END_REF][START_REF] Pibiri | PTHash: Revisiting FCH minimal perfect hashing[END_REF]. While these are highly efficient with practical implementations, the hyperedge query problem should be addressed on its own. This is so, as the d-dimensional structure of the hyperedges in our target application can enable special hashing methods, and converting the tensor's data into other structures for hashing affects the run time. One can also use approximate set membership filters based on Bloom filter and its variants [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF][START_REF] Putze | Cache-, hash-, and space-efficient bloom filters[END_REF][START_REF] Lang | Performance-optimal filtering: Bloom overtakes cuckoo at high throughput[END_REF][START_REF] Dillinger | Fast succinct retrieval and approximate membership using ribbon[END_REF][START_REF] Graf | Binary fuse filters: Fast and smaller than xor filters[END_REF]. Approximate set membership filters answer queries in such a way that the "no" answers are always correct while the "yes" answers could be incorrect (i.e., false positives are possible but false negatives are not). In order to use such filters for answering hyperedge queries or in other computations where exact answers are required, one has to double-check all the "yes" answer using an exact method. Therefore, a second exact hashing method needs to be built alongside the chosen approximate set membership method. Hence, such filters promise fast query response with an increased construction time and memory overhead.

We compare our approach experimentally (Section 4) with a number of methods that use the current state-of-the-art minimal and non-minimal perfect hashing methods, and a recent approximate membership filter. The most efficient version of the proposed method consistently outperforms all other methods considered. We note that there are recent studies which use random hypergraph models to build variants of Cuckoo hashing methods [START_REF] Botelho | Practical perfect hashing in nearly optimal space[END_REF][START_REF] Dietzfelbinger | Dense peelable random uniform hypergraphs[END_REF][START_REF] Genuzio | Fast scalable construction of minimal perfect hash functions[END_REF][START_REF] Pagh | Cuckoo hashing[END_REF][START_REF] Walzer | Random hypergraphs for hashing-based data structures[END_REF][START_REF] Walzer | Peeling close to the orientability threshold-spatial coupling in hashing-based data structures[END_REF]. Our work does not build random hypergraph models for designing hashing schemes; we seek static hashing methods for querying the existence of hyperedges in a given hypergraph.

Preliminaries and background

For an event E, we use Pr(E) to denote the probability that E holds. For a random variable X, we use E(X) to denote the expectation of X. Markov's inequality states that for a random variable X that assumes only nonnegative values with expectation E(X), the probability that X ≥ c for a positive c is no larger than

E(X) c , that is, Pr(X ≥ c) ≤ E(X)
c . Let, U = {0, . . . , u -1} be the universe. Recall that a family of hash functions H from U to {0, . . . , n -1} is universal if for any x = y ∈ U , the probability that their key values are equal is bounded by 1/n [START_REF] Carter | Universal classes of hash functions[END_REF]. In other words, Pr(h(x) = h(y)) ≤ 1/n for a uniform random function h ∈ H. This definition can also be found in more recent treatments [START_REF] Sanders | Sequential and parallel algorithms and data structures: The basic toolbox[END_REF]Ch. 4].

We now give a brief summary of the hashing method by Fredman et al. [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF] for static data sets. This method represents a given set of items using linear space and entertains constant time existence queries. We do not give the proofs, as some of our proofs for the proposed method in Section 3 follow closely that of Fredman et al. adapted to our case.

Let U = {0, . . . , u -1} be the universe and S ⊆ U with |S| = n be the set to be represented. The FKS method [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF] relies on a two-level approach for storing the set S. It needs a prime number p greater than u -1 and defines an extended universe U = {0, . . . , p-1}. First, it chooses an element k ∈ U uniformly at random, and defines the first level hash function h k : U → {0, . . . , n -1} as h k (x) = (kx mod p) mod n. It then assigns each element x of S to the bucket B i where i = h k (x). As the outcome of the hashing function ranges from 0 to n -1, there are n buckets. Then, for a bucket B i containing b i > 0 elements, a storage space of size b 2 i is allocated, a number k (i) ∈ U is chosen at random, and the second level hash function

h k (i) (x) = (k (i) x mod p) mod b 2 i is defined for items in B i . A first requirement is that i b 2
i should be O(n) so that the method uses linear space. The second requirement is that each k (i) should be an injection for the respective bucket. In other words, two different elements in B i should have different key values computed with the function h k (i) (•). If the hash functions are from a universal family, then both of these requirements can be met with high probability.

The FKS method constructs a representation of the given set by finding the values of k and k (i) respecting the constraints. These values are found with random sampling and trials. That is, the FKS method randomly chooses a k ∈ U and computes the size of the buckets when the first level hash function uses k. If the summation i b 2 i is smaller than 3n, then k is accepted, and the method proceeds to the second level. Otherwise, another k is randomly sampled and tried. A similar strategy is adopted for the hash functions in the second level. For the bucket B i , a random k (i) ∈ U is chosen, and the mapping defined by (k (i) x mod p) mod b 2 i is tested to see if it is an injection for the set of elements assigned to B i . If so, that k (i) is accepted, if not, another one is sampled and tried. Fredman et al. note that with the bound i b 2 i < 3n, and the injection requirement of b 2 i space per bucket, one may end up testing many k and k (i) . In order to have a construction time of O(n) in expectation, they suggest testing with i b 2 i < 5n and using 2b 2 i space for each bucket B i . Under these relaxations, at least one half of the potential k and k (i) values guarantee that the two requirements are met. The bounds 3n and 5n given in the original paper can be shown to be 2n and 4n, when a universal hash function family is used.

In the FKS method, the membership query for an element q ∈ U can be answered in constant time by following the construction of the data structure. First, the bucket containing q is found by computing i = (kx mod p) mod n. If the bucket B i is empty, then q is not in S. If B i is not empty, the value = (k (i) x mod p) mod 2b 2 i is computed, the element at location is compared with q, and the result of the comparison is returned as the answer to the query. The comparison between q and the element stored at the location is required as more than one element from U can map to -whereas this can happen for only one element from S.

A lean variant of FKS

We discuss our adaptation of the FKS method for the hyperedge queries. We first discuss a family of hash functions for the two levels and show that the two requirements of having a total space of O(n) and an injection for each bucket are met. We then propose two techniques for reducing the space requirement of the proposed method.

3.1. The hash function and its properties. In a d-partite d-uniform hypergraph H = (V, E), the hyperedge set E is a set of d-tuples, which we will represent for hyperedge queries. Let n denote the number of hyperedges, and p be a prime number larger than n. Let U be the universe of all d-tuples of the form [x 0 , . . . , x d-1 ] where x i is between 0 and p -1; in other words U = {0, . . . , p -1} d and E ⊆ U . A potential approach to adapt the FKS for hyperedge queries is to convert d-tuples to unique integers by linearizing them. In this approach, in the case d = 3 for example, [x 0 , x 1 , x 2 ] can be converted to x 0 + s 0 × (x 1 + s 1 × x 2 ), where s i corresponds to the size of dimension i; and a longer formula for higher d can be generated similarly. Afterwards, the FKS method can be used without any modification. Such an approach has limited applicability-the numbers get quickly too big for sparse tensors, as also noted by Kolda and Hong [START_REF] Kolda | Stochastic gradients for large-scale tensor decomposition[END_REF]. That is why we use d-tuples in defining the hash functions. Furthermore, since storing d-tuples in the buckets makes the storage requirement depend on d, we store the ids of the hyperedges in the buckets which are taken in the given order.

Let x, y be two elements of the universe U . We use x T y = d-1 i=0 x i y i to denote the inner product of the vectors corresponding to x and y. In the proposed approach, as in the FKS method, a k ∈ U is chosen for the first level, and the hash function h : U → {0, . . . , n -1} is defined as h(x) = (k T x mod p) mod n. Then, each hyperedge x ∈ E is assigned to the bucket B i where i = h(x). We again use b i to refer to the number of hyperedges from E that are mapped to B i . Lemma 3.1 below ensures that the linear space requirement can be met for any given set of hyperedges. We give the proof in Appendix A for completeness, where we also explain why the bound is 4n, instead of 3n as in the original FKS method. Lemma 3.1. For a given set E ⊆ U of n hyperedges, there is a k ∈ U such that when (k T x mod p) mod n is used as the first level hash function, we have n-1 i=0 b 2 i < 4n. Lemma 3.1 ensures the existence of a d-tuple resulting in a linear space, but does not specify how frequent such d-tuples are in the universe. The following corollary, whose proof is in the appendix, expresses a relaxation of the requirement on k as done by Fredman et al. to yield many candidates.

Corollary 3.2. Let E ⊆ U be a given set of n hyperedges. Then, for at least half of the potential k ∈ U , when k is used in the first level hash function, we have n-1 i=0 b 2 i < 7n. Thanks to Corollary 3.2, one needs a constant number of trials, in expectation, to find a k respecting the space requirement of n-1 i=0 b 2 i < 7n. We next show that for each bucket B i , if we use a space of size b 2 i , we can map each element to a unique position with a function of the form (k (i) T x mod p) mod b 2 i . The proof is given in the appendix for completeness.

Lemma 3.3. For each bucket B i with b i > 0 elements, there is a k ∈ U such that the function (k T x mod p) mod b 2 i is an injection for p b 2 i . While the bound i b 2
i from Lemma 3.1 does not guarantee p b 2 i , this must hold in practice for the original FKS and the proposed method to be efficient. A proposition below (Proposition 3.5) shows that there are many nonempty buckets, suggesting that a large b i is unlikely for a random k.

As done by Fredman et al., one can relax the storage requirement of each bucket to have a constant number of trials in expectation to find a k defining an injection. This is shown in the following corollary, whose proof is in the appendix.

Corollary 3.4. Let B i be a bucket with b i > 0 elements. For at least half of the d-tuples k ∈ U , it holds that the function (k T x mod p) mod 2b 2 i defines an injection for the elements of B i for p b 2 i . 3.2. Reducing the space requirements. While the previous lemmas show that we can use the FKS method with d-tuples k and k (i) for each bucket B i , there is a catch. For a bucket B i , we need a space of size d to store k (i) . This results in a space requirement of O(nd) over all buckets. The space requirement will thus be large when the input tensor has a large number n of nonzeros or dimensions d.

An obvious way to reduce the space required to store the k (i) s is to avoid creating such a d-tuple for buckets with at most one element (those buckets B i with b i = 0 or b i = 1). As we discuss in Proposition 3.5, one will still need, in expectation over all sets F ⊆ U of n hyperedges, a total of Ω(nd) space. Proposition 3.5. For a random k = [0, . . . , 0] and a random set F with n hyperedges, the first level hash function using k creates at least n 1 -e -1+2/p nonempty buckets in expectation, where e is the base of natural logarithm.

< l a t e x i t s h a 1 _ b a s e 6 4 = " U b H e m A I Z b 6 v B p v O h Z d d Y m C q 0 V J Q = " > A A A F q n i c p V T L b t N A F L 0 N G E p 5 p W X J J i J C Y l F F d o G G F Q p i A y s C I m 1 R G 1 V + j F M r f s k z h l R R f o U t / B J / A H / B u T d O G 9 I m v M a y f e f M P f d x Z m w v j y N t b P v b W u 3 K V e v a 9 f U b G z d v 3 b 5 z t 7 6 5 t a e z s v B V z 8 / i r D j w X K 3 i K F U 9 E 5 l Y H e S F c h M v V v v e 8 C W v 7 3 9 U h Y 6 y 9 L 0 5 z V U / c Q d p F E a + a w A d 1 7 e O j B o Z H Y 7 D o X 4 T h l q Z y X G 9 a b d s G Y 2 L h l M Z z c 7 z D v H o Z p u 1 D h 1 R Q B n 5 V F J C i l I y s G N y S e M 6 J I d s y o H 1 a Q y s g B X J u q I J b Y B b w k v B w w U 6 x H O A 2 W G F p p h z T C 1 s H 1 l i 3 A W Y D X o I T g a / A j Z n a 8 h 6 K Z E Z X R Z 7 L D G 5 t l O 8 v S p W A t T Q C d D f 8 W a e f 8 r j X g y F 9 E x 6 i N B T L g h 3 5 1 d R S l G F K 2 / M d W U Q I Q f G d o D 1 A r Y v z J n O D e F o 6 Z 2 1 d W X 9 u 3 g y y n O / 8 i 3 p R 1 V l A C S U S t S c p l N 9 P X B i e E 8 w L 1 C / J 5 Z N L d z b i M j W D n q Z 2 b v U r v Z x W d R A K h u K K l q q j x G X K + S 6 L s v j n E V v 0 9 O 5 r E 8 k 0 6 r 9 4 c i c N Z I 9 S V a e s B S e X E F Q n c x F b i S 7 w 3 z u 6 J P 0 l M h + M 2 c M 3 M d 7 I F r x K e 8 L x v 2 N 5 A v 4 G w W a 4 E / + Q U e O E V y i Y R v 7 c q 7 b 4 z P b g T 3 T c F l X L 0 S 3 Z b 0 s n h H 2 m 3 0 D H u o e g z + p r l V Z u v + Z p X u e B f 8 s Z / E P d d H Y 2 2 k 5 u y 3 7 L X 5 e r 2 k 6 1 u k + P a B H U K V N H X q F m D 1 k H t F n + k J f r W 3 r n f X B O p y 6 1 t Y q z j 3 6 Z V j B T w e s H 4 g = < / l a t e x i t > fksO↵set < l a t e x i t s h a 1 _ b a s e 6 4 = " J X K D D 8 s Q t 5 T c i + N D Y T b w r Z + B R 3 c = " > A A A F q 3 i c p V T L b t N A F L 0 N G E q h k N I l G 4 s I i Q V E d o G G Z V A 3 s E t V 0 l Y 0 U f F j E q z 4 h T 2 G R l E + g z V b + C T + A P 6 h C 8 6 9 c d q Q N u F l y / a d M / f c x 5 n x u G k Y 5 N q y v q 1 U r l w 1 r l 1 f v b F 2 8 9 b 6 7 T v V j b v 7 e V J k n m p 7 S Z h k h 6 6 T q z C I V V s H O l S H a a a c y A 3 V g T v Y 4 f m D D y r L g y R + r Y e p 6 k Z O P w 5 6 g e d o Q M f V z Y 5 W J z r v j X q D f E 8 n m d N X 4 + N q z a p b c p k X D b s 0 a s 2 d 0 / d v P 4 X r r W S j 0 q Q O + Z S Q R w V F p C g m D T s k h 3 L c R 2 S T R S m w L o 2 A Z b A C m V c 0 p j V w C 3 g p e D h A B 3 j 3 M T o q 0 R h j j p k L 2 0 O W E E 8 G p k k P w E n g l 8 H m b K b M F x K Z 0 U W x R x K T a x v i 6 5 a x I q C a 3 g H 9 H W / q + a c 8 7 k V T j 5 5 L D w F 6 S g X h 7 r w y S i G q c O X m T F c a E V J g b P u Y z 2 B 7 w p z q b A o n l 9 5 Z W 0 f m v 4 s n o z z 2 S t + C f p R V + k B 6 U o m a 0 X S i r w t O C O 8 x x h n q d 8 W y q I 7 n E S K y t Y V e p v Y 2 N c p 1 X B T V l 8 o G o k o u 1 Y e I y x V y X Z f l s c + i N + j Z T N a n k m n Z + n B k z h r I m k R L d 1 g M T 6 7 A L 3 f m P D e Q 1 W E + d / R R e o p k v Z k z A u 7 h 2 x e t e J d 3 B e P + T u Q P + B s F a u C P / 0 F H j u F f o m E D 6 3 K u 2 5 M z 2 4 Y 9 1 X B R V y 9 E t 0 W 9 z O 8 R 9 p v + A y 7 q H o E / L u 9 l W V r / m a V 1 n g V n l j 1 / Q l 0 0 9 r f q 9 n b d 2 s X h 9 Y o m 1 y r d o / v 0 E K o 0 q E k v E b O N z E P 6 T F / o q / H Y 2 D P e G J 2 J a 2 W l 5 G z S L 5 e h f g K o B y K g < / l a t e x i t > fksStorage id B 0 B 1 B n-1 id/k id 0 d-1 2 2 2 -1 × id0 id1 id id1 id0 id2 1 r k 1 k 0 k r k 0 2 3 2 -1 × 0 Figure 1.
In the proposed variant of FKS, the contents of a bucket B i depend on the number b i of hyperedges assigned to it.

If b i is 0, nothing is stored for B i . If b i is 1, the id of the hyperedge mapping to i is stored. If b i is greater than 1, then the index of a suitable d-tuple from k 0 to k r in K is stored, along with a space of size 2b 2 i to hold the ids of b i hyperedges assigned to B i .
The proof of this proposition can be found in the appendix.

In order to further reduce the memory requirements and obtain a lean variant of FKS for hyperedge queries, we propose to share the second level hash functions among the buckets. This can be achieved by storing a set K of d-tuples and keeping a reference to one suitable element of K for each bucket. The proposed variant of FKS is explained in Figure 1. We keep the first level the same as in the original FKS method and obtain a k in expected linear time that results in a suitable bound on the memory utilization as highlighted in Corollary 3.2. On the second level, rather than keeping a d-tuple per bucket we keep a set K of d-tuples with cardinality |K| much smaller than n. The set K is such that for each bucket B i with b i > 1, there is at least one d-tuple in K defining an injection for the hyperedges in B i , and B i keeps a reference id to this tuple. The data structure fksStorage holds necessary space for all buckets, one after another. The data structure fksOffset holds the start of the storage space for each bucket. For an empty bucket B i , nothing is stored and fksOffset[i] is nil; for a bucket B i with one hyperedge, only the id of that hyperedge is stored in fksStorage and fksOffset[i] points to that position in fksStorage. For a bucket B i with b i > 1 elements, fksOffset[i] points to the start of B i in fksStorage. The space associated with B i is of size 2b 2 i + 1 in which the id of a d-tuple in K is stored along with the ids of b i hyperedges at suitable places.

We now discuss how to create the set K of tuples and bound the number of d-tuples we need to store in K. As the buckets independently need d-tuples for hashing, a random sequence of d-tuples generated for a bucket is also a random sequence of d-tuples for another one. With this observation in mind let us fix a random sequence of the d-tuples in the universe U . When we need a random d-tuple for a bucket, we try the d-tuples in the fixed random order, until we find one. We then include those d-tuples which were used by at least one bucket in K. Theorem 3.6 below shows that the number of d-tuples in K is O(log 2 n) in the expectation.

Theorem 3.6. The size of K generated with the above technique will be smaller than 1 + log 2 n in expectation for a given set E of n hyperedges.

Proof. For each bucket, we know from Corollary 3.4 that at least half of the tuples from the universe U defines an injection. For a given bucket B i , let X i be a random variable counting the number of trials we did to find a suitable k (i) , where at the jth trial we consider the jth tuple from the fixed random sequence. Then, Pr(X i = t) ≤ 1 2 t for all t and i = 0, . . . , n -1 .

Let X i,t be a random variable taking on value 1 if X i = t, and 0 otherwise. Then, the expected number of buckets for which we did t trials to find an injection is

E n-1 i=0 X i,t ≤ n 2 t ,
by the linearity of expectation. For a given t, the probability that there is a bucket for which we have found a second level hash at the trial t is

Pr(X i = t for some i) = Pr n-1 i=0 X i,t ≥ 1 ≤ E n-1 i=0 X i,t ≤ n 2 t ,
by Markov's inequality. Let us define another random variable

R K = max i (X i ) ,
which corresponds to the maximum number of trials required until a second level hash function has been defined for all buckets, and therefore describes the number of d-tuples in K.

We will bound the expectation of R K to obtain the bound stated in the theorem. We first note that

Pr(R K ≥ r) = Pr(X i ≥ r for some i) ≤ ∞ t=r Pr(X i = t for some i) ≤ ∞ t=r n 2 t = n 2 r-1 . (1)
The bound obtained in (1) is very large for small values of r. Indeed, when r is smaller than log 2 n, 1 is a better bound on the probability. Therefore, we define a new random variable Y which is equal to log 2 n if R K ≤ log 2 n and R K otherwise. We will bound the expectation of Y . Since E(Y ) ≥ E(R K ), the bound will also apply to the expectation of R K and hence to the number of tuples in K. We have

E(Y ) = log 2 n Pr(R K ≤ log 2 n) + ∞ r=1+log 2 n Pr(R K ≥ r) ≤ log 2 n + ∞ r=1+log 2 n n 2 r-1 ,
by using the bound (1) and the fact that Pr

(R K ≤ log 2 n) ≤ 1. Since ∞ r=1+log 2 n n 2 r-1 = n 2 log 2 n = 1 we obtain the result E(R K ) ≤ E(Y ) ≤ 1 + log 2 n.
We note that Theorem 3.6 can also be useful to understand how far from its average value the number of elements in K can be. Indeed, we immediately deduce the following corollary from the proof above.

Corollary 3.7. The probability that the number of d-tuples in K exceeds t log 2 n + 1 is bounded by n 1-t .

Another more intuitive way of seeing the O(log 2 n) bound of Theorem 3.6 is as follows. A randomly sampled k ∈ U defines an injection with probability more than 1/2 for a given bucket by Corollary 3.4. If we try a randomly sampled k on all buckets, we will have an injection for half of the buckets in expectation. We can then randomly sample another d-tuple, which will again define an injection for half of the remaining buckets in expectation. By continuing this way, we see that O(log 2 n) tuples will thus be enough to define all injections, in expectation.

Based on Corollary 3.7, we suggest to create the set K to contain 2 log n tuples at the outset. In the off chance that those tuples are not enough to define an injection for each bucket, new tuples can be created easily. The expected run time of construction can then be bounded as O(nd). This is so since k can be found in expectation with two trials, where each trial is tested in O(nd) time. Then O(2d log n) time is spent in creating K. By the intuitive explanation of Theorem 3.6, we see that another O(nd) time is spent in perfectly hashing all buckets, leading to an overall O(nd) run time bound in expectation.

A query for the existence of a hyperedge q ∈ U can be answered by first checking the size of the bucket B i where i = (k T q mod p) mod n. If b i = 0, then q is not a hyperedge of the given hypergraph. If b i = 1, the query is answered by comparing q with the hyperedge whose id is stored for B i . If b i > 1, then the associated d-tuple from K is retrieved as k (i) , and = (q T k (i) mod p) mod 2b 2 i is computed. If there is an id stored at the location , then the query is answered by comparing that hyperedge with q. If there is no id at the location , then q is not in the hypergraph. A query can thus be read and answered in O(d) time.

The space requirement can further be reduced by having more than n buckets; see the discussion following the proof of Lemma 3.1 given in Appendix and also the original FKS method [10, Section 4]. The gist of the idea is to reduce the number of items in the buckets so that fksStorage would need less total space. In the extreme case that we have n 2 buckets, fksStorage will just contain n entries with a suitable k; however this time fksOffset will be of size n 2 . On the other hand, with slightly more buckets than hyperedges, reductions in the space requirements will be observable in practice. Furthermore, with larger number of buckets than hyperedges, the number of buckets with at most one hyperedge will increase and hence the construction time and query response time are likely to reduce. In the experiments we analyze this parameter and find around 2.4×n buckets to result in about the same space requirement when n buckets are used, while improving the construction and query response time.

3.3. Further discussions.

3.3.1.

Addressing general hypergraphs. We focus on the d-partite, d-uniform hypergraphs as this is a large class covering the requirements of the tensor decomposition application. The proposed method is not limited to this class. We can apply the algorithms to any hypergraph, without a requirement that the vertices belong to disjoint partitions or that the hyperedges are all of equal size. Let H = (V, E) be a hypergraph and r be the maximum size of a hyperedge in E. Let us assume that 0 is not a member of V . We now define a new hypergraph H = (V , E ) as follows. The vertex set V = r-1 i=0 V (i) where V (i) = V ∪ {0} for i = 0, . . . , r -1. The hyperedge set E contains a hyperedge e for each unique hyperedge e ∈ E of the original hypergraph. To create e from e, we first sort the vertices in e and use them in this order for the first |e| dimensions of e . For the dimensions |e|, . . . , r -1, we append a 0 to e from the corresponding vertex partition V (i) . The hypergraph H is therefore r-uniform and r-partite. Any query hyperedge q for H can be converted similarly into a query hyperedge q for H by sorting its vertices, and adding the vertex 0 to q for all missing dimensions j = |q|, . . . , r -1 so that q becomes of size r as well. A query q posed on H can therefore be answered equivalently by the query q on H .

The above transformation of padding queries and hyperedges with 0 for missing positions should be done implicitly, otherwise the run time and space requirements can increase prohibitively. In particular, when processing a hyperedge in H , only the original vertices should be used while computing inner products with the k vectors. If the hyperedges and queries are not sorted at the outset, one needs to sort them, in which case query response time can increase in complexity.

Space complexity.

The proposed method strives to achieve worst case optimal query response time on hypergraph data while maintaining the space requirement linear in the number n of hyperedges. Other perfect hash functions deal with the bits-per-key complexity, which measures the storage required to represent a minimum perfect hash function. The current state-of-the-art MPHFs generally target less than 3 bits/element. We do not concern ourselves with this complexity measure, as the motivating application stores the hyperedges in O(nd)-space in order to answer queries for zeros of the tensor, and the yes answers are checked with respect to the input. While it is always good to reduce the space requirement, the bits-per-key complexity is not deemed to be an important aspect [START_REF] Limasset | Fast and Scalable Minimal Perfect Hashing for Massive Key Sets[END_REF], and the query time is of utmost importance for the motivating application. To store the hash functions of the proposed method, one at least needs to store k, the number of elements, and the index of a d-tuple in K for each bucket with more than one element-one does not store the ids of hyperedges in buckets, see Figure 1. Since the number of d-tuples in K is O(log 2 n), one needs Ω(log 2 log 2 (n)) bits to store the id of a d-tuple per bucket. That is, the bits-per-key complexity will be Ω(log 2 log 2 (n)) to store the ids of d-tuples per bucket. This quantity is greater than 4 even when n = 10 6 , which is already much larger than the bits-per-key complexity of the current state-of-the-art MPHFs. When this bit-complexity is too much, or when its implementation with standard data types requires too much space, then methods with smaller memory requirement are preferable.

Experiments

We compare the proposed algorithm called FKSlean with the following current stateof-the-art hashing methods based on different approaches:

BBHash [START_REF] Limasset | Fast and Scalable Minimal Perfect Hashing for Massive Key Sets[END_REF]: a minimal perfect hash function. It has a parameter γ for which the original paper suggests values 1, 2 and 5, where γ = 1 optimizes space, γ = 5 optimizes the lookup time, and γ = 2 is in between. We use BBHash with γ = 1 and γ = 5. RecSplit [START_REF] Esposito | RecSplit: Minimal perfect hashing via recursive splitting[END_REF]: another minimal perfect hash function. It has two parameters (LEAF SIZE, bucket size), where the configurations (8,100) and [START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF] are suggested in the original paper. We use RecSplit with these two configurations. PTHash [START_REF] Pibiri | PTHash: Revisiting FCH minimal perfect hashing[END_REF]: the most recent minimal perfect hash function to the best of our knowledge, whose recent implementation [START_REF] Pibiri | Parallel and external-memory construction of minimal perfect hash functions with pthash[END_REF] We use the version which creates non-minimal hash functions. FastFilter: This method uses one of the latest approximate set membership filters called 3-wise XOR binary fuse filters [START_REF] Graf | Binary fuse filters: Fast and smaller than xor filters[END_REF] to filter out "no" answers and then needs to call one of the exact hashing methods for the "yes" answers. We also experiment with a method which we call HashàlaFKS.

HashàlaFKS: the standard average-case constant time hashing method available in the C++ standard library as unordered map; we propose to use the first level hash function (k T x mod p) mod n of FKSlean with it. There is no second level hashing in HashàlaFKS. The tuple k used for HashàlaFKS enjoys the same properties as that of FKSlean in reducing the collisions (the number of hyperedges per bucket). We experiment with HashàlaFKS as its core is available in the standard library, the proposed hash function is a good one, and one can easily deploy it. In a preliminary set of experiments, we also tried a sort-based method, as it was used before in the original tensor decomposition application [START_REF] Kolda | Stochastic gradients for large-scale tensor decomposition[END_REF]. This method sorts the hyperedges in linear time using radix sort [4, Section 8.3], and then uses a binary search scheme to answer queries. We observed that the query time in this case was an order of magnitude larger than that of FKSlean on a large set of instances that we use in this section, and hence deemed it too slow. We thus do not give results with it. We note that comparison based search can be improved [START_REF] Khuong | Array layouts for comparison-based searching[END_REF], these nonetheless will be inferior to constant time methods that we use in our experiments; especially since sorting and searching will need to work on d-dimensional data. In order to use the hashing methods BBHash, RecSplit, and PTHash in our context, we created the corresponding hash functions on the n hyperedges of a given hypergraph, and then used the resulting mapping function to uniquely store the id of each hyperedge in an array of suitable size. The resulting approaches are called uBBH, uRecSplit, and uPTHash, respectively, where the configurations are specified with (1) and ( 5) for BBHash, (8, 100) and [START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF] for RecSplit, and ( 1)-(4) for PTHash. All codes are compiled with g++ version 9.2 with options -O3, -std=c++17 -march=native as used in PTHash. We carry out the experiments on a machine having Xeon(R) CPU E7-8890 v4 with a clock-speed of 2.20GHz. All codes are available at https://gitlab.inria.fr/bora-ucar/hedge-queries.

We first describe the data set, implementation, and the measurement details in the next two subsections. We then determine the extension parameter for FKSlean in Section 4.3. Using the determined parameter, in Section 4.4 we compare FKSlean with the other methods listed at the beginning of this section. We then investigate the space requirement of FKSlean in Section 4.5, and finally give a summary of experimental results in Section 4.6.

4.1. Data set. We present experiments both on real-life data corresponding to matrices and tensors, and synthetic data. We use the real-life data to compare the different algorithms, and use the synthetic data to investigate the behavior of different methods with respect to different problem parameters.

We take tensors from FROSTT [START_REF] Smith | FROSTT: The formidable repository of open sparse tensors and tools[END_REF], and build the associated d-uniform d-partite hypergraphs. The properties of the hypergraphs are shown in Table 1. The hypergraphs in the table are sorted in decreasing order of the number n of hyperedges, first for matrices, then for tensors. The tensors delicious-3d and delicious-4d contain the same data, with different dimensions. It turns out that the hyperedges are unique with or without the fourth dimension. Therefore, both hypergraphs have the same number of hyperedges. A similar observation is made concerning flickr-*d, while the number of hyperedges in vast-2015-mc1-*d differ only by 91. We also experiment with three bipartite graphs which correspond to real-life matrices available in The SuiteSparse Matrix Collection [START_REF] Davis | The University of Florida sparse matrix collection[END_REF]; the original files from this collection list nonzeros that are on or below the main diagonal which we use as the hyperedges. These are listed in the table with d = 2. These tensors and matrices arise in diverse real-world applications; ranging from natural language learning (nell-*), to e-mail data (sender-receiver-word-date in enron), and protein graphs (kmer A2a) to social networks (com-Orkut).

The synthetic data are built using a model similar to the well-known Erdös-Renyi random graph model. Given a desired number d of parts, a desired number s of vertices in each part, and a desired number n of hyperedges, the model R(d, s, n) creates a random hypergraph as follows. First, n hyperedges are created by sampling their vertices in the ith part uniformly at random from the range [0, s). Then, duplicate hyperedges are discarded. Note that the number of hyperedges can be slightly smaller than n, and that the maximum element in a part can be different from (s -1).

Implementation and measurement details.

In order to use BBHash, PTHash, and RecSplit we convert each input into 64-bit integers using SpookyHashV2. This function is also used by RecSplit implementation to handle keys different from 128-bit strings. We call SpookyHashV2 on each hyperedge by casting (no copy) the hyperedge to Table 1. Real-life test data corresponding to the hypergraphs used in the experiments. char *. We modified RecSplit to use such 64-bit integers as input (instead of bit-strings of length 128 bits). We use two arrays to implement FKSlean, as shown in Figure 1. Here, fksStorage is a contiguous array for storing all buckets one after another; fksOffset is an array of size (n + 1), and fksOffset[i] stores the start of bucket B i 's storage in fksStorage.

We use fastmod library [START_REF] Lemire | Faster remainder by direct computation: Applications to compilers and software libraries[END_REF] for all (• mod n) operations, and fast modulo operations with Mersenne primes [START_REF] Thorup | High speed hashing for integers and strings[END_REF] to compute (• mod p) for p = 2 31 -1; one can also use the fastmod library for efficiency in case this p is not large enough. For the mod 2b 2 i operations, we use the standard modulo operator % in C++. For reading the tensors from the disk, we use PIGO [START_REF] Gabert | PIGO: A parallel graph input/output library[END_REF].

The construction time reported for FKSlean includes all the steps: finding the first level hash satisfying Lemma 3.1 or Corollary 3.2, allocating fksOffset and fksStorage, building the set K of 2 log(n) d-tuples, and setting up the data structure as shown in Figure 1.

We report the average of five runs in all measurements per hypergraph. A number q of queries are generated by mixing a set of existing hyperedges and a set of random hyperedges using a parameter t, called hit-ratio. First t × q hyperedges from the given hypergraph are chosen uniformly at random; then the remaining queries are generated by setting their ith coordinate with rand()%s [i] where s[i] is the size of the tensor in dimension i. At each of the five repetitions of the experiments, the same set of queries is used. We use t = 0.5 for all experiments below, unless otherwise stated. The time to generate the queries is not included in the query response time that we report.

4.3.

Determining the extension parameter for FKSlean. As described in Section 3.2, the total storage requirement of FKSlean for the arrays fksOffset and fksStorage is contingent on the number of buckets. The higher the number of buckets, the less storage is needed for fksStorage. As an extreme, if we increase the number of buckets to n 2 , then each bucket can have at most one element with a suitable k. Furthermore, the construction time and the query time are also affected: with more buckets, there will be more buckets with at most one element, and hence the first level hashing will suffice in more cases.

We study the impact of increasing the number of buckets on the storage requirement, and the performance of the construction and the query phases of FKSlean. Figures 2 and3 show the effect of varying the number of buckets for two representative inputs from our test-suite. We set the number of buckets to ρn, where ρ ≥ 1. We call ρ the extension parameter. As we can observe from Figures 2a and3a, with increase in ρ, the total storage requirement of FKSlean initially decreases up to a point and then it increases. We also observe from Figures 2b and3b that the construction time monotonically decreases with increase in ρ. Similarly, the query response time also goes down with increase in ρ as we observe in plots 2c and 3c. We perform this study on the synthetic data set of random hypergraphs as well, and observe similar trends; especially the total storage requirements were almost always identical to the plots in Figures 2a and3a.

In an initial study, for ρ = 1.0, the storage requirement of FKSlean was observed to be slightly less than 5n, which are also seen in Figures 2a and3a. Based on the empirical evidence shown in Figures 2 and3, we identify ρ = 2.4 as a sweet-spot for FKSlean. Fixing the number of buckets to 2.4n reduces the total storage requirement below 5n and reduces the construction and query time compared to that with n buckets. In the remainder of the experiments, we set the number of buckets to 2.4n for FKSlean unless otherwise stated. 4.4. Comparisons.

4.4.1.

With exact hashing methods. Table 2 presents the construction time of the ten methods on the real-life hypergraphs from Table 1. For every hypergraph, the absolute run time of HashàlaFKS is given in seconds, while the run time of the other methods are normalized with respect to HashàlaFKS. The last row of this table gives the geometric mean of the ratios of construction times to that of HashàlaFKS. As seen in this table, on all inputs, the construction time of all methods but FKSlean are longer than that of HashàlaFKS-as indicated by values greater than 1 for all the methods except FKSlean. FKSlean's construction time is 0.54 of HashàlaFKS's on average. FKSlean is the fastest method followed by uPTHash- [START_REF] Botelho | Practical perfect hashing in nearly optimal space[END_REF].

Table 3 presents the query response times for the ten methods to answer 10 methods to that of HashàlaFKS are given in the last row. As seen in this table, among all methods, HashàlaFKS's query response is the largest, in general. FKSlean has the fastest query response on all the inputs, followed by uPTHash-(1) and uPTHash-(4).

FKSlean is nearly 4 times faster than HashàlaFKS on average, and is nearly twice as fast, on average, compared to the next best performing methods.

In order to investigate how the methods behave with respect to the number of hyperedges and the dimension, we present further experiments with the random hypergraph family R(d, s, n). In the first set of experiments, we investigate how the run time of different methods change with the number n of hyperedges. To do so, we compare all methods on the random hypergraphs R(d, s, n) with d = 4, s = 10 6 , and n taking different values in the range 10 6 to 5 × 10 8 . Ideally, we expect the construction time to increase linearly with the increasing n, and the query response time to remain nearly constant, independent of n, for all the methods.

The plot for the construction times of the different methods on the random hypergraphs with 10 6 ≤ n ≤ 5 × 10 8 is shown in Figure 4. The x-axis the and y-axis are both in the log-scale. From the figure, we observe that FKSlean consistently has the shortest construction time compared to the other methods on random hypergraphs as before. We further observe that for most of the methods the construction time varies linearly with n, as expected in theory. For instance, for uBBH-(1) there is a ten-fold increase in the construction time (1s to 10s) as n goes from 10 6 to 10 7 . For HashàlaFKS and FKSlean, the construction time does not always increase linearly with n, but is largely linear for the most part. For instance, for FKSlean, after n = 10 7 the construction time increases nearly linearly with n. 4) uPTHash [START_REF] Botelho | Practical perfect hashing in nearly optimal space[END_REF] FKSlean uPTHash(3) uRecSplit [START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF] Figure 4. The construction time of all methods on random hypergraphs in seconds. The x-and y-axes are in log-scale. At = 5 × 10 8 , the plots correspond to, from top to bottom, the methods as listed in the legend (from left to right, top to bottom).

Figure 5. The response time for 10 7 queries, in seconds, of all methods on the random hypergraphs. The x-axis is in log-scale. At n = 5 × 10 8 , the plots correspond to, from top to bottom, the methods as listed in the legend (from left to right, top to bottom).

We next compare the query response times of different methods on the R(d, s, n) hypergraphs family with the same parameters as before. Figure 5 presents the results for the query response time; the x-axis is in the log-scale. From the figure, we reconfirm that FKSlean is consistently considerably faster than the others for all values of n. We also see that the query response time of all methods increases with the increasing number of hyperedges. This is because for larger n, the internal data structures take up more memory. As a result, the random accesses in the data structures increase the overall look up time. We next investigate the behavior of the methods under study with respect to d. For this analysis, we pick HashàlaFKS, uRecSplit-(5,5), uPTHash-(2), uPTHash-(4), uBBH-(5), and FKSlean, since these methods have good performance so far. We analyse the performance of these methods in both the construction and the query phases. Figure 6a and Figure 6b show the construction and query response time of these methods on the random hypergraphs R(d, s, n) where d = {4, 8, 16}, s = 10 6 , and n = 2 × 10 7 . We see in Figure 6a that the construction time of FKSlean is the least of all the remaining methods for all values of d, as before. We further observe that the construction time of uRecSplit- [START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF], uPTHash-(2), uPTHash-(4) and uBBH-( 5) are very stable with the increasing value of d. This is because all these methods first map the input to a 64bit integer before proceeding with the computation. As a result, the increase in the dimensions does not affect the performance of these methods after this mapping. On the other hand, we observe that for HashàlaFKS and FKSlean, the construction time increases with the increasing d. This is because for these methods, the work done per hyperedge increases with the increasing d. Figure 6b shows the query response time of the six methods on 10 7 queries. The query response time of FKSlean is the shortest for all values of d. Like their construction times, the query response times of uRecSplit- [START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF], uPTHash-(2), uPTHash-(4) and uBBH- [START_REF] Davis | The University of Florida sparse matrix collection[END_REF], are stable with increasing d. Furthermore, the query response time of HashàlaFKS and FKSlean increase with the increasing d. This is again because of the increase in the work done per query with the increase in d.

4.4.2.

FKSlean vs FastFilter. In this section we compare FKSlean with FastFilter. Fast-Filter method uses 3-wise XOR binary fuse filters first, and for all the "yes" answers it calls FKSlean (with ρ = 2.4), since this method is identified as the fastest in the previous subsection. In order to use FastFilter, we again use SpookyHashV2.

We compare FastFilter with two different variants of FKSlean-with ρ = 1.0, and ρ = 2.4. Figure 7 shows the comparison of query response times of FastFilter and FKSlean, for 10 7 queries, on two large inputs, with varying hit ratios. We observe that 0.5 1.

for both nell-1 (7a) and kmer A2a (7b), the query response time of FKSlean (with ρ = 2.4) is lower than FastFilter for all hit-ratios. On the other hand, the query response time of FKSlean (with ρ = 1.0) is higher than that of FastFilter till the hit-ratio reaches 0.6; thereafter, the former has a lower query response time.

We further zoom-in on the performance of FastFilter and observe that the lookup using 3-wise XOR binary fuse filters takes up a significant chunk of the total query response time. For instance, for nell-1, the 3-wise XOR binary fuse filters lookup takes 0.45 seconds out of the total query response time of 0.93 seconds, for hit-ratio t = 0. For kmer A2a, the 3-wise XOR binary fuse filters lookup takes 0.47 seconds out of the total query response time of 0.92 seconds, for hit-ratio t = 0.

We next compare the construction times of FKSlean (with ρ = 2.4) and FastFilter. The construction time of FastFilter is always more than that of FKSlean. This is expected since FastFilter constructs 3-wise XOR binary fuse filters and FKSlean data structure. We look closely at the time spent in the construction phase of the 3-wise XOR binary fuse filters and FKSlean. We observe that for nell-1, the total construction time for the FastFilter is 52.80 seconds. Out of this, 21.73 seconds are spent in the construction of the 3-wise XOR binary fuse filters, while 31.07 seconds are spent in constructing the FKSlean data structure. We further observe that for kmer A2a, the total construction time of FastFilter is 65.63 seconds. Out of this, 25.16 seconds are spent in the construction of the 3-wise XOR binary fuse filters, while 40.47 seconds are spent in constructing the FKSlean data structure. In general, across all the inputs, we find that constructing 3wise XOR binary fuse filters takes at least 60% of the construction time of the FKSlean, which attests the efficiency of FKSlean. 4.5. Storage Requirement of FKSlean. We now look at the storage requirement of FKSlean, and see how the theoretical properties shown in Lemma 3.1 and Proposition 3.5 compare with the results in practice. Table 4 shows the storage requirement of FKSlean for the arrays fksOffset and fksStorage for the input tensors from Table 1. The storage requirement, computed in terms of the number of cells of the two arrays, is normalized by the number n of hyperedges for each input data. From the table, we observe that the storage requirement of FKSlean is always comfortably less than 5n for all the inputs. The geometric mean storage requirement of FKSlean across all the input tensors is 4.71n. 4.6. Summary of experimental observations. We summarize the findings of our experiments. Our extensive comparative study of the different methods shows that among all the methods, FKSlean is always the best performing method-it has the least construction time, as well as, the least query response time on all the reallife, and synthetic inputs. uPTHash is the next best method among the exact perfect hashing methods considered, both in construction and query response. However, we note that among the four variants of uPTHash, the same variant is not always the fastest in both construction and query. For instance, among the different variants of PTHash, uPTHash-(2) has the least construction time on average (cf. Table 2). On the other hand, uPTHash-(1) has the least query response time on average (cf. Table 3). Thus, the choice of the uPTHash variant needs to factor in the resulting trade-off between the construction time and the query response time.

The construction time of all exact methods varies nearly linearly with the number n of hyperedges (cf. Figure 4). The query response time of all methods increases gradually with increasing n (cf. Figure 5). The construction time and the query response time of uRecSplit, uPTHash and uBBH are unaffected by the dimension of the input hypergraphs. On the other hand, the performance of HashàlaFKS and FKSlean depends on the dimension of the input data (cf. Figure 6a and Figure 6b). Next, FKSlean (with ρ = 2.4) has a better query response than FastFilter for all hit-ratios (cf. Figure 7). Finally, HashàlaFKS's construction time is lower than all perfect hashing methods but FKSlean. However, its query response time is the largest among all the methods under study. Notwithstanding its inferior query response time, an advantage HashàlaFKS offers is simplicity and the ease of use. In order to use HashàlaFKS, one just needs to implement routines for determining a prime number p > n and for computing (k T x mod p) mod n. The unordered map from C++ standard library takes care of the rest.

We note that the way the proposed FKSlean method handles the hyperedges natively makes a difference. To use BBHash, RecSplit, PTHash, and 3-wise XOR binary fuse filters one has to quickly convert the input data to 64-bit integers, or map the input data to a smaller universe (which is called universe reduction [START_REF] Thorup | High speed hashing for integers and strings[END_REF]). While this reduction/conversion does not take much time with the common libraries used, such as SpookyHashV2, it is not negligible. This is so even for FastFilter, as the proposed FKSlean (with the extension parameter ρ = 2.4) was demonstrated to be faster in query response. Apart from the overhead incurred during the universe reduction, there is also a theoretical issue associated with the worst case optimal hashing methods. Such reductions can create duplicate keys with a very small probability. In the presence of duplicate keys, the proposed FKSlean and other mentioned methods will have infinite loops unless the codes are modified to guard against the duplicates.

While FKSlean exhibits a superior performance than the other methods, it takes up more memory than the minimal and non-minimal perfect hashing methods considered in the experiments. On average FKSlean's storage requirement is 4.71n (cf. Table 4) unsigned integers (or the id type).

Conclusion

We investigated the problem of answering queries asking for the existence of a given hyperedge in a given hypergraph, with a special focus on d-partite, d-uniform hypergraphs arising in a tensor decomposition application. We proposed a perfect hashing method called FKSlean based on a well-known approach [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF]. FKSlean has provably smaller space requirements than a direct adaptation of the original approach, thanks to the reuse of hash functions. Experimental results demonstrated in practice that the space requirement is in fact less than 5n plus an additional O(d log 2 n) term for storing the shared hash functions. We compared FKSlean with the methods using the current state-of-the-art minimal perfect hash functions (MPHFs), approximate set membership filters, and the unordered map from C++ standard library equipped with the first level hash function used by FKSlean. Experiments on real-life and synthetic data showed that FKSlean achieves the shortest query response time among all alternatives while also having the least construction time of all. We have addressed the parallelization of the construction phase of FKSlean recently [START_REF] Singh | An Efficient Parallel Implementation of a Perfect Hashing Method for Hypergraphs[END_REF].

We have three lines of future work. On the application of interest with tensors, we need an implementation of the stochastic gradient method in an efficient library (instead of in Matlab) to test the effects of the proposed method in that particular application. On the more algorithmic front, we plan to address the dynamic case where hyperedges may get inserted or deleted. A suitable starting point is provided by Dietzfelbinger and others [START_REF] Dietzfelbinger | Dynamic perfect hashing: Upper and lower bounds[END_REF]. On the theoretical side, we observed that for any randomly chosen d-tuple k in the first level hashing, the quantity i b 2 i was always comfortably smaller than the upper bound we have shown. Can a tighter upper bound be shown theoretically? multiplying with the upper bound on the number of elements in the right hand size, 2p n + 1, will give the total number of times any pair x, y ∈ E satisfies (3).

At (5), we can freely set any k j for j = , and k must then be chosen accordingly with these selections to make the equation hold. Because p is prime, for each distinct configuration of the k j values for j = , there is a unique value of k that makes (5) hold. In other words, for any value in the right hand side of (4), there are p d-1 different k tuples, which are formed by considering all different p values for each k j for j = .

As there are no more than 2p n + 1 different right hand side values in (4), and for each one we have at most p d-1 different k tuples satisfying (3), we obtain an upper bound on the right hand side of (2) as

x,y∈S

x =y |{k ∈ U : (k T x mod p) mod n = (k T y mod p) mod n}| ≤ p d-1 2p n + 1 n(n -1) 2 ,
since there are n(n-1) 2 pairs x, y. Combining with the left hand side of (2), we see that

k∈U n-1 i=0 b (k) i (b (k) i -1) 2 ≤ p d-1 2p n + 1 n(n -1) 2 .
Since there are p d different k, for at least one of them the inner sum

n-1 i=0 b (k) i (b (k) i -1) 2
should be no larger than the average. That is, = n, we obtain the bound stated in the lemma.

In the original FKS method, we have scalar values. Therefore the equivalent of (4) is k(x -y) mod p ∈ {0, ±n, ±2n, . . . , ± p -1 n n} .

Since p is prime and both k and x -y are less than p, the equality k(x -y) mod p = 0 cannot hold, and the set on the right hand side is {±n, ±2n, . . . , ± p-1 n n}. This difference affects the upper bound, as obtained above.

Consider now that we have n buckets with n < n < p. In this case, the first level hashing will use (• mod p) mod n to hash the hyperedges, and thus there will be 2p n + 1 different right hand side values in (4). Following through the proof above we see that the upper bound in [START_REF] Dietzfelbinger | Dense peelable random uniform hypergraphs[END_REF] reduces to 3n n (n -1). Thus, the total space requirement of individual buckets (fksStorage in Fig. 1) reduces, and the space requirements for holding the buckets (fksOffset in Fig. 1) increases.

Restatement of Corollary 3.2: Let E ⊆ U be a given set of n hyperedges. Then, for at least half of the potential k ∈ U , when k is used in the first level hash function, we have n-1 i=0 b 2 i < 7n.

Proof. Let X be the random variable representing when we randomly choose k. Then, by [START_REF] Dietzfelbinger | Dynamic perfect hashing: Upper and lower bounds[END_REF] and the fact that p > n, we have E(X) ≤ 3 (n-1) 2 . By Markov's inequality, Pr(X ≥ 3(n -1)) ≤ E(X) 3(n-1) , and hence Pr(X ≥ 3n) ≤ 1 2 . Therefore, we have Pr(X < 3n) ≥ 1 2 , and hence for at least half of the randomly chosen k we have

i b (k) i (b (k) i -1) 2
< 3n. The event that i b 2 i < 7n is identical to the event 2X + n < 7n, and hence holds with probability no smaller than 1/2. Therefore, at least half of k ∈ U satisfies the bound of the corollary.

Restatement of Lemma 3.3: For each bucket B i with b i > 0 elements, there is a k ∈ U such that the function (k T x mod p) mod b 2 i is an injection for p b 2 i .

Proof. The proof follows the same approach used in proving Lemma 3.1. There are two differences: here we have at most 2 p-1 b 2 i + 1 potential values for a pair to have an equal hash value (the equivalent of ( 4)), and the total number of pairs is b i (b i -1)

2 instead of n(n-1) 2
. This leads to an average (over all possible k) no larger than one for each position in the storage space of size b 2 i for p b 2 i . And hence, k can be chosen.

Restatement of Corollary 3.4: Let B i be a bucket with b i > 0 elements. For at least half of the d-tuples k ∈ U , it holds that the function (k T x mod p) mod 2b 2 i defines an injection for the elements of B i for p b 2 i .

Proof. We follow the proof of Lemma 3.1 (and Lemma 3. to be the number of elements of B i that map to j ∈ {0, . . . , 2b 2 i -1} with the function (k T x mod p) mod 2b 2 i . We obtain the inequality k ∈U

2b 2 i -1 j=0 b (k ) j (b (k ) j -1) 2 ≤ |U | p 2 p -1 2b 2 i + 1 b i (b i -1) 2 .
By arithmetic simplification and using p b 2 i , we obtain [START_REF] Dillinger | Fast succinct retrieval and approximate membership using ribbon[END_REF] k ∈U

2b 2 i -1 j=0 b (k ) j (b (k ) j -1) 2 ≤ |U | 1 2 .
Let X be the random variable represeting ≥ 2 must hold for some j ∈ {0, . . . , 2b 2 i -1}. In that case, we will have the event X ≥ 1. By Markov's inequality, Pr(X ≥ 1) ≤ E(X) ≤ 1 2 .

Therefore, Pr(X < 1) ≥ 1 2 , and hence at least half of the potential k ∈ U defines an injection for B i for p b 2 i .

Restatement of Proposition 3.5: For a random k = [0, . . . , 0] and a random set F with n hyperedges, the first level hash function using k creates at least n 1 -e -1+2/p nonempty buckets in expectation, where e is the base of natural logarithm.

Proof. For each x ∈ U let us define a random variable R k

x taking on the value (k T x mod p) mod n for a tuple k. We will compute for any tuple k, the number of sets F ⊆ U of cardinality n such that for all x in F we have R k x = i. We will obtain for each value i the probability over k and F that bucket B i is non-empty. By summing over i, we will obtain the expected number of non-empty buckets for a randomly chosen k and a random set F of size n.

We first compute the expected value over k and F of the random variable R k F,i = |{x ∈ F |R k x = i}|. For a fixed tuple k = [0, . . . , 0], let us find the number of x ∈ U such that R k x = i. If R k x = i, we should have (9) k T x mod p ∈ i, i ± n, i ± 2n, i ± 3n, . . . , i ± p -1 -i n n .

This means that there are

t i = 2 p -1 -i n + 1
possible values for k T x mod p. For any value j in the right hand size of (9), let us consider the tuples x j such that k T x j mod p = j. Since k is not uniformly zero, there is an index such that k = 0. Then, for any of the p d-1 possible values of x j r , where r = , there exists one unique value of x j such that k T x j mod p = j. Thus, there exist p d-1 such x j tuples for j. This yields a total of p d-1 t i alternatives for x such that (9) holds, and hence for which R k x = i, among all p d elements of U . There are therefore p

  also creates non-minimal hash functions for efficiency. The original paper identifies four configurations which we use in our experiments: (1) C-C, α = 0.99, c = 7, which optimizes the lookup time; (2) D-D, α = 0.88, c = 11, which optimizes the construction time; (3) EF, α = 0.99, c = 6, which optimizes the space effectiveness of the function; (4) D-D, α = 0.94, c = 7, which optimizes the general trade-off.

Figure 2 .

 2 Figure 2. Analysis of the extension parameter ρ of FKSlean on nell-1.

Figure 3 .

 3 Figure 3. Analysis of the extension parameter ρ of FKSlean on kmer A2a.

Figure 6 .

 6 Figure 6. The construction time and the query response time for 10 7 queries, in seconds, of six methods in hypergraphs from the family R(d, s, n) for d = {4, 8, 16}, s = 10 6 , and n = 2 × 10 7 . At d = 16, the plots correspond to, from top to bottom, the methods as listed in the legends (from left to right, top to bottom).

Figure 7 .

 7 Figure 7. Comparison of query response times of FKSlean and FastFilter for 10 7 queries on two instances.

i - 1 2 ,

 12 for a k. Let k denote the tuple attaining that bound. Then,

  3), while replacing E by B i , n by b i , and by defining b

  over all potential k ∈ U . For a randomly chosen k not to be an injection, b (k ) j

  d-1 •(p-t i ) n sets F for which R k x = i, where the symbol a b = a! b!(a-b)! is the binomial coefficient.Then, for a fixed tuple k, the probability that none of the elements of a random F maps to i isPr(∩ x∈F R k x = i) = p d-1 •(p-t i ) n p d n.

Table 2 .

 2 The construction time for the ten methods on real-life tensors. The absolute run time of HashàlaFKS is given in seconds. The construction time of the other methods are normalized with respect to that of HashàlaFKS. Lower values imply better performance.

			uRecSplit	uBBH	uPTHash
	name	HashàlaFKS (s) (8,100) (5,5) (1) (5) (1) (2) (3) (4) FKSlean
	kmer A2a	83.66	5.55 1.39 3.16 1.54 1.85 1.17 2.53 1.53	0.49
	queen 4147	56.34	7.59 1.70 3.58 1.82 2.24 1.38 3.15 1.78	0.72
	com-Orkut	51.74	5.71 1.25 2.49 1.22 1.54 1.00 2.23 1.28	0.56
	nell-1	68.89	5.30 1.22 2.59 1.34 1.70 1.05 2.10 1.20	0.47
	delicious-3d	64.71	5.49 1.22 2.49 1.30 1.59 1.02 2.22 1.32	0.55
	delicious-4d	65.68	5.47 1.23 2.55 1.27 1.60 1.01 2.23 1.29	0.55
	flickr-3d	51.59	5.52 1.19 2.45 1.18 1.56 0.99 2.22 1.27	0.55
	flickr-4d	50.08	5.69 1.21 2.41 1.19 1.58 1.00 2.22 1.30	0.53
	nell-2	34.05	5.66 1.15 2.41 1.00 1.48 0.97 2.16 1.25	0.57
	enron	24.17	5.64 1.17 2.47 0.87 1.47 0.97 2.03 1.22	0.58
	vast-2015-mc1-3d	10.68	6.12 1.17 2.56 0.82 1.44 0.96 1.92 1.20	0.64
	vast-2015-mc1-5d	11.64	5.55 1.09 2.27 0.76 1.27 0.83 1.74 1.04	0.60
	chicago-crime	1.63	8.13 1.44 3.20 0.97 1.47 1.10 1.90 1.29	0.36
	uber	0.77	10.45 1.87 4.11 1.26 1.80 1.40 2.29 1.60	0.42
	lbnl-network	0.25	16.45 2.85 6.25 1.98 2.53 2.08 3.12 2.29	0.63
	geo-mean		6.57 1.36 2.88 1.19 1.65 1.10 2.24 1.37	0.54

  7 queries on hypergraphs from Table1. In this table, the absolute query response time of HashàlaFKS is given in seconds. The response time of the other methods are normalized with respect to that of HashàlaFKS. Geometric mean of the ratios of the response time different

			uRecSplit	uBBH	uPTHash
	name	HashàlaFKS (s) (8,100) (5,5) (1) (5) (1) (2) (3) (4) FKSlean
	kmer A2a	6.93	0.76 0.73 0.84 0.81 0.44 0.52 0.54 0.47	0.21
	queen 4147	6.35	0.73 0.72 0.80 0.77 0.46 0.53 0.56 0.48	0.24
	com-Orkut	6.49	0.69 0.70 0.73 0.73 0.45 0.51 0.54 0.46	0.23
	nell-1	6.85	0.69 0.69 0.75 0.75 0.50 0.51 0.54 0.46	0.24
	delicious-3d	6.69	0.71 0.69 0.76 0.74 0.48 0.53 0.57 0.49	0.25
	delicious-4d	6.81	0.74 0.77 0.81 0.78 0.63 0.69 0.65 0.64	0.28
	flickr-3d	6.65	0.68 0.67 0.72 0.70 0.48 0.52 0.56 0.49	0.24
	flickr-4d	6.49	0.72 0.74 0.77 0.76 0.63 0.69 0.65 0.64	0.28
	nell-2	6.52	0.67 0.63 0.69 0.69 0.48 0.52 0.56 0.49	0.24
	enron	6.60	0.69 0.68 0.70 0.69 0.59 0.63 0.62 0.60	0.28
	vast-2015-mc1-3d	6.53	0.61 0.57 0.63 0.56 0.46 0.49 0.53 0.47	0.24
	vast-2015-mc1-5d	6.71	0.63 0.61 0.65 0.60 0.52 0.56 0.58 0.53	0.30
	chicago-crime	5.32	0.52 0.50 0.56 0.52 0.39 0.43 0.45 0.39	0.27
	uber	4.75	0.48 0.44 0.51 0.52 0.32 0.36 0.39 0.33	0.25
	lbnl-network	3.67	0.54 0.48 0.58 0.60 0.34 0.39 0.41 0.34	0.23
	geo-mean		0.65 0.63 0.69 0.68 0.47 0.52 0.54 0.48	0.25

Table 3 .

 3 The query response time for 10 7 queries with the ten methods. For HashàlaFKS, its absolute query response time is given in seconds. The response time of the other methods are normalized with respect to that of HashàlaFKS. Lower values imply better performance.

Table 4 .

 4 4.73 4.70 4.74 4.74 4.74 4.74 4.73 4.73 4.74 4.73 4.73 4.73 4.75 4.51 4.65 The storage requirement of FKSlean for fksOffset and fksStorage arrays, normalized by n. The hypergraphs are labeled Hi, for i = 1, . . . , 15 and are given in the same order as Table

Acknowledgements

We thank Julian Shun, the Reproducibility Referee, for his help in ensuring that the computational results in the manuscript are reproducible.

Appendix A. Omitted proofs

We give the omitted proofs from Section 3. For convenience, we repeat the body of the lemmas and corollaries.

We start with Lemma 3.1 repeated below. Its proof follows closely the original proof by Fredman et al. and is given for completeness. After the proof, we explain why the upper bound is higher than that of the original theorem of Fredman et al.

Restatement of Lemma 3.1: For a given set E ⊆ U of n hyperedges, there is a k ∈ U such that when (k T x mod p) mod n is used as the first level hash function, we have n-1 i=0 b 2 i < 4n.

Proof. For a given k, let b

denote the number of hyperedges in E having the same hash value i = (k T x mod p) mod n. The number of two-element subsets {x, y} of E with the same hash value i is therefore

so that we can obtain the average number of two-element subsets of E with the same hash value over all potential k tuples. As there is at least one k for which the corresponding sum

is no larger than the average, we will use that k to attain the bound stated in the lemma.

We first observe that (2)

as the right hand side counts the total number of times any two different hyperedges x, y of E have the same value for hash value over all k ∈ U . We will bound the right hand side of (2) from above. For this, we need a bound on the number of different k for which any x, y ∈ E give the same value (3) (k T x mod p) mod n = (k T y mod p) mod n .

In other words, we want to count the number of different k for which we have

Since x = y, there is at least one dimension 0 ≤ < d such that x = y . Let us arbitrarily pick one such and write

Note that the number of alternatives in the right hand side of ( 5) is less than 2p n +1. Since we treat each pair x, y once, we can assume x > y without loss of generality. Let us take a value v from the right hand side of (5) and fix k (x -y ) + j = k j (x j -y j ) mod p = v. We will count the number of k tuples for which this equality holds. Then, We can thus bound Pr(R k F,i = 0) as follows:

p by the definition of t i and the fact that p > n > i. By defining a binary variable Y i = 1 if bucket B i is empty and another one Z = i Y i , we see that the expected number of empty buckets is

for a randomly chosen k and a random set of n hyperedges, which concludes the proof.