EVOLUTION-MANAGER

Edit File: collapsing.html

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.8.1: http://docutils.sourceforge.net/" />
<title>Collapsing of Search Results</title>
<style type="text/css">

/*
:Author: David Goodger (goodger@python.org)
:Id: $Id: html4css1.css 7056 2011-06-17 10:50:48Z milde $
:Copyright: This stylesheet has been placed in the public domain.

Default cascading style sheet for the HTML output of Docutils.

See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/

/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
  border: 0 }

table.borderless td, table.borderless th {
  /* Override padding for "table.docutils td" with "! important".
     The right padding separates the table cells. */
  padding: 0 0.5em 0 0 ! important }

.first {
  /* Override more specific margin styles with "! important". */
  margin-top: 0 ! important }

.last, .with-subtitle {
  margin-bottom: 0 ! important }

.hidden {
  display: none }

a.toc-backref {
  text-decoration: none ;
  color: black }

blockquote.epigraph {
  margin: 2em 5em ; }

dl.docutils dd {
  margin-bottom: 0.5em }

object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
  overflow: hidden;
}

/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
  font-weight: bold }
*/

div.abstract {
  margin: 2em 5em }

div.abstract p.topic-title {
  font-weight: bold ;
  text-align: center }

div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
  margin: 2em ;
  border: medium outset ;
  padding: 1em }

div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
  font-weight: bold ;
  font-family: sans-serif }

div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
  color: red ;
  font-weight: bold ;
  font-family: sans-serif }

/* Uncomment (and remove this text!) to get reduced vertical space in
   compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
  margin-bottom: 0.5em }

div.compound .compound-last, div.compound .compound-middle {
  margin-top: 0.5em }
*/

div.dedication {
  margin: 2em 5em ;
  text-align: center ;
  font-style: italic }

div.dedication p.topic-title {
  font-weight: bold ;
  font-style: normal }

div.figure {
  margin-left: 2em ;
  margin-right: 2em }

div.footer, div.header {
  clear: both;
  font-size: smaller }

div.line-block {
  display: block ;
  margin-top: 1em ;
  margin-bottom: 1em }

div.line-block div.line-block {
  margin-top: 0 ;
  margin-bottom: 0 ;
  margin-left: 1.5em }

div.sidebar {
  margin: 0 0 0.5em 1em ;
  border: medium outset ;
  padding: 1em ;
  background-color: #ffffee ;
  width: 40% ;
  float: right ;
  clear: right }

div.sidebar p.rubric {
  font-family: sans-serif ;
  font-size: medium }

div.system-messages {
  margin: 5em }

div.system-messages h1 {
  color: red }

div.system-message {
  border: medium outset ;
  padding: 1em }

div.system-message p.system-message-title {
  color: red ;
  font-weight: bold }

div.topic {
  margin: 2em }

h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
  margin-top: 0.4em }

h1.title {
  text-align: center }

h2.subtitle {
  text-align: center }

hr.docutils {
  width: 75% }

img.align-left, .figure.align-left, object.align-left {
  clear: left ;
  float: left ;
  margin-right: 1em }

img.align-right, .figure.align-right, object.align-right {
  clear: right ;
  float: right ;
  margin-left: 1em }

img.align-center, .figure.align-center, object.align-center {
  display: block;
  margin-left: auto;
  margin-right: auto;
}

.align-left {
  text-align: left }

.align-center {
  clear: both ;
  text-align: center }

.align-right {
  text-align: right }

/* reset inner alignment in figures */
div.align-right {
  text-align: inherit }

/* div.align-center * { */
/*   text-align: left } */

ol.simple, ul.simple {
  margin-bottom: 1em }

ol.arabic {
  list-style: decimal }

ol.loweralpha {
  list-style: lower-alpha }

ol.upperalpha {
  list-style: upper-alpha }

ol.lowerroman {
  list-style: lower-roman }

ol.upperroman {
  list-style: upper-roman }

p.attribution {
  text-align: right ;
  margin-left: 50% }

p.caption {
  font-style: italic }

p.credits {
  font-style: italic ;
  font-size: smaller }

p.label {
  white-space: nowrap }

p.rubric {
  font-weight: bold ;
  font-size: larger ;
  color: maroon ;
  text-align: center }

p.sidebar-title {
  font-family: sans-serif ;
  font-weight: bold ;
  font-size: larger }

p.sidebar-subtitle {
  font-family: sans-serif ;
  font-weight: bold }

p.topic-title {
  font-weight: bold }

pre.address {
  margin-bottom: 0 ;
  margin-top: 0 ;
  font: inherit }

pre.literal-block, pre.doctest-block, pre.math {
  margin-left: 2em ;
  margin-right: 2em }

span.classifier {
  font-family: sans-serif ;
  font-style: oblique }

span.classifier-delimiter {
  font-family: sans-serif ;
  font-weight: bold }

span.interpreted {
  font-family: sans-serif }

span.option {
  white-space: nowrap }

span.pre {
  white-space: pre }

span.problematic {
  color: red }

span.section-subtitle {
  /* font-size relative to parent (h1..h6 element) */
  font-size: 80% }

table.citation {
  border-left: solid 1px gray;
  margin-left: 1px }

table.docinfo {
  margin: 2em 4em }

table.docutils {
  margin-top: 0.5em ;
  margin-bottom: 0.5em }

table.footnote {
  border-left: solid 1px black;
  margin-left: 1px }

table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
  padding-left: 0.5em ;
  padding-right: 0.5em ;
  vertical-align: top }

table.docutils th.field-name, table.docinfo th.docinfo-name {
  font-weight: bold ;
  text-align: left ;
  white-space: nowrap ;
  padding-left: 0 }

h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
  font-size: 100% }

ul.auto-toc {
  list-style-type: none }

</style>
</head>
<body>
<div class="document" id="collapsing-of-search-results">
<h1 class="title">Collapsing of Search Results</h1>

<div class="contents topic" id="table-of-contents">
<p class="topic-title first">Table of contents</p>
<ul class="simple">
<li><a class="reference internal" href="#introduction" id="id1">Introduction</a></li>
<li><a class="reference internal" href="#performance" id="id2">Performance</a></li>
<li><a class="reference internal" href="#api" id="id3">API</a></li>
<li><a class="reference internal" href="#statistics" id="id4">Statistics</a></li>
<li><a class="reference internal" href="#examples" id="id5">Examples</a><ul>
<li><a class="reference internal" href="#duplicate-elimination" id="id6">Duplicate Elimination</a></li>
<li><a class="reference internal" href="#restricting-the-number-of-matches-per-source" id="id7">Restricting the Number of Matches per Source</a></li>
</ul>
</li>
</ul>
</div>
<div class="section" id="introduction">
<h1><a class="toc-backref" href="#id1">Introduction</a></h1>
<p>Xapian provides the ability to eliminate &quot;duplicate&quot; documents from the MSet.
This feature is known as &quot;collapsing&quot; - think of a pile of duplicates being
collapsed down to leave a single result (or a small number of results).</p>
<p>The collapsing always removes the worse ranked documents (if ranking by
relevance, those with the lowest weight; if ranking by sorting, those which
sort lowest).</p>
<p>Whether two documents count as duplicates of one another is determined by their
&quot;collapse key&quot;.  If a document has an empty collapse key, it will never be
collapsed, but otherwise documents with the same collapse key will be collapsed
together.</p>
<p>Currently the collapse key is taken from a value slot you specify (via the
method <tt class="docutils literal"><span class="pre">Enquire::set_collapse_key()</span></tt>), but in the future you should be able
to build collapse keys dynamically using <tt class="docutils literal"><span class="pre">Xapian::KeyMaker</span></tt> as you already
can for sort keys.</p>
</div>
<div class="section" id="performance">
<h1><a class="toc-backref" href="#id2">Performance</a></h1>
<p>The collapsing is performed during the match process, so is pretty efficient.
In particular, this approach is much better than generating a larger MSet and
post-processing it.</p>
<p>However, if the collapsing eliminates a lot of documents then the collapsed
search will typically take rather longer than the uncollapsed search because
the matcher has to consider many more potential matches.</p>
</div>
<div class="section" id="api">
<h1><a class="toc-backref" href="#id3">API</a></h1>
<p>To enable collapsing, call the method <tt class="docutils literal"><span class="pre">Enquire::set_collapse_key</span></tt> with the
value slot, and optionally the number of matches with each collapse key to keep
(this defaults to 1 if not specified), e.g.:</p>
<pre class="literal-block">
// Collapse on value slot 4, leaving at most 2 documents with each
// collapse key.
enquire.set_collapse_key(4, 2);
</pre>
<p>Once you have the <tt class="docutils literal">MSet</tt> object, you can read the collapse key for each
match with <tt class="docutils literal"><span class="pre">MSetIterator::get_collapse_key()</span></tt>, and also the &quot;collapse count&quot;
with <tt class="docutils literal"><span class="pre">MSetIterator::get_collapse_count()</span></tt>.  The latter is a lower bound on
the number of documents with the same collapse key which collapsing eliminated.</p>
<p>Beware that if you have a percentage cutoff active, then the collapse count
will (at least in the current implementation) will always be either 0 or 1
as it is hard to tell if the collapsed documents would have failed the cutoff.</p>
</div>
<div class="section" id="statistics">
<h1><a class="toc-backref" href="#id4">Statistics</a></h1>
<p>As well as the usual bounds and estimate of the &quot;full&quot; MSet size (i.e. the
size if you'd asked for enough matches to get them all), the matcher also
calculates bounds and an estimate for what the MSet size would be if collapsing
had not been used - you can obtain these using these methods:</p>
<pre class="literal-block">
Xapian::doccount get_uncollapsed_matches_lower_bound() const;
Xapian::doccount get_uncollapsed_matches_estimated() const;
Xapian::doccount get_uncollapsed_matches_upper_bound() const;
</pre>
</div>
<div class="section" id="examples">
<h1><a class="toc-backref" href="#id5">Examples</a></h1>
<p>Here are some ways this feature can be used:</p>
<div class="section" id="duplicate-elimination">
<h2><a class="toc-backref" href="#id6">Duplicate Elimination</a></h2>
<p>If your document collection includes some identical documents, it's unhelpful
when these show up in the search results.  Sometimes it is possible to
eliminate them at index time, but this isn't always feasible.</p>
<p>If you store a checksum (e.g. SHA1 or MD5) of the document contents and store
this in a document value then you can collapse on this to eliminate such
duplicates.</p>
<p>If the document files will be identical, then the checksum can just be of the
file, but sometimes it makes sense to extract and normalise the text, then
calculate the checksum of this.</p>
</div>
<div class="section" id="restricting-the-number-of-matches-per-source">
<h2><a class="toc-backref" href="#id7">Restricting the Number of Matches per Source</a></h2>
<p>It's sometimes desirable to avoid one source dominating the results.  For
example, in a web search application, you might want to show at most three
matches from any website, in which case you could collapse on the hostname
with collapse_max set to 3.</p>
<p>When displaying the results, you can use the collapse count of each match
to inform the user that there are at least that many other matches for this
host (unless you are also using a percentage cutoff - see above).  If it is
non-zero it means you can usefully provide a &quot;show all documents for host
&lt;get_collapse_key()&gt;&quot; button which reruns the search without collapsing and
with a boolean filter for a prefixed term containing the hostname (though note
that this may not always give a button when there are collapsed documents
because the collapse count is a lower bound and may be zero when there are
collapsed matches with the same key).</p>
<p>This approach isn't just useful for web search - the &quot;source&quot; can be defined
usefully in many applications.  For example, a forum or mailing list search
could collapse on a topic or thread identifier, an index at the chapter level
could collapse on a book identifier (such as an ISBN), etc.</p>
</div>
</div>
</div>
</body>
</html>