xapian-core/docs/collapsing.rst

   1 .. Copyright (C) 2009,2011 Olly Betts
   2
   3 ============================
   4 Collapsing of Search Results
   5 ============================
   6
   7 .. contents:: Table of contents
   8
   9 Introduction
  10 ============
  11
  12 Xapian provides the ability to eliminate "duplicate" documents from the MSet.
  13 This feature is known as "collapsing" - think of a pile of duplicates being
  14 collapsed down to leave a single result (or a small number of results).
  15
  16 The collapsing always removes the worse ranked documents (if ranking by
  17 relevance, those with the lowest weight; if ranking by sorting, those which
  18 sort lowest).
  19
  20 Whether two documents count as duplicates of one another is determined by their
  21 "collapse key".  If a document has an empty collapse key, it will never be
  22 collapsed, but otherwise documents with the same collapse key will be collapsed
  23 together.
  24
  25 Currently the collapse key is taken from a value slot you specify (via the
  26 method ``Enquire::set_collapse_key()``), but in the future you should be able
  27 to build collapse keys dynamically using ``Xapian::KeyMaker`` as you already
  28 can for sort keys.
  29
  30 Performance
  31 ===========
  32
  33 The collapsing is performed during the match process, so is pretty efficient.
  34 In particular, this approach is much better than generating a larger MSet and
  35 post-processing it.
  36
  37 However, if the collapsing eliminates a lot of documents then the collapsed
  38 search will typically take rather longer than the uncollapsed search because
  39 the matcher has to consider many more potential matches.
  40
  41 API
  42 ===
  43
  44 To enable collapsing, call the method ``Enquire::set_collapse_key`` with the
  45 value slot, and optionally the number of matches with each collapse key to keep
  46 (this defaults to 1 if not specified), e.g.::
  47
  48     // Collapse on value slot 4, leaving at most 2 documents with each
  49     // collapse key.
  50     enquire.set_collapse_key(4, 2);
  51
  52 Once you have the ``MSet`` object, you can read the collapse key for each
  53 match with ``MSetIterator::get_collapse_key()``, and also the "collapse count"
  54 with ``MSetIterator::get_collapse_count()``.  The latter is a lower bound on
  55 the number of documents with the same collapse key which collapsing eliminated.
  56
  57 Beware that if you have a percentage cutoff active, then the collapse count
  58 will (at least in the current implementation) will always be either 0 or 1
  59 as it is hard to tell if the collapsed documents would have failed the cutoff.
  60
  61 Statistics
  62 ==========
  63
  64 As well as the usual bounds and estimate of the "full" MSet size (i.e. the
  65 size if you'd asked for enough matches to get them all), the matcher also
  66 calculates bounds and an estimate for what the MSet size would be if collapsing
  67 had not been used - you can obtain these using these methods::
  68
  69     Xapian::doccount get_uncollapsed_matches_lower_bound() const;
  70     Xapian::doccount get_uncollapsed_matches_estimated() const;
  71     Xapian::doccount get_uncollapsed_matches_upper_bound() const;
  72
  73 Examples
  74 ========
  75
  76 Here are some ways this feature can be used:
  77
  78 Duplicate Elimination
  79 ---------------------
  80
  81 If your document collection includes some identical documents, it's unhelpful
  82 when these show up in the search results.  Sometimes it is possible to
  83 eliminate them at index time, but this isn't always feasible.
  84
  85 If you store a checksum (e.g. SHA1 or MD5) of the document contents and store
  86 this in a document value then you can collapse on this to eliminate such
  87 duplicates.
  88
  89 If the document files will be identical, then the checksum can just be of the
  90 file, but sometimes it makes sense to extract and normalise the text, then
  91 calculate the checksum of this.
  92
  93 Restricting the Number of Matches per Source
  94 --------------------------------------------
  95
  96 It's sometimes desirable to avoid one source dominating the results.  For
  97 example, in a web search application, you might want to show at most three
  98 matches from any website, in which case you could collapse on the hostname
  99 with collapse_max set to 3.
 100
 101 When displaying the results, you can use the collapse count of each match
 102 to inform the user that there are at least that many other matches for this
 103 host (unless you are also using a percentage cutoff - see above).  If it is
 104 non-zero it means you can usefully provide a "show all documents for host
 105 <get_collapse_key()>" button which reruns the search without collapsing and
 106 with a boolean filter for a prefixed term containing the hostname (though note
 107 that this may not always give a button when there are collapsed documents
 108 because the collapse count is a lower bound and may be zero when there are
 109 collapsed matches with the same key).
 110
 111 This approach isn't just useful for web search - the "source" can be defined
 112 usefully in many applications.  For example, a forum or mailing list search
 113 could collapse on a topic or thread identifier, an index at the chapter level
 114 could collapse on a book identifier (such as an ISBN), etc.