Search Data Structure Learning
Authors: Mathieu Duchesneau
Hansenclever Bassani
Alain Tapp
Venue:  (2021)
Keywords: Machine Learning
Search Data Structure
Information Retrieval
Binary Embeddings

Abstract: In our modern world, an enormous amount of data surrounds us, and we are rarely interested in more than a handful of data points at once. It is like searching for needles in a haystack, and in many cases, there is no better algorithm than a random search, which might not be viable. Previously proposed algorithms for efficient database access are made for particular applications such as finding the min/max, finding all points within a range or finding the k-nearest neighbours. Consequently, there is a lack of versatility concerning what we can search when it comes to a gigantic database. In this work, we propose Search Data Structure Learning (SDSL), a generalization of the standard Search Data Structure (SDS) in which the machine has to learn how to search in the database. To evaluate approaches in this field, we propose a novel metric called Sequential Search Work Ratio (SSWR), a natural way of measuring a search's efficiency and quality. Finally, we inaugurate the field with the Efficient Learnable Binary Access (ELBA), a family of models for Search Data Structure Learning. It requires a means to train two parametric functions and a search data structure for binary codes. For the training, we developed a novel loss function, the F-beta Loss. For the SDS, we describe the Multi-Bernoulli Search (MBS), a novel approach for probabilistic binary codes. Finally, we exhibit the F-beta Loss and the MBS synergy by experimentally showing that it is at least twice as better than using the alternative loss functions of MIHash and HashNet and twenty times better than with another SDS based on the Hamming radius.

Under review as a conference paper at ICLR 2021
SEARCH DATA STRUCTURE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In our modern world, an enormous amount of data surrounds us, and we are rarely interested in more than a handful of data points at once. is like searching for needles in a haystack, and in many cases, there is no better algorithm than a ran- dom search, which might not be viable. Previously proposed algorithms for ef- ficient database access are made for particular applications such as finding the min/max, finding all points within a range or finding the k-nearest neighbours. Consequently, there is lack of versatility concerning what we can search when it comes to a gigantic database. In this work, we propose Search Data Structure Learning (SDSL), generalization of the standard Search Data Structure (SDS) in which the machine has to learn how to search in the database. To evaluate ap- proaches in this field, we propose novel metric called Sequential Search Work Ratio (SSWR), a natural way of measuring a search's 's efficiency and quality. Fi- nally, inaugurate the field with the Efficient Learnable Binary Access (ELBA), a family of models for Search Data Structure Learning. It requires a means to train two parametric functions and a search data structure for binary codes. For the training, we developed novel loss function, the F-beta Loss. For the SDS, we describe the Multi-Bernoulli Search (MBS), novel approach for probabilistic binary codes. Finally, we exhibit the F-beta Loss and the MBS synergy by exper- imentally showing that functions of MIHash and HashNet and twenty times better than with another SDS based on the Hamming radius.
least twice as better than using the alternative loss
INTRODUCTION
In many applications, the machines need to perform many searches in a gigantic database where the number of relevant documents is minuscule, e.g. ten in billion. It is like searching for some needles a haystack. In those cases, considering every document is extremely inefficient. For productivity, the search should not consider the whole database. Traditionally, this is accomplished by building search data structure and seeking within it. Those data structures can take many forms. For example, there are tree-baset structures such the B B-Tree (Bayer & McCreight 1970), the k-d tree (Friedman et al.) (177), the R-Tree (Guttman 1984) or the M- (Ciaccia et al. 1997) to name few. In addition trees, KNNG (Paredes & Chávez 2005) build graph designed for the k-nearest. neighbour search. Later approaches improve on KNNG, both for construction and search time and for the search quality itself. In those lines, there is Efanna (Fu & Cai 2016), HNSW (Malkov & Yashunin] 2018) and ONNG ([wasaki & Miyazaki 2018). One of the most common types of search data structures the hash table. is useful that is implemented natively in programming languages such as Python (with the dictionary type). Hash table is often the main tool an application will use for efficiency. For example, from short and noisy song sample, Shazam (Wang et al.) 2003) can retrieve the whole song by using hash tables filled with well-designed fingerprints of each song.
Traditionally, the design of a search data structure was for particular type of search. For example, hash tables can retrieve documents very quickly, even in gigantic databases. However, the query must be equal to the key. This requirement makes the hash table not always applicable. For instance, the database is indexed by date and time and we seek all documents from a specific day, then might not be optimal to query every second of that day with equality search. B- B-er (Bayer & McCreight) 1970) was precisely introduced for applications where a range search is preferable (and faster insertion than dichotomic search is needed). Equality and range are far from being the only

---

Under review as a conference paper at ICLR 2021
types of search. For instance, the k-nearest neighbours is another well-studied type search. Also, the subset search is a more exotic example that occurs when every queries and documents are sets and when document is relevant if and only if it is subset of the query. As final example, the auto-complete function often uses a Trie data structure (De La Briandais 1959) to suggest the end of each word.
is easy not to realize how the problem of efficiently finding needles in a haystack was solved multiple times for specific applications. This is the ascertainment that make Search Data Struc- ture Learning (SDSL) a significant subject. Machine Learning has been a very flexible paradigm, whether by solving multiple NLP (Natural Language Processing) tasks with a unique Transformer (Vaswani et al. (017) or solving most Atari games with Reinforcement Learning (Mmih et al.. 20133) the capacity of a single learning algorithm to perform on multiple tasks is outstanding. Search Data Structure Learning aims at developing generic learning algorithms meant for multiple types of search. Furthermore, what makes document relevant need not to be described formally or even understood by human. It might be k-nearest neighbour with complex metric or something else altogether, the only thing we need for learning is a dataset. While we use the term "Search Data Structure Learning" for the first time, algorithms that fall into its paradigm already exist. The large rideo-hosting platform YouTube implements an SDSL algorithm (Covington et al.] (016)) for its recommendation system (the user being the query and the videos being the documents).
Not having a formalized definition of what makes a document relevant and relying on Machine Learning has its challenges, the most important being the evaluation. Traditional search data struc- ture, such as the hash table, the Trie, the B-Tree, are exact, meaning the documents retrieved contains all and uniquely the relevant documents. For comparing those exact search data structures, when possible, the comparison between two exact search data structures is made with the asymptotic time complexity (the O notation). However, when the search is not exact, it unclear how to com- pare structures with different efficiency and exactitude. The precision at Hamming distance of 2 an attempt to unify those two properties into a single measure specific to the context of binary encoding. However, as described below, it fails in many aspects. It might seem like it is up to the programmer to decide what is more important between the speed and the quality of the retrieved documents. For example, the recall-queries per second (Aumüller understand the trade-off between speed and quality. In section 3] we describe a reliable measure to evaluate the efficiency and quality simultaneously of any search data structure. This metric solidifies the Machine Learning subfield of Search Data Structure Learning.
al., 2017) helps to visually
This article presents the SDSL framework that brings two crucial generalization w.r.t. its predeces- sors (Li et al. 2011 Cayton & Dasgupta 2008). First, it allows for dynamic databases, i.e. datahases that might change or evolve after training. For example, it is plausible that company wants to de- sign and train a search engine ready for distribution to multiple clients without further training on each client's database. The current mindset is to retrain each time a new database is given; however, this is not feasible in many cases. Hopefully, this article motivates the research towards models that can generalize to never seen databases. Secondly, the previous framework does not support relative relations, i.e. when the relevance of a document w.r.t. a query depends on the other documents in the database. The most studied relative relations is probably the KNN task, which is relative since is impossible to know if document is in the k-nearest neighbour of query without knowing the other documents. In contrast, radius search is an example of what we call an absolute relation because it is possible to know if a document is relevant to a query only by looking at the query- -ocy-ede pair. In this work, however, we did not introduce relative relations only for KNN. Many interesting relative relation tasks exist; for example, another rather exciting example of relative relation is the multiple supporting facts:
A harder task is to answer questions where two supporting statements have to be chained to answer the question [...] where to answer the question "Where is the football?" one has to combine information from two sentences "John is in the playground" and "John picked up the football". (Weston et al. 2015).
In this work, we first introduce a general framework to formalize the SDSL task in which we present a novel metric to simultaneously evaluate the efficiency and quality of the search. Then, we inau- gurate the field of SDSL with Efficient Learning Binary Access (ELBA) (Section 4 that describes a family of models that use a traditional search data structure and parametric functions (c.g. neural networks) to create discrete binary code(s) for both the queries and documents. A reader familiar
2

---

Under review as a conference paper at ICLR 2021
with the field must appreciate the difficulty that has be overcome when dealing with (semi)- discrete structure. To instantiate ELBA, we concocted the F-beta Loss used for the training and Search (MBS), novel SDS technique designed for probabilistic binary codes. Fi- nally, for comparisons, we will instantiate ELBA with other loss functions and another SDS, namely the MIHash's loss (Cakir et al. 2017), the HashNet's loss (Cao et al. (017), and the Hamming Ra- dius Search[C.4] We will then experimentally show the F-beta Loss and MBS's ' advantage by putting in evidence their synergy.
2 RELATED WORK
In data structure terminology, the concepts of dynamic and static structures descrihe whether or not the structure can change via insertion, deletion or merge. In SDSL,, if the database(s) used for training are not the same as the one(s) used for evaluation, then the structure has to search for documents only seen once at insertion. From a Machine Learning perspective, this is known as One-Shot Learning task. For example, Matching Network (Vinyals al. 2016) tries to match never seen elements together. However, applying their technique would require a database scan. Hence incompatible with a gigantic database. In the same vein, soft addressing (or attention) is differentiable mechanism to select an element from many, thus compatible with gradient de- scent. Memory Network (Kumar et al., 2016), Neural-Turing Machine (Graves et al., 2014) and Transformer (Vaswani al. (017)) all use some kind of soft addressing. It is interesting for train- ing our models but cannot be used alone in SDSL. For the same reason as above, would require considering the whole database.
Finding the k-nearest neighbour is trivial with unlimited resources. In this field, the research focuses mainly on the efficiency of both the search and the structure's 's construction. The exact algorithms are as efficient in higher dimensions than a random search due to the curse of dimensionality. Conse- quently, the focus has recently been on approximate k-nearest neighbour. 'he search data structure developed are mostly tree-based, such as the k-d tree (Friedman et al. 1977) or the K-Means tree (Nister& & Stewenius 2006), and graph-based. such the KNNG (Paredes & Chávez 2005). Efanna (Fu & Cail (0166), HNSW (Malkov & Yashunin) (018)) or ONNG (Iwasaki & Miyazaki, 2018) just to name a few. good resource for comparing those approaches is the ann- ann-benchhark (Aumüller et al. (2017). In this work, we generalize the problem to conceive algorithms able to learn what to search efficiently.
Efficient Learnable Binary Access, described below, encodes queries and documents into binary vectors. this work, we will use neural networks as the encoders. Such encoders already exists in the literature. For example, CNNH (Xia et al.] 2014). DPSH (Li et al. 2015). DHN (Zhu et al.) 2016). GreedyHash (Su et al. 2018), PGDH Yuaa et al. 2018 HashGan (Cao et al. 2018 ADSH Jiang & Li 2018) or JMLH (Shen al. 2019), just to name few. Below we compare different loss functions, the F-beta Loss 4 the MIHash's 's loss Cakir et al. 2017) and HashNet's 's loss Cao et al. (0177).
Graph learning, introduced in Zhu et al. (2003) for semi-supervised learning, is a type of data struc- ture learning that has shown experimentally to be strong idea. Those models learn do inference from graphs, sometime by generating them first. Some approaches work with static graphs (static
structures) (Zhu al. 2003 Perozzi et al. 2014 Scarselli et al. 2008 Bruna al. 2013) while other work with dynamic graphs (dynamic structures) (Narayan & Roe 2018 Manessi et al. 2020
While this literature does not focus on retrieval, they learn compute using a data structure.
To put SDSL in contrast with the Learning to Search framework (Li et al. 201T). As mentioned in the introduction, it does not support dynamic databases and relative relation. It is possible to update the framework to deal with dynamic databases by taking an expectation over the databases in the retrieval quality Q(T) and computational cost C(T). However, it is not clear how to deal with relative relations because the selection function T(q, is a "matching function" that does not exist for relative tasks. Generalizing the selection function by allowing it to consider the whole database (i.e. with T'(gx)) does not work because T(g, X) could use the ranking function s(x; g) on every document and nothing would penalize such exhaustive strategies since the computational cost is the number of candidates. Nevertheless, this is not the main issue. As with the framework proposed in Cayton & Dasgupta (2008), the computational cost does not consider the retrieval cost but only the size of the candidates set (divided by the number of documents in the database for the
3

---

Under review as a conference paper at ICLR 2021
latter framework). Those frameworks fail quantify the work needed to retrieve the candidates. For example, while proposing the Learning to Search framework, the authors relied on timing to evaluate their model. The SDSL framework, proposed below, provides unique quantity that quantifies both the cost of retrieval and the candidates' quality simultaneously.
Finally, while not introduced such, SDSL algorithm is used in NLP. In this field, many articles attempt to accelerate the training and inference of the neural network based models, in which the main bottleneck is the normalization over a large vocabulary. [Morin & Bengio (2005) use pre- computed tree and train their model to travel from the root to leaf, where each leaf corresponds to a word. Doing so accelerates both training and inference. Latter, Mnih & Hinton (2009) proposed a way to learn the structure of the tree.
3 FORMALISATION OF THE PROBLEM
Let Q be the query universe, let U be the document universe, and let D be the set of databases, i.c. the set of all finite sets of documents, The task is formulated with set of relations corresponding to each database R = (Ro: Q + 2D D E M.. This is to allow the general case where the relation relative.
Definition 3.1. The relation set R. is absolute if there is a match function M Q U (True, False} s.t. Vq E Q DE D, d D, Míg, d) +> d E Rp(g) otherwise, we say it relative.
This definition can easily be generalized to the cases where each RD is probabilistic map by using probability instead of a truth value.
For the F-beta loss to be defined in Section 4 thus, only the query-document pair determines if the document is relevant. However, the rest of this formalization is for both relative and absolute relation sets.
we restrict ourselves absolute relation sets and
The mAP is a widely used metric in information retrieval. However, it does not consider the work done to perform the ranking. An SDS could compare the query every document in the database and have a good mAP. In SDSL, we want to monitor the quality as well as the efficiency of retrieval. The Recall Query per second (RQPS) (Aumüller et al. 2017) is also used in the ANN literature. However, it is not suitable for theoretical analysis since the results depend on the implementation and the hardware. It possible to generalize the RQPS by changing what quantifies the amount of work done for retrieval (to something else than the number of seconds). Nevertheless, the RQPS has a parameter (k) that limits the number of candidates generate. This parameter prevents a model from generating all documents in the database as its candidates, which would give 100% recall without any computation and, consequently, having an excellent score doing nothing. Ultimately, the parameter k is a fix to the flaw that the RQPS does not consider the precision. In SDSL, we want to legitimately compare models that might not generate the same number of candidates. To the best of our knowledge, the precision at Hamming distance of two (p@2) is the only proposal in the literature to consolidate the search's 's efficiency and quality without relying on the hardware and the implementation. Obviously, this metric has many limitations. First, it is only relevant when the model transforms the queries and documents into binary codes. More importantly, does not consider the recall quality. For example, a query should return several relevant documents but only one relevant document (and no irrelevant ones) are within a Hamming distance of two according to the model, the p@2 2 score would be maximal for this query even though the system has very poor recall. Another significant limitation is the fact that it does not weight the score w.r.t. the distance. In many contexts, the amount of work increases a thousandfold when comparing a perfect match (Hamming distance 0) and distance 2.
In this work, we present a generic metric for any SDSL task. We grounded the metric on a very pragmatic standpoint by asking what kind of strategy a programmer would use to find relevant documents in a database quickly. At first, one might consider a random search with a good matching function (e.g. neural network). However, if the database is enormous, this strategy will give poor performances. One could then consider filtering a significant portion of the database using a search data structure, but the retrieved documents might contain multiple false positives, decreasing the precision. We believe we can have the best of both solutions by combining them, first filtering a large portion of the database with search data structure and then using good matching function to filter
4

---

Under review as a conference paper at ICLR 2021
the retrieved documents. Finally, to evaluate if the search data structure is useful, the programmer could consider the cost of searching in the structure plus the cost of a random search in the retrieved documents versus the cost of random search in the whole database. This is the central idea of the Search Work Ratio, the precursor of the Sequential Search Work Ratio, both defined below.
Definition 3.2. relevance oracle an oracle capable of computing a document is relevant.
Definition 3.3. The relevance oracle cost, noted C(N, K, kt,, is the expected number of oracle's calls needed to find relevant documents within a set containing N documents where K are relevant, when doing random search without replacement.
Lemma 3.1. C(N, K, k) = k(N + () + 1). (Proof in appendix A
As mentioned previously, we do not intend for the search data structure produce the final results. Instead, another entity (e.g. program or a human) should refine the retrieved documents. In many applications, mainly when the relevance function is absolute. it is conceivable that this entity is nearly perfect or, at least, significantly more precise than the SDS. Consequently, we define the cost of finding relevant documents in a set of size N containing K relevant documents as the relevance oracle cost C(N, K, k).
As generalization, we can weigh differently when the oracle receives a relevant document versus when it does not. The weighting would consider real refinement entity's 's potential errors and put different values to the false positives and false negatives. For simplicity, in this work, we will not weight the calls to the oracle.
The Search Work Ratio (SWR) is the ratio between the work done using the SDS versus the work done without using the SDS. Consequently, SWR score of less than I implies that it is less costly to use the SDS and vice-versa. Furthermore, the SWR has a simple interpretation. For example, an SWR of 1/2 implies that using the SDS reduces the cost by factor of two.
Definition 3.4. Let D E ID, R E 2D, k E N. WD E I and d0 E 2P, then the Search Work Ratio is
SWR(D, R, k, Wo, da) C(1bol. 1ō0 n Rl, k) + wo C(ID), [R], k)
E RR
where D is a database, R is the relevant documents in this database, the minimum number of documents we want to find, wp E R is the cost of searching with the SDS, and óg is the candidates retrieved by the SDS. The cost could be any complexity measure, e.g. time or space. In this work, since we will work only with hash tables, wi will be the number of hashes computed. We assume that using the oracle has the same cost as computing a hash. The SWR has a significant flaw; requires that the SDS find enough relevant documents. Otherwise, it is not defined. We will now slightly generalize this definition using a relevance generator to avoid this issue.
It is not rare that an SDS can be slightly modified produce sequence of sets of candidates.. For example, an approximate tree or graph search often employs a limit of nodes in the exploration. is possible to modify those algorithms generate candidates with increasing number of nodes to explore.
Definition 3.5. Let D D. Re 2D, k w E RN and d E (2D)N s.t. min s.t. t N and U &, n R 2 k} exists, then the Sequential Search Work Ratio is
SSWR(D, R, k w, 5) C(0rl, 15 n Rl, k | n RD + |H| + Ei R
C(DD), [R]. k)
with H = -T 8, if and H =0 otherwise.
The SSWR's numerator corresponds to random search with the relevance oracle on the last gener- ated candidates set plus the cost of considering all previously generated candidates plus the amount of work for computing all candidates sets up to T. The SSWR uses the relevance oracle cost only over the last sets of candidates because the generator did not found enough relevant documents be- fore generating the last sets of candidates. Consequently, the previous sets of candidates was performed before asking the generator to yield more candidates. The SSWR account for this exhaustive search with the |H] term. Finally, the sets of candidates intended to be mutually exclusive because this will reduce the relevance oracle cost computed over the last sets of candidates and give better SSWR. However, it is not mandatory.
exhaustive search with the oracle in
5

---

Under review as a conference paper at ICLR 2021
Definition 3.6. The Search Data Structure Learning (SDSL) framework consists of minimizing the expected SSWR over generators (of sets) of candidates w.r.t database-query pairs. Formally, given work function W 9D, q H (Wo, Wi, "...)..) IN where w.r.t. a database E ID the goal of SDSL is to minimize,
Q and GD is generators
min ED SSWR(D, k W(GD.9), 9n(1))) g
We minimize the expectation over all databases to ensure the generator's quality even if the database changes, i.e. for dynamic databases. By letting the distribution over D to be deterministic, fall into the framework with a static database.
4 EFFICIENT LEARNABLE BINARY ACCESS
This section describes family of models to tackle SDSL tasks: the Efficient Learnable Binary Access (ELBA). It consists of two parametric families of function Fg and Fu (e.g. neural networks) called the queries and documents encoders, and a Multi-Bernoulli Search (MBS) data structure S that will be made explicit later. Any function from Fo and Fu must have their domain on Q and U, respectively, and their image in [0, 1]"h to be interpreted as the parameters of a Multi- Bernoull (in its canonical form). Precisely, ELBA is specified by the following triplet ELBA (Fo, Fu, S) with Fo = (fo Q > [o, 1j" E O2) and Fu {fo U + [0. 1 I E @w).
Note that in the particular case where Q U, it is possible to use the same function for the queries and the documents (ELBA = (F, S)). We call this the shared variant ELBA. As opposed to the unshared variant where the parametric families might be the same, but the parameters are free be different (e.g. the same neural network but with different parameters).
Multi-Bernoulli Search (MBS) data structure is key-value based data structure that implements insert and search. This data structure uses M back-end key-value based data structures compatible with binary vectors keys. The back-end data structures S1, S2, .... SM, must also implement insert(S, key, value) where S E {S1, S2, ..... S is the data structure into which we insert the value w.r.t the key. Similarly, the back-end structures must implement scarch(S, key), which must return the appropriate set of values. While the key given to the back-end data structures are binary vectors, the key given the MBS must the parameters of a Multi-Bernoulfi distribution of dimension n, i.e.
key = (TI, T2. Tn) 1].
For insertion, the MBS computes the M most probable outcomes of the might not be unique) and uses them as the keys for inserting in a back-end data structures. For searching, the MBS computes the T most probable outcomes of the Multi-Bernoully (which, again, might not be unique) and uses them as the keys for searching in each back-end data structures. Consequently, the search performs '' back-end searches. The pseudo-code is in the appendix B.2 Note that the insert method does not require T'. Consequently, we can make the insertions and then choose T. This fact makes possible the modification of the scarch to generate candidates every time it searches in a back-end structure. Finally, to conform with the SDSL's framework, it is possible to generate candidates by yielding candidates each time we search in a back-end structure.
(which
Computing efficiently the top-k most probable outcomes of Throughout this work, we will use the Hashing Multi-
Helti-BBrnnollii is not trivial. In the
appendix B we describe how Bernoulli Search (HMBS), implementation of the MBS that uses hash tables as its back-end data structures. An example of how inserting, searching and generating can be found in the appendix B.3
To implement ELBA, we need a means to select a function from each parametric family. As the parametric families, consider neural networks, which we aim to train with gradient descent. Consequently, we need a loss function. Thus in this section, we will describe the F-beta Loss, a novel loss function design to perform well with MBS.
'The Dalti-Bernoulli is random vector composed of independent but identical Bernoulli.

---

Under review as a conference paper at ICLR 2021
We will restrain ourselves to absolute relevance function. For this reason, will use dataset of the form [lg, d, r:)l== = (%: d, M(q. d)) The model will try to predict the Matching function M. We will denote the matching prediction function Ma.
Since the Multi-Bernoule Search requires the (canonical) parameters of the Multi-Bernoulli repre- sentation of the query {T] ) for search and of the document {m()²= ]==] for insert (with n the cho- random variables). it is primordial that the model
sen number of Bernoulli in the provides such quantity in its computational pipeline. Let f (g) x and (d) = x" be the para- metric functions for the queries and the documents, both implemented with neural network ending with a sigmoid. Note that, depending on the case, the two neural networks might or might not share parameters. Finally, since we want to create a synergy with Hashing need the bits to be all equal and only if the matching prediction function is one. Thus we define,
Search, we
Mo(g, d)
II m
m +
(1-x))(1
which is the probability of both Multi-Bernoulii random variables are equal according to the distri- butions { and (-:))-1
We define three essential quantities: the recall, the fallout, and the predicted matching marginal (pmm for short), respectively:
[Ma(g. di]. M [ola. d)). = Eg,d [Mala. a)}
En M(q.))
We can compute empirical averages to produce unbiased estimators of those quantities.
1 1+
Σ SE
Me(gn dd), S
Σ I EEI
1
Mo(gi, de),
mng qio + (1 98880-
where I+ and I are the sets of indexes for query-document pairs the dataset that match and do not match, respectively, and with q being the probability of having a matching pair. is also possible to derive an estimator for the precision po gTv with po qiv However, it is biased.
my
me
For numerical stability and because the gradients w.r.t re, 8p and mg are near zero when the training starts, we need to consider their logarithm for the loss function. Maximizing precision gives a model capable of discriminating between positive and negative pairs, but it leaves the recall untouched, and having a high recall is vital for the HMBS to find the relevant documents. Furthermore, only maximizing the recall induce the model towards constant Multi-Bernoulli distribution with entropy, i.e., independent of the input and where all the probabilities are near or 1. We tried maximizing the recall while minimizing the fallout, i.e. with a loss similar max, log(ra) A log(se). However, we found it extremely hard to optimize - there was no sweet spot for lambda. When the model's ' recall was sufficient, was because it collapsed to a constant function. Scheduling À to alternate between a small value and relatively high value has shown limited experimental success. In the end, we were looking for a tradeoff between the precision and the recall. The F-beta came naturally. However, since our precision estimator is biased, it is simpler to reparameterize the standard F-beta with the pmm using P4-
qre given us
ma
(1 + )gro
F8
with B R
3. + mg
For the above reasons, we considered the logarithm of the F-beta,
log Fe log((1 + (²)g) + log(re) log(g me) with 3 E I
However, if we replace the recall term by its estimator directly we will get the LogSumExp (LSE) w.r.t. log Mo(g,, d,) for E I+_ i..., log(fe) = LSE (log Me(g: de) / I+} which is known to act as soft maximum (not be confused with its gradient, the Softmax). Doing this will yield a near-zero gradient for the matching pairs with the lowest predicted matching value. would be problematic since those pairs the ones that need the most gradient.
7

---

Under review as a conference paper at ICLR 2021
3
8
6
6
3
8
Figure 1: In the first row are the queries and in the second row are the documents, Each query corresponds uniquely to one document. On the left, the task is easy, but on the right, it is not.
Instead, we propose an alternative estimator of the log F-beta, which we call the F-beta Loss, where we replace the LSE with the average logarithm of the predicted matching value.
log Po = c
1 |++
Σ 1E7+
log Molac d:) - log(q32 ma)
with 3 E R+ and = log(1 3 logg.
Note that it is simple to compute with numerical stability the logarithm of the sigmoid function. Most, if not all, Machine Learning libraries natively define this function.
EXPERIMENTS AND RESULTS
We performed all experiments on dataset build from MNIST (LeCun et al. 1998), which we call MoisyMnist. We do not intend NoisyMnist to be a challenging task but rather a tool to analyze the convergence properties and draw comparisons between each models' qualities. In this dataset, the document and query are MNIST images with value ranging from 0 to I with additive Gaussian noise (the value can consequently go below 0 and above 1). The mean and std of the noise is 0 and 0.2, respectively. The relevance function of NoisyMnist is absolute, and we define the matching function as follows: a query match with document if and only if their original MNIST image was the same before we added the noise. In figure 1 there are 6 examples of queries-documents pairs. For evaluation, We build a fixed database with 10K different images from MNIST not accessible while training. From those 10K, we randomly selected 1K to create the queries. Finally, we added the noise on each image (the query and their corresponding document do not share the same noise). In this evaluation database, there is unique document relevant for each query. It is one in ten thousand, making it proper database for SDSL.
We considered two alternatives for the F-beta Loss and one alternative to the MBS. For the F-beta Loss, we selected the loss function of MIHash (Cakir et al.] (2017) and the loss function of HashNet (Cao et al. 2017) because of their compatibility with with BLBA. More specifically, they both produce quantities that can be interpreted as the parameters of a Multi-Bernoulli, and they both can be trivially generalized to the unshared case. Furthermore, as an alternative MBS, we choose the Hamming Radius Search (HRS) described in appendix C.4, Combining the three losses with the two data structures creates six Efficient Learnable Binary Access models. We deployed each model in both the shared and unshared categories, for a total of twelve scenarios.
Training was run 5 times for each model, and the top sets of parameters w.r.t the SSWR were selected for a total of 25 sets of parameters for each of the twelve models. All the values provided are the average of those 25 points. Each training consisted of 100K batches of size 32, which was plenty for all models to converge. At each 500 batches, we performed an evaluation giving us 200
sets of parameters to select from. We performed all evaluations using the same fixed set 10K validation documents and a corresponding fixed set of IK validation query described above. Those documents and queries were never seen while training. All networks are ResNet18 (He et al., 2016) adapted to MNIST, i.e. the first convolution takes from one channel with stride and the last linear layer output a vector of size 64 (for 64 bits). The hyperparameters and training schedule can be found in the appendix C Finally,
halting for all six models is describe below.
8

---

Under review as a conference paper at ICLR 2021
Table 1: The comparative table of SSWR
Unshared
Shared
Models
HRS
HMBS
HRS
HMBS
F-beta
0.3798
0.0169
0.1636
0.0035
MIHash
1.3559
1.8907
0.2119
0.0083
HashNet
1.4162
2.0001
0.2536
0.2828
When using generators iterating over binary codes, such as HRS and MBS, erucial to halt the iteration before it finishes. For example, for 64 bits, there are 261 possible hashes, which is certainly larger than any database. In those cases, it does not make sense to compute every possible hash. Halting is the mechanism that decides when to stop relevance generator and produce the database's 's remaining document as the final candidates set. Note that, when halting, the SSWR is always greater than one. In all experiments with HRS, used halting of 2081. It corresponds to generating every document with binary codes within a radius of two from the query's 's code (for 64 bits). In this case, halting afterward is arbitrary since the next 41664 codes (distance of 3) come in no particular order. Finally, in all experiments with HMBS, we use a halting of 5001, which corresponds to stopping when the amount of work done exceeds the expected amount of work without an SDS, i.c. C(10000, 1, 1).
Table D shows that F-beta (from this work) outperforms MIHash and HashNet in both unshared and shared categories. Noteworthily, MIHash and HashNet fail in the unshared categories. While Hash- Net successfully produces binary codes with lower Hamming distance for positive than negative pairs, the distance is way too high to be used with hash tables. MIHash, on the other hand, only push towards increasing the mutual information between the Hamming distance and whether or not the pair matches. It implies that there is no (explicit) pressure towards having small Hamming distance. The synergy between the loss function and shared parameters is why MIHash and Hash- Net produce low Hamming distances for positive pairs for the shared problem. The found solutions for the unshared problem are not available when the queries and documents networks are the same. Parameter sharing acts a colossal regularization. Those poor results suggest that both MIHash and HashNet are constrained to similarity search. Making F-beta the superior loss function for ELBA with hash table based SDS.
On the other hand, HMBS's results are far superior to those of HRS. In the case of shared F-beta, they are 46 times better. The only case for which not true is for shared HashNet. However, both of those models are not competitive. The fat tail of its Hamming distances distribution is at cause. In our experiments, we noted that varying the halting did not seem change the results drastically. Additional figures provided in the appendix D might convey a more intuitive understanding of the contrast between the different scenarios.
6 CONCLUSION AND FUTURE WORK
In this article, we proposed a novel and practical field of Machine Learning called Search Data Structure Learning, for which we propose natural metric, the SSWR. We inaugurated this field with a new family of models, the Efficient Learnable Binary Access, which we instantiated with the F-beta Loss and the MBS that outperformed multiple alternatives, reducing by least factor of two the SSWR. We cannot overstate the importance of F-beta in this project. The capacity to obtain convergence on discrete output without being caught in local minimum is powerful tool. In NLP, the F-beta led us to several exciting breakthroughs when learning semantically rich discrete embedding for words. The fact that studying SDSI. led to breakthroughs other domains is, for us, an attestation of its significance.
Furthermore, we plan to extend the formalization to consider insertion, deletion, dependent queries, and dependent retrieved documents in future work. Such generalization could be useful for tasks like dialogue modelling or question answering. Also, in this work, the halting procedure was sim- plistic. In the future, we are interested in working with models that can decide when to stop based on the query and the retrieved documents. Finally, we are eager to work with non- hashing- based approaches, such trees or graphs.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmark- ing tool for approximate nearest neighbor algorithms. In International Conference on Similarity Search and Applications, pp. 34-49. Springer, 2017.
I Bayer and E McCreight. R. organization and maintenance of large ordered indices. In Proc. ACMSIGFIDET Workshop on Data Description and Access, Houston, Texas, Nov, 1970.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 2013.
Fatih Cakir, Kun He, Sarah Adel Bargal, and Stan Sclaroff. Mihash: Online hashing with mutual information. In Proceedings of the IEEE International Conference Computer Vision, pp. 437- 445, 2017.
Yue Cao, Bin Liu, Mingsheng Long, and Jianmin Wang. Hashgan: Deep learning to hash with pair conditional wasserstein gan. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, pp. 1287-1296, 2018.
Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Philip S Yu. Hashnet: Deep learning to hash by continuation. In Proceedings of the IEEE international conference on computer vision, pp. 5608-5617, 2017.
Lawrence Cayton and Sanjoy Dasgupta. A learning framework for nearest neighbor search. In Advances in Neural Information Processing Systems, pp. 233-240, 2008.
Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An cient access method for similarity search in metric spaces. In Proceedings of the 23rd VLDB conference, Athens, Greece, pp. 426- 435. Citeseer, 1997.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM conference on recommender systems, pp. 191-198, 2016.
Rene De La Briandais. File searching using variable length keys. In Papers presented at the the March 3-5, 1959, western joint computer conference, pp. 295-298, 1959.
Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), (3):209-226, 1977.
Cong Fu and Deng Cai. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.077 072288. 2016.
Alex Graves, Greg Wayne, and Ivo Danihelka. arXiv:1410.5401 2014.
Neural turing machines. arXiv preprint
Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pp. 47-57, 1984.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv: 180000355 2018.
Qing- Yuan Jiang and Wu-Jun Li. Asymmetric deep supervised hashing. In Thirty-Scoond AAAI Conference on Artificial Intelligence, 2018
Ankit Kumar, Ozan Irsoy, Peter Ondruska, Mohit Iyyer, James Bradbury, Ishaan Guirajani, Victor Zhong, Romain Paulus, and Richard Socher. Ask me anything: Dynamic memory networks for natural language processing. In International conference on machine learning, pp. 1378-1387, 2016.
10

---

Under review as a conference paper at ICLR 2021
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25 2324, 1998.
Wu-Jun Li, Sheng Wang, and Wang-Cheng Kang. Feature learning based deep supervised hashing with pairwise labels. arXiv preprint arXiv: 2015.
Zhen Li, Huazhong Ning, Liangliang Cao, Tong Zhang, Yihong Gong, and Thomas S Huang. Learn- ing to search efficiently in high dimensions. In Advances in Neural Information Processing Sys- fems, pp. 1710-1718, 2011.
Yury A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 2018.
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. Pattern Recognition, 97:107000, 2020.
Andriy Mnih and Geoffrey Hinton. A scalable hierarchical distributed language model. In Ad- vances in neural information processing systems, pp. 1081-1088, 2009.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1r 1312.5602, 2013.
Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In Aistats, volume 5, pp. 246-252, Citeseer, 2005.
Apurva Narayan and Peter HO'N Roe. Learning graph dynamics using deep neural networks. IFAC- PapersOnLine, 51(2):333-433 2018.
David Nister and Henrik Stewenius. Scalable recognition with vocabulary tree. In 2006 IEEE Com- puter Society Conference on Computer Vision and Pattern Recognition (CVPR'06, volume 2, pp. 2161-2168. leee, 2006.
Rodrigo Paredes and Edgar Chávez. Using the k-nearest neighbor graph for proximity searching in metric spaces. In International Symposium String Processing and Information Retrieval, pp- 127-138. Springer, 2005.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Yuming Shen, Jie Qin, Jiaxin Chen, Li Liu, Fan Zhu, and Ziyi Shen. Embarrassingly simple binary representation learning. In Proceedings of the IEEE International Conference on Computer Vision Workshops, 2019.
Shupeng Su, Chao Zhang, Kai Han, and Yonghong Tian. Greedy hash: Towards fast optimization for accurate hash coding in cnn. In Advances in Neural Information Processing Systems, pp- 798-807, 2018
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008. 2017.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, pp. 3630-3638, 2016.
Avery Wang et al. An industrial strength audio search algorithm. In Ismir, volume 2003, pp. 7-13. Washington, DC, 2003.
11

---

Under review as a conference paper at ICLR 2021
Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. Towards ai-complete question answering: A set of prerequisite toy tasks. arXiv preprint arXtv:1502.05698 2015.
Rongkai Xia, Yan Pan, Hanjiang Lai, Cong Liu, and Shuicheng Yan. Supervised hashing for im- age retrieval via image representation learning. In Twenty-eighth AAAI conference artificial intelligence, 2014.
Xin Yuan, Liangliang Ren, Jiwen Lu, and Jie Zhou. Relaxation-free deep hashing via policy gra- dient. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 134-150, 2018.
Han Zhu, Mingsheng Long, Jianmin Wang, and Yue Cao. Deep hashing network for efficient simi- larity retrieval. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912 1229119,44 2003.
A THE RELEVANCE ORACLE COST
Formally, let S be set of documents containing S N relevant documents. From this K ele- ments, we want to find at least k < K elements. We want to compute how many calls in expectation are needed to find those elements if we sample from S uniformly without replacement. We will denote this expectation C(N. K, I))
Let ( ; N, K, n) be the Hypergeometric Distribution with parameters N, K, n. This distribution gives the probability that from a set with N documents from which K are relevant, we sample exactly relevant documents in n uniform trials without replacement.
G(k; N, K,n) = (HEK
Let P(n: N, K. be probability distribution, defined below, with parameters K, k. This gives the probability that from set with N documents from which K are relevant, it takes n uniform trials without replacement to get precisely ie relevant documents. We have,
K (k N (n (n-1)
P(n: K,K,K) G(k N, K,
which the probability that we have relevant documents in trials multiplied by the probability that we sample a relevant document in set with N - (n 1) documents from which K (k- 1) are relevant.
Finally, the expectation of P(nn: N, N,K, k) yields the wanted measure. Le. if ~ P(:; K,K. then.
N C(N, K, E = Σ
N k K +
nP(n; N,K,A)= =
n
with the last equality shown below A.I Lemma A.1. X ~ P(:; ; N, K, k) then,
+
X
K +1
12

---

Under review as a conference paper at ICLR 2021
Proof.
with A B 2 b and A > B all natural numbers.
E
X =
nn(;; k))
n=
N N-(K-K) k)
Σ
nP(n: k,)
remove zeros
n=k
(-(K-k)
ng(k 1 N, K,K,n K (k: 1)
Σ
(n 1)
N-(K-R) R)
(N-K) (- n-
K
K - (k 1)
(n 1)
N K 8)
N K) K (k-1)
(A) A A
n n-k
with
n
N (n
a- A a
a
m=
N-n+1
N (K (K-R)
(M=
n=
N-(K-N
(8) (A-B)
(A-a)
Σ
with
n=
N-(K-K)
K
(N-
N n
k
K k.
a variant of Vandermonde's identity
k
N
with (A+1) a 1 a a
A+1 (A)
(A)
(K)
N +1 (N+1)
K K11
B TOP-K MAXIMAL MULTI-BERNOULLI OUTCOMES
Let b, be independent and non-identical Bernoulli random variables with probability to be one. Let 2; the most probable outcome of and let p; be the probability that b, be the most probable outcome (b: = 2,) i.e.
{
m > 1/2
T > 1/2
=
otherwise
1
otherwise
note that is always greater equal than 1/2. The theorem
B.2 gives us the following result.
P(b=o) > p(b-a)
log(p:)
log(1 ps) <
log(p:) log(1 ps)
This implics that finding the Top-K Minimal Subset Sum of A {az, 0g an with a, log(p:) - log(1 p.) 2 0 will yield the Top-K Maximal Minimal Subset Sum problem can be solve using standard programming techniques. The pseudo-
Outcomes. The Top-K
code for the reduction is in the appendix B.2
13

---

Under review as a conference paper at ICLR 2021
B.1 REDUCTION TO TOP-K MINIMAL SUBSET SUM
Lemma B.I. Let Ps E 00 11. E 1) and by E {0, for E {0, 1, n) then
p (1 -a)
di (1 p.) p,))=b;
Pi
[=1
==1
1
0/ - ps)
b: (1 p.)
P.
P:
1=1
Proof. Let 1+ = 1i i N, isism, = b,) and let /+ =
N, 1 1si5 S n, a: # bz
we have,
n
RL p:) 1=) II Pj (1 p:) l-b
Pi (1 1-a
II
Pi (1 p:)) 1-a: 1:)'=a;
II iEI+
by
(1 ps)
II SE1
11 p.))
P
IE/+
NET
Ps (1 p.) 1-a
II iET-
P;
by
(1-p:)²
1-:)-bi
P.
1-b:
- pi)
II P
1-02 (1 ps)
since ViE ET, 0, -
iET
iET
Pi
by (1 p,)
II NET
(1 p:)
4: (1 p.)
Pi 1-a; (1 )
SEfT
KEI
iE7
by (1 - pz)*
<
P1
0. (1 p2)
1
1=1
Theorem B.2. Let b be Multi-Bernoulli of parameter J0, 11th and let
[1 >12>1/2
1/2
otherwise
Pi
T
otherwise
then, for any {0, 1 and {0, 10,13" 13"h we have
P(b=x) P(b-y) + log(p.) log(1 pi)
log(p.) log(1 p:)
14

---

Under review as a conference paper at ICLR 2021
Proof. For notational simplicity, let 2; @ and let Us @ 22 (with ① being the exclusive or)
P(b=x) > P(b=y)
P(b:=z
P(b,=y))
since the Bernoulli independent
21 (1 - -T:)'=
1=1
i=1
Pr 1--2 - pp)
D1 501 ps)
proved by cases (T; > 1/2 and n; S 1/22
1=1
P (1 pi)
Ri (1 p.)
by lemma B.I
Ty log(p;) (1 x4.) log(1 - pi) Σ Ue log(ps) + (1 -.)))log log(1 pc)
Ei (log(p:) - -lo((1 - -p:)) + log(1 - -Pi) <
1=1
Σ Is (log(p:) - log(1 - pp)) + logg111 - p.)
n
Te (log(p:) 1og(1 pi)) <
Di (log(p;) -oogll pi))
log(p;) log(1 pi) <
log(p;) log(1 ps)
S.L
S.t.
Remark. The case where m, is exactly one zero for some i can be trivially taken into account by setting the bit to the only possible value. All outcomes that are not generated will have probability
B.2 ALGORIHTS
Search Data Structure insert Require: Int n, Int M, SDSArray[M [M] S. Reaalrrayy [n] key, Object value outcomes Top-K Maximal Multi- Belti-Berroullii Out,omes(M,, n, key)
Algorithm
for i {1, .... M) do
insert(S; outcomes,, value)
end for
Algorithm 2 Multi-Bernoullh Search Data Structure- scarch
Require: Int n, Int M, Int T, S.SDAArra(M] S, RealArray(1) key values +- set() outcomes +- Top-K K Maximal Multi-Bernoulli Outcomes(T, n, key)
for E (1, ... T)} do
for i E {1, values + values U search(S,, outcomes,)
M) do
end for end for return values
15

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Top-K Maximal Multi-Bernoulli Outcomes
Require: Int k. Int n, RealArray [n] π
I: f- SinaryArray (r]
2: < RealArray n
3: f- RealArray/n
4: for = 1, ...., 72 do
5: if m; 1/2 then
6:
2i (-1
7:
pt f- πı
8:
else
9:
2,
10:
f 1 Ti
end if
12:
log(p;) log(1 pt) end for
14: outcomes < BrraryArraylk x n]
15: index t Hogg&WniimaStbbeeSSunnneees
n, a)
16: for j 1, ...., 3 do
n do 18: if indexes; then
17: for i =
19:
outcomesji + 1-
20: else
21:
outcomesji + 24 end if
23: end for
end for
25:
return outcomes
B.3 HMBS EXAMPLE
In this example, the number of bits in the Multi-Bernoulli is 3. the number of back-end data structures is M 3, and the number search keys T = 2. Since this a Hashing Multi- Bernoulli Search data structure, the M 3 back-end structures will be hash tables; will call them H1 H2 and Hy.
Let say want insert document with the following key,
= (0.3, 0.1,
first need to compute its M = most probable outcomes. Here they are in order:
(0,0, 1), (1,0, 1), (0,0,0)
then we will insert the document in H, using the most probable outcome as the key. insert the document in Hy with the second most probable outcome as the key and insert the document in Ha with the third most probable outcome as the key.
Now, say we have two other documents insert with the following keys, respectively:
n² (0.7,0.9, 0.2), 3a (0.3, 0.2,0.2..11 0.1).
Here are their M 3 most probable outcomes, respectively:
(),, (,, (1, 1, and (0, 0, 0), (1,0,0), 10,
We will then insert both of them in the M hash tables like did for the first document.
To search in the HMBS given query π (0.1, 0.6, 0.2), we first need to compute its T = 2 most probable outcomes:
(0, 1. 0), (0, 0, 0).
We will then search in the hash tables with these T 2. doing a total of TM = 6 search in the back-end structures. These searches will find all of the three documents since the first document
16

---

Under review as a conference paper at ICLR 2021
is in H3 with the key (0, 0, 0), the second document is in H2 with the key (0,1,0) and the third document is both in H1 with the key (0, 0) and in H3 with the key (0, 1,).
To generate documents in the SDSL's framework, do not need the parameter T. However, might want to halt before considering all possible outcomes of the query. With the same query as above, say want to generate document but halt after the fifth hashes, i.e. after doing 5 searches in the back-end structures. We will first generate the most probable outcome (0, 1. and search in Hi; however, will find nothing. We will then try the same outcome in H2 and find the second document, which we will yield. Then we will try the same outcome in H3 and find the third document, which we will yield. After this, we will compute the second most probable outcome (0, O, 0) and search in H1 to find the third document again; thus, we will do nothing. After we will try the same outcome in H2 and find nothing. Finally, we will halt since we computed hashes, ultimately never finding the first documents. Note that if there were multiple documents simultaneously, we would have yielded them together as set.
C EXPERIMENTS' MODELS
C.1
FBETA
For the F-beta model 4 ramping for the B hyperparameter using this equation,
32 & i
32
if < 10K
log2 81 =
ToK
8 otherwise
for each batch i 0, .... 100K.
C.2 MIHASH
MIHash Cakir et al. (2017) is based on the mutual information
I(X Σ P(K-z, Y=z) log ( P(X=2, Y=2)
(((x=))((Y=s)
ZEQ
and generalization of the Hamming distance,
1 d(z, y) マ/ (n x. y)
for x and y in RR. Note that if i and y in {0, 1)ah d(2xr 1, 1,2y is their Hamming distance.
Lets the above notation, i.c. let (g( parametric query and document functions (in the original article, they uses the same function for the queries and the documents). Let X and Y be two Malti-Bernoulli of dimension with parameters n and r" respectively. Finally, with H d(2X - 1, 2Y - 1), they aim to maximize,
Tº E [0, and f%
nd E [0, 1]" be the
I(H, d))
To allow gradient descent, they use differentiable histogram binning, i... they approximate P(H=k M(q, 1)) with
P(H=k MMg. d)=
Σ deb +ES+
[++
with
d (k: (k
if if [k: - 1,
8
(k (k-1)-d
if d; E kk: k + +1] otherwise
and d, = d(2r% 1, 2n 1). Similarly they estimate P(H=k Mig. d)= and P(H=k) to compute the mutual information.
17

---

Under review as a conference paper at ICLR 2021
C.3 HASHNET
HashNet Cao et al. (017) optimize an increasingly closer to discrete sequence of tasks to alleviate the challenge of solving discrete task with differentiable methods. It is possible frame their approach entirely with sigmoids but it is is simpler to use the tanh function as in the original article. Let Netg (4) = logits & IR" and Netg (d) logits" E th be the parametric query and document functions before activation. Let 00 (q) = tanh ((Net((2) and de (d) tanh (#Nott (d) be the activated functions. Note that,
96 (g) +1 f8(1) (q)
5 ( +1 f (d)
2
2
For simplicity, let of = -6(()) and g: = 90 (d,). In their work they modelize the matching random variable with,
M(gi, d,) Ber (a (a 9f ))
This gives,
P(M(g: d.)=)) a (a of )() (1 a (ax of +4)
Finally, they train the model with the (weighted) negative log-likelihood.
J; = wi (log + exp (a of ,(')) m,a of 9
with a positive real number useful when match and non-match are unbalanced. In the following experiment we ignored this term since the task way to unbalanced and adding a weighting term would break the loss function.
The term, the tanh, is first This process repeats ten times, creating a sequence of of increasingly harder optimization which, if repeated infinitely, would converge discrete optimization.
and then increased when convergence criteria obtain.
lim tanh(3r) sign(x) 8000
In all experiments, 0.2 for the sigmoid to have enough signal in the range [-32, 32].
C.4 HAMMING RADIUS SEARCH
The Hamming Radius Search (HRS) is naive approach quickly find documents indexed with a binary code which have low Hamming distance (the radius) to a particular binary code (the query). For insertion, we map each document's binary code the the document using hash table. For searching, we compute all binary codes at distance than 0 (i.c. only the query) and use the hash table, then do the same for distance up r, the radius.
The number binary codes to consider grow very quickly w.r.t to the radius. For example, at radius 2 with 64 bits codes, the number of codes to consider is 2081.
64
64
64
+
2081
2
and for the radius 3 we there is 43745 codes to consider. Radius would not make sense for database of 10K elements as the last 41664 elements comes in no particular order. This is why we consider for the following experiments 2081 hash before halting for Hamming Radius Search.
18

---

Under review as a conference paper at ICLR 2021
D SUPPLEMENTARY FIGURES
Table 2: The comparative table of SSWR's Halting Percentage
Unshared
Shared
Models
HRS
HMBS
HRS
HMBS
Fbeta
22.51
0.20
8.64 %
0.00
MIHash
92.72 %
92.19 %
11.81 %
0.10 %
HashNet
100.00
100.00
16.14 %
12.88
Aug Fbett J-MBS-SSWR=0 01.69)
MiHash [HMBS-SSWRa11] pain
Hashlett JHMBS HIMBS-5WHR=221 0001]
posttive regative
postiic
regathon
negatthe
3.5
0.5-
0.5
0.
0.7
02
012
0.0
Avg Shareed-beet [HiMBS SSWR-0 00355
Avg Shered--Miftehh [HMBS Sww.S-SWWWSS... 00033
Shaned-tteshhte [HKBS- S---S------------ 2020)
pasalive nogathee pairs
negative pains
regative pa
Vf
0.2
0.2
0.2
0.1
0:1
0.3
0.0
Figure 2: The average Hamming distance of the 25 models of each 6 HMBS models w.r.t. the positive (matching) pairs and negative (non-matching) pairs. Using the fixed 10K documents and 1K queries, creating 1K positive pairs and 9999K negative pairs for which we computed the Hamming distance.
lbbt
Shared- beta
Shered-Millash
0.0070
#totfee-1
#rstles-3
0015
etatles-3
authow?
0.04
0013
Prables-16
0.0035
#1s
0012
etalles-16
0.0050
0013
0015
0/010
0.00
0.26
0.0055
0.00
2000
4002
6000
5000
10000
2200
4000
6000
2000
10200
2000
4000
6000
8000
10000
Figure 3: The average SSWR Curves W.r Halt number for Fbeta, Shared-Fbeta and SHared- MIHash. The colored area is =0.0IxSTD of the respective curve. The range of the axis is changing throughout each graphs, this could be misleading when comparing the STD. As reference, the av- erage STD is 0.1959, 0.0374 and 0.0864 for Fbeta, Shared- -beeta and Shared-MIHase respectively.
19


Reviews:
[{"review_id": "w2qzaLJ1EOD", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new objective to learn representations that allow for efficient and accurate search with the Multi-Bernoulli Search data structure. The motivation for such a scheme is strong and the preliminary empirical results demonstrate the utility of using the proposed representation learning objective and the data structure. \n\n\nHowever, I am currently leaning towards a reject because of two main reasons: The first being the clarity of the presentation in the paper that makes it hard to identify (i) novel contributions, (ii) key algorithmic and technical details -- the main paper is supposed to be somewhat self-sufficient; with the current version, it was significantly hard for me to follow through the presentation even when repeatedly referring to the supplement. The second reason is the lack of positioning of the proposed scheme/objective/data structure to a long line of research on the use of machine learning (with novel metrics/objectives and data structures) for search, including the learning of space partitioning trees [A, B, C], locality sensitive hashes [E] and representations [D] -- it is quite possible that the proposed scheme is solving a different and/or more general problem but I believe it would be useful to connect this \"Search Data Structure Learning\" to the existing work on \"Learning to Search\".\n\n\nBeyond the aforementioned high level comments, please find the following specific comments/questions that should be addressed:\n\n- The set of relations $\\mathcal{R}$ and the per-database $\\mathcal{R}_D$ could use further motivation as to how they relate to search and/or relate to the task of learning search data structures. \n- It is not clear why the distinction between \"absolute\" and \"relative\" is necessary in the context of the problem being targeted in this paper.\n- The SSWR definition is unclear to me and can use more exposition. It is not clear that $\\delta_t, t = 1, \\ldots, T$ is a sequence of sets. Also, it is not explained why the oracle costs are only incurred for the final $\\delta_T$ and not all intermediate ones (unless $\\delta_{t-1} \\subseteq \\delta_t$) or to the complete $\\cup_{i=1}^T \\delta_t$.\n- At the end of section 3, after presentation of SSWR, it is not clear why we are minimizing for a search sequence generator $\\mathcal{G}$ that is aggregated over database-query pairs $(D, q)$ -- wouldn't we learn a data structure per database (as is done for data structures used for nearest-neighbor search)? Can this be clarified, and if it is deliberate, please motivate the need and advantage of learning across databases.\n- The algorithm description is very hard to follow -- there are M back-end data structures and also the learned representation is used to generate M probable back-ends to insert in and T probable back-end to search from. It is not clear how the search involves $T$ passes over the $M$ back-ends. It would be good to clarify in the main paper that the \"outcomes\" are keys for each backend and all $T$ keys are tried in all $M$ back-ends.\n- How are we leveraging multiple databases as shown in the previous loss function?\n- The halting mechanism requires better presentation and clarification. It makes intuitive sense. But the presentation of the training algorithm (at least in the main paper) seems insufficient to provide enough context about the specifics of the halting mechanism.\n\n\n\n[A] Li, Z., Ning, H., Cao, L., Zhang, T., Gong, Y., & Huang, T. S. (2011). Learning to search efficiently in high dimensions. In Advances in Neural Information Processing Systems (pp. 1710-1718).\n[B] Cayton, L., & Dasgupta, S. (2008). A learning framework for nearest neighbor search. In Advances in Neural Information Processing Systems (pp. 233-240).\n[C] Dong, Yihe, et al. \"Learning Space Partitions for Nearest Neighbor Search.\" ICLR 2020.\n[D] Sablayrolles, A., Douze, M., Schmid, C., & Jegou, H. (2018, September). Spreading vectors for similarity search. In International Conference on Learning Representations.\n[E] Wang, J., Liu, W., Kumar, S., & Chang, S. F. (2015). Learning to hash for indexing big data -- A survey. Proceedings of the IEEE, 104(1), 34-57.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "sdI5n-45XLQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed Search Data Structure Learning (SDSL), which they claim to be a generalization of the standard Search Data Structure. They also present a new metric called Sequential Search Work Ratio (SSWR) to evaluate the quality and efficiency of the search. They introduced a new loss called F-beta Loss, showing their algorithm is better than two previous results, MIHash (Cakir et al. 2017) and HashNet (Cao et al. 2017).\n\nI appreciate the key message the paper is trying to convey: we need the formal definition or mutual agreement on the problem as well as the correct evaluation metrics to push forward a research area. However, I have several major concerns about the contribution of this paper. \n\n1. I do not see a formal definition of SDSL. Definition 3.1 is just a definition of matching and non-matching relations. \n2. What is new in the metric defined in Definition 3.4? The denominator is constant for all search methods. C(.,.,.) is the cost of re-ranking, and w0 is the cost of searching (filtering the candidate). \n3. There is no theoretical or empirical comparison/evaluation of the proposed metric. The calculations in Appendix A are very standard calculations. It is unclear about the innovation of this metric from a theory perspective. In experiments, the authors directly use SSWR, and there is no justification on why this is the right metric.\n\nBefore proposing the new loss, etc., I suggest the authors could go back and justify the metric's effectiveness. Otherwise, it is hard to conclude if this paper has made any progress.\n\n=========================================\n\nThanks for the rebuttal and revision. My first concern has been addressed. However, I still found the proposal lack empirical or theoretical proof, so I am not convinced the contribution is principle enough. I decide to keep my original score.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "cRftJDEmlT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis article presents a new evaluation metric that improves upon hamming distance of two. Meanwhile, a new F-beta loss is proposed with advantages over other learn to hash methods in this evaluation metric. \n\n\n\nStrength:\nA new formulation on both evaluation metric and a new loss function\n\n\nWeakness:\n1. Claim: In the introduction of the paper, different data structures such as graph-based Efanna, HNSW, and ONNG. However, in the following sections of the paper, the author does not discuss the possibility of SWR pr SSWR on these methods. Is SSWR only designed for binary codes based information retrieval?\n2. Definition of cost: In Appendix A, the cost is estimated by how many calls in expectation\nare needed to find those k elements if we sample from S uniformly without replacement. Is there any justification for why we assume the k elements by uniform sampling? In hashing based retrieval, the sampling is based on a distribution with PDE monotonic to the distance [1]. In this case, is the cost estimated correctly?\n3. Comparison with other evaluation metrics: Is there any discussion of SSWR with evaluation metrics other than p@2. For instance, mAP, queries per second(QPS), and speedups over brutal force search. Is higher QPS or higher speedups over brutal force equivalent to higher SSWR?\n4. Experiments: This paper only presents results in image search settings.  Is there more comparison of f-beta loss in different search settings? For instance, (1) ANN search with l2 or cosine similarity. (2) Maximum Inner Product Search (3) Cross-modal retrieval such as text-image search.\n\n[1]Mutual Information Estimation using LSH Sampling https://www.semanticscholar.org/paper/Mutual-Information-Estimation-using-LSH-Sampling-Spring-Shrivastava/7241d1e839fdb69f7f0cc70220ad055e8900946c\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_NaBhYj9qy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is generally well written, and the authors target on an important and challenging problem of learning how to search. Search is a complex problem, and people designed various data structures to handle different kinds of search problems. The authors generalize these searching data structures by search data structure learning. The idea is novel and very interesting.\n\nThen, the authors design SSWR metric evaluate the efficiency and quality of the search process. And the authors design ELBA(Efficient Learning Binary Access) by proposing a novel loss function and neural networks to create a discrete binary code(s) for both the queries and documents. And the authors conduct several experiments on NoisyMnist dataset to compare with several methods to show the advantage of the proposed framework.\n\nMNIST dataset is a simple and small dataset, so more challenging datasets (such as SIFT-1M and GIST-1M) used in the search community are suggested to make the paper more convincing.\n\n=======================\n\nAfter reading all the review comments and rebuttals, I would like to change my score to 4. \nThe paper is interesting, but more detailed analysis and experiments are needed to make the work more clear and convincing.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses an interesting problem and all reviewers agree.  Most reviewers found the paper difficult to understand and it was hard to see the novel contributions.    The paper will need a significant revision before publication.
Decision: Reject