You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ct...@apache.org on 2021/08/12 15:46:28 UTC
[lucene-solr] branch branch_8x updated: SOLR-14655: Add MinHash docs
This is an automated email from the ASF dual-hosted git repository.
ctargett pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new 48ce929 SOLR-14655: Add MinHash docs
48ce929 is described below
commit 48ce929adcf27f7017f67adcb1355c2947303495
Author: Cassandra Targett <ct...@apache.org>
AuthorDate: Thu Aug 12 10:45:48 2021 -0500
SOLR-14655: Add MinHash docs
---
solr/solr-ref-guide/src/filter-descriptions.adoc | 52 ++++++
solr/solr-ref-guide/src/other-parsers.adoc | 193 +++++++++++++++++++++++
2 files changed, 245 insertions(+)
diff --git a/solr/solr-ref-guide/src/filter-descriptions.adoc b/solr/solr-ref-guide/src/filter-descriptions.adoc
index a50c404..c4f6fe8 100644
--- a/solr/solr-ref-guide/src/filter-descriptions.adoc
+++ b/solr/solr-ref-guide/src/filter-descriptions.adoc
@@ -964,6 +964,58 @@ With this configuration the set of mappings is named "english" and can be manage
See <<Synonym Graph Filter>> below for example input/output.
+== MinHash Filter
+
+Generates a repeatably random fixed number of hash tokens from all the input tokens in the stream.
+To do this it first consumes all of the input tokens from its source.
+This filter would normally be preceded by a <<Shingle Filter>>, as shown in the example below.
+
+Each input token is hashed.
+It is subsequently "rehashed" `hashCount` times by combining with a set of precomputed hashes.
+For each of the resulting hashes, the hash space is divided in to `bucketCount` buckets.
+The lowest set of `hashSetSize` hashes (usually a set of one) is generated for each bucket.
+
+This filter generates one type of signature or sketch for the input tokens and can be used to compute Jaccard similarity between documents.
+
+*Arguments:*
+
+`hashCount`::
+The number of hashes to use.
+The default is `1`.
+
+`bucketCount`::
+The number of buckets to use.
+The default is `512`.
+
+`hashSetSize`::
+The size of the set for the lowest hashes from each bucket.
+The default is `1`.
+
+`withRotation`::
+If a hash bucket is empty, generate a hash value from the first previous bucket that has a value.
+The default is `true` if the `bucketCount` is greater than `1` and `false` otherwise.
+
+The number of hashes generated depends on the options above.
+With the default settings for `withRotation`, the number of hashes generated is `hashCount` x `bucketCount` x `hashSetSize` => 512, by default.
+
+*Example:*
+
+[source,xml]
+----
+<analyzer>
+ <tokenizer class="solr.ICUTokenizerFactory"/>
+ <filter class="solr.ICUFoldingFilterFactory"/>
+ <filter class="solr.ShingleFilterFactory" minShingleSize="5" outputUnigrams="false" outputUnigramsIfNoShingles="false" maxShingleSize="5" tokenSeparator=" "/>
+ <filter class="org.apache.lucene.analysis.minhash.MinHashFilterFactory" bucketCount="512" hashSetSize="1" hashCount="1"/>
+</analyzer>
+----
+
+*In:* "woof woof woof woof woof"
+
+*Tokenizer to Filter:* "woof woof woof woof woof"
+
+*Out:* "℁팽徭聙↝ꇁ홱杯", "℁팽徭聙↝ꇁ홱杯", "℁팽徭聙↝ꇁ홱杯", .... a total of 512 times
+
== N-Gram Filter
Generates n-gram tokens of sizes in the given range. Note that tokens are ordered by position and then by gram size.
diff --git a/solr/solr-ref-guide/src/other-parsers.adoc b/solr/solr-ref-guide/src/other-parsers.adoc
index 7441ec5..1bbd636 100644
--- a/solr/solr-ref-guide/src/other-parsers.adoc
+++ b/solr/solr-ref-guide/src/other-parsers.adoc
@@ -903,6 +903,199 @@ Example:
{!maxscore tie=0.01}C OR (D AND E)
----
+== MinHash Query Parser
+
+The `MinHashQParser` builds queries for fields analysed with the `MinHashFilterFactory`.
+The queries measure Jaccard similarity between the query string and MinHash fields; allowing for faster, approximate matching if required.
+The parser supports two modes of operation.
+The first, when tokens are generated from text by normal analysis; and the second, when explicit tokens are provided.
+
+Currently the score returned by the query reflects the number of top level elements that match and is *not* normalised between 0 and 1.
+
+`sim`::
+The required minimum similarity.
+The default behaviour is to find any similarity greater than zero.
+A numeric value between `0.0` and `1.0`.
+
+`tp`::
+The required true positive rate.
+The default is `1.0`.
+For values lower than `1.0`, an optimised and faster banded query may be used.
+The banding behaviour depends on the values of `sim` and `tp` requested.
+
+`field`::
+The field in which the MinHash value is indexed.
+This field is normally used to analyse the text provided to the query parser.
+It is also used for the query field.
+
+`sep`::
+A separator string.
+By default, this is the empty string, "".
+If a non-empty separator string is provided, the query string is interpreted as a list of pre-analysed values separated by the separator string.
+In this case, no other analysis of the string is performed: the tokens are used as found.
+
+`analyzer_field`::
+This parameter can be used to define how text is analysed, distinct from the query field.
+It is used to analyse query text when using a pre-analysed string `field` to store MinHash values.
+See the example below.
+
+This query parser is registered with the name `min_hash`.
+
+=== Example with Analysed Fields
+
+Typical analysis:
+
+[source,xml]
+----
+ <fieldType name="text_min_hash" class="solr.TextField" positionIncrementGap="100">
+ <analyzer>
+ <tokenizer class="solr.ICUTokenizerFactory"/>
+ <filter class="solr.ICUFoldingFilterFactory"/>
+ <filter class="solr.ShingleFilterFactory" minShingleSize="5" outputUnigrams="false" outputUnigramsIfNoShingles="false" maxShingleSize="5" tokenSeparator=" "/>
+ <filter class="org.apache.lucene.analysis.minhash.MinHashFilterFactory" bucketCount="512" hashSetSize="1" hashCount="1"/>
+ </analyzer>
+ </fieldType>
+...
+
+ <field name="min_hash_analysed" type="text_min_hash" multiValued="false" indexed="true" stored="false" />
+----
+
+Here, the input text is split on whitespace, the tokens normalised, the resulting token stream assembled into a stream of all the 5 word shingles which are then hashed.
+The lowest hashes from each of 512 buckets are kept and produced as the output tokens.
+
+Queries to this field would need to generate at least one shingle so would require 5 distinct tokens.
+
+Example queries:
+
+[source,text]
+----
+ {!min_hash field="min_hash_analysed"}At least five or more tokens
+
+ {!min_hash field="min_hash_analysed" sim="0.5"}At least five or more tokens
+
+ {!min_hash field="min_hash_analysed" sim="0.5" tp="0.5"}At least five or more tokens
+----
+
+=== Example with Pre-Analysed Fields
+
+Here, the MinHash is pre-computed, most likely using Lucene analysis inline as shown below.
+It would be more prudent to get the analyser from the schema.
+
+[source,java]
+----
+ ICUTokenizerFactory factory = new ICUTokenizerFactory(Collections.EMPTY_MAP);
+ factory.inform(null);
+ Tokenizer tokenizer = factory.create();
+ tokenizer.setReader(new StringReader(text));
+ ICUFoldingFilterFactory filter = new ICUFoldingFilterFactory(Collections.EMPTY_MAP);
+ TokenStream ts = filter.create(tokenizer);
+ HashMap<String, String> args = new HashMap<>();
+ args.put("minShingleSize", "5");
+ args.put("outputUnigrams", "false");
+ args.put("outputUnigramsIfNoShingles", "false");
+ args.put("maxShingleSize", "5");
+ args.put("tokenSeparator", " ");
+ ShingleFilterFactory sff = new ShingleFilterFactory(args);
+ ts = sff.create(ts);
+ HashMap<String, String> args2 = new HashMap<>();
+ args2.put("bucketCount", "512");
+ args2.put("hashSetSize", "1");
+ args2.put("hashCount", "1");
+ MinHashFilterFactory mhff = new MinHashFilterFactory(args2);
+ ts = mhff.create(ts);
+
+ CharTermAttribute termAttribute = ts.getAttribute(CharTermAttribute.class);
+
+ ts.reset();
+ while (ts.incrementToken())
+ {
+ char[] buff = termAttribute.buffer();
+ ...
+ }
+ ts.end();
+----
+
+The schema will just define a multi-valued string value and an optional field to use at anlysis time - similar to above.
+
+[source,xml]
+----
+ <field name="min_hash_string" type="strings" multiValued="true" indexed="true" stored="true"/>
+
+ <!-- Optional -->
+ <field name="min_hash_analysed" type="text_min_hash" multiValued="false" indexed="true" stored="false"/>
+
+ <fieldType name="strings" class="solr.StrField" sortMissingLast="true" multiValued="true"/>
+
+ <!-- Optional -->
+ <fieldType name="text_min_hash" class="solr.TextField" positionIncrementGap="100">
+ <analyzer>
+ <tokenizer class="solr.ICUTokenizerFactory"/>
+ <filter class="solr.ICUFoldingFilterFactory"/>
+ <filter class="solr.ShingleFilterFactory" minShingleSize="5" outputUnigrams="false" outputUnigramsIfNoShingles="false" maxShingleSize="5" tokenSeparator=" "/>
+ <filter class="org.apache.lucene.analysis.minhash.MinHashFilterFactory" bucketCount="512" hashSetSize="1" hashCount="1"/>
+ </analyzer>
+ </fieldType>
+----
+
+Example queries:
+
+[source,plain]
+----
+{!min_hash field="min_hash_string" sep=","}HASH1,HASH2,HASH3
+
+{!min_hash field="min_hash_string" sim="0.9" analyzer_field="min_hash_analysed"}Lets hope the config and code for analysis are in sync
+----
+
+It is also possible to query analysed fields using known hashes (the reverse of the above)
+
+[source,plain]
+{!min_hash field="min_hash_analysed" analyzer_field="min_hash_string" sep=","}HASH1,HASH2,HASH3
+
+Pre-analysed fields mean hash values can be recovered per document rather than re-hashed.
+An initial query stage that returns the minhash stored field could be followed by a `min_hash` query to find similar documents.
+
+=== Banded Queries
+
+The default behaviour of the query parser, given the configuration above is to generate a boolean query and OR 512 constant score term queries together: one for each hash.
+In this case, generating a score of 1 if one hash matches and a score of 512 if they all match.
+
+A banded query mixes conjunctions and disjunctions.
+We could have 256 bands each of two queries ANDed together, 128 with 4 hashes ANDed together etc.
+With fewer bands query performance increases but we may miss some matches.
+There is a trade off between speed and accuracy.
+With 64 bands the score will range from 0 to 64 (the number of bands ORed together)
+
+Given the required similarity and an acceptable true positive rate, the query parser computes the appropriate band size^[1]^.
+It finds the minimum number of bands subject to
+
+latexmath:[tp \leq 1 - (1 - sim^{rows})^{bands}]
+
+If there are not enough hashes to fill the final band of the query it wraps to the start.
+
+=== A Note on Similarity
+
+Low similarities can be meaningful.
+The number of 5 word hashes is large.
+Even a single match may indicate some kind of similarity either in meaning, style or structure.
+
+=== Further Reading
+
+For a general introduction see "Mining of Massive Datasets"^[1]^.
+
+For documents of ~1500 words expect an index size overhead of ~10%; your milage will vary.
+512 hashes would be expected to represent ~2500 words well.
+
+Using a set of MinHash values was proposed in the initial paper^[2]^ but provides a biased estimate of Jaccard similarity.
+There may be cases where that bias is a good thing.
+Likewise with rotation and short documents.
+The implementation is derived from an unbiased method proposed in later work^[3]^.
+
+^[1]^ Leskovec, Jure; Rajaraman, Anand & Ullman, Jeffrey D. "Mining of Massive Datasets", Cambridge University Press; 2 edition (December 29, 2014), Chapter 3, ISBN: 9781107077232.
+
+^[2]^ Broder, Andrei Z. (1997), "On the resemblance and containment of documents", Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997 (PDF), IEEE, pp. 21–29, doi:10.1109/SEQUEN.1997.666900.
+
+^[3]^ Shrivastava, Anshumali & Li, Ping (2014), "Improved Densification of One Permutation Hashing", 30th Conference on Uncertainty in Artificial Intelligence (UAI), Quebec City, Quebec, Canada, July 23-27, 2014, AUAI, pp. 225-234, http://www.auai.org/uai2014/proceedings/individuals/225.pdf
+
== More Like This Query Parser
The `MLTQParser` enables retrieving documents that are similar to a given document.