AsterixDB Support of Similarity Queries

Table of Contents

• Motivation
• Data Types and Similarity Functions
• Similarity Selection Queries
• Similarity Join Queries
• Using Indexes to Support Similarity Queries

Motivation [Back to TOC]

Similarity queries are widely used in applications where users need to find objects that satisfy a similarity predicate, while exact matching is not sufficient. These queries are especially important for social and Web applications, where errors, abbreviations, and inconsistencies are common. As an example, we may want to find all the movies starring Schwarzenegger, while we don’t know the exact spelling of his last name (despite his popularity in both the movie industry and politics :-)). As another example, we want to find all the Facebook users who have similar friends. To meet this type of needs, AsterixDB supports similarity queries using efficient indexes and algorithms.

Data Types and Similarity Functions [Back to TOC]

AsterixDB supports edit distance (on strings) and Jaccard (on sets). For instance, in our TinySocial example, the friendIds of a Gleambook user forms a set of friends, and we can define a similarity between the sets of friends of two users. We can also convert a string to a set of grams of a length “n” (called “n-grams”) and define the Jaccard similarity between the two gram sets of the two strings. Formally, the “n-grams” of a string are its substrings of length “n”. For instance, the 3-grams of the string schwarzenegger are sch, chw, hwa, …, ger.

AsterixDB provides tokenization functions to convert strings to sets, and the similarity functions.

Similarity Selection Queries [Back to TOC]

The following query asks for all the Gleambook users whose name is similar to Suzanna Tilson, i.e., their edit distance is at most 2.

    use TinySocial;

    select u
    from GleambookUsers u
    where edit_distance(u.name, "Suzanna Tilson") <= 2;

The following query asks for all the Gleambook users whose set of friend ids is similar to [1,5,9,10], i.e., their Jaccard similarity is at least 0.6.

    use TinySocial;

    select u
    from GleambookUsers u
    where similarity_jaccard(u.friendIds, [1,5,9,10]) >= 0.6f;

AsterixDB allows a user to use a similarity operator ~= to express a condition by defining the similarity function and threshold using “set” statements earlier. For instance, the above query can be equivalently written as:

    use TinySocial;

    set simfunction "jaccard";
    set simthreshold "0.6f";

    select u
    from GleambookUsers u
    where u.friendIds ~= [1,5,9,10];

In this query, we first declare Jaccard as the similarity function using simfunction and then specify the threshold 0.6f using simthreshold.

Similarity Join Queries [Back to TOC]

AsterixDB supports fuzzy joins between two sets. The following query finds, for each Gleambook user, all Chirp users with names similar to their name based on the edit distance.

    use TinySocial;

    set simfunction "edit-distance";
    set simthreshold "3";

    select gbu.id, gbu.name, (select cu.screenName, cu.name
                              from ChirpUsers cu
                              where cu.name ~= gbu.name) as similar_users
    from GleambookUsers gbu;

Using Indexes to Support Similarity Queries [Back to TOC]

AsterixDB uses two types of indexes to support similarity queries, namely “ngram index” and “keyword index”.

    use TinySocial;

    create index gbUserIdx on GleambookUsers(name) type ngram(3);

    use TinySocial;

    select u
    from GleambookUsers u
    where edit_distance(u.name, "Suzanna Tilson") <= 2;

    use TinySocial;

    select u
    from GleambookUsers u
    where edit_distance_check(u.name, "Suzanna Tilson", 2)[0];

    use TinySocial;

    select m
    from GleambookMessages m
    where contains(m.message, "phone");

    use TinySocial;

    drop index GleambookMessages.gbMessageIdx if exists;
    create index gbMessageIdx on GleambookMessages(message) type keyword;

    select m
    from GleambookMessages m
    where similarity_jaccard_check(word_tokens(m.message), word_tokens("love like ccast"), 0.2f)[0];

    use TinySocial;

    create index gbUserIdxFIds on GleambookUsers(friendIds) type keyword;

    select u
    from GleambookUsers u
    where similarity_jaccard_check(u.friendIds, {{3,10}}, 0.5f)[0];

    use TinySocial;

    select u
    from GleambookUsers u
    where similarity_jaccard(u.friendIds, [1,5,9,10]) >= 0.6f;

    use TinySocial;

    select u
    from GleambookUsers u
    where similarity_jaccard_check(u.friendIds, [1,5,9,10], 0.6f)[0];