Archive for the ‘Trees’ Category

Constructing a true LCSH tree of a science and engineering collection

Monday, November 19th, 2012

Constructing a true LCSH tree of a science and engineering collection by Charles-Antoine Julien, Pierre Tirilly, John E. Leide and Catherine Guastavino.

Abstract:

The Library of Congress Subject Headings (LCSH) is a subject structure used to index large library collections throughout the world. Browsing a collection through LCSH is difficult using current online tools in part because users cannot explore the structure using their existing experience navigating file hierarchies on their hard drives. This is due to inconsistencies in the LCSH structure, which does not adhere to the specific rules defining tree structures. This article proposes a method to adapt the LCSH structure to reflect a real-world collection from the domain of science and engineering. This structure is transformed into a valid tree structure using an automatic process. The analysis of the resulting LCSH tree shows a large and complex structure. The analysis of the distribution of information within the LCSH tree reveals a power law distribution where the vast majority of subjects contain few information items and a few subjects contain the vast majority of the collection.

After a detailed analysis of records from the McGill University Libraries (204,430 topical authority records) and 130,940 bibliographic records (Schulich Science and Engineering Library), the authors conclude in part:

This revealed that the structure was large, highly redundant due to multiple inheritances, very deep, and unbalanced. The complexity of the LCSH tree is a likely usability barrier for subject browsing and navigation of the information collection.

For me the most compelling part of this research was the focus on LCSH as used and not as it imagines itself. Very interesting reading. A slow walk through the bibliography will interest those researching LCSH or classification more generally.

Demonstration of the power law with the use of LCSH makes one wonder about other classification systems as used.

Posted in Cataloging, Classification, Classification Trees, Hierarchy, LCSH, Library, Trees | No Comments »

Trees – A Primer

Monday, September 17th, 2012

Trees – A Primer by Jeremy Kun.

From the post:

This post comes in preparation for a post on decision trees (a specific type of tree used for classification in machine learning). While most mathematicians and programmers are familiar with trees, we have yet to discuss them on this blog. For completeness, we’ll give a brief overview of the terminology and constructions associated with trees, and describe a few common algorithms on trees. We will assume the reader has read our first primer on graph theory, which is a light assumption. Furthermore, we will use the terms node and vertex interchangeably, as mathematicians use the latter and computer scientists the former.

A nice introduction/refresher on tree data structures.

Posted in Programming, Trees | No Comments »

Parsing the Newick format in C using flex and bison

Friday, July 13th, 2012

Parsing the Newick format in C using flex and bison by Pierre Lindenbaum.

From the post:

The following post is my answer for this question on biostar “Newick 2 Json converter“.

The Newick tree format is a simple format used to write out trees (using parentheses and commas) in a text file .

The original question asked for a parser based on perl but here, I’ve implemented a C parser using flex/bison.

If that doesn’t grab your interest, consider the following from the Wikipedia article cited by Pierre on the Newick tree format:

In mathematics, Newick tree format (or Newick notation or New Hampshire tree format) is a way of representing graph-theoretical trees with edge lengths using parentheses and commas. It was adopted by James Archie, William H. E. Day, Joseph Felsenstein, Wayne Maddison, Christopher Meacham, F. James Rohlf, and David Swofford, at two meetings in 1986, the second of which was at Newick’s restaurant in Dover, New Hampshire, US. The adopted format is a generalization of the format developed by Meacham in 1984 for the first tree-drawing programs in Felsenstein’s PHYLIP package.[1]

Of interest both for conversion but also for the representation of graph-theoretical trees. About the same time as GML and other efforts on trees.

In case you are in Dover, Newick’s survives to this day. I don’t know if they are aware of the reason for their fame but you could mention it.

Posted in Bioinformatics, Graphs, Trees | No Comments »

Extracting Conflict-free Information from Multi-labeled Trees

Friday, June 1st, 2012

Extracting Conflict-free Information from Multi-labeled Trees by Akshay Deepak, David Fernández-Baca, and Michelle M. McMahon.

Abstract:

A multi-labeled tree, or MUL-tree, is a phylogenetic tree where two or more leaves share a label, e.g., a species name. A MUL-tree can imply multiple conflicting phylogenetic relationships for the same set of taxa, but can also contain conflict-free information that is of interest and yet is not obvious. We define the information content of a MUL-tree T as the set of all conflict-free quartet topologies implied by T, and define the maximal reduced form of T as the smallest tree that can be obtained from T by pruning leaves and contracting edges while retaining the same information content. We show that any two MUL-trees with the same information content exhibit the same reduced form. This introduces an equivalence relation in MUL-trees with potential applications to comparing MUL-trees. We present an efficient algorithm to reduce a MUL-tree to its maximally reduced form and evaluate its performance on empirical datasets in terms of both quality of the reduced tree and the degree of data reduction achieved.

You may not agree with:

That is, for every MUL-tree $T$ there exists a singly-labeled tree that displays all the conflict-free quartets of $T$ — and possibly some other quartets as well. Motivated by this, we only view conflict-free quartet topologies as informative, and define the information content of a MUL-tree as the set of all conflict-free quartet topologies it implies.

Preferring to view conflicts as information content (I would) but each to his own.

I suspect “multi-labeled” trees are more common than one might expect.

Other examples?

Posted in Trees | No Comments »

Trees in the Database: Advanced Data Structures

Monday, March 5th, 2012

Trees in the Database: Advanced Data Structures

Lorenzo Alberton writes:

Despite the NoSQL movement trying to flag traditional databases as a dying breed, the RDBMS keeps evolving and adding new powerful weapons to its arsenal. In this talk we’ll explore Common Table Expressions (SQL-99) and how SQL handles recursion, breaking the bi-dimensional barriers and paving the way to more complex data structures like trees and graphs, and how we can replicate features from social networks and recommendation systems. We’ll also have a look at window functions (SQL:2003) and the advanced reporting features they make finally possible. The first part of this talk will cover several different techniques to model a tree data structure into a relational database: parent-child (adjacency list) model, materialized path, nested sets, nested intervals, hybrid models, Common Table Expressions. Then we’ll move one step forward and see how we can model a more complex data structure, i.e. a graph, with concrete examples from today’s websites. Starting from real-world examples of social networks’ and recommendation systems’ features, and with the help of some graph theory, this talk will explain how to represent and traverse a graph in the database. Finally, we will take a look at Window Functions and how they can be useful for data analytics and simple inline aggregations, among other things. All the examples have been tested on PostgreSQL >= 8.4.

Very impressive presentation!

Definitely makes me want to dust off my SQL installations and manuals for a closer look!

Posted in Data Structures, Database, PostgreSQL, RDBMS, SQL, Trees | No Comments »

Compact Binary Relation Representations with Rich Functionality

Wednesday, January 18th, 2012

Compact Binary Relation Representations with Rich Functionality by Jérémy Barbay, Francisco Claude, Gonzalo Navarro.

Abstract:

Binary relations are an important abstraction arising in many data representation problems. The data structures proposed so far to represent them support just a few basic operations required to fit one particular application. We identify many of those operations arising in applications and generalize them into a wide set of desirable queries for a binary relation representation. We also identify reductions among those operations. We then introduce several novel binary relation representations, some simple and some quite sophisticated, that not only are space-efficient but also efficiently support a large subset of the desired queries.

Read the introduction (runs about two of the thirty-two pages) and tell me you aren’t interested. Go ahead.

Just the start of what looks like a very interesting line of research.

Posted in Algorithms, Binary Relations, Graphs, Trees, Wavelet Trees | No Comments »

Tree Traversal in O(1) Space

Saturday, October 8th, 2011

Tree Traversal in O(1) Space by Sanjoy.

From the post:

I’ve been reading some texts recently, and came across a very interesting way to traverse a graph, called pointer reversal. The idea is this — instead of maintaining an explicit stack (of the places you’ve visited), you try to store the relevant information in the nodes themselves. One approach that works on directed graphs with two (outgoing) arcs per node is called the Deutsch-Schorr-Waite algorithm. This was later extended by Thorelli to work for directed graphs with an unknown number of (outgoing) arcs per node.

Implemented here for a tree, care to go for a more general graph?

Posted in Algorithms, Graphs, Software, Trees | No Comments »

Working with Trees in the Phyloinformatic Age

Monday, February 28th, 2011

Working with Trees in the Phyloinformatic Age by William H. Piel discusses the processing and display of phylogenetic trees.

The PhyloWidget that is mentioned in the slides can be found at: Phylowidget

If you are working on topic maps in bioinformatics, this should be on your list of works to review.

I was particularly amused by the advice given at the Phylowidget site in its step-by-step instructions:

* If you are a biologist: we recommend starting with the First Step and moving forwards.
* If you are a developer: we recommend starting with the Last Step and moving backwards.

Posted in Bioinformatics, Phylogenetic Trees, Trees | No Comments »