PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Inner Product Approximation in Hybrid Spaces

Xiang Wu, Ruiqi Guo, David Simcha, Dave Dopson, Sanjiv Kumar

arXiv:1903.08690v1cs.LGstat.ML

TL;DR

Searching hybrid vectors is challenging because sparse- and dense-data techniques do not transfer well across the two components. The paper approximates their inner products separately with specialized data structures; on a 5M-point sample from its billion-point QuerySim dataset, it reports over 20x faster search than the closest competition in the high-recall regime.

  • Problem

    Sparse- and dense-vector search methods do not transfer well to hybrid spaces, where efficient, high-recall search remains a challenge.

    Source: §1 · p. 1, §1.2 · p. 2

  • Method

    The method independently approximates sparse and dense inner products using cache-sorted inverted indices and product quantization, with residual reordering to improve recall.

    Source: §2.1 · p. 2, §2.3 · p. 3, §3.1 · p. 3

  • Results

    On a random 5M-point sample from QuerySim’s original 1B points, the proposed hybrid approach is over 20x faster than the closest competition in the high-recall regime.

    Source: §7.2 · p. 8

  • Takeaways & Limitations

    The authors demonstrate the method on two public datasets and one very large industrial dataset.

    Source: §1.2 · p. 2

    The cache-sorting efficiency analysis assumes independent sparse-matrix entries and considers nonzero probabilities ordered by dimension, with a power-law distribution described as common in real-world data.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

Many emerging use cases of data mining and machine learning operate on large datasets with data from heterogeneous sources, specifically with both sparse and dense components. For example, dense deep neural network embedding vectors are often used in conjunction with sparse textual features to provide high dimensional hybrid representation of documents. Efficient search in such hybrid spaces is very challenging as the techniques that perform well for sparse vectors have little overlap with those that work well for dense vectors. Popular techniques like Locality Sensitive Hashing (LSH) and its data-dependent variants also do not give good accuracy in high dimensional hybrid spaces. Even though hybrid scenarios are becoming more prevalent, currently there exist no efficient techniques in literature that are both fast and accurate. In this paper, we propose a technique that approximates the inner product computation in hybrid vectors, leading to substantial speedup in search while maintaining high accuracy. We also propose efficient data structures that exploit modern computer architectures, resulting in orders of magnitude faster search than the existing baselines. The performance of the proposed method is demonstrated on several datasets including a very large scale industrial dataset containing one billion vectors in a billion dimensional space, achieving over 10x speedup and higher accuracy against competitive baselines.

1 INTRODUCTION

Hybrid representations combine sparse features such as n-grams with dense embeddings, but existing search techniques do not provide efficient, high-recall search across both components. The paper develops approximation methods and data structures for this setting and evaluates them on public and industrial datasets.

1 INTRODUCTION

  • Hybrid feature vectors reflect data from varied sources and can differ in dimensionality, sparsity, and modality.Examples include data from web services, mobile devices, location services, and digital imagery.Source: §1 · p. 1
  • Sparse n-grams can preserve rare features, while dense embeddings capture correlations among features, motivating their use together in hybrid representations.The paper cites Wide-and-Deep as an example combining dense neural-network features with sparse logistic-regression features.Source: §1 · p. 1

1.1 Insufficiency of the existing methods

  • Existing sparse and dense search methods have limited overlap, and separate searches can miss items that rank highly only in the combined space.Projection methods such as LSH and RPTree can also lose substantial recall on hybrid data.Source: §1.1 · p. 1
  • On QuerySim, treating all dimensions as dense is infeasible, treating them all as sparse takes a few minutes per query, and LSH performs poorly even with many bits.The dataset has one billion points, 200 dense dimensions, and one billion sparse dimensions, with about 200 nonzeros per vector.Source: §1.1 · pp. 1–2

1.2 Contributions

  • The paper combines sparse and dense inner-product approximation with data structures designed for modern CPUs, then evaluates the approach on two public and one industrial dataset.Its contributions include cache-sorted inverted indices, dense-component quantization with LUT16, and residual reordering to improve recall.Source: §1.2 · p. 2

2 OUR APPROACH

The approach approximates sparse and dense inner products separately, then uses specialized indexing and quantization methods for each component. Its sparse index accumulates contributions over active dimensions, while its dense representation uses product quantization.

2.1 Overview

  • Sparse and dense inner products are approximated independently, using a cache-sorted inverted index for sparse data and product-code quantization with LUT16 for dense data.A second pass with residual indices alleviates approximation error and substantially increases recall.Source: §2.1 · p. 2

2.2 Inverted Index for Sparse Inner Product

  • The sparse inner product is computed by iterating over each nonzero query dimension and accumulating contributions from datapoints active in that dimension’s inverted list.Figure 1 illustrates this accumulation over nonzero dimensions.Source: §2.2 · p. 2, Figure 1 · p. 2
  • Cache-sorting reorders datapoints to reduce memory-access bottlenecks in inverted-index computation.The authors identify memory access as the practical bottleneck and claim cache-sorting can yield several-fold gains in sparse inner-product computation.Source: §2.2 · p. 2

2.3 Product Codes for Dense Inner Product

  • Dense vectors are split into K contiguous subvectors, each quantized separately using a learned codebook, and their codes form the product representation.The codebooks are learned independently by k-means in each subspace.Source: §2.3 · p. 3
  • Product codes support dense inner-product approximation using the query’s dense component and the quantized representation of the indexed vector.Figure 2 illustrates one learned codebook per subspace and the resulting K-code representation.Source: §2.3 · p. 3, Figure 2 · p. 3

3 EFFICIENT DATA STRUCTURES

Efficient hybrid search depends not only on asymptotic complexity but also on memory bandwidth, cache behavior, and instruction-level parallelism. This section develops cache sorting to reduce sparse-index memory accesses and make them more sequential.

3.1 Memory I/O and Inverted Index

  • Memory bandwidth and accumulator cache-line access constrain sparse inverted-index query performance more than arithmetic throughput.Counting expected cache-lines touched per query provides an accurate estimate of query time.Source: §3.1 · p. 3
  • Cache sorting seeks a datapoint permutation that minimizes expected sparse-index query cost by reducing accumulator cache-line accesses.The cost model counts a cache-line when any of its B datapoints is nonzero in a queried dimension.Source: §3.1 · p. 3

3.2 Cache Sorting

  • The authors use greedy recursive partitioning by active dimensions to arrange datapoint indices into contiguous blocks, yielding an efficient cache-sorting permutation.The optimization is hard in general, while the greedy algorithm takes a few seconds even with millions of datapoints and is faster than LP-relaxation approaches.Source: §3.2 · pp. 3–4

3.3 Efficiency of Cache Sorting

  • Under an independent-entry model with decreasing, power-law activity rates, the analysis estimates cache-line savings by skipping all-zero blocks and grouping active datapoints.The model assumes dimension-specific nonzero probabilities and estimates accesses before and after permutation.Source: §3.3 · pp. 4–5

N /B , respectively. (b) The number of times cache-sorting reduces cache-line access versus the unsorted,

Cache sorting reduces cache-line accesses in the modeled setting and yields over 10x throughput improvement on several real-world datasets. The analysis assumes zero correlation between dimension activity patterns, making it somewhat pessimistic.

N /B , respectively. (b) The number of times cache-sorting reduces cache-line access versus the unsorted,

  • Cache sorting significantly reduces expected cache-line accesses across dimensions in the modeled setting of N = 1M, α = 2.0, and B = 16.The analysis assumes Pj = Qj = j^-α.Source: N /B , respectively. (b) The number of… · p. 5
  • Larger cache-line size B increases the modeled savings from cache sorting.The authors cite this trend as motivation for quantizing inverted-index values to reduce memory footprint.Source: N /B , respectively. (b) The number of… · p. 5
  • The analysis assumes zero correlation between dimensions’ activity patterns, although real-world datasets often have significant correlations.The authors describe the analysis as somewhat pessimistic.Source: N /B , respectively. (b) The number of… · p. 5
  • Over 10x throughput improvement was observed on several real-world datasets using cache sorting.For active dimensions, sorting also creates long sequential runs that can be encoded efficiently and computed with vectorized SIMD instructions.Source: N /B , respectively. (b) The number of… · p. 5

4 INDEXING AND SEARCH

The section approximates dense and sparse inner products with component-specific indexing, lookup, and pruning methods. It also analyzes their approximation errors and describes an AVX2 optimization for dense lookup accumulation.

4.1 Dense Component

  • Product quantization encodes each of K dense subvectors with a codebook index, using K ⌈log2 l⌉ bits when each codebook has l centers.Source: §4.1 · p. 5

4.1.1 Asymmetric Distance Computation (ADC).

  • ADC approximates a dense inner product by summing K query-specific lookup-table entries indexed by the subvectors’ quantized codewords.Each table is precomputed from the query and the corresponding subspace codebook.Source: §4.1.1 · p. 5

4.1.2 AVX2 In-Register Lookup Table.

  • Unsigned accumulation with a lookup-value bias avoids a costly width-extension step, then post-processing subtracts the bias effect to recover the result.The implementation leaves upper bits unzeroed and corrects their known effect afterward.Source: §4.1.2 · pp. 5–6
  • ∼16.5 lookup-accumulate operations per clock-cycle are sustained for batches of 3 or more queries, 8x LUT256’s architectural upper bound; single-query speed is memory-bandwidth-limited.The throughput includes post-processing final inner products.Source: §4.1.2 · p. 6

4.1.3 Approximation Error from Product Quantization.

  • For whitened dense data, the analysis assumes PQ mean squared error near the Gaussian rate-distortion bound and gives a probabilistic inner-product error bound.The query is transformed along with the data for whitening.Source: §4.1.3 · p. 6

4.2 Sparse Component; 4.2.1 Approximation Error from Pruning.

  • Pruning small sparse entries reduces index size and search arithmetic; under the stated independent-sparsity model, the inner-product error has a probabilistic bound.When dp^2 ≪ 1, the probability bound approaches 1 at rate O(e^-nϵ), where nϵ is the minimum number of removed entries needed to exceed error ϵ.Source: §4.2 · p. 6, §4.2.1 · p. 6

5 RESIDUAL REORDERING FOR IMPROVED SEARCH

Residual reordering corrects approximate hybrid-search scores on overfetched candidates, trading a small additional cost for improved recall. The section also gives a gap-dependent recall condition and an empirical overfetch setting for real-world datasets.

5 RESIDUAL REORDERING FOR IMPROVED SEARCH

  • The method overfetches αh candidates, reorders them with dense residuals down to βh, then uses sparse residuals to return the top h.The parameters α and β can be tuned to balance recall and search time.Source: §5 · pp. 6–7
  • Residual reordering uses less than 10% of overall search time in the reported similarity-search benchmarks while significantly improving final retrieval recall.It operates on a small subset of O(h) residuals.Source: §5 · p. 7

5.1 Retrieval Performance

  • For most real-world datasets with h ≪ N, α ≤ 10 achieves ≥90% recall empirically.Source: §5.1 · p. 7
  • Recall is at least the probability that approximation error is below half the score gap between the hth and αhth-ranked datapoints.The passage says a sufficiently large α can satisfy this condition when the inner-product distribution has a quickly vanishing upper tail.Source: §5.1 · p. 7

6 OVERALL INDEXING ALGORITHM

The indexing algorithm builds separate sparse and dense data indexes, plus residual indexes for reordering. Its parameter choices trade compact first-pass scans for more accurate residual corrections.

6 OVERALL INDEXING ALGORITHM

  • The algorithm builds a pruned sparse index and a product-quantized dense index, then indexes each component’s residuals for later reordering.Source: §6 · p. 7

6.1.1 Dense Index Parameters.

  • The dense data index uses KU = dD/2 and l = 16, reducing storage 16x versus 32-bit floating-point values and enabling LUT16 lookup.The residual index uses KV = dD and l = 256; it is one-quarter the original dataset size.Source: §6.1.1 · p. 7

6.1.2 Sparse Index Parameters.

  • A high first sparse threshold keeps only the top hundreds of nonzero values per dimension, making the data index about two orders of magnitude smaller with little empirical retrieval loss.The lower residual threshold retains most nonzeros, and the combined approximations lift recall to the high 90s%.Source: §6.1.2 · p. 7

7 EXPERIMENTS

The evaluation uses hybrid public recommendation datasets and a billion-point industrial query dataset, then compares search speed and recall. On QuerySim, the proposed approach is over 20x faster than the closest competitor in the high-recall regime, with projected all-pair search completing within a week and online search reaching 90% recall@20 at 79ms average latency.

7.1.1 Public Datasets.

  • Netflix and MovieLens users are represented with sparse ratings and 300-dimensional dense SVD components, with 10k embeddings sampled as queries.The dense components are formed from U weighted by λ; the remaining users form the dataset.Source: §7.1.1 · p. 7

7.1.2 QuerySim Dataset.

  • QuerySim combines sparse unigram and bigram tf × idf features with neural-network dense vectors, and contains one billion points in over one billion dimensions.The dense and sparse inner-product weights were tuned against a comprehensive metric such as area under ROC; the sparse component has power-law nonzero counts and a long-tailed value distribution.Source: §7.1.2 · p. 8, Figure 5 · p. 8

7.2 Recall and Speedup

  • The evaluation compares top-20 search speed and recall, using dense and sparse brute force, sparse inverted-index, hashing, and component-only baselines.Single-machine benchmarks used a 3.5GHz Intel CPU and 64GB memory; distributed benchmarks used 200 servers with 2GHz Intel CPUs and 128GB each.Source: §7.2 · p. 8
  • Over 20x faster than the closest competitor in the high-recall regime on QuerySim; Table 3 reports performance on a sampled 5M datapoints.The latency and recall comparison uses a random 5M sample from the original 1B datapoints.Source: §7.2 · p. 8, Table 3 · p. 9
  • Within a week, the proposed hybrid approach could complete projected 1B×1B QuerySim all-pair search, versus about 9 years for sparse brute force and about 3 months for sparse inverted index.The projection assumes 104 CPU cores and is compared with a weekly production update requirement.Source: §7.2 · p. 8
  • 90% recall@20 at 79ms average latency was achieved for a single query in the distributed online search system.The dataset was randomly divided into 200 shards, with one shard loaded into memory on each of 200 servers.Source: §7.2 · p. 8

8 CONCLUSION

The paper presents approximate inner-product search and optimized in-memory indexes for sparse-dense hybrid spaces. It reports more than 10x speedup with recall in the 90s% on a large-scale real-world search scenario.

8 CONCLUSION

  • The proposed approach combines approximate inner-product similarity with in-memory index optimizations for sparse and dense vectors, achieving more than 10x speedup with recall in the 90s% in a large-scale real-world search scenario.The optimizations target modern computer architecture.Source: §8 · p. 9
  • The authors frame fast, accurate approximation as a possible route to information-retrieval systems operating directly on sparse and dense features at massive scale.The paper states this as a hope for future systems.Source: §8 · p. 9

Related papers

Loading 1903.08690v1…