1 Search Results for "Sivertsen, Johan"

Document

DOI: 10.4230/LIPIcs.ICDT.2020.22

The Space Complexity of Inner Product Filters

Authors: Rasmus Pagh and Johan Sivertsen

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract

Motivated by the problem of filtering candidate pairs in inner product similarity joins we study the following inner product estimation problem: Given parameters d∈ℕ, α>β≥0 and unit vectors x,y∈ ℝ^d consider the task of distinguishing between the cases ⟨x,y⟩≤β and ⟨x,y⟩≥α where ⟨x,y⟩ = ∑_{i=1}^d x_i y_i is the inner product of vectors x and y. The goal is to distinguish these cases based on information on each vector encoded independently in a bit string of the shortest length possible. In contrast to much work on compressing vectors using randomized dimensionality reduction, we seek to solve the problem deterministically, with no probability of error. Inner product estimation can be solved in general via estimating ⟨x,y⟩ with an additive error bounded by ε = α - β. We show that d log₂ (√{1-β}/ε) ± Θ(d) bits of information about each vector is necessary and sufficient. Our upper bound is constructive and improves a known upper bound of d log₂(1/ε) + O(d) by up to a factor of 2 when β is close to 1. The lower bound holds even in a stronger model where one of the vectors is known exactly, and an arbitrary estimation function is allowed.

Cite as

Rasmus Pagh and Johan Sivertsen. The Space Complexity of Inner Product Filters. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pagh_et_al:LIPIcs.ICDT.2020.22,
  author =	{Pagh, Rasmus and Sivertsen, Johan},
  title =	{{The Space Complexity of Inner Product Filters}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.22},
  URN =		{urn:nbn:de:0030-drops-119468},
  doi =		{10.4230/LIPIcs.ICDT.2020.22},
  annote =	{Keywords: Similarity, estimation, dot product, filtering}
}

Refine by Author
1 Pagh, Rasmus
1 Sivertsen, Johan

Refine by Classification
1 Theory of computation → Data structures design and analysis
1 Theory of computation → Streaming, sublinear and near linear time algorithms

Refine by Keyword
1 Similarity
1 dot product
1 estimation
1 filtering

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Sivertsen, Johan"

The Space Complexity of Inner Product Filters

Abstract

Cite as

Thanks for your feedback!

Could not send message