Fast nGram-based string search over data encoded using algebraic signatures

Abstract

We propose a novel string search algorithm for data stored once and read many times. We encode the data records coming for storage into their cumulative algebraic signatures. We define two variants of our algorithm that we analyse theoretically and experimentally. The experiments compares the speed of our algorithm to the Boyer-Moore scheme, usually the fastest method known. Our search was up to a seventy times faster for DNA data, up to eleven times faster for ASCII, and up to a six times faster for XML documents. Our method applies to databases in general and to scalable distributed data structures, P2P and grid systems used for the Database as Service (DAS) context especially. The client sends the data for storage at the (remote) servers encoded. The servers match the stored data for the pattern requested by the client without decoding. No local user can then involuntarily discover the content of the stored data. 1.