Non-Overlapping Indexing -Cache Obliviously

Keywords

Cache Oblivious; Data Structure; String Algorithms; Suffix Trees

Abstract

The non-overlapping indexing problem is defined as follows: pre-process a given text T[1, n] of length n into a data structure such that whenever a pattern P[1, p] comes as an input, we can efficiently report the largest set of non-overlapping occurrences of P in T. The best known solution is by Cohen and Porat [ISAAC, 2009]. Their index size is O(n) words and query time is optimal O(p+nocc), where nocc is the output size. We study this problem in the cache-oblivious model and present a new data structure of size O(n log n) words. It can answer queries in optimal O( p/B + logB n + nocc/B ) I/Os, where B is the block size.

Publication Date

5-1-2018

Publication Title

Leibniz International Proceedings in Informatics, LIPIcs

Volume

105

Number of Pages

81-89

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.4230/LIPIcs.CPM.2018.8

Socpus ID

85048307992 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85048307992

This document is currently not available here.

Share

COinS