Balisage Paper: Exploring the Unknown

More data than you know what to do with

It’s increasingly common for information workers to come in contact with unfamiliar datasets. Governments around the world are releasing more and bigger datasets. Corporations are collecting and releasing more data than ever, often in XML or another format easily convertible to XML. This trend, while welcomed by many, poses questions about how to come to understand large XML datasets.

In general, bulk analysis of large datasets gets done through an ad-hoc assortment of machine learning techniques. Few of these, however, are specifically targeted at the unique aspects of the XML data model, as examined in this paper.

One tool in particular that has come into widespread use for analyzing datasets is R, which has available a set of XML libraries R Language; Package 'XML'. However, while R is often useful for initial exploration, it lacks an upgrade path into an operational data store such as an XML database, and the XML capabilities provided are DOM and XPath-centric, which are less suited to bulk analysis.

The most common approach used by databases to deal with searching and navigating through large datasets is an index, trading space for time. Once an index is set up and occupying additional disk and/or memory space, certain kinds of queries run significantly faster.

With an unknown dataset, though, this presents a chicken-and-egg problem. Many database systems assume the availability of indexes to perform navigational functions such as faceted search. Without such features, it’s more difficult to get to know the data. And if the structure of the data is unknown, how can one create the necessary indexes in the first place?

One answer is that indexes should be arranged based on queries rather than data. This is a valid approach, although not of much help in the case of bootstrapping a truly unknown dataset.

Another approach, one explored in the remainder of this paper, is to rely on statistical sampling approaches rather than indexes. This presents tradeoffs in terms of size, speed, and accuracy. At the same time, it offers benefits:

Though the techniques shown here are universally applicable, for convenience, code samples in this paper are based on an early access release of MarkLogic 6 MarkLogic docs.

Random Sampling

A common approach to characterizing a large population involves taking a random sample. A simple XQuery expression

fn:collection()[1]

For larger samples, greater automation is needed for the analysis. We can define a process producing a sample of size N to be considered random if any particular collection of documents is equally likely to turn up as any other same-sized collection of documents. Randomness of a sample is important, because a non-random sample will lead to systematic errors not accounted for in statistical measures of probability.

Within a random sample it is possible to examine characteristics of the sample and make statistical inferences about the overall population. The more documents in the sample, the better the approximation. When the overall population is small, it is possible to sample most or even all of the documents. But with large collections of documents, the proportion of documents contained in a reasonably-sized sample will be very small. When dealing with a dataset of this size, certain simplifying assumptions become possible, as outlined in later sections of this paper.

Users of search interfaces have become accustomed to approximations, for example, a web search engine may report something like “Page 2 of about 415,000,000 results”, but as users go deeper into the result set, the estimated number tends to converge on some actual value. Users have accepted this behavior, though it is less commonly used in finer-grained navigational situations. For example, if a sidebar on a retail site says, “New in last 90 days (328)”, quite often one will find that exactly 328 items will be available by clicking through all the pages of results.

This difference in user expectations can be exploited. In particular, in the case of first contact with a new XML dataset, exact results are far less important than overall trends and correlations, which makes a sampling approach ideal.

1 div math:sqrt($sample-size)
        

Dipping a toe into the database

Getting familiar with an XML dataset requires a combination of automated and hands-on approaches. While writing this paper, I had on hand a dataset of over 5 million documents, crawled from an assortment of public social media sources, of which I knew very little in advance.

The first-document-in-the-collection approach mentioned above yields this ^[2]:

<sl:streamlet
xmlns:sl="http://example.com/ns/social-media/streamlet">
  <sl:vid>13067505336836346999</sl:vid>
  <sl:tweet>#Jerusalem #News 'Iran cuts funding for
  Hamas due to Syria unrest'
  http://t.co/ARRqabU</sl:tweet>
</sl:streamlet>
        

The choice of the "first" document, is, of course, completely arbitrary. The second document has something completely different:

<person:person
xmlns:person="http://example.com/ns/social-media/person">  
  <person:id>8999631448253261463</person:id>
  <person:follower-count>0</person:follower-count>
  <person:influence>0</person:influence>
  <person:name>Borana Mukesh</person:name>
  ...
</person:person>
        

There's only so much one can learn from picking through individual documents.

The following XQuery 3.0 XQuery 3.0 code demonstrates this approach by examining a sample of documents in order to extract potentially interesting features, which a human operator can use to make decisions about where to dive deeper. The code assembles the following:

  let $dv := distinct-values#1
  let $n := ($sample-size, 1000)[1]
  let $xml-docs := spx:est-docs()
  let $text-docs := spx:est-text-docs()

  let $samp := spx:random-sample($n)
  let $cnames := $dv($samp/*/spx:name(.))
  let $all-ns := $dv($samp//namespace::*)
  let $leafe := $samp//*[empty(*)]
  let $leafetxt := $leafe[text()]
  let $leafe-long := $leafetxt
    [string-length(.) ge 10]
  let $leafe-short := $leafetxt
    [string-length(.) le 4]
  let $dates := $dv($leafe-long
    [. castable as xs:dateTime]/spx:name(.))
  let $near-dates := $dv($leafe-long
    [matches(local-name(.), '[Dd]ate')]
    [not(. castable as xs:dateTime)]/spx:name(.))
  let $all-years := $dv($leafe-short
    [matches(., "^(19|20)\d\d$")]/spx:name(.))
  let $all-smallnum := $dv($leafe-short
    [. castable as xs:double]/spx:name(.))
  let $epd := count($samp//*) div count($samp/*)
  return
    <spx:data-sketch
      xml-doc-count="{$xml-docs}"
      text-doc-count="{$text-docs}"
      binary-doc-count="{$binary-docs}"
      elements-per-doc="{$epd}">
      {$cnames!<spx:root-elem
        name="{.}"
        count="{spx:est-by-QName(spx:QName(.))}"/>
      }
      {$all-ns!<spx:ns-seen>{.}</spx:ns-seen>}
      {$dates!<spx:date>{.}</spx:date>}
      {$near-dates!<spx:almost-date>{.}</spx:almost-date>}
      {$all-years!<spx:year>{.}</spx:year>}
      {$all-smallnum!<spx:small-num>{.}</spx:small-num>}
    </spx:data-sketch>
    

This code and the following listings make use of the following helper functions which contain vendor-specific implementations, which are not important here (see the Code section later for details):

This code produced the following (with adjustments for line length):

<spx:data-sketch
xmlns:spx="http://dubinko.info/spelunx"
  xml-doc-count="5789128"
  text-doc-count="0"
  binary-doc-count="0"
  elements-per-doc="12.88" >
  <spx:root-elem name="{...}person" count="1248848"/>
  <spx:root-elem name="{...}media" count="2117625"/>
  <spx:root-elem name="{...}streamlet" count="1173545"/>
  <spx:root-elem name="{...}author" count="1248815"/>
  <spx:ns-seen>
    http://example.com/ns/social-media/person
  </spx:ns-seen>
  <spx:ns-seen>
    http://example.com/ns/social-media/media
  </spx:ns-seen>
  <spx:ns-seen>
    http://example.com/ns/social-media/streamlet
  </spx:ns-seen>
  <spx:ns-seen>
    http://example.com/ns/social-media/author
  </spx:ns-seen>
  <spx:ns-seen>
    http://www.w3.org/XML/1998/namespace
  </spx:ns-seen>
  <spx:date>{...}ingested</spx:date>
  <spx:date>{...}published</spx:date>
  <spx:date>{...}canonical</spx:date>
  <spx:date>{...}inserted</spx:date>
  <spx:small-num>{...}follower-count</spx:small-num>
  <spx:small-num>{...}influence</spx:small-num>
  <spx:small-num>{...}follower-count</spx:small-num>
</spx:data-sketch>
    

This dataset appears fairly homogeneous: only four different root element QNames, were observed over 1,000 samples. Additionally, these documents contain a number of elements that seem date-like, but would require some cleanup in order to be represented in as the Schema datatype xs:dateTime. For purposes of this paper, one particular element, influence, as seen earlier, seems particularly interesting. Is there a way to learn more about it?

Digging Deeper

It’s possible to perform similar kinds of analysis on specific nodes in the database. Given a starting node, the system of XPath axes provides a number of different ways in which to characterize that element’s use in a larger dataset. Some care must be taken to handle edge cases, assuming nothing in an unknown environment. The following code listing characterizes a given element node (named with a QName) along several important axes:

  let $dv := distinct-values#1
  let $n := ($sample-size, 1000)[1]
  let $samp := spx:random-sample($n)

  let $ocrs := $samp//*[node-name(.) eq $e]
  let $vals := data($ocrs)
  let $number-vals := $vals
    [. castable as xs:double]
  let $nv := $number-vals
  let $date-values := $vals
    [. castable as xs:dateTime]
  let $blank-vals := $vals[matches(., "^\s*$")]
  let $parents := $dv(
    $ocrs/node-name(..)!spx:formatq(.))
  let $children := $dv($ocrs/*!spx:name(.))
  let $attrs := $dv($ocrs/@*!spx:name(.))
  let $roots := $dv($ocrs/root()/*!spx:name(.))
  let $paths := $dv($ocrs/spx:node-path(.))
  return
    <spx:node-report
      estimate-count="{spx:est-by-QName($e)}"
      sample-count="{count($ocrs)}"
      number-count="{count($number-vals)}"
      date-count="{count($date-values)}"
      blank-count="{count($blank-vals)}">
      {$parents!<spx:parent>{.}</spx:parent>}
      {$roots!<spx:root>{.}</spx:root>}
      {$paths!<spx:path>{.}</spx:path>}
      <spx:min>{min($number-vals)}</spx:min>
      <spx:max>{max($number-vals)}</spx:max>
      {if (exists($vals)) then
      <spx:mean>
        {sum($nv) div count($nv)}
      </spx:mean>
      else ()
      }
    </spx:node-report>
    

These two techniques combine to provide a powerful tool for picking through an unknown dataset. First identify ‘interesting’ element nodes, then dig into each one to see how it is used in the data. While the sample documents are in memory, it is possible to infer datatype information, and for values that look numeric, to calculate the sample min, max, mean, median, standard deviation, and other useful statistics.

These techniques can be readily expanded to include statistics for other node types, notably attribute and processing-instruction nodes.

Free-form faceting

Index-backed approaches make it possible to produce a histogram of values, often called "facets", for example all the prices in a product database, arranged into buckets of values like 'less than $10' or '$10 to $50' and so on.

It’s possible to combine the concepts introduced thus far by breaking down a random sample into faceted data. With no advance knowledge of the range of values, it’s difficult to arrange values into reasonable buckets, but with some spelunking, as in the preceding section, it’s possible to construct reasonable bucketing. Based on the exploration from the preceding sections, the influence element looks worth further investigation.

The following XQuery function plots out the values of a given element as xs:double values in specified ranges.

declare function spx:histogram(
  $e as xs:QName,
  $sample-size as  xs:unsignedInt?,
  $bounds as xs:double+
) {
  let $n := ($sample-size, 1000)[1]
  let $samp := spx:random-sample($n)
  let $full-population := spx:est-docs()
  let $multiplier := ($full-population div $n)
  let $ocrs := $samp//*[node-name(.) eq $e]
  let $vals := data($ocrs)
  let $number-vals := $vals
    [. castable as xs:double]!xs:double(.)
  let $bucket-tops := ($bounds, xs:float("INF"))
  for $bucket-top at $idx in $bucket-tops
  let $bucket-bottom :=
    if ($idx eq 1)
    then xs:float("-INF")
    else $bucket-tops[position() eq $idx - 1]
  let $samp-count := count($number-vals
    [. lt $bucket-top][. ge $bucket-bottom])
  let $p := $samp-count div $n
  let $moe := 1 div math:sqrt($sample-size)
  let $SE := math:sqrt(($p * (1 - $p)) div $n)
  let $est-count := $samp-count * $multiplier
  let $error := $SE * $full-population
  let $est-top := $est-count + $error
  let $est-bot := $est-count - $error
  return
    <histogram-value
      ge="{$bucket-bottom}"
      lt="{$bucket-top}"
      sample-count="{$samp-count}"
      est-count="{$est-count}"
      est-range="{$est-bot} to {$est-top}"
      error="{$error}"/>
};
    

This code accepts a particular QName referring to an element, a sample size, and an ordered set of numeric bounds, and returns the approximate count of values that occur in between each boundary. The first bucket includes values down to -INF, and the last bucket includes all values up to INF. Selecting values to partition the values into order-of-magnitude buckets will give a broad first approximation of the distribution.

For comparison, the following vendor-specific code, which requires a pre-existing in-memory index, resolves the exact counts of different values occurring in the database.

for $bucket in cts:element-value-ranges(
  QName("http://example.com/ns/social-media/person", "influence"),
  (1,10,100,1000), "empties")
return
    <histogram-value
        ge="{($bucket/cts:lower-bound, '-INF')[1]}"
        lt="{($bucket/cts:upper-bound, 'INF')[1]}"
        count="{cts:frequency($bucket)}"/>
    

The results of calling these function on the test database are given below in table format.

How wrong can you get?

As the book Statistics Hacks Statistics Hacks states, Anytime you have used statistics to summarize observations, you’ve probably been wrong. This technique is no exception.

As mentioned earlier, if we assume that the sample is of a small proportion of the overall population and is randomly selected, the maximum margin of error is a simple function of sample size. However, against particular values we can usually find a more accurate estimate.

To estimate the overall proportion, the standard error of the proportion must be computed, using the following formula.

math:sqrt(($p - $p * $p) div $sample-size )

The following table illustrates the tradeoffs in accuracy, run-time, and necessity of a preconfigured index. The columns on the left represent histogram buckets of values of various ranges, while the rows across the top represent different sample sizes, or in the case of the final column, exact index resolution. The hardware under test consisted of a 2.4Ghz Dual-core 64-bit Intel machine with two 15k rpm disks in a RAID O configuration.

Unsurprisingly, at smaller sample sizes, it is probable that infequently-occurring data will be completely excluded from the random sample. Even the most frequently-occurring values, in this case the bucket of values less than one, occurs in less than 14% of the 5.7M documents. Given this, the accuracy of the random sampling technique, even at the lower sample counts, is more than enough to give a general impression of the distribution of the data values.

To visulaize this, it is possible to export these values into a desktop spreadsheet program and produce a graph, including error bars, as shown in the following figure.

Figure 1: Graphical representation of data distribution (by percentage)

Conclusion

The techniques shown in the paper offer a useful framework within which to make the initial foray into an unknown XML dataset. Starting with an automated run-down of high-level features in the dataset, particular QNames chosen by the user can be drilled down into deeper analysis. The dataset can even be summarized through histogram facets, much like those available to significantly more resource-intensive indexed databases.

The techniques shown here do not rely on proprietary features and are applicable to a wide range of available XQuery processors.

The book How to Lie with Statistics How to Lie with Statistics concludes with advice on how to be properly skeptical of statistics, and the guidelines apply to the techniques in this paper as much as in any other area.

With those caveats, the techniques in this paper can provide a useful lever by which to pry open a large, unkonwn XML data set.

Code availability

The code samples mentioned in this paper are in available in a project named Spelunx available at GitHub Spelunx.

Further topics to explore