Show simple item record

Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures

dc.contributor.authorLitwin, Witold
dc.contributor.authorMokadem, Riad
dc.contributor.authorRigaux, Philippe
HAL ID: 172888
ORCID: 0000-0002-9189-7292
dc.contributor.authorSchwartz, Thomas
dc.date.accessioned2010-10-21T13:25:42Z
dc.date.available2010-10-21T13:25:42Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4957
dc.language.isoenen
dc.subjectdatabasesen
dc.subjectalgebraic signatureen
dc.subjectSearch algorithmen
dc.subject.ddc005.7en
dc.titleFast nGram-Based String Search Over Data Encoded Using Algebraic Signaturesen
dc.typeCommunication / Conférence
dc.description.abstractenWe propose a novel string search algorithm for data stored once and read many times. Our search method combines the sublinear traversal of the record (as in Boyer Moore or Knuth-Morris-Pratt) with the agglomeration of parts of the record and search pattern into a single character – the algebraic signature – in the manner of Karp-Rabin. Our experiments show that our algorithm is up to seventy times faster for DNA data, up to eleven times faster for ASCII, and up to a six times faster for XML documents compared with an im- plementation of Boyer-Moore. To obtain this speed-up, we store records in encoded form, where each original character is replaced with an algebraic signature. Our method applies to records stored in databases in general and to distributed implementations of a Database As Service (DAS) in particular. Clients send records for insertion and search patterns already in encoded form and servers never operate on records in clear text. No one at a node can involuntarily discover the content of the stored data.en
dc.identifier.citationpages207-218en
dc.relation.ispartoftitleProceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007en
dc.relation.ispartofeditorKoch, Christoph
dc.relation.ispartofeditorGehrke, Johannes
dc.relation.ispartofeditorGarofalakis, Minos
dc.relation.ispartofeditorSrivastava, Divesh
dc.relation.ispartofeditorAberer, Karl
dc.relation.ispartofeditorDeshpande, Anand
dc.relation.ispartofeditorForescu, Daniela
dc.relation.ispartofeditorChan, Chee Yong
dc.relation.ispartofeditorGanti, Venkatesh
dc.relation.ispartofeditorKanne, Karl-Christian
dc.relation.ispartofeditorKlas, Wolfgang
dc.relation.ispartofeditorNeuhold, Erich J.
dc.relation.ispartofpublnameAMCen
dc.relation.ispartofdate2007
dc.description.sponsorshipprivateouien
dc.subject.ddclabelOrganisation des donnéesen
dc.relation.ispartofisbn978-1-59593-649-3en
dc.relation.conftitle33rd International Conference on Very Large Data Bases VLDB 2007en
dc.relation.confdate2007-09
dc.relation.confcityVienneen
dc.relation.confcountryAutricheen


Files in this item

Thumbnail
Name:
Fast_ngram.PDF
Size:
450.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record