Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: range query

Sortuj według:

Ogranicz wyniki do:

A Linear Space Data Structure for Range LCP Queries

Ganguly A., Shah R., Patil M., Thankachan S. V.

Fundamenta Informaticae

2018

Vol. 163, nr 3

245--251

Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string S[1...n] of n characters, such that whenever an interval [i; j] comes as a query, we can report max{LCP(Sp,Sq) i ≤ p < q ≤ j} Here LCP((Sp, Sq) is the longest common prefix of the suffixes of S starting at locations p and q, and LCP((Sp,Sq)) is its length. This problem was first addressed by Amir et al. [ISAAC, 2011]. They showed that the query can be answered in O(log log n) time using an O(n log 1+ε n) space data structure for an arbitrarily small constant ε > 0. In an attempt to reduce the space bound, they presented a linear space data structure of O(d log log n) query time, where d = (j - i + 1). In this paper, we present a new linear space data structure with an improved query time of O[formula].

Computing a Longest Common Palindromic Subsequence

Chowdhury S. R., Hasan M. M., Iqbal S., Rahman M. S.

Fundamenta Informaticae

2014

Vol. 129, nr 4

329--340

The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem.

Modele kosztowe dla indeksu STCAT

Gorawski M., Thiele M.

Studia Informatica

2007

Vol. 28, nr 4

19-42

Przedstawiono modele kosztowe służące do estymacji liczby dostępów do węzłów podczas realizacji zapytań zakresowych, agregacyjnych oraz ANN na indeksie STCAT (ang. Spatio-Temporal Cup Aggregate Tree). Zostały one opracowane na podstawie istniejących modeli kosztowych dla indeksów przestrzennych. Modele zaimplementowano, przetestowano i porównano z modelami dla R-drzewa.

The paper proposes cost models for STCAT (Spatio-Temporal Cup Aggregate Tree) index which lets us estimate number of node accesses during executing rangę, aggregate and &NN ąueries. It is based on existing cost models for spatial indices. The models was implemented, tested and compared with cost models for R-tree.