2 Search Results for "Sindahl Nielsen, Jesper"


Document
Data Structure Lower Bounds for Document Indexing Problems

Authors: Peyman Afshani and Jesper Sindahl Nielsen

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


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.

Cite as

Peyman Afshani and Jesper Sindahl Nielsen. Data Structure Lower Bounds for Document Indexing Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ICALP.2016.93,
  author =	{Afshani, Peyman and Nielsen, Jesper Sindahl},
  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 =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.93},
  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}
}
Document
Applications of Incidence Bounds in Point Covering Problems

Authors: Peyman Afshani, Edvin Berglin, Ingo van Duijn, and Jesper Sindahl Nielsen

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


Abstract
In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in d-dimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed. First we give a non-parameterized algorithm for both problems in O*(2^n) (where the O*(.) notation hides polynomial factors of n) time and polynomial space, beating a previous exponential-space result. Combining this with incidence bounds similar to the famous Szemeredi-Trotter bound, we present a Curve Cover algorithm with running time O*((Ck/log k)^((d-1)k)), where C is some constant. Our result improves the previous best times O*((k/1.35)^k) for Line Cover (where d=2), O*(k^(dk)) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in R^3 with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k).

Cite as

Peyman Afshani, Edvin Berglin, Ingo van Duijn, and Jesper Sindahl Nielsen. Applications of Incidence Bounds in Point Covering Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2016.60,
  author =	{Afshani, Peyman and Berglin, Edvin and van Duijn, Ingo and Sindahl Nielsen, Jesper},
  title =	{{Applications of Incidence Bounds in Point Covering Problems}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{60:1--60:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.60},
  URN =		{urn:nbn:de:0030-drops-59527},
  doi =		{10.4230/LIPIcs.SoCG.2016.60},
  annote =	{Keywords: Point Cover, Incidence Bounds, Inclusion Exclusion, Exponential Algorithm}
}
  • Refine by Author
  • 2 Afshani, Peyman
  • 1 Berglin, Edvin
  • 1 Nielsen, Jesper Sindahl
  • 1 Sindahl Nielsen, Jesper
  • 1 van Duijn, Ingo

  • Refine by Classification

  • Refine by Keyword
  • 1 Data Structure Lower Bounds
  • 1 Exponential Algorithm
  • 1 Incidence Bounds
  • 1 Inclusion Exclusion
  • 1 Pattern Matching
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail