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.2019.6
URN: urn:nbn:de:0030-drops-104773
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10477/
Go to the corresponding LIPIcs Volume Portal

Amir, Amihood ; Kondratovsky, Eitan

Sufficient Conditions for Efficient Indexing Under Different Matchings

pdf-format:
LIPIcs-CPM-2019-6.pdf (0.5 MB)

Abstract

The most important task derived from the massive digital data accumulation in the world, is efficient access to this data, hence the importance of indexing. In the last decade, many different types of matching relations were defined, each requiring an efficient indexing scheme. Cole and Hariharan in a ground breaking paper [Cole and Hariharan, SIAM J. Comput., 33(1):26-42, 2003], formulate sufficient conditions for building an efficient indexing for quasi-suffix collections, collections that behave as suffixes. It was shown that known matchings, including parameterized, 2-D array and order preserving matchings, fit their indexing settings. In this paper, we formulate more basic sufficient conditions based on the order relation derived from the matching relation itself, our conditions are more general than the previously known conditions.

BibTeX - Entry

@InProceedings{amir_et_al:LIPIcs:2019:10477,
  author =	{Amihood Amir and Eitan Kondratovsky},
  title =	{{Sufficient Conditions for Efficient Indexing Under Different Matchings}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Nadia Pisanti and Solon P. Pissis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10477},
  URN =		{urn:nbn:de:0030-drops-104773},
  doi =		{10.4230/LIPIcs.CPM.2019.6},
  annote =	{Keywords: off-the-shelf indexing algorithms, general matching relations, weaker sufficient conditions for indexing}
}

Keywords: off-the-shelf indexing algorithms, general matching relations, weaker sufficient conditions for indexing
Collection: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Issue Date: 2019
Date of publication: 06.06.2019

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