• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
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, dans 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

Voir/Ouvrir
Fast_ngram.PDF (450.5Kb)
Type
Communication / Conférence
Date
2007
Titre du colloque
33rd International Conference on Very Large Data Bases VLDB 2007
Date du colloque
2007-09
Ville du colloque
Vienne
Pays du colloque
Autriche
Titre de l'ouvrage
Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007
Auteurs de l’ouvrage
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.
Éditeur
AMC
Isbn
978-1-59593-649-3
Pages
207-218
Métadonnées
Afficher la notice complète
Auteur(s)
Litwin, Witold
Mokadem, Riad
Rigaux, Philippe cc
Schwartz, Thomas
Résumé (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.
Mots-clés
databases; algebraic signature; Search algorithm

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    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
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo