[
https://issues.apache.org/jira/browse/LUCENE-3298?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13162752#comment-13162752
]
Carlos González-Cadenas commented on LUCENE-3298:
-------------------------------------------------
Yeap, at the beginning of this project we tried to implement this autocomplete
system using regular inverted indexes, but the response time required for
autocomplete to work from a user perspective is very low (<50ms), and it would
be quite hard to achieve such a performance with inverted indexes.
I still think this is the way to go, but as you say we have to be careful with
the data generation part. Most of the work should be put in making sure that
the data is well distributed and organized in order to avoid combinatorial
explosion.
Let me go in detail with the sources of data permutations and the reasoning
behind them:
1) With regards to infix matches, if a user types "barcelona" we want to match
"hotels in barcelona". In order to achieve this, we generate:
hotels in barcelona => hotels in barcelona
in barcelona => hotels in barcelona
barcelona => hotels in barcelona
The FST should be able to conflate these prefixes nicely in just one path,
right?. Therefore this part shouldn't be a problem.
2) In addition, another feature we want to achieve is to be able to match
inputs without prepositions. That means that if the user types "hotels
barcelona jacuzzi", we should be able to match "hoteles in barcelona with
jacuzzi". Now the only way we envision of doing it properly is to generate this
permutation within the data:
hotels barcelona jacuzzi => hotels in barcelona with jacuzzi
I can see how this can explode the FST by creating different branches.
Theoretically this could be done at runtime without the need of generating the
data, but we don't see a way to do it in a clean way. To make things more
complicated :) we've implemented fuzzy matching at query time (we use a
levenshtein automata generated with the user input + an edit distance and then
we intersect with the FST), and this is making very complicated to do
preposition handling at query time.
3) PP permutations (i.e. hoteles in barcelona with jacuzzi and hoteles with
jacuzzi in barcelona). I don't really see a way to work around this. Probably
we need to be careful and only generate these permutations for the top-K
cities, in order to limit the potential size.
Summarizing, I believe that we can reduce the set of "bad permutations" a lot
if we can figure out how to implement the prepositions at runtime. If you have
any ideas, let me know. Thanks! :)
> FST has hard limit max size of 2.1 GB
> -------------------------------------
>
> Key: LUCENE-3298
> URL: https://issues.apache.org/jira/browse/LUCENE-3298
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
> Attachments: LUCENE-3298.patch
>
>
> The FST uses a single contiguous byte[] under the hood, which in java is
> indexed by int so we cannot grow this over Integer.MAX_VALUE. It also
> internally encodes references to this array as vInt.
> We could switch this to a paged byte[] and make the far larger.
> But I think this is low priority... I'm not going to work on it any time soon.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
