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

Afshani, Peyman ; Nielsen, Jesper Sindahl

Data Structure Lower Bounds for Document Indexing Problems

pdf-format:
LIPIcs-ICALP-2016-93.pdf (0.5 MB)

Abstract

We study data structure problems related to document indexing and pattern matching queries and our main contribution is to show that the pointer machine model of computation can be extremely useful in proving high and unconditional lower bounds that cannot be obtained in any other known model of computation with the current techniques. Often our lower bounds match the known space-query time trade-off curve and in fact for all the problems considered, there is a very good and reasonable match between our lower bounds and the known upper bounds, at least for some choice of input parameters.

The problems that we consider are set intersection queries (both the reporting variant and the semi-group counting variant), indexing a set of documents for two-pattern queries, or forbidden-pattern queries, or queries with wild-cards, and indexing an input set of gapped-patterns (or two-patterns) to find those matching a document given at the query time.

BibTeX - Entry

@InProceedings{afshani_et_al:LIPIcs:2016:6192,
  author =	{Peyman Afshani and Jesper Sindahl Nielsen},
  title =	{{Data Structure Lower Bounds for Document Indexing Problems}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{93:1--93:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6192},
  URN =		{urn:nbn:de:0030-drops-61923},
  doi =		{10.4230/LIPIcs.ICALP.2016.93},
  annote =	{Keywords: Data Structure Lower Bounds, Pointer Machine, Set Intersection, Pattern Matching}
}

Keywords: Data Structure Lower Bounds, Pointer Machine, Set Intersection, Pattern Matching
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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