Approximate dictionary queries

Gerth Stølting Brodal, Leszek Gasieniec

    Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


    Given a set of n binary strings of length m each. We consider the problem of answering d-queries. Given a binary query string of length m, a d-query is to report if there exists a string in the set within Hamming distance d of .
    We present a data structure of size O(nm) supporting 1-queries in time O(m) and the reporting of all strings within Hamming distance 1 of in time O(m). The data structure can be constructed in time O(nm). A slightly modified version of the data structure supports the insertion of new strings in amortized time O(m).
    Original languageEnglish
    Title of host publicationCombinatorial Pattern Matching : 7th Annual Symposium, CPM 96 Laguna Beach, California, June 10–12, 1996 Proceedings
    EditorsDan Hirschberg, Gene Myers
    Number of pages10
    Publication date1996
    ISBN (Print)978-3-540-61258-2
    Publication statusPublished - 1996
    Event7th Annual Symposium Combinatorial Pattern Matching. CPM 1996 - Laguna Beach, CA, United States
    Duration: 10 Jun 199612 Jun 1996


    Conference7th Annual Symposium Combinatorial Pattern Matching. CPM 1996
    Country/TerritoryUnited States
    CityLaguna Beach, CA
    SeriesLecture Notes in Computer Science


    Dive into the research topics of 'Approximate dictionary queries'. Together they form a unique fingerprint.

    Cite this