The 2023 Big ANN Challenge, held at NeurIPS 2023, focused on advancing the state-of-the-art in indexing data structures and search algorithms for practical variants of Approximate Nearest Neighbor (ANN) search that reflect its the growing complexity and diversity of workloads. Unlike prior challenges that emphasized scaling up classical ANN search (Simhadri et al., NeurIPS 2021), this competition addressed sparse, filtered, out-of-distribution, and streaming variants of ANNS. Participants developed and submitted innovative solutions that were evaluated on new standard datasets with constrained computational resources. The results showcased significant improvements in search accuracy and efficiency, with notable contributions from both academic and industrial teams. This paper summarizes the competition tracks, datasets, evaluation metrics, and the innovative approaches of the top-performing submissions, providing insights into the current advancements and future directions in the field of approximate nearest neighbor search.

We study hybrid search in text retrieval where lexical and semantic search are fused together with the intuition that the two are complementary in how they model relevance. In particular, we examine fusion by a convex combination of lexical and semantic scores, as well as the reciprocal rank fusion (RRF) method, and identify their advantages and potential pitfalls. Contrary to existing studies, we find RRF to be sensitive to its parameters; that the learning of a convex combination fusion is generally agnostic to the choice of score normalization; that convex combination outperforms RRF in in-domain and out-of-domain settings; and finally, that convex combination is sample efficient, requiring only a small set of training examples to tune its only parameter to a target domain.

Maximum Inner Product Search or top- k retrieval on sparse vectors is well understood in information retrieval, with a number of mature algorithms that solve it exactly. However, all existing algorithms are tailored to text and frequency-based similarity measures. To achieve optimal memory footprint and query latency, they rely on the near stationarity of documents and on laws governing natural languages. We consider, instead, a setup in which collections are streaming—necessitating dynamic indexing—and where indexing and retrieval must work with arbitrarily distributed real-valued vectors. As we show, existing algorithms are no longer competitive in this setup, even against naïve solutions. We investigate this gap and present a novel approximate solution, called Sinnamon , that can efficiently retrieve the top- k results for sparse real valued vectors drawn from arbitrary distributions. Notably, Sinnamon offers levers to trade off memory consumption, latency, and accuracy, making the algorithm suitable for constrained applications and systems. We give theoretical results on the error introduced by the approximate nature of the algorithm and present an empirical evaluation of its performance on two hardware platforms and synthetic and real-valued datasets. We conclude by laying out concrete directions for future research on this general top- k retrieval problem over sparse vectors.

Maximum inner product search (MIPS) over dense and sparse vectors have progressed independently in a bifurcated literature for decades; the latter is better known as top- \(k\) retrieval in Information Retrieval. This duality exists because sparse and dense vectors serve different end goals. That is despite the fact that they are manifestations of the same mathematical problem. In this work, we ask if algorithms for dense vectors could be applied effectively to sparse vectors, particularly those that violate the assumptions underlying top- \(k\) retrieval methods. We study clustering-based approximate MIPS where vectors are partitioned into clusters and only a fraction of clusters are searched during retrieval. We conduct a comprehensive analysis of dimensionality reduction for sparse vectors, and examine standard and spherical k -means for partitioning. Our experiments demonstrate that clustering-based retrieval serves as an efficient solution for sparse MIPS. As byproducts, we identify two research opportunities and explore their potential. First, we cast the clustering-based paradigm as dynamic pruning and turn that insight into a novel organization of the inverted index for approximate MIPS over general sparse vectors. Second, we offer a unified regime for MIPS over vectors that have dense and sparse subspaces, that is robust to query distributions.

BERT based ranking models have achieved superior performance on various information retrieval tasks.However, the large number of parameters and complex self-attention operations come at a significant latency overhead.To remedy this, recent works propose late-interaction architectures, which allow precomputation of intermediate document representations, thus reducing latency.Nonetheless, having solved the immediate latency issue, these methods now introduce storage costs and network fetching latency, which limit their adoption in real-life production systems.In this work, we propose the Succinct Document Representation (SDR) scheme that computes highly compressed intermediate document representations, mitigating the storage/network issue.Our approach first reduces the dimension of token representations by encoding them using a novel autoencoder architecture that uses the document's textual content in both the encoding and decoding phases.After this token encoding step, we further reduce the size of the document representations using modern quantization techniques.Evaluation on MSMARCO's passage rereranking task show that compared to existing approaches using compressed document representations, our method is highly efficient, achieving 4x-11.6xhigher compression rates for the same ranking quality.Similarly, on the TREC CAR dataset, we achieve 7.7x higher compression rate for the same ranking quality.

Many IR collections contain forbidden documents (F-docs), i.e. documents that should not be retrieved to the searcher. In an ideal scenario F-docs are clearly flagged, hence the ranker can filter them out, guaranteeing that no F-doc will be exposed. However, in real-world scenarios, filtering algorithms are prone to errors. Therefore, an IR evaluation system should also measure filtering quality in addition to ranking quality. Typically, filtering is considered as a classification task and is evaluated independently of the ranking quality. However, due to the mutual affinity between the two, it is desirable to evaluate ranking quality while filtering decisions are being made. In this work we propose nDCGf, a novel extension of the nDCGmin metric[14], which measures both ranking and filtering quality of the search results. We show both theoretically and empirically that while nDCGmin is not suitable for the simultaneous ranking and filtering task, nDCGf is a reliable metric in this case.

Summary form only given. We propose a method and algorithm for lossless compression of tabular data - including, for example, machine learning datasets, server logs and genomic datasets. Superior compression ratios are achieved by exploiting dependencies between the fields (or "features") in the dataset. The algorithm compresses the records w.r.t. a probabilistic graphical model - specifically an optimized forest, where each feature is a node. The work extends a method known as a Chow-Liu tree by incorporating a more accurate correction term to the cost function, which corresponds to the size required to describe the model itself. Additional features of the algorithm are efficient coding of the metadata (such as probability distributions), as well as data relabeling in order to cope with large datasets and alphabets. We test the algorithm on several datasets, and demonstrate an improvement in the compression rates of between 2X and 5X compared to gzip. The larger improvements are observed for very large datasets, such as the Criteo click prediction dataset which was published as part of a recent Kaggle competition.

We present a novel quasi-Newton method for convex optimization, in which the Hessian estimates are based not only on the gradients, but also on the diagonal part of the true Hessian matrix (which can often be obtained with reasonable complexity). The new algorithm is based on the well known Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm and has similar complexity. The proposed Diagonal-Augmented BFGS (DA-BFGS) method is shown to be stable and achieves a super-linear convergence rate in a local neighborhood of the optimal argument. Numerical experiments on logistic regression and factorization machines problems showcase that DA-BFGS consistently outperforms the baseline BFGS and Newton algorithms.

We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similar to the classical definition of a successively refinable source, we say that a source is strongly successively refinable if successive refinement coding can achieve the second order optimum rate (including the dispersion terms) at both decoders. We establish a sufficient condition for strong successive refinability. We show that any discrete source under Hamming distortion and the Gaussian source under quadratic distortion are strongly successively refinable. We also demonstrate how successive refinement ideas can be used in point-to-point lossy compression problems in order to reduce complexity. We give two examples, the binary-Hamming and Gaussian-quadratic cases, in which a layered code construction results in a low complexity scheme that attains optimal performance. For example, when the number of layers grows with the block length n, we show how to design an O(nlog(n)) algorithm that asymptotically achieves the rate-distortion bound.

We study the problem of compression for the purpose of similarity identification, where similarity is measured by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem - the minimal compression rate and the error exponent - were found in a previous work, in this paper we focus on the nonasymptotic domain and on practical, implementable schemes. We first present a finite blocklength achievability bound based on shape-gain quantization: The gain (amplitude) of the vector is compressed via scalar quantization and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated and they converge to the asymptotic values as predicted by the error exponent. We then give a nonasymptotic lower bound on the performance of any compression scheme, and compare to the upper (achievability) bound. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice.

We consider the problem of compressing discrete memory less data sequences for the purpose of similarity identification, first studied by Ahlswede et al. (1997). In this setting, a source sequence is compressed, where the goal is to be able to identify whether the original source sequence is similar to another given sequence (called the query sequence). There is no requirement that the source will be reproducible from the compressed version. In the case where no false negatives are allowed, a compression scheme is said to be reliable if the probability of error (false positive) vanishes as the sequence length grows. The minimal compression rate in this sense, which is the parallel of the classical rate distortion function, is called the identification rate. The rate at which the error probability vanishes is measured by its exponent, called the identification exponent (which is the analog of the classical excess distortion exponent). While an information-theoretic expression for the identification exponent was found in past work, it is uncomputable due to a dependency on an auxiliary random variable with unbounded cardinality. The main result of this paper is a cardinality bound on the auxiliary random variable in the identification exponent, thereby making the quantity computable (solving the problem that was left open by Ahlswede et al.). The new proof technique relies on the fact that the Lagrangian in the optimization problem (in the expression for the exponent) can be decomposed by coordinate (of the auxiliary random variable). Then a standard Caratheodory - style argument completes the proof.

The problem of performing similarity queries on compressed data is considered. We focus on the quadratic similarity measure, and study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on the compressed data. For a Gaussian source, we show that the queries can be answered reliably if and only if the compression rate exceeds a given threshold-the identification rate-which we explicitly characterize. Moreover, when compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that, as with classical compression, the Gaussian source requires the largest compression rate among sources with a given variance. Moreover, a robust scheme is described that attains this maximal rate for any source distribution.

Shannon's capacity and rate-distortion function, combined with the separation principle, provide tight bounds for the minimum possible distortion in joint source-channel coding. These bounds, however, are usually achievable only in the limit of a large block length. In their 1973 paper, Ziv and Zakai introduced a family of alternative capacity and rate-distortion functions, based on functionals satisfying the data-processing inequality, which potentially give tighter bounds for systems with a small block length. There is a considerable freedom as to how to choose those functionals, and the ways of finding the best possible functionals yielding the best bounds for a given source-channel combination are not specified. We examine recently conjectured high SNR asymptotic expressions for the Ziv-Zakai bounds, based on the Rényi-divergence functional. We derive nonasymptotic bounds on the Ziv-Zakai-Rényi rate-distortion function and capacity for a broad class of sources and additive noise channels, which hold for arbitrary SNR and prove the conjectured asymptotic expressions in the limit of a small distortion/high SNR. The results lead to new bounds on the best achievable distortion in finite dimensional joint source-channel coding. Examples are presented where the new bounds achieve significant improvement upon Shannon's original bounds.

We consider compression of sequences in a database so that similarity queries can be performed efficiently in the compressed domain. The fundamental limits for this problem setting, which characterize the trade off between compression rate and reliability of the answers to the queries, have been characterized in past work. However, how to approach these limits in practice has remained largely unexplored. Recently, we proposed a scheme for this task that is based on existing lossy compression algorithms, for the general case where the similarity measure satisfies a triangle inequality. Although it was shown that it achieves the fundamental limits for some cases, it is suboptimal in general. In this paper we propose a new scheme that also uses lossy compression algorithms as a building block, but with a carefully chosen distortion measure that is different than the one defining the similarity between sequences. The new scheme significantly improves the compression rate compared to the previously proposed scheme in many cases. For example, for binary sources and Hamming similarity measure, simulation results show a compression rate close to the fundamental limit, and an improvement over the previously proposed scheme of up to 55% (for the same reliability). The results shed light on the fact that compression for similarity identification is inherently different than classical lossy compression.

We study the problem of compression of a Gaussian vector for the purpose of similarity identification, where similarity is defined by the mean square Euclidean distance between vectors. While the asymptotical fundamental limits of the problem - the minimal compression rate and the error exponent - were found in a previous work, in this paper we focus on the nonasymptotic domain. We first present a finite blocklength achievability bound based on shape-gain quantization: The gain (amplitude) of the vector is compressed via scalar quantization, and the shape (the projection on the unit sphere) is quantized using a spherical code. The results are numerically evaluated, and they converge to the asymptotic values as predicted by the error exponent. For a practical implementation of such a scheme, we use wrapped spherical codes, studied by Hamkins and Zeger, and use the Leech lattice as an example for an underlying lattice. As a side result, we obtain a bound on the covering angle of any wrapped spherical code, as a function of the covering radius of the underlying lattice.

We study the problem of compressing a source for the goal of answering similarity queries from the compressed data. Unlike classical compression, here there is no requirement that the source be reproduced from the compressed form. For discrete memoryless sources and an arbitrary similarity measure, we fully characterize the minimal compression rate that allows query answers, that are reliable in the sense of having a vanishing false-positive probability, when false negatives are not allowed. The result is partially based on a previous work by Ahlswede et al. [1], and the inherently typical subset lemma plays a key role in the converse proof. We then discuss the performance that is attainable by using schemes that use lossy source codes as a building block, and show that such schemes are, in general, suboptimal. Finally, we discuss the problem of computing the fundamental limit, and present numerical results.

We investigate the second order asymptotics (source dispersion) of the successive refinement problem. Similarly to the classical definition of a successively refinable source, we say that a source is strongly successively refinable if successive refinement coding can achieve the second order optimum rate (including the dispersion terms) at both receivers. We propose a sufficient condition for strong successive refinability. As a corollary, we show that any discrete source with Hamming distortion is strongly successively refinable. For a Gaussian source with quadratic distortion, we show directly that the source is strongly successively refinable.

The problem of performing similarity queries on compressed data is considered. We study the fundamental tradeoff between compression rate, sequence length, and reliability of queries performed on compressed data. For a Gaussian source and quadratic similarity criterion, we show that queries can be answered reliably if and only if the compression rate exceeds a given threshold - the identification rate - which we explicitly characterize. When compression is performed at a rate greater than the identification rate, responses to queries on the compressed data can be made exponentially reliable. We give a complete characterization of this exponent, which is analogous to the error and excess-distortion exponents in channel and source coding, respectively. For a general source, we prove that the identification rate is at most that of a Gaussian source with the same variance. Therefore, as with classical compression, the Gaussian source requires the largest compression rate. Moreover, a scheme is described that attains this maximal rate for any source distribution.

In this paper, we consider the problem of determining whether sequences X and Y, generated i.i.d. according to PX× PY, are equal given access only to the pair (Y, T(X)), where T(X) is a rate-R compressed version of X. In general, the rate R may not be sufficiently large to reliably determine whether X=Y. We precisely characterize this reliability - i.e., the exponential rate at which an error is made - as a function of R. Interestingly, the exponent turns out to be related to the Bhattacharyya distance between the distributions PXand PY. In addition, the scheme achieving this exponent is universal, i.e. does not depend on PX, PY.

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev in 1994, the codewords are points in ann-dimensional Euclidean space (an infinite constellation) and the tradeoff between their density and the error probability is considered. The normalized log density (NLD) plays the role of the communication rate, and capacity as well as error exponent bounds for this setting are known. This paper considers the infinite constellation setting in the finite block-length (dimension) regime. A simplified expression for Poltyrev's achievability bound is found and it is shown to be closely related to the sphere converse bound and to a recently proposed achievability bound based on point processes. The bounds are then analyzed asymptotically for growingn: for fixed NLD, the bounds turn out to be extremely tight compared to previous error exponent analysis. For fixed error probability ε, it is shown that the gap of the highest achievable NLD to the optimal NLD (Poltyrev's capacity) is approximately √{[1/(2n)]}Q-1(ε) , whereQis the standard complementary Gaussian cumulative distribution function, thus extending the channel dispersion analysis to infinite constellations. Connections to the error exponent of the power-constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed. Finally, the new tight bounds are compared to state-of-the-art coding schemes.

We revisit the setting of a Gaussian channel without power constraints, proposed by Poltyrev, where the codewords are points in Euclidean space and their density is considered instead of the communication rate. We refine the expurgation technique (proposed by Poltyrev for the derivation of the error exponent) to the finite dimensions case and obtain a finite-dimensional achievability bound. While the expurgation exponent improves upon the random coding exponent only for certain rates (below a rate known as δex), we show that for finite dimensions the expurgation technique is useful for a broader range of rates. In addition, we present precise asymptotical analysis of the expurgation bound and find the sub-exponential terms, which turn out to be non-negligible.

We consider a discrete memoryless joint source-channel setting. In this setting, if a source sequence is reconstructed with distortion below some threshold, we declare a success event. We prove that for any joint source-channel scheme, if this threshold lower (better) than the optimum average distortion, then the success probability approaches zero as the block length increases. Furthermore, we show that the probability has an exponential behavior, and evaluate the optimal exponent. Surprisingly, the best exponential behavior is attainable by a separation-based scheme.

In this work we investigate the behavior of the minimal rate needed in order to guarantee a given probability that the distortion exceeds a prescribed threshold, at some fixed finite quantization block length. We show that the excess coding rate above the rate-distortion function is inversely proportional (to the first order) to the square root of the block length. We give an explicit expression for the proportion constant, which is given by the inverse Q-function of the allowed excess distortion probability, times the square root of a constant, termed the excess distortion dispersion. This result is the dual of a corresponding channel coding result, where the dispersion above is the dual of the channel dispersion. The work treats discrete memoryless sources, as well as the quadratic-Gaussian case.

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev, the codewords are points in an n-dimensional Euclidean space (an infinite constellation) and their optimal density is considered. Poltyrev's “capacity” is the highest achievable normalized log density (NLD) with vanishing error probability. This capacity as well as error exponents for this setting are known. In this work we consider the optimal NLD for a fixed, nonzero error probability, as a function of the codeword length (dimension) n. We show that as n grows, the gap to capacity is inversely proportional (up to the first order) to the square-root of n where the proportion constant is given by the inverse Q-function of the allowed error probability, times the square root of 1/2. In an analogy to similar result in channel coding, the dispersion of infinite constellations is 1/2 nat2per channel use. We show that this optimal convergence rate can be achieved using lattices, therefore the result holds for the maximal error probability as well. Connections to the error exponent of the power constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed.

The capacity and random coding error exponent of multilevel coding (MLC) with multistage decoding (MSD) are analyzed. General discrete memoryless channels with arbitrary input distributions are considered. The capacities of MLC with maximum likelihood decoding and with MSD are calculated, and it is shown that using MLC may result in loss in the achievable rate for reliable communication. Necessary and sufficient conditions for the rate loss to be zero are derived. A new random coding error exponent is derived for MLC with MSD. For the special case of uniform inputs, the new error exponent can be easily calculated by its inverse function, which is given by the sum of the inverse error exponents of the conditional sub-channels.

In this work we study simple joint source-channel (JSCC) schemes for transmitting k independent Gaussian source samples with different variances over k additive white Gaussian noise (AWGN) channels. The channels shall have an average power constraint, and the distortion measure shall be the average square error. This problem arises in several practical cases, e.g. in transform coding where the output of the decorrelation process is our source, that may have different variances.

In this work we consider joint source-channel coding (JSCC) schemes that are limited to work in blocks of finite length. We focus on the high resolution and high signal to noise ratio (SNR) regime, and derive new lower bounds for the distortion of JSCC schemes over rth-moment constrained additive noise channels. These new bounds are based on the method of Ziv and Zakai [11], combined with the Renyi information measure, as was recently proposed by Leibowitz and Zamir [5]. Numerical results are presented for the case of Gaussian source and channel, and it is shown that the new bounds improve upon Shannon's original bound in several cases, including bandwidth expansion and reduction.

In this work we consider dimension reducing mappings that can be used for joint source-channel coding (JSCC) systems. In such systems, the source coding and the channel coding is performed as a single operation. Although it is known by Shannon's separation theorem that asymptotically JSCC is not required for attaining the optimal performance, utilizing such schemes is beneficial for practical reasons such as delay and implementation simplicity. We specifically focus on the bandwidth reduction case, where the bandwidth of the data is greater than the bandwidth of the channel. More specifically, we focus on bandwidth reduction mappings, where the JSCC operation is performed using a single nonlinear operation. A modification of the spiral mapping is presented, so the power at the output is proportional to that of the input

In this work we consider the problem of universal prediction of individual sequences where the universal predictor is a deterministic finite state machine, with a fixed, relatively small, number of states. We examine the case of self-information loss, where the predictions are probability assignments which is equivalent to universal data compression. While previous results in that area are asymptotic only, we examine a class of machine structures and find an optimal method for allocating the probabilities to the machine states which achieves minimal redundancy w.r.t. the constant predictors class. We show analytic bounds for the redundancy of machines from that class, and construct machines with redundancy that is arbitrarily close to these bounds. Finally, we compare our machines to previously proposed machines and show that our machine with 300 states achieves smaller redundancy than the best machine known so far with 6000 states.

We consider the problem of universal prediction of individual binary sequences where the universal predictor is a deterministic finite state machine with a fixed number of states. We examine the case of self-information loss, where the predictions are probability assignments. The performance of the predictors is measured by their redundancy w.r.t. the constant predictors class. We obtain an improved lower bound on the redundancy of any finite state (FS) predictor with K states. We construct a FS predictor based on the lower bound and compare the performance of the predictor to the lower bound. Numerical results show that the redundancy of the proposed FS predictor is close to that predicted by the lower bound