NGRAM_MATCH behavior does not appear to match documentation and makes it less useful for substring search

[MrCreosote]

My Environment

• ArangoDB Version: 3.11.4
• Deployment Mode: Single server from arangodb:3.11 Docker image from Dockerhub
• Deployment Strategy: whatever the docker image does
• Configuration: whatever the docker image does
• Infrastructure: laptop
• Operating System: Ubuntu 18.04
• Total RAM in your machine: 32GB, 20GB for VirtualBox VM
• Disks in use: SSD
• Used Package: Docker image

Component, Query & Data

Affected feature: ArangoSearch query using web interface

AQL query (if applicable): Query 1:

RETURN NGRAM_MATCH("flaviobacter", "obact", 1, "ngram3")

Query 2:

RETURN NGRAM_MATCH("xxobaxxxbacxxxactxxx", "obact", 1, "ngram3")

AQL explain and/or profile (if applicable): N/A

Dataset: N/A

Size of your Dataset on disk: N/A

Replication Factor & Number of Shards (Cluster only): RF: 3 Shards: N/A

Steps to reproduce

1. Add the following analyzer to the DB:

   {
   "name": "test::ngram3",
   "type": "pipeline",
   "features": [
       "frequency",
       "position"
   ],
   "properties": {
       "pipeline": [
           {
               "type": "norm",
               "properties": {
                   "locale": "en",
                   "case": "lower",
                   "accent": false
               }
           },
           {
               "type": "ngram",
               "properties": {
                   "min": 3,
                   "max": 3,
                   "preserveOriginal": false,
                   "streamType": "utf8",
                   "startMarker": "",
                   "endMarker": ""
               }
           }
       ]
   }
   }

2. Execute query 1, note the true result
3. Execute query 2, note the true result

Problem: The documentation describes the scoring of the ngram match as:

The similarity is calculated by counting how long the longest sequence of matching n-grams is, divided by the target’s total n-gram count. Only fully matching n-grams are counted. [Emphasis mine]

Based on that description I would expect query 1 to match (3 trigrams in the query, a sequence of 3 matching trigrams in the target for a score of 1) and query 2 to fail (3 trigrams in the query, the longest matching sequence is 1 trigram in the target for a score of 0.33), but both match.

I was hoping to use NGRAM_MATCH as a fast (and it's definitely really fast) substring query but given the current behavior that's not going to work, unless I'm doing something wrong.

Expected result: Query 2's result should be false if I understand the documentation correctly

Thanks for any advice you can give me if there's something incorrect with my setup

[MBkkt]

Hello.

query 2 to fail (3 trigrams in the query, the longest matching sequence is 1 trigram in the target for a score of 0.33)

It's not correct, longest matching sequence is also 3 here xxobaxxxbacxxxactxxx

[MBkkt]

In general you can imagine it like

"obact" -> target ngram array [oba bac act] "xxobaxxxbacxxxactxxx" -> ngram array [xxo xob oba bax ....]

And we just find LCP longest common subsequence, when score is lcp divide by target array length

[MBkkt]

If you have long tokens (which is separated to ngrams) probably will be good is increase ngram size

[MrCreosote]

Thanks for clearing up my understanding.

It's not correct, longest matching sequence is also 3 here xxobaxxxbacxxxactxxx

Hmm, that's not what I would think of as a sequence. I would think they'd need to be contiguous. I understand that things are working as intended though, so at most we're talking about a terminology difference.

That being said - is there a way to use arangosearch to find an arbitrary length substring in a field without scanning every document value for the field? There's LIKE, which the documentation says is backed by indexes, but for a search like %foo% to use an index you'd need a suffix tree or something like that, not just a regular inverted index (right?). My naive assumption is that inverted indexes will only accelerate LIKE searches where the left side of the query is anchored, like foo%.

[MBkkt]

There's LIKE, which the documentation says is backed by indexes, but for a search like %foo% to use an index you'd need a suffix tree or something like that, not just a regular inverted index (right?). My naive assumption is that inverted indexes will only accelerate LIKE searches where the left side of the query is anchored, like foo%.

Yep, you're completely right, but we plan to add wildcard analyzer in 3.12. That helps for leading wildcard query too (internally it uses ngram and post filtering)

[MBkkt]

As another option you can try to make ngram with different size and search your substring by exact term search. But it can make inverted index big ofc

[MrCreosote]

we plan to add wildcard analyzer in 3.12

Oh great, looking forward to 3.12 then. Hurry hurry hurry!