Paper Info
Title
Succinct Index for Dynamic Dictionary Matching
Abstract
In this paper we revisit the dynamic dictionary matching problem, which asks for an index for a set of patterns P 1, P 2, ..., P k that can support the following query and update operations efficiently. Given a query text T, we want to find all the occurrences of of these patterns; furthermore, as the set of patterns may change over time, we also want to insert or delete a pattern. The major contribution of this paper is the first succinct index for dynamic dictionary matching. Prior to our work, the most compact index is given by Chan et al. (2007), which is based on the compressed suffix arrays (Grossi and Vitter (2005) and Sadakane (2003)) and the FM-index (Ferragina and Manzini (2005)), and it requires O(n 驴) bits where n is the total length of patterns and 驴 is the alphabet size. We develop a dynamic succinct index using a different (and simpler) paradigm based on suffix sampling. The new index not only improves the space complexity to (1 + o(1))n log驴 + O(klogn) bits, but also the time complexity of the query and update operations. Specifically, the query and update operations respectively take O(|T|logn + occ) and O(|P|log驴 + logn) times, where occ is the number of occurrences.
Year
DOI
Venue
2009
10.1007/978-3-642-10631-6_104
ISAAC
Keywords
Field
DocType
succinct index,new index,dynamic dictionary matching,dynamic succinct index,dynamic dictionary,patterns p,following query,compact index,query text,update operation,space complexity,indexation,time complexity
Discrete mathematics,Combinatorics,Suffix,Computer science,Suffix array,Sampling (statistics),FM-index,Compressed suffix array,Time complexity,Alphabet
Conference
Volume
ISSN
Citations 
5878
0302-9743
9
PageRank 
References 
Authors
0.55
18
5
Name
Order
Citations
PageRank
Wing-Kai Hon185678.67
Tak-Wah Lam21860164.96
Rahul Shah3105961.31
Siu-Lung Tam412719.19
Jeffrey Scott Vitter566281246.72