Arrow Research search

Author name cluster

Alejandro A. Schäffer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

TCS Journal 1996 Journal Article

Multiple matching of parameterized patterns

  • Ramana M. Idury
  • Alejandro A. Schäffer

We extend Baker's theory of parameterized string matching (1993) to algorithms that match multiple patterns in a text. We first consider the case where the patterns are fixed and preprocessed once, and then the case where the pattern set can change by insertions and deletions. Baker's algorithms are based on suffix trees, whereas ours are based on pattern matching automata.

Details DOI

TCS Journal 1994 Journal Article

Dynamic dictionary matching with failure functions

  • Ramana M. Idury
  • Alejandro A. Schäffer

Amir and Farach (1991) and Amir et al. (to appear) recently initiated the study of the dynamic dictionary pattern matching problem. The dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user may also present a text string and ask to search for all occurrences of any patterns in the text. For the static dictionary problem, Aho and Corasick (1975) gave a strategy based on a failure function automaton that takes O(|D|log|Σ|) time to build a dictionary of size |D| and searches a text T in time O(|T|log|Σ|+tocc), where tocc, is the total number of pattern occurrences in the text. Amir et al. (to appear) used an automaton based on suffix trees to solve the dynamic problem. Their method can insert or delete a pattern P in time O(|P|log|D|) and can search a text in time O((|T|+tocc)log|D|). We show that the same bounds can be achieved using a framework based on failure functions. We then show that our approach also allows us to achieve faster search times at the expense of the update times; for constant k, we can achieve linear O(|T|(k+log|Σ|)+k tocc) search time with an update time of O(k|P∥D| 1 k ). This is advantageous if the search texts are much larger than the dictionary or searches are more frequent than updates. Finally, we show how to build the initial dictionary in O(|D|log|Σ|) time, regardless of what combination of search and update times is used.

Details DOI

TCS Journal 1994 Journal Article

Markov analysis of multiple-disk prefetching strategies for external merging

  • Vinay Sadananda Pai
  • Alejandro A. Schäffer
  • Peter J. Varman

Multiple-disk organizations can be used to improve the I/O performance of problems like external merging. Concurrency can be introduced by overlapping I/O requests at different disks and by prefetching additional blocks on each I/O operation. To support this prefetching, a memory cache is required. Markov models for two prefetching strategies are developed and analyzed. Closed-form expressions for the average parallelism obtainable for a given cache size and number of disks are derived for both prefetching strategies. These analytic results are confirmed by simulation.

Details DOI