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.CPM.2016.24
URN: urn:nbn:de:0030-drops-60684
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6068/
Go to the corresponding LIPIcs Volume Portal

Kopelowitz, Tsvi ; Krauthgamer, Robert

Color-Distance Oracles and Snippets

pdf-format:
LIPIcs-CPM-2016-24.pdf (0.5 MB)

Abstract

In the snippets problem we are interested in preprocessing a text T so that given two pattern queries P_1 and P_2, one can quickly locate the occurrences of the patterns in T that are the closest to each other. A closely related problem is that of constructing a color-distance oracle, where the goal is to preprocess a set of points from some metric space, in which every point is associated with a set of colors, so that given two colors one can quickly locate two points associated with those colors, that are as close as possible to each other.
We introduce efficient data structures for both color-distance oracles and the snippets problem. Moreover, we prove conditional lower bounds for these problems from both the 3SUM conjecture and the Combinatorial Boolean Matrix Multiplication conjecture.

BibTeX - Entry

@InProceedings{kopelowitz_et_al:LIPIcs:2016:6068,
  author =	{Tsvi Kopelowitz and Robert Krauthgamer},
  title =	{{Color-Distance Oracles and Snippets}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{24:1--24:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Roberto Grossi and Moshe Lewenstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6068},
  URN =		{urn:nbn:de:0030-drops-60684},
  doi =		{10.4230/LIPIcs.CPM.2016.24},
  annote =	{Keywords: Snippets, Text Indexing, Distance Oracles, Near Neighbor Search}
}

Keywords: Snippets, Text Indexing, Distance Oracles, Near Neighbor Search
Collection: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Issue Date: 2016
Date of publication: 27.06.2016

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