Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Date: Wed, 1 Feb 2017 14:35:51 +0000 (UTC)
From: "Jim Ferenczi (JIRA)" <jira@apache.org>
To: dev@lucene.apache.org
Message-ID: <JIRA.13035237.1484577409000.8157.1485959751645@Atlassian.JIRA>
In-Reply-To: <JIRA.13035237.1484577409000@Atlassian.JIRA>
References: <JIRA.13035237.1484577409000@Atlassian.JIRA> <JIRA.13035237.1484577409329@jira-lw-us.apache.org>
Subject: [jira] [Updated] (LUCENE-7638) Optimize graph query produced by
 QueryBuilder
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
archived-at: Wed, 01 Feb 2017 14:36:03 -0000


     [ https://issues.apache.org/jira/browse/LUCENE-7638?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Jim Ferenczi updated LUCENE-7638:
---------------------------------
    Attachment: LUCENE-7638.patch

I pushed a new patch that changes how we build boolean graph query with multi-term synonyms. It first finds the articulation points of the graph and builds a boolean query for each point. The articulation points (or cut vertices) are computed using the algorithm described in:
https://en.wikipedia.org/wiki/Biconnected_component
This means that each time we find a state where side paths of different lengths start, we generate all path that start at this state and end at the next articulation points. If {quote}QueryBuilder#autoGenerateMultiTermSynonymsPhraseQuery{quote} is set to true, a phrase query is generated for each path, otherwise a boolean query. 

[~mattweber] [~mikemccand] can you take a look ?


> Optimize graph query produced by QueryBuilder
> ---------------------------------------------
>
>                 Key: LUCENE-7638
>                 URL: https://issues.apache.org/jira/browse/LUCENE-7638
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Jim Ferenczi
>         Attachments: LUCENE-7638.patch, LUCENE-7638.patch
>
>
> The QueryBuilder creates a graph query when the underlying TokenStream contains token with PositionLengthAttribute greater than 1.
> These TokenStreams are in fact graphs (lattice to be more precise) where synonyms can span on multiple terms. 
> Currently the graph query is built by visiting all the path of the graph TokenStream. For instance if you have a synonym like "ny, new york" and you search for "new york city", the query builder would produce two pathes:
> "new york city", "ny city"
> This can quickly explode when the number of multi terms synonyms increase. 
> The query "ny ny" for instance would produce 4 pathes and so on.
> For boolean queries with should or must clauses it should be more efficient to build a boolean query that merges all the intersections in the graph. So instead of "new york city", "ny city" we could produce:
> "+((+new +york) ny) +city"
> The attached patch is a proposal to do that instead of the all path solution.
> The patch transforms multi terms synonyms in graph query for each intersection in the graph. This is not done in this patch but we could also create a specialized query that gives equivalent scores to multi terms synonyms like the SynonymQuery does for single term synonyms.
> For phrase query this patch does not change the current behavior but we could also use the new method to create optimized graph SpanQuery.
> [~mattweber] I think this patch could optimize a lot of cases where multiple muli-terms synonyms are present in a single request. Could you take a look ?


--
This message was sent by Atlassian JIRA
(v6.3.15#6346)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org