Efficient Set of Vectors Search

• URL: http://arxiv.org/abs/2107.06817v1
• Date: Wed, 14 Jul 2021 16:22:20 GMT
• Title: Efficient Set of Vectors Search
• Abstract summary: We present approximate search algorithms for the general case. The underlying idea in these algorithms is encoding a set of vectors via a "long" single vector.
• Score: 2.741266294612776
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider a similarity measure between two sets $A$ and $B$ of vectors, that balances the average and maximum cosine distance between pairs of vectors, one from set $A$ and one from set $B$. As a motivation for this measure, we present lineage tracking in a database. To practically realize this measure, we need an approximate search algorithm that given a set of vectors $A$ and sets of vectors $B_1,...,B_n$, the algorithm quickly locates the set $B_i$ that maximizes the similarity measure. For the case where all sets are singleton sets, essentially each is a single vector, there are known efficient approximate search algorithms, e.g., approximated versions of tree search algorithms, locality-sensitive hashing (LSH), vector quantization (VQ) and proximity graph algorithms. In this work, we present approximate search algorithms for the general case. The underlying idea in these algorithms is encoding a set of vectors via a "long" single vector.

Related papers

• Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian [3.891921282474929]
  We present randomized algorithms for the shortest vector problem (SVP)<n>For the $n$-dimensional lattice $mathcal L$, our algorithms solve SVP in time $20.6039n+o(n)$ classically and $20.5411n+o(n)$ quantumly and space $20.5n+o(n)$.
  arXiv  Detail & Related papers  (2026-08-03T16:46:49Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  We show that in $q$-metric spaces, metric trees can leverage a stronger version of the triangle inequality to reduce comparisons for exact search.<n>We propose a novel projection method that embeds datasets with arbitrary dissimilarity measures into $q$-metric spaces.
  arXiv  Detail & Related papers  (2025-06-06T22:09:44Z)
• Multi-thresholding Good Arm Identification with Bandit Feedback [1.079960007119637]
  We consider a good arm identification problem in a bandit setting with multi-objectives.<n>We propose the Multi-Thresholding UCB(MultiTUCB) algorithm with a sample complexity bound.
  arXiv  Detail & Related papers  (2025-03-13T14:04:04Z)
• Robust random graph matching in dense graphs via vector approximate message passing [0.0]
  We focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent correspondence. Our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n1-o(1)$ size.
  arXiv  Detail & Related papers  (2024-12-21T03:15:38Z)
• A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
  Finding a good approximation of the top eigenvector of a given $dtimes d$ matrix $A$ is a basic and important computational problem. We give two different quantum algorithms that output a classical description of a good approximation of the top eigenvector.
  arXiv  Detail & Related papers  (2024-05-23T16:33:13Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  Exact nearest neighbor retrieval has been generally acknowledged to be a $O(Nd)$ problem with no sub-linear solutions. We propose a novel algorithm for logarithmic Fast Exact Retrieval for Nearest-neighbor lookup (FERN) The algorithm achieves $O(dlog N)$ look-up with 100% recall on 10 million $d=128$ uniformly randomly generated vectors.
  arXiv  Detail & Related papers  (2024-05-07T15:57:39Z)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's algorithm for Streaming Principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time. We show that a simple single-pass procedure that thresholds the output of Oja's algorithm can achieve the minimax error bound under some regularity conditions in $O(d)$ space and $O(nd)$ time.
  arXiv  Detail & Related papers  (2024-02-11T16:36:48Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Matching Map Recovery with an Unknown Number of Outliers [0.0]
  We consider the problem of finding the matching map between two sets of $d$-dimensional noisy feature-vectors. We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than $5(dlog(4nm/alpha))1/4$, the true matching map can be recovered with probability $1-alpha$.
  arXiv  Detail & Related papers  (2022-10-24T15:59:10Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
  We consider an algorithm that computes all $s$-well separated pairs in certain point sets in $mathbbRn$, $n$ $>$ $1$. We also consider an algorithm that is a permutation of Dijkstra's algorithm, that computes $K$-nearest neighbors using a certain power weighted shortest path metric in $mathbbRn$, $n$ $>$ $1$.
  arXiv  Detail & Related papers  (2021-03-20T17:38:13Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.