Come strutturare un indice per digitare avanti per un set di dati estremamente grande utilizzando Lucene o simili?

Question

Ho un set di dati di 200 milioni di record + e sto cercando di creare un backend dedicato per alimentare una soluzione di tipo successivo. Lucene è interessante per la sua popolarità e il tipo di licenza, ma sono aperto anche ad altri suggerimenti open source. Sto cercando consigli, racconti dalle trincee, o anche istruzioni dirette migliori su ciò di cui avrò bisogno per quanto riguarda la quantità di hardware e struttura del software. Requisiti:

deve avere:

• La capacità di fare inizia con la corrispondenza sottostringa (digito 'st' e dovrebbe corrispondere a 'Stephen')
• La capacità di restituire risultati molto rapidamente, ho 'd dire che 500ms è un limite superiore.

Bello avere:

• La possibilità di alimentare rilevanza informazioni nel processo di indicizzazione, in modo che, ad esempio, termini più popolari sarebbero stati restituiti avanti degli altri e non solo alfabetico, aka stile Google .
• in parola corrispondente stringa, così per esempio ('st' sarebbe partita 'bestseller')

Nota:

• Questo indice sarà puramente essere usato per il tipo avanti, e non ha bisogno per servire query di ricerca standard.
• Non sono preoccupato di ottenere consigli su come configurare il front-end o AJAX, a condizione che l'indice possa essere interrogato come servizio o direttamente tramite codice Java.

Up voti per tutte le informazioni utili che mi permette di avvicinarmi ad un livello Enterprise Tipo avanti soluzione

Answer 1

Se ogni record è relativamente piccolo (meno di un paio di parole) si può provare una struttura di dati Trie:

http://en.wikipedia.org/wiki/Trie

è costruito per schiarire la corrispondenza prefisso veloce ed è relativamente efficiente dello spazio. Ho usato questa struttura dati per l'esatta funzionalità di completamento automatico che stai cercando, e conosco altri che lo hanno fatto per i siti web di produzione ad alto volume. Nella mia esperienza puoi aspettarti tempi di risposta di decine di millisecondi per una singola query.

È possibile implementare un Trie da soli abbastanza facilmente oppure esistono implementazioni che è possibile scaricare. Vedi

Where do I find a standard Trie based map implementation in Java?

A seconda di cosa implementazione si usa, dovrebbe essere relativamente semplice per contrassegnare ogni record indicizzato con un pertinenza valutazione, che è quindi possibile utilizzare per ordinare da quando si ottiene un elenco di record da una query .

Answer 2

Potrebbe non essere necessario nulla di troppo elegante. La tua lista "deve avere" può essere soddisfatta da un semplice motore di database (ad esempio BerkeleyDB o ESENT). Metti tutte le parole in un tavolo e poi usa cerca di cercare le parole.

Un b-tree con pagine da 8kb dovrebbe ottenere almeno 250 stringhe/pagina, che risulterebbero in pagine foglia 1M, dando un b-tree di altezza 3.Anche con un disco portatile da 5400 RPM, la latenza di I/O è inferiore a 15 ms, nel peggiore dei casi, si otterranno risultati in ~ 50 ms nel caso peggiore (dati completamente non collegati e un'unità lenta).

(Ho creato un'applicazione typeahead che utilizza la classe PersistentDictionary basata su ESENT. Con i record 200K ottengo una risposta di ~ 35ms per la prima ricerca, in cui i dati non sono memorizzati nella cache. il tempo di risposta scende a ~ 5 ms).

Per supportare molti utenti simultanei è possibile aggiungere più cache o dischi più veloci. Probabilmente è possibile effettuare il caching di tutti i dati (8 GB di RAM sono abbastanza convenienti in questi giorni) ei dati di tipo typeahead saranno certamente abbastanza piccoli da adattarsi a un SSD, il che fornirebbe un numero ridicolo di IOPS. Potrei andare per l'SSD perché ciò darà grandi prestazioni anche quando la cache è fredda (ad esempio dopo un riavvio).

Una soluzione basata su motore di database deve essere estremamente rapida da costruire.

Answer 3

Ecco come lo facciamo in SOLR:

La chiave per la ricerca, se per avere il tipo di dati corretto con gli appositi stabilimenti filtro.

Imposta un tipo di dati nello schema chiamato textPrefix

Esempio:

<!-- 
This type is used for type ahead style searching and starts with searching. 
--> 
− 
<fieldType name="textPrefix" class="solr.TextField" positionIncrementGap="1" sortMissingLast="true"> 
− 
<analyzer type="index"> 
<tokenizer class="solr.KeywordTokenizerFactory"/> 
<filter class="ISOLatin1AccentFilterFactory"/> 
<filter class="solr.LowerCaseFilterFactory"/> 
<!-- Remove non alpha-numeric characters --> 
<filter class="solr.PatternReplaceFilterFactory" pattern="[^a-zA-Z0-9 ]" replacement="" replace="all"/> 
<filter class="solr.TrimFilterFactory"/> 
<!-- Remove leading "the "--> 
<filter class="solr.PatternReplaceFilterFactory" pattern="^the\s" replacement="" replace="all"/> 
<filter class="solr.TrimFilterFactory"/> 
<filter class="solr.EdgeNGramFilterFactory" minGramSize="1" maxGramSize="6"/> 
</analyzer> 
− 
<analyzer type="query"> 
<tokenizer class="solr.KeywordTokenizerFactory"/> 
<filter class="ISOLatin1AccentFilterFactory"/> 
<filter class="solr.LowerCaseFilterFactory"/> 
<!-- Remove non alpha-numeric characters --> 
<filter class="solr.PatternReplaceFilterFactory" pattern="[^a-zA-Z0-9 ]" replacement="" replace="all"/> 
<filter class="solr.TrimFilterFactory"/> 
<!-- Remove leading "the "--> 
<filter class="solr.PatternReplaceFilterFactory" pattern="^the\s" replacement="" replace="all"/> 
<filter class="solr.TrimFilterFactory"/> 
</analyzer> 
</fieldType> 

Poi nel documento dello schema creare un nuovo campo di dati come ad esempio:

<field name="CustomerNamePrefix" type="textPrefix" indexed="true" stored="false"/> 

Poi memorizzare una copia del nome del cliente in questo campo CustomerNamePrefix.

Ora, quando si esegue una query su questo campo, è possibile utilizzare semplicemente le prime lettere del nome e questo darà la corrispondenza migliore per tali lettere. A seconda di come fai la tua domanda, potresti aumentare i risultati in base ad altri fattori all'interno del tuo documento.

Esempio:

http://solrserver:8080/solr/select/?q=CustomerNamePrefix:jame&q.alt=*:*&start=0&rows=10&mm=1