Balisage Paper: Markup as Index Interface

An inverted index contains a mapping from terms to posting lists.

Terms may represent atomic units of the document.

Terms may be defined by functions over the atomic units of the document.

Term-generating functions may apply contextual information from the document itself, or external context.

There may be alternative, overlapping atomic units.

There may be hierarchies of atomic units.

The set of available terms affects the recall and precision of queries.

Specialized indexes store values of different types and provide mechanisms for returning posting lists satisfying type-specific constraints.

Values may act as terms.

The set of available terms and of values contained in specialized indexes defines the effective information content of the document.

Term vectors may be used to classify and cluster documents.

An inverted index contains a mapping from terms to posting lists.

Terms have some kind of key that can be selected quickly to return a posting list from the inverted index. The essential feature of the key is that it can be ordered, so we can quickly look it up, and that it be distinct, so that different terms have different keys. It doesn't need to be a simple string. Indeed, it doesn't actually necessarily need to be distinct, as long as we are willing to tolerate a certain loss of precision. It is useful to know that the character N-gram dog is not the same term as the word dog, but it isn't a fundamental failure if those terms get consolidated.

Markup features can be used as terms. The fact that a particular element named {http://www.opengis.net/gml/3.2}Point exists in a document can be recorded in an inverted index just as well as the fact that the word dog does. Where tokenization breaks word terms from documents; format-appropriate parsing breaks markup elements from documents. A search for documents containing that markup component will return the set of postings from the inverted index in exactly the same way that a search for documents containing the word dog did.

Just as there was no need to define the set of words to index up front, there is no need to define the set of XML elements or attributes or the set of JSON properties or the set of RFC822 header types to add to the index. As long as there is a parser that breaks out the markup elements for the index, the documents themselves define the index.

Example:

Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
To: "Nupoor Kotasthane" <Nupoor.Kotasthane@marklogic.com>
Date: Wed, 24 Jun 2015 12:20:28 -0700
Subject: interiorPoint
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: "Mary Holstege" <mary.holstege@marklogic.com>
Organization: Mark Logic
Message-ID: <op.x0q1cezwfi7tae@mary-z620.marklogic.com>
User-Agent: Opera Mail/12.16 (Linux)

That looks good to me. //mh
         

Markup components in the inverted index (I am using XPath syntax to indicate markup components as distinct from words in the index.)

//Content-Transfer-Encoding
//Content-Type
//Date
//From
//Message-ID
//MIME-Version
//Organization
//Subject
//To
//User-Agent
         

Terms may represent atomic units of the document.

We have seen how (language-specific) tokenization identifies tokens of different kinds (punctuation vs white space vs words), extracts words from documents, and those words induce terms in the inverted index. Similarly, (format-specific) parsing identifies markup components of different kinds (elements vs attributes vs text), extracts markup components from documents, and those markup components induce terms in the inverted index.

Consider the XML document:

<apidoc:function xmlns:apidoc="http://marklogic.com/xdmp/apidoc"
                 name="distance" type="builtin" lib="geo">
  <apidoc:summary>Returns the distance between two points.</apidoc:summary>
</apidoc:function>
         

The atomic markup units are the three attributes (name, type, and lib), the two elements (apidoc:function and apidoc:summary), and perhaps also the document as a whole and the namespace declaration. An inverted index might have:

//apidoc:function
//apidoc:function/@lib
//apidoc:function/@name
//apidoc:function/@type
//apidoc:summary
           

Given an XML parser, there is no need to define in advance what markup components to add to the index: this is a generic operation.

Terms may be defined by functions over the atomic units of the document.

Various precision- or recall-enhancing functions may be applied to form new terms from existing terms. These functions run the gamut from simple case-folding to advanced linguistic analysis such as sentiment analysis. Generally functions that enhance recall group existing terms into equivalence classes, and functions that enhance precision provide more detailed subdivisions of other terms. Some of this is clearly a matter of perspective: if you regard individual characters as the atoms of the text, then simple word terms are the result of the precision-enhancing function of tokenization.

Precision-enhancing functions over markup atoms divide classes and create distinctions. For example, we may add the specific information about which element is a root element or which elements are contained in other elements:

/apidoc:function
//apidoc:function/apidoc:summary
//apidoc:function//apidoc:summary
         

Recall-enhancing functions over markup atoms create equivalence classes over them. For example, it is possible to collapse markup from different formats to single indexes. Consider the following XML, JSON, and INI file documents.

{"example": 
  {"nested": "here is some content",
   "mixed": false
  }
}
         

and

<example>
  <nested>here is some content</nested>
  <mixed>false</mixed>
</example>
         

and

[example]
nested: here is some content
mixed: false
         

From these we can produce the same markup indexes:

/example
//example
//example/mixed
//example//mixed
//example/nested
//example//nested
//mixed
//nested
         

As with character N-grams, sometimes this can be a matter of perspective: micro-parsing can be seen as either creating pieces of atomic units, or creating new, alternative atomic units. For example, micro-parsing of the CSS in this piece of HTML adds new atomic units/fragments of the attribute unit:

<p style="background-color=red;font-style=italic">Exciting!</p>
         

Micro-parsed markup indexes:

//p/@style/@background-color
//p/@style/@font-style
         

Term-generating functions may apply contextual information from the document itself, or external context.

Adjacent or nearby terms may provide context, for example in disambiguating parts of speech. The language of the text (which may be internally defined for XML documents, or part of the external context, is necessary for performing stemming, decompounding, noun phrase identification, or more advanced linguistic analysis. Extensive knowledge of the world may be necessary for things like entity recognition or synonym identification.

Stemming, case-folding, and soundex indexing have the effect of mapping multiple distinct words to a single term, creating equivalence classes of words. Analogous functions can be applied to markup components as well: case-folding of JSON property names and HTML element names, ignoring element namespaces, having attribute terms that ignore the parent element, "stemming" RFC822 header names by stripping off X-. Functions that require more external knowledge also apply: simple vocabulary mapping can treat p and para as synonyms. Similarly, we can map the rdf:Description element and attribute to the same index entry.

Just as word N-gram indexing creates molecules that enhance precision in searching for phrases, so too can indexing element N-grams and terms formed from parent/child or sibling/sibling relationships create molecules that enhance precision in searching for matching paths: a path like //apidoc:function/apidoc:summary can be matched precisely with a element/child index entries, slightly less precisely with an element/descendant index entries, and quite imprecisely with just separate element index entries.

Beyond simple vocabulary mapping, one can create "synonyms" of markup, reconceptualizing the manifest markup even across vocabularies:

"aboutness"=union((//title)[1],/db:article/db:abstract,/e:book/e:summary,//h:diagnosis)
         

There may be alternative, overlapping atomic units.

Dehyphenation and decompounding produce alternative word sequences that overlap with one another. Character or word N-grams can be viewed as defining different sequences of atomic units.

Similarly, milestone markup in XML can be interpreted as defining atomic markup units ("demilestoning"):

<example>Here is the <start id="2"/> milestones marking <start id="1"/> 
something <end id="2"/> where there is intertwingling <end id="1"/> of 
milestones.</example>
         

Given an understanding of the milestone markup this can be indexed as if there were the sequence of words something where there is interwingling and the sequence of words milestones marking something, each within their own distinct element.

Markup formats such as LMNL are designed to represent overlapping atomic units, so that such detailed knowledge of the markup is not necessary and the document itself can define the interface to the index with no additional context:

[s}[l}He manages to keep the upper hand{l]
[l}On his own farm.{s] [s}He's boss.{s] [s}But as to hens:{l]
[l}We fence our flowers in and the hens range.{l]{s]
         

(This example is from Piez12.)

Here we have He manages to keep the upper hand On his own farm., He's boss., and But as to hens: We fence our flowers in and the hens range. each within its own s, intertwined with He manages to keep the upper hand, On his own farm. He's boss. But as to hens:, and We fence our flowers in and the hens range. each within its own l.

There may be hierarchies of atomic units.

Words consist of characters. Phrases consist of words. Other hierarchies (sentences, paragraphs, topics, sentiment regions) are possible.

Markup languages such as XML, HTML, or even JSON are intrinsically hierarchical. Elements contain other elements. Properties contain objects which contain properties.

{
  type: "GeometryCollection",
  geometries: [
    {
      type: "Point",
      coordinates: [-122.041944, 37.3175]
    },
    {
      type: "LineString",
      coordinates: [
        [-122.04199, 37.3175],[-122.019444,37.2725],[-122.0375,37.371111]
      ]
    }
  ]
}
         

The set of available terms affects the recall and precision of queries.

Each new kind of term enables the inverted index to directly resolve certain kinds of queries. This in turn enhances precision for that kind of query where the alternative is to return a poor "best effort" based on the terms that are available. Terms that define equivalence classes over other terms enhance recall where the alternative is to return the matches for a less expansive term.

Even without fuzzy matching, relevance is in the eye of the beholder. Scoring algorithms attempt to capture intuitions about what makes a matching document "better". Adding recall-enhancing functions that create larger equivalence classes tends to undermine precision. However, an effective scoring algorithm can ameliorate that tradeoff: if the irrelevant results end up at the bottom of the scoring ordering, they don't matter for many practical applications.

TF-IDF regimes can be applied to markup terms just as well as non-markup terms, although in truth for pure-markup matching, relevance scoring feels a little odd. Is a document that contains ten title elements within section elements really a better match for a search for section//title than one that has only one? Perhaps. On the other hand, the relative rarity of a particular markup element (IDF) may indeed make it more interesting (relevant) for certain kinds of applications.

<doc>
  <section>
    <title>One</title>
  </section>
  <section>
    <title>Two</title>
  </section>
  <section>
    <title>Three</title>
  </section>
</doc>             
           

<doc>
  <section>
    <title>One</title>
  </section>
</doc>             
           

Certainly relevance makes sense applied to terms that combine markup with textual content: a document that has several title elements that contain the word example is surely a better match for a query of title containing example than one than has only one such title element and is also surely a better match than one that has many instances of example and many instances of title but not of example in title.

<doc>
  <section>
    <title>example one</title>
  </section>
  <section>
    <title>another example</title>
  </section>
  <section>
    <title>last example</title>
  </section>
</doc>             
           

<doc>
  <section>
    <title>only example</title>
  </section>
</doc>             
           

<doc>
  <section>
    <title>not here</title>
    example one
  </section>
  <section>
    <title>not there</title>
    another example
  </section>
  <section>
    <title>or here either</title>
    last example
  </section>
</doc>             
           

Specialized indexes store values of different types and provide mechanisms for returning posting lists satisfying type-specific constraints.

Traditional search engine fields define specific parts of documents to index separately, so that a search for a word in a particular field can be distinguished from a search for a word in the document as a whole. It is common to take the next step and index typed values in fields, including types that support more specialized search operations such as geospatial or date/time values.

Fields are really just part of a continuum to markup-based indexing. Indeed, frequently fields are defined in terms of markup: a field may defined by reference to an XML element. Field value types may be manifest in the format or defined by reference to a schema of some kind.

In the following JSON document, property names can automatically induce fields, with the duck-typing specifying the value types:

{"example": "these words", "value": 47}
         

Producing field index entries such as:

//example contains "these"
//example contains "word"(English stem)
//example contains "words"
//example="these words"
//value=47(number)
         

More advanced value extraction from markup is possible by applying external knowledge about the specific markup, just as more knowledge enables advanced linguistic analysis and indexing based on it.

For example, knowledge of the KML specification KML220 means that the point value (37.3175,-122.041944) can be extracted from the following bit of markup:

<Location xmlns="http://www.opengis.net/kml/2.2">
  <longitude>-122.041944</longitude>
  <latitude>37.3175</latitude>
  <altitude>72</altitude>
</Location> 
         

Notice that simple concatenation is not enough: we have to understand the meaning of the elements.

Given an understanding of both the KML specification and the GML specification GML321, it is possible to create a combined index containing points from either format. (A recall-enhancing move.)

Values can also be defined by the markup, rather than being simply wrapped in the markup. For example, MathML MathML30 defines empty elements that designate various mathematical operators.

<apply xmlns="http://www.w3.org/1998/Math/MathML"><sin/><ci>x</ci></apply>
         

<mrow xmlns="http://www.w3.org/1998/Math/MathML"><mi>sin</mi><mo>&#x2061;</mo><mi>x</mi></mrow>
         

Given an understanding of the MathML vocabulary, the content markup element <sin/> can be indexed identically to presentation markup <mi>sin</mi>, so that search for either matches the other.

Values may act as terms.

Typed values may support specialized query operations, even quite complex query operations such as finding all the matches containing a polygon that intersects with a query polygon. However, even relatively elaborate typed values ground out on basic term-based queries: is it a fact that this document contains this value?

Search for markup atoms and molecules may also benefit from specialized query operators. However, basic term-fact queries are the root of it all: return the documents about which this markup fact is true.

//example                1 2
//example="these words"  1 3
//value                  2 4 5
//value=47(number)       2 5        => 2 5
these                    1 3 5 7
word(English stem)       1 3 6
words                    1 3
           

The set of available terms and of values contained in specialized indexes defines the effective information content of the document.

From the point of view of a search engine relying on an inverted index, if a term isn't in the index, it is as if it doesn't appear in the document, and if a term is in the index, it is as if it were manifest in the document. It is common, for example, for indexing to skip excessively common words such as the. These are called stop words. A search for a stop word would fail, because no such entry exists: the behaviour is identical to a search for a word that never appears in a corpus. From the search engine point of view, therefore, stop words do not exist. On the other hand, suppose the word foxes never appears in the corpus, but its singular form fox does. With stemming, a search for foxes will match the documents containing fox. From the search engine point of view, therefore, all the forms of the word occur in the document.

Similarly, if a search for the MathML <sin/> element returns a document in which, in fact, it never occurs but the equivalent term <mi>sin</mi> does occur, in effect <sin/> does occur in that document. Conversely, if indexing treats XHTML <br/> elements as stop words and doesn't index them, from a search perspective it is as if they did not occur in the documents.

Term vectors may be used to classify and cluster documents.

The mathematics of term vectors applies without regard to what the terms signify. Indeed, there is a rich and extensive literature on term vectors applied to a wide variety of fields having nothing to do words at all. Classification and clustering over term vectors referencing both word terms and markup terms can discriminate based on both.

For example, SVM classification can readily discriminate the piggy documents from the market documents if there are terms in the term vector for elements.

<piggy>one little piggy went to market</piggy>

<piggy>two little piggies stayed home</piggy>

<market>one little piggy went to market</market>

<market>one little piggy went to market</market>
         

Selecting terms generated from recall-enhancing functions (that is, those that create large equivalence classes) for clustering tasks enables detection of larger classes using fewer terms, allowing for more effective operation. It can also reduce some of the noise, leading to better results. Selecting terms generated from precision-enhancing functions (that is, those that create subclasses) for clustering tasks enables the detection of more fine-grained classes than would be possible otherwise.

For example, including vocabulary mapping terms makes detection of cross-vocabulary classes easier. Including terms for parent/child relationships makes discrimination of classes for distinct usages of specific elements possible. Combining markup terms with content terms in term vectors can allow for classification and clustering tasks to be accomplished that could not be done with purely content terms or purely markup terms. How document similarity is computed depends on what kinds of terms are in the document term vectors.