License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.15
URN: urn:nbn:de:0030-drops-49995
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4999/
Go to the corresponding LIPIcs Volume Portal

Pagh, Rasmus

Large-Scale Similarity Joins With Guarantees (Invited Talk)

pdf-format:
26.pdf (0.4 MB)

Abstract

The ability to handle noisy or imprecise data is becoming increasingly important in computing. In the database community the notion of similarity join has been studied extensively, yet existing solutions have offered weak performance guarantees. Either they are based on deterministic filtering techniques that often, but not always, succeed in reducing computational costs, or they are based on randomized techniques that have improved guarantees on computational cost but come with a probability of not returning the correct result. The aim of this paper is to give an overview of randomized techniques for high-dimensional similarity search, and discuss recent advances towards making these techniques more widely applicable by eliminating probability of error and improving the locality of data access.

BibTeX - Entry

@InProceedings{pagh:LIPIcs:2015:4999,
  author =	{Rasmus Pagh},
  title =	{{Large-Scale Similarity Joins With Guarantees (Invited Talk)}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{15--24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4999},
  URN =		{urn:nbn:de:0030-drops-49995},
  doi =		{10.4230/LIPIcs.ICDT.2015.15},
  annote =	{Keywords: Similarity join, filtering, locality-sensitive hashing, recall}
}

Keywords: Similarity join, filtering, locality-sensitive hashing, recall
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI