1 Search Results for "Feigenblat, Guy"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2012.70

Exponential Space Improvement for minwise Based Algorithms

Authors: Guy Feigenblat, Ely Porat, and Ariel Shiftan

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract

In this paper we introduce a general framework that exponentially improves the space, the degree of independence, and the time needed by min-wise based algorithms. The authors, in SODA 2011, we introduced an exponential time improvement for min-wise based algorithms by defining and constructing an almost k-min-wise independent family of hash functions. Here we develop an alternative approach that achieves both exponential time and exponential space improvement. The new approach relaxes the need for approximately min-wise hash functions, hence gets around the Omega(log(1/epsilon)) independence lower bound in [Patrascu 2010]. This is done by defining and constructing a d-k-min-wise independent family of hash functions. Surprisingly, for most cases only 8-wise independence is needed for the additional improvement. Moreover, as the degree of independence is a small constant, our function can be implemented efficiently. Informally, under this definition, all subsets of size d of any fixed set X have an equal probability to have hash values among the minimal k values in X, where the probability is over the random choice of hash function from the family. This property measures the randomness of the family, as choosing a truly random function, obviously, satisfies the definition for d=k=|X|. We define and give an efficient time and space construction of approximately d-k-min-wise independent family of hash functions for the case where d=2, as this is sufficient for the additional exponential improvement. We discuss how this construction can be used to improve many min-wise based algorithms. To our knowledge such definitions, for hash functions, were never studied and no construction was given before. As an example we show how to apply it for similarity and rarity estimation over data streams. Other min-wise based algorithms, can be adjusted in the same way.

Cite as

Guy Feigenblat, Ely Porat, and Ariel Shiftan. Exponential Space Improvement for minwise Based Algorithms. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 70-85, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{feigenblat_et_al:LIPIcs.FSTTCS.2012.70,
  author =	{Feigenblat, Guy and Porat, Ely and Shiftan, Ariel},
  title =	{{Exponential Space Improvement for minwise Based Algorithms}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{70--85},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.70},
  URN =		{urn:nbn:de:0030-drops-38495},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.70},
  annote =	{Keywords: Streaming, Min-Wise, Hash Functions, Similarity, On line algorithms, Sub-linear algorithms}
}

Refine by Author
1 Feigenblat, Guy
1 Porat, Ely
1 Shiftan, Ariel

Refine by Classification

Refine by Keyword
1 Hash Functions
1 Min-Wise
1 On line algorithms
1 Similarity
1 Streaming
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2012

1 Search Results for "Feigenblat, Guy"

Exponential Space Improvement for minwise Based Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message