Sorting Facets on CategoryPath (Label) [LUCENE-5370]

[asfimport]

Facet support sorting through FacetRequest.SortOrder. This is used in the ResultSortUtils. For my application it would be very nice if the facets can also be sorted on their label.

I think this could be accomplished by altering FacetRequest with an extra enum SortType, and two extra Heap in ResultSortUtils which instead of comparing the double value, compare the CategoryPath.

What do you think of this idea? Or could the same behaviour be accomplished in a different way already?

(btw: I tried building this patch on the trunk of lucene5.0; but I couldn't get the maven build to build correctly. I will try again lateron on the 4.6 branch.

---

Migrated from LUCENE-5370 by Rob Audenaerde, updated Mar 24 2014

[asfimport]

Rob Audenaerde (migrated from JIRA)

I have implemented sorting on label based on the 4.7 branch. The cost in terms of speed is not really that high compared to retrieving values.

I have an index with 999.999 random documents. To retrieve a top-ten facet list based on value takes +- 510 ms. Retrieving labels takes +- 580 ms.

So it looks like there is only increase in time of about 15%.

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

What does sort by label mean? Do you ignore the counts/weights and just want to show the top-10 label-sorted facets? Or after you compute the top-10 facets (by weight), you want to sort their labels?

Note that sorting by label is greatly affected by the size of the taxonomy, less by the number of documents. Asking the taxonomy to label each ordinal will be very costly if the taxonomy is huge (e.g. not all labels can be cached in memory) vs if it's small.

[asfimport]

Massimo Ferrario (migrated from JIRA)

HI,
I'm also interested in this thread.
For my purpose, it's sufficient to sort facet after compute the top-n facets by weigth
(as suggest by Shai Erera)

Thank in advance for any suggestion.

[asfimport]

Rob Audenaerde (migrated from JIRA)

I currently use the code below:

	private FacetResult getTopValueChildren( int topN, final SortDir sortDir, String dim, String... path ) throws IOException
	{
		if ( topN <= 0 )
		{
			throw new IllegalArgumentException( "topN must be > 0 (got: " + topN + ")" );
		}

		DimConfig dimConfig = this.verifyDim( dim );
		FacetLabel cp = new FacetLabel( dim, path );
		int dimOrd = this.taxoReader.getOrdinal( cp );
		if ( dimOrd == -1 )
		{
			return null;
		}

		TopOrdAndLabelQueue q = new TopOrdAndLabelQueue( Math.min( this.taxoReader.getSize(), topN ) )
		{
			`@Override`
			protected boolean lessThan( OrdAndLabel a, OrdAndLabel b )
			{
				if ( sortDir == SortDir.DESC )
				{
					return super.lessThan( a, b );
				}
				else
				{
					return !super.lessThan( a, b );
				}
			}

		};

		int ord = this.children[dimOrd];
		int totValue = 0;
		int childCount = 0;

		TopOrdAndLabelQueue.OrdAndLabel reuse = null;
		while ( ord != TaxonomyReader.INVALID_ORDINAL )
		{
			if ( this.values[ord] > 0 )
			{
				totValue += this.values[ord];
				childCount++;
				if ( reuse == null )
				{
					reuse = new TopOrdAndLabelQueue.OrdAndLabel();
				}
				reuse.ord = ord;
				reuse.value = this.values[ord];
				reuse.label = this.taxoReader.getPath( ord ).components[cp.length];
				reuse = q.insertWithOverflow( reuse );
			}

			ord = this.siblings[ord];
		}

		if ( totValue == 0 )
		{
			return null;
		}

		if ( dimConfig.multiValued )
		{
			if ( dimConfig.requireDimCount )
			{
				totValue = this.values[dimOrd];
			}
			else
			{
				// Our sum'd value is not correct, in general:
				totValue = -1;
			}
		}
		else
		{
			// Our sum'd dim value is accurate, so we keep it
		}

		LabelAndValue[] labelValues = new LabelAndValue[q.size()];
		for ( int i = labelValues.length - 1; i >= 0; i-- )
		{
			TopOrdAndLabelQueue.OrdAndLabel ordAndValue = q.pop();
			labelValues[i] = new LabelAndValue( ordAndValue.label, ordAndValue.value );
		}

		return new FacetResult( dim, path, totValue, labelValues, childCount );
	}

I use the same approach as sorting on counts, except that I sort on the label instead. It costs some in terms of retrieving the labels from the taxonomyreader.

So I ignore the counts in terms of sorting; but I do use them because the user is interesed in the counts fo the sorted facet labels.

Btw. I'm currently experimenting with a similar approach where we have facetlabels that are effectively numbers (like currency). Because I do not know on beforehand what will be in the facets, I put the String representation in the FacetLabel and store the numberic value in the Float part of a FloatAssociatedFacetField. Facets then can be sorted on the FloatAssociated value, which should be faster than retrieving labels from the reader.

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

For my purpose, it's sufficient to sort facet after compute the top-n facets by weigth

You can then sort the LabelAndValues[] by their label part.

Btw. I'm currently experimenting with a similar approach where we have facetlabels that are effectively numbers (like currency). Because I do not know on beforehand what will be in the facets, I put the String representation in the FacetLabel and store the numberic value in the Float part of a FloatAssociatedFacetField. Facets then can be sorted on the FloatAssociated value, which should be faster than retrieving labels from the reader.

Do you have a unique value per document? If so, you should consider indexing the values in a NumericDocValues field (not go through the taxonomy at all and FacetsConfig) and then you can use the facet module's range faceting for example.

[asfimport]

Massimo Ferrario (migrated from JIRA)

Yes, I did exaclty what you suggested: I created a simple comparator for FacetResultNode so I can re-order list using string label, after computed the top-n facet.

Yes, I have d unique value per document, but my facet are strings (for example Company Name) not number.
Thanks for suggestions.