Metadata++: A Scalable Hierarchical Framework for Digital Libraries1*

Mathew Weaver, *Lois Delcambre, **Timothy Tolle***

Computer Science & Engineering
OGI School of Science & Engineering
Oregon Health & Science University{mweaver, lmd}@cse.ogi.edu

Abstract:

Metadata++ is a digital library systemthat we are developing to serve the needsof the United States Department ofAgriculture Forest Service, the UnitedStates Department of the Interior Bureauof Land Management, and the UnitedStates Department of the Interior Fish andWildlife Service to support natural
resource managers, scientists and publics
as they analyze issues and makedecisions. The system provides access toinstitutional knowledge consisting offormal and informal agency reports anddocuments – including Environmental
Assessments, Decision Notices, Appeal
Decisions, specialist reports, and so forth.
Metadata++ uses a set of hierarchicallystructured controlled vocabularies – withsynonyms and associations – as theprimary organizational framework. Users
browse the hierarchy to select searchterms and see the search results directly inthe context of the hierarchy. In order tobe useful as a digital library
infrastructure, this hierarchy must be
implemented in an efficient and scalable
manner. This paper introduces theMetadata++ system and evaluates theperformance of four different approaches
to managing the hierarchy. We present a
novel approach that uses a common filesystem with an associated indexing
engine to store terms as directories (withnarrower terms as subdirectories) andshow how we achieve both scalability andefficiency.

Keywords:

Information technologies for digital
libraries; Development of digital libraries

1

Resource Planning and Monitoring
Pacific Northwest Region
USDA Forest Service
ttolle@fs.fed.us

Introduction

Resources in a digital library are typicallydescribed by metadata, including an indication of thesubject(s) or topic(s) (also called keywords or terms)of the resource. In this work, we are particularlyinterested in keywords that have been predefined ina controlled vocabulary with a hierarchical structure
relating broader/narrower terms. Using a controlled
vocabulary produces more meaningful and useful
metadata. In addition to providing a finite set of
keywords, a controlled vocabulary often includes a
structured organization of the keywords – as in a
traditional thesaurus [1] and Dewey Decimal [5].
Most common metadata standards – such as Dublin
Core [6] and FGDC [7] – require or permit the useof one or more controlled vocabularies.
Controlled
vocabularies
areanessential tool within
naturalresource
management. Scientists,
governing agencies, andnaturalresource
managers use specificvocabularies to describe
their
work.
Our
environmental research
partners[3]
have
identified approximately
twenty-eight domains ofinterest, such as location,hydrology, climatology,
forestry, and planning, as
central to the organization of documents and haveidentified, evaluated, and selected one or more
controlled vocabularies for each domain. Figure 1
shows excerpts of controlled vocabularies from threedomains. Each controlled vocabulary organizes
terms according to the way that specialists in a given
domain view the concepts.
For a forester,“Forestry” is a primary topic, with “Agriculture” and“Botany” as sub-topics. The climatologist, on the

1 This work is supported in part by the National Science Foundation, grant number EIA 9983518.

Any opinions, findings,
conclusions, or recommendations expressed here are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation.

++

!
#
$%

$
'
(

&
'
! (
) ! $% *
'
!

*

!

"

!

(,,
!
*
)
!

other hand, considers “Air” as a primary topic, with“Air quality” and “Weather” as sub-topics.
The hierarchical relationship among terms
represents various relationships including spatial
containment (e.g., watersheds), administrative
jurisdiction (e.g., national forests and ranger
districts), classification of the plant and animal
kingdom (e.g., taxonomic description of species), or
simple broader/narrower term (e.g., air vs. air
quality) as shown in Figure 1. In our model, we use
one hierarchical relationship as an abstraction ofthese – called broader/narrower term. Like astandard thesaurus [1], Metadata++ includes
synonym and association relationships among terms,
as well.
As shown in Figure 2, domain specialists select!"#appropriate controlled vocabularies for Metadata++(upper right portion of the figure) and authors or
local librarians supply metadata and select terms
from the controlled vocabularies to describe
documents within Metadata++ (left portion of the
figure). Users are then able to easily browse thecontrolled vocabularies and search for documents(shown on the lower right of the figure). This paper
explains how Metadata++ uses controlled
vocabularies and evaluates four alternative
approaches to implementing a large-scale, dynamichierarchy.

2"$

Using Controlled Vocabularies in
Metadata++

Controlled vocabularies provide an intuitive
framework for cataloging and retrieving natural
resource information. Users may explore thehierarchy of controlled vocabularies and see
documents related to the terms of interest. Figure 3
shows a portion of a screen shot of the Metadata++
application while browsing the hierarchy. Explicit
documents are documents that an author or librarian
explicitly attached to the relevant term (by selecting
the term as a keyword for the document). For
example, the author of the document titled “Air
Quality Analysis and Assessment” selected the term
“Air quality” as a keyword for that document.
Implicit documents, on the other hand, contain one
or more occurrences of the term, but have not been
explicitly attached. For example, the document“Monitoring for ozone injury in West Coast”
actually contains the term “Air quality” – but theterm was not selected as an explicit keyword. As thelibrary grows, librarians may modify the hierarchy
by adding new vocabularies or changing existing
vocabularies. The concept of explicit documents

and implicit documents allows authors, librarians,
and users to immediately benefit from new
vocabularies – without having to rebuild metadata
for existing documents.
In addition to exploring the hierarchy, the user
may issue a search for a specific term. The results ofthe search include documents related directly to thesearch term as well as documents related todescendant terms. For example, a search for “Air”
would include the document “Air Quality Analysis
and Assessment,” because the term “Air quality” is a
descendant of the term “Air”. Instead of returning aranked list of documents, Metadata++ returns
structured search results – so the user can view the
documents in context of the hierarchy. Metadata++
uses the SUBTREE function to compute alldescendants of a given term.
In addition to finding descendant terms, the user
must also be able to find one or more terms given a
specified string value. For example, a novice user
may be unfamiliar with the hierarchy and havedifficulty finding a term of interest. Instead ofmanually browsing the entire hierarchy to find thedesired term, the user may type in a string – such as“evaporation”. A function called FIND returns all
terms that contain the specified string. The FIND
function supports two modes – exact match (which
returns only terms that exactly match the string) andwildcard (which returns all terms that contain thestring).

() *+

,

#%
&'

!- "

3

Implementing
HierarchicalControlled Vocabularies

Metadata++ uses a hierarchy of controlled
vocabularies to provide an intuitive framework forbuilding a digital library, as described above. In
order to be useful as a digital library framework, thishierarchy must be implemented in an efficient andscalable manner. Specifically, the SUBTREE and
FIND functions must be performed in real-time. We
must also accommodate concurrent additions andmodifications to the controlled vocabularies. Thissection describes four different approaches toimplementing the hierarchy for Metadata++ using
various combinations of database, XML, and filesystem technology. We implemented and evaluatedthe advantages and disadvantages of each approach.
3.1 Parent-Child Binary Relation
The simplest approach uses a relational databasetable that represents a binary relationship between
terms – one row in the table for each parent-childrelationship. This approach (illustrated in Figure 4)
is similar to the edge relation described in [4, 8]. It
is important to note that this approach (as well as thenext two approaches) actually uses term identifiers
that act as foreign keys to a separate table of terms.
The figure shows the actual text of the term (insteadof the term identifier) to improve readability.
This approach is functional, but fails in terms ofscalability and performance. Because each parentchild relationship is a separate row in the table,
executing the SUBTREE function (i.e. to do a searchor display the hierarchy to the user) requires anadditional query for each term. Even with relatively
few terms (i.e. 102 terms), the performance of the
SUBTREE function is noticeably slow. The FIND
function also performs slowly. It does not take longto find the matching terms (exact match or wildcard)– the majority of the time is spent finding theancestors in order to return the precise location in
the hierarchy. Despite poor query performance,
adding or deleting leaf nodes is very efficient –simply add rows or delete rows from the relation.
Modifying internal (non-leaf) nodes requires moretime to correctly process the affected sub-trees. The
underlying database management system supports
concurrent updates to the hierarchy.
3.2 Breadth-first PathOur second implementation also uses a relational
database, but includes a more novel approach forstoring the hierarchy (similar to Dietz’s numbering
scheme as described in [11]). Instead of storing the

%
'

(+#

/
2
1
0

.

8

.

7

.

6

.

5

.

4

.

/3

.

//

.

.

/2

.

.

/1

.

.

/0

.

.
.

"

hierarchy as a set of parent-child relationships, astructure is used based on the breadth-first orderingof the tree. Each node of the tree is stored – inbreadth-first order – with its full path in thehierarchy (as illustrated in Figure 5). (As noted
previously, the path is actually stored using term
identifiers, but the figure shows the term text for
improved readability).
The hierarchy can beconstructed using a single SQL query.
Thisapproach offers a great improvement over theprevious approach when executing the SUBTREE
function. The nodes in the SUBTREE can be
determined by matching the prefix of each path –and the structure of the SUBTREE can be created byre-building the tree in breadth-first order. This
implementation requires only a single SQL query –instead of several SQL queries or expensive joins.
The FIND function is also efficient – doing a string
comparison on the path. Because the relation storesthe full path, the FIND function does not need toissue additional queries to determine the path (aswith the Parent-Child approach).
As the number of terms increases (i.e., 103 terms),
modifications to the hierarchy take unreasonableamounts of time.
Whenever a new term or
vocabulary is added to the hierarchy – or an existingterm is moved to a new location – the entire
hierarchy must be saved. This process requires
computing the breadth-first index and full path foreach node – and saving the complete hierarchy to the

database. With a large number of terms, this process
takes several minutes to complete – an obvious
failure in performance. Because the hierarchy mustbe saved in its entirety (after computing the breadthfirst index), this solution does not easily support
concurrent modifications. Deleting existing terms issignificantly faster – because it does not requirerebuilding the index. When a node is deleted fromthe hierarchy – it simply requires deleting theappropriate row(s) from the table.
3.3 XML BLOB
The flexible structure of XML provides an ideal
representation for the hierarchy of terms. Our third
approach for managing the hierarchy in Metadata++
uses a single XML document to represent thehierarchy, stored as text in a relational database(using a BLOB field). This approach is illustrated in
Figure 6. (As with the previous approaches, theXML in the figure shows the text of the terms, but
the actual implementation uses term identifiers).
Other data (synonyms, associations, document
metadata) are also stored in relational tables.
Metadata++ uses the XML to build (and save) the
hierarchy and uses the relational tables (i.e. SQL) toquery the related information.
Because the hierarchy is in XML, it is easy (using
XPath) to execute both the SUBTREE and FIND
functions. One drawback of this approach is that theentire XML document must be retrieved from thedatabase and parsed into main memory. This
process adds significant initial processing overhead.
Additionally, this solution does not support
modifications from concurrent users. Suppose oneuser is adding terms to one portion of the hierarchy,
while a second user is adding terms to a different
portion of the hierarchy. Because the entire XML
string is treated as a single value – and the updates tothat string are serialized by the relational databasesystem – only the latest modifications are retained in
%
'
/

/ &

9:;< <$:=>
9? @ A < BCC>
9? @ A < BCC&>
9? @ A < BC C&
>
9&
?@ >
9? @ A < BCC>
9? @ A < BCC&>
9? @ A < BCC&>
9? @ A < BC
C&
>
9&
?@ >
9? @ A < BC C>
9? @ A < BCC>
9? @ A < BCC&>
9? @ A < BC
C&
>
9&
?@ >
9? @ A < BCC>
9? @ A < BCC&>
9? @ A < BC
C&
>
9&
?@ >
9&
?@ >
9&
:;< <$:=>

0 / &1& 1

3 *+ 4%the database.
3.4 NTFS and Microsoft Index Server
Allowing concurrent access to native XML would
be a suitable solution. This would provide efficient
execution of all of the necessary functions andsupport modifications from multiple users.
Although some native XML databases do exist [10,15], few are actually available for use. We foundnone that include all of the important features foundin mature relational databases (such as concurrency).
In order to achieve the concurrency needed tosupport multiple users and obtain the necessary
performance requirements, we implemented a simple
solution based on the file system (Microsoft© NTFS)
and Microsoft Index Server© [12].
The hierarchy is stored and modified as folders in
the file system as illustrated in Figure 7. It should
be noted that there is no concept of term identifier inthis implementation – the folder names are the actual
terms. The file system is naturally hierarchical –and already has familiar tools for creating, editing,and deleting folders. The file system also provides
the concurrency necessary to allow multiple users tomodify the hierarchy simultaneously. Different
users can work in different parts of the hierarchy andall of the changes will persist. The SUBTREE
function looks at the directory structure to find alldescendant terms.
(It should be noted thatscalability limitations with user interface tools –such as Windows Explorer© – are not necessarily
limitations of the file system itself).
We configured Microsoft Index Server – a fulltext indexing and search service – to catalog all of
the file system folders defined in the hierarchy. The
index is searchable by folder name – providing
support for the FIND function (both exact match andwildcard). Microsoft Index Server provides anefficient query interface for finding folders within
the hierarchy. Microsoft Index Server also provides
full-text indexing of all documents in Metadata++,thus enabling the identification of implicit
documents, as described above.

4

Performance Results

We implemented each approach described in theprevious section on an IBM© xSeries 220 eServer
containing a single Intel© Pentium III (1.0 GHz)
processor, 896 MB of RAM, and IBM ServeRAID
storage. The server is running Microsoft Windows©
Server 2003 Standard Edition and Microsoft SQL
The fourthServer© 2000 Enterprise Edition.
solution uses Microsoft Index Server© (included in
the Windows Server 2003 operating system). We
conducted the experiments using code written andcompiled with the Microsoft .NET Framework. The
hierarchy consisted of numerous controlled
vocabularies provided by various application domain
experts – with a combined total of more than 70,000
terms. Figure 8 summarizes the depth (number oflevels) and width (number of children per node) of
the hierarchy.

E
@

/0

7,
0

4547

D/4,
8

D

)
2#

"$

$

$

@

2,
1406

2,
0284

3,
1887

3,
3303

3,
27/5

/,
//31

3,
7036

3,
4167

3,
0041

3,
2/83

3,
2786

3,
8334

'

3,
0223

3,
7731

3,
683/

3,
3303

3,
3063

3,
0230

?A &
;

3,
16/2

3,
7702

3,
1761

3,
333/

3,
3//5

3,
/516

!+

.7

F!

5(

61+)

entire hierarchy. The XML is easily modifiablewhile in-memory, but does not support concurrent
updates (and requires serialization with each
modification). The NTFS/IS approach has theoverall best performance. The file system natively
supports concurrent updates to different parts of thedirectory structure, and Index Server watched forchanges in the hierarchy and efficiently updated its
index for each modification.

For each approach, we implemented andevaluated both the SUBTREE and FIND functions.
We executed each function multiple times (withinputs and outputs varying in size and complexity)
and averaged the execution times. Figure 9 shows
the results of the SUBTREE function for fivedifferent queries.
Figure 10 compares the
maximum, minimum, and average SUBTREE
execution times for each approach.
Figure 11 shows the results of the FIND function
for four different queries. We executed each queryin both modes (exact match and wildcard) andaveraged the results. Figure 12 compares the5

Related WorkThe natural choice for representing a hierarchy isXML. Recent languages such as XQuery and XPath

A! (*

61+)
1,
8
1
2,
8
2
/,
8
/
3,
8
3
$

F!

8 61+)-( -maximum, minimum, and average execution times
for each approach. The NTFS/IS approach is anorder of magnitude faster (both maximum andaverage).
As described in the previous section, eachapproach performed differently with regards toconcurrent updates. The Parent-Child approachefficiently handled updates at the leaf level (adding
or deleting leaf nodes), but not when modifying
entire sub-trees. The Path approach efficiently
handles deletes – by simply deleting the appropriate
rows in the table – but additions require saving the

$

'

?A &
;

!

! "

make it easy and efficient to query hierarchical datastored in XML. However, the large and dynamic
nature of the Metadata++ hierarchy is not adequately
supported by current XML tools. A full-featured
XML database would be an ideal solution, but thework in this area [10, 15] has yet to produce a native
XML database with all of the necessary features.
An alternative to building a native XML databaseis to map the XML to relations. The first two
implementations described in this paper (ParentChild and Path) are attempts at mapping XML-likedata into a relational database. The Parent-Child
$

@

55,
0677

2,
4246

3,
6//3

83,
02/4

18,
7105

/7,
6277

3,
0080

3,
2864

/1,
8652

6,
6823

'

80,
3728

/,
4755

3,
8364

00,
/3/7

28,
/732

?A &
;

3,
7283

/,
6100

3,
8728

3,
8721

3,
56//

%
*'

!

F!

(

(
)E

!

,7
)

*

%
*'

A! (*

233
/83
/33
83
3
$

F!
%
*'

-( -

relation is similar to the edge relation described in[4, 8]. LegoDB [2] takes a novel approach to
mapping XML into relations by doing a cost-based
evaluation of different relational representations.
Because the hierarchy in Metadata++ is a simple treeof arbitrary width and depth, the LegoDB algorithm
would also result in a simple edge-based relation.
Metadata++ requires functionality (i.e. SUBTREE
and FIND) that is not efficiently supported by thistype of representation. Our Path approach is similar
to XML indexing techniques described in [11]. This
technique works well for static data, but updates are
more difficult. The authors propose leaving gaps in
the ordering to handle updates, but this is still notsuitable for frequent and arbitrary updates.
The Lightweight Directory Access Protocol(LDAP) [9, 13] defines basic directory services for ahierarchically structured set of directories. LDAP
allows a single conceptual directory hierarchy to be
stored in multiple, distributed locations.
The
Metadata++ hierarchy differs from the directory
abstraction supported by LDAP in that Metadata++
terms (in the hierarchy) consist only of the word orphrase that makes up the term (the name of thedirectory); there is no type structure for terms and, inparticular, there is no need to have attributes forterms. Thus Metadata++ uses a much simpler
structure for the term hierarchy with a rather narrowfocus on the SUBTREE and FIND functions.

6

Conclusions and Work in Progress

Metadata++
makes
severalimportantcontributions.
As a model for controlled
vocabularies, Metadata++ differs from standard
thesauri by (1) allowing terms to appear in multiple
locations in the hierarchy, (2) allowing two terms,
when they both appear in two different portions of
the hierarchy, to have different narrower/broader
term relationships, and (3) treating all terms with

!

'

?A &
;
! "

equal emphasis (i.e., there is no notion of preferredterm). As a digital library application, Metadata++
allows users to see search results directly in thecontext of the hierarchy. That is, documents are notranked in the search result; they are shown directlywith the term or narrower term that they match.
Metadata++ also unifies the use of terms attachedexplicitly by a librarian (for explicit documents in asearch result) with terms found through text
indexing techniques (for implicit documents in asearch result).
The focus of this paper is on implementation
strategies for a large-scale term hierarchy. With
over 70,000 terms, with new terms being added andarranged on an ongoing basis, we had to find an
implementation that would support the SUBTREE
and FIND operations efficiently while still
maintaining consistency during concurrent updates.
The primary contribution of this paper is theperformance analysis of a series of implementations
that demonstrates that the directory/subdirectory
structure of a file system, when coupled with anindex server, provides an ideal solution for storinglarge-scale term hierarchies. This result may be
applicable to other applications that must manage
large-scale hierarchical information.
Work in progress includes extensive user testing,with a goal of deploying Metadata++ for use innatural resource management, and formalizing theMetadata++ model. We will also continue our workin integrating Metadata++ with geographic
information systems [14].

7References[1] ANSI/NISO Z39.19 – 1993. Guidelines for theConstruction, Format, and Management ofMonolingual Thesauri. NISO Press, 1994.
[2] Bohannon, Philip, Juliana Freire, Prasan Roy and
Jerome Simeon From XML Schema to

[3]

[4]
[5]
[6]
[7]
[8]
[9]

Relations: A Cost-Based Approach to XML
Storage (ICDE 2002)
Delcambre, Lois, Timothy Tolle. “Harvesting
InformationTo
Sustain
Forests”.
Communications of the ACM, January 2003
Volume 46, Number 1, pp. 38-39.
Deutsch, Alin, Mary F. Fernandez, Dan
Suciu. Storing Semistructured Data withSTORED. (SIGMOD 1999)
Dewey
DecimalClassification.
http://www.oclc.org/dewey/index.htm
DublinCore
Metadata
Initiative.
http://www.dublincore.org/
FederalGeographic
Data
Committee.
http://www.fgdc.gov/
Florescu, Daniela, Donald Kossmann: Storing andQuerying XML Data using an RDMBS. IEEE
Data Engineering Bulletin 22(3): 27-34 (1999)
Howes, Timothy A., Mark C. Smith, LDAP:
Programming Directory-Enabled Applications
with Lightweight Directory Access Protocol,
Macmillan Technical Publishing, 1997.

[10] Jagadish, H.V., Shurug Al-Khalifa, Adriane
Chapman, Laks V.S. Lakshmanan, Andrew
Nierman, Stelios Paparizos, Jignesh M.
Patel, Divesh Srivastava, Nuwee
Wiwatwattana, Y.Wu and C.Yu.
TIMBER: A Native XML Database. The
VLDB Journal, Volume 11 Issue 4 (2002)
pp 274-291.

[11] Kaushik, Raghav, Philip Bohannon, Jeffrey F.
Naughton, Henry F. Korth Covering indexes
forbranchingpath
queries. SIGMOD
Conference 2002: 133-144[12] Nareddy, Krishna. “Indexing with Microsoft Index
Server”. Microsoft Corporation, January 1998.
[13] Open LDAP Project. http://www.openldap.org/[14] Weaver, Mathew, Lois Delcambre, Leonard Shapiro,
Jason Brewster, Afrem Gutema, Timothy Tolle.
“A Digital GeoLibrary: Integrating Keywords
And Place Names”, 7th European Conference
on Digital Libraries (ECDL 2003), Trondheim,
Norway, August 2003.

[15] XML:DB Initiative for XML Databases.
http://www.xmldb.org/