• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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

Litwin, Witold; Mokadem, Riad; Rigaux, Philippe; Schwartz, Thomas (2007), Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures, in Koch, Christoph; Gehrke, Johannes; Garofalakis, Minos; Srivastava, Divesh; Aberer, Karl; Deshpande, Anand; Forescu, Daniela; Chan, Chee Yong; Ganti, Venkatesh; Kanne, Karl-Christian; Klas, Wolfgang; Neuhold, Erich J., Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007, AMC, p. 207-218

View/Open
Fast_ngram.PDF (450.5Kb)
Type
Communication / Conférence
Date
2007
Conference title
33rd International Conference on Very Large Data Bases VLDB 2007
Conference date
2007-09
Conference city
Vienne
Conference country
Autriche
Book title
Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007
Book author
Koch, Christoph; Gehrke, Johannes; Garofalakis, Minos; Srivastava, Divesh; Aberer, Karl; Deshpande, Anand; Forescu, Daniela; Chan, Chee Yong; Ganti, Venkatesh; Kanne, Karl-Christian; Klas, Wolfgang; Neuhold, Erich J.
Publisher
AMC
ISBN
978-1-59593-649-3
Pages
207-218
Metadata
Show full item record
Author(s)
Litwin, Witold
Mokadem, Riad
Rigaux, Philippe cc
Schwartz, Thomas
Abstract (EN)
We 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.
Subjects / Keywords
databases; algebraic signature; Search algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    Cumulative Algebraic Signatures for Fast String Search, Protection Against Incidental Viewing and Corruption of Data in an SDDS 
    Litwin, Witold; Mokadem, Riad; Schwarz, Thomas (2007) Communication / Conférence
  • Thumbnail
    AS-Index: A Structure For String Search Using n-grams and Algebraic Signatures 
    Constantin, Camelia; du Mouza, Cedric; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas (2016) Article accepté pour publication ou publié
  • Thumbnail
    AS-Index: A Structure For String Search Using n-grams and Algebraic Signatures 
    du Mouza, Cedric; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas (2009) Communication / Conférence
  • Thumbnail
    AS-Index: A Structure for String Search Using n-Grams and Algebraic Signatures 
    Rigaux, Philippe; Litwin, Witold; du Mouza, Cédric; Schwarz, Thomas (2009) Communication / Conférence
  • Thumbnail
    Large-scale indexing of spatial data in distributed repositories: the SD-Rtree 
    Rigaux, Philippe; Litwin, Witold; du Mouza, Cédric (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo