LOGML and XGMML - XML Languages for Web Characterization and Web Data Mining

John R. Punin, Mukkai S. Krishnamoorthy, Mohammed J. Zaki
Department of Computer Science, RPI, Troy, NY, 12180 USA

Abstract

Two new XML languages, XGMML and LOGML, and a Web usage mining application which uses both these XML languages, are described in this paper. Each of these XML languages exploit both the structure of the web as well as the log-data from the server. We illustrate the ease with which the web data mining application is written because of the XGMML and LOGML. XGMML and LOGML facilitate in obtaining frequent structural information - such as associations and sequences of the web site. We illustrate this with a web site of an educational institution. We further provide an example to illustrate the ease with which the characterization about a web site is obtained using LOGML.

Keywords: XML, XGMML, LOGML, Web Usage Mining, Web Characterization, Web Graph, WWWPal System, Frequent Pattern Mining

1 Introduction

Recently XML is gaining wider acceptance in both commercial and research establishments. In this paper, we suggest two XML languages and a web data mining application which utilizes them to extract complex structural information.

XGMML (Extensible Graph Markup and Modeling Language) [21] is an XML 1.0 application [23] based on Graph Modeling Language (GML) [6] which is used for graph description. XGMML uses tags to describe nodes and edges of a graph. The purpose of XGMML is to make possible the exchange of graphs between different authoring and browsing tools for graphs. The conversion of graphs written in GML to XGMML is straight forward. Using XSL (Extensible Stylesheet Language) [26] with XGMML allows the translation of graphs to different formats. In Section 2, we present details of XGMML.

Log Markup Language (LOGML) [7] is an XML 1.0 application designed to describe log reports of web servers. Web data mining is one of the current hot topics in computer science. Mining data that has been collected from web server logfiles, is not only useful for studying customer choices, but also helps in organizing web pages. This is accomplished by knowing which web pages are most frequently accessed by the web surfers. In section 2 we explain how the structure of a web site can be represented as a web graph using XGMML. In mining the data from the log statistics, we use the web graph in annotating the log information. Further we give summary reports, comprising of information such as client sites, types of browsers and the usage time statistics. We also gather the client activity in a web site as a subgraph of the web site graph. This subgraph can be used to get better understanding of general user activity in the web site. In LOGML, we create a new XML vocabulary to structurally express the contents of the logfile information. In section 3, we present details of LOGML. Section 4 describes LOGML generator as an additional module for the WWWPal system [13].

Web data mining has been gaining a lot of attention because of its potential commercial benefits. For example, consider a web log database at a popular site, where an object is a web user and an attribute is a web page. The mined patterns could be the sets or sequences of most frequently accessed pages at that site. This kind of information can be used to restructure the web-site, or to dynamically insert relevant links in web pages based on user access patterns. Furthermore, click-stream mining can help E-commerce vendors to target potential online customers in a more effective way, at the same time enabling personalized service to the customers.

Web Mining is an umbrella term that refers to mainly two distinct tasks. One is Web Content Mining [3], which deals with problems of automatic information filtering and categorization, intelligent search agents, and personalize web agents. Web Usage Mining [3] on the other hand relies on the structure of the site, and concerns itself with discovering interesting information from user navigational behavior as stored in web access logs.

The focus of this paper is primarily on using web usage mining. While extracting simple information from web logs is easy, mining complex structural information is very challenging. Data cleaning and preparation constitute a very significant effort before mining can even be applied. The relevant data challenges include: elimination of irrelevant information such as image files and cgi scripts, user identification, user session formation, incorporating temporal windows in the user modeling, and so on. After all this pre-processing one is ready to mine the resulting database.

The proposed LOGML and XGMML languages have been designed to facilitate this web mining process in addition to storing additional detailed summary information extracted from web logs. Using the LOGML generate documents the pre-processing steps of mining are considerably simplified. We also propose a new mining paradigm, called Frequent Pattern Mining, to extract increasingly informative patterns from the LOGML database. Our approach and its application to real log databases is discussed further in Section 5.

Section 6 illustrates how LOGML can be applied for web characterization. We provide an example to demonstrate the ease with which information about a website can be generated using LOGML with style sheets (XSLT). Additional information about web characterization can also be extracted from the mined data.

2 XGMML (Extensible Graph Markup and Modeling Language)

A Graph, G= (V,E), is a set of nodes V and a set of edges E. Each edge is either an ordered (directed graph) or unordered (undirected) pair of nodes. Graphs can be described as data objects whose elements are nodes and edges (which are themselves data objects). XML is an ideal way to represent graphs. Structure of the World Wide Web is a typical example of a graph where the web pages are "nodes," and the hyperlinks are "edges." One of the best ways to describe a web site structure is using a graph structure and hence XGMML documents are a good choice for containing the structural information of a web site. XGMML was created to be used for the WWWPal System [13] that visualizes web sites as a graph. The web robot of W3C (webbot) [19], part of the WWWPal System, navigates through web sites and saves the graph information as an XGMML file. XGMML, as any other XML application, can be mixed with other markup languages to describe additional graph, node and/or edge information.

2.1 Structure of XGMML Documents

An XGMML document describes a graph structure. The root element is the graph element and it can contain node, edge and att elements. The node element describes a node of a graph and the edge element describes an edge of a graph. Additional information for graphs, nodes and edges can be attached using the att element. A graph element can be contained in an att element and this graph will be considered as subgraph of the main graph. The graphics element can be included in a node or edge element, and it describes the graphic representation either of a node or an edge. The following example is a graph with just one node.

Example 1

<?xml version="1.0"?>
<!DOCTYPE graph PUBLIC "-//John Punin//DTD graph description//EN" "http://www.cs.rpi.edu/~puninj/XGMML/xgmml.dtd">
<graph directed="1" id="2">
<node id="1" label="Node 1"/>
</graph>

XGMML well formed documents can be part of other XML documents using namespaces [10]. The following example is a graph inside of an XHTML [22] document :

Example 2

<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" 
      xmlns:xsi="http://www.w3.org/2000/10/XMLSchema-instance"
      xmlns:xgmml="http://www.cs.rpi.edu/XGMML"
      xsi:schemaLocation="http://www.w3.org/1999/Style/Transform
                          http://www.w3.org/1999/Style/Transform/xslt.xsd
                          http://www.w3.org/1999/xhtml
                          http://www.w3.org/1999/xhtml/xhtml.xsd
                          http://www.cs.rpi.edu/XGMML
                          http://www.cs.rpi.edu/~puninj/XGMML/xgmml.xsd"

      xml:lang="en">
      
<head>
<title>Graph Information</title>
</head>
<body>

<!-- XHTML Document here -->

     <xgmml:graph directed="1" graphic="1" Layout="points">
       <xgmml:node id="1" label="1" weight="0">
         <xgmml:graphics type="circle" x="250" y="90" />
       </xgmml:node>
       <xgmml:node id="2" label="2" weight="0">
         <xgmml:graphics type="circle" x="190" y="150" />
       </xgmml:node>
       <xgmml:edge source="1" target="2" weight="0" />
     </xgmml:graph>

<!-- XHTML Document here -->

</body>
</html>

RDF (Resource Description Framework) [14] is one way to describe metadata about resources. XGMML includes metadata information for a graph, node and/or edge using the att tag. Example 3 is part of a graph describing a website. The nodes represent web pages and the edges represent hyperlinks. The metadata of the webpages is included as attribute of a node. RDF and DC (Dublin Core)[5] vocabularies have been used to describe the metadata of the nodes.

Example 3

<?xml version="1.0"?>
<graph xmlns = "http://www.cs.rpi.edu/XGMML"
       xmlns:xsi="http://www.w3.org/2000/10/XMLSchema-instance"
       xsi:schemaLocation="http://www.cs.rpi.edu/XGMML
       http://www.cs.rpi.edu/~puninj/XGMML/xgmml.xsd"
       directed="1" >
<node id="3" label="http://www.cs.rpi.edu/courses/" weight="5427">
<att>
<rdf:RDF
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
  xmlns:dc="http://purl.org/dc/elements/1.0/">
  <rdf:Description about="http://www.cs.rpi.edu/courses/"
    dc:title="Courses at Rensselaer Computer Science
    Department"
    dc:subject="www@cs.rpi.edu; M.S. requirements; CSCI-1190
    Beginning C Programming for Engineers; Courses; People;
    Graduate Program; CSCI-4020 Computer  Algorithms; CSCI-
    2220-01  Programming in Java; Research; Course Selection
    Guide; CSCI-4961-01,  CSCI-6961-01 Advanced Robotics; 
    Programming in Java; CSCI-2400 Models  of Computation"
    dc:date="2000-01-31"
    dc:type="Text"
    >
    <dc:format>
      <rdf:Bag
        rdf:_1="text/html"
        rdf:_2="5427 bytes"
      />
    </dc:format>
  </rdf:Description>
</rdf:RDF>
</att>
</node>
....
<edge source="1" target="3" weight="0" label="SRC IMG gfx/courses2.jpg" />
<edge source="7" target="3" weight="0" label="SRC IMG ../gfx/courses2.jpg" />
</graph>

2.2 XGMML Valid Documents

An XGMML valid document must be an XML well-formed document [25]. An XGMML valid document additionally can be validated against an XGMML DTD [21] or XGMML Schema [21]. The XGMML Schema is based on the XML Schema Working Draft 22 September 2000 [24]. A valid XML document can have multiple schemas. The namespace for XGMML is: http://www.cs.rpi.edu/XGMML and the suffix for the XGMML elements is xgmml:. Example 2 and 3 shows two valid XML documents that can be validated using several XML Schemas including XGMML Schema.

2.3 XGMML Elements and Attributes.

The main elements of XGMML are: graph, node, edge, att and graphics. The graph element is the root element of an XGMML valid document. The graph element may not be unique in the XGMML document. Other graphs can be included as subgraphs of the main graph. All XGMML elements have global attributes that are id, name and label. The id attribute is an unique number (NMTOKEN) [25] to identify the XGMML element. The name is a string to identify the elements and the label is a string used a text representation of the elements. The graph element has the directed attribute that is a boolean value to express whether the graph is directed or not.

Nodes and edges can reference XGMML documents. For example, a node may represent a graph that can be shown when the user points in the node. This behavior is similar to hyperlinks in HTML documents. XGMML uses XLink framework [23] to create hyperlinks either in nodes or edges. The XLink attributes: type, role, title, show, actuate and href, are added as attributes of the node and edge elements. All these attributes are taken directly from the XLink Working Draft.

The node element describes the properties of a node object. The node can be rendered as a graphic object and also can have additional meta information to be used for the application program. The only elements allowed inside the node are graphics and att. The graphic representation of the node is reported on the graphics element. For example, a graphical representation of a node can be a rectangle, a circle or a bitmap. The additional meta information is reported on the att element. For example, if a node is a representation of a web page, useful metadata is the title, date of creation and size of the web page.

The edge element describes the properties of an edge object. For each edge element at least two node elements have to be included in the graph element. An edge is between a source node and a target node. The application program must verify if the source node and target node are included in the XGMML document. The weight attribute is used to save the weight number for weighted graphs. The edge element as the node element can have a graphical representation and additional metadata information. The graphics element shows the graphical representation of an edge. For example, a graphical representation of an edge can be a line or an arc. An att element is used to attach additional meta information related to an edge. For example, if an edge is a representation of a hyperlink, useful metadata is the anchor string and the type of the hyperlink (Typed Links)[17].

An att element is used to hold meta information about the element that contains the att element. An att element can contain other att elements, for example to represent structured metadata such as records, lists, etc. For example, the metadata of an object person A is name: John, ssn: 123456789 and e-mail: john@rpi.edu. To attach this metadata to a node of a graph using the att element, the following lines must be included in the node element:

<att type="list" name="person_description">
<att name="name" value="John"/>
<att name="ssn" value="123456789"/>
<att name="e-mail" value="john@rpi.edu"/>
</att>

The graphics element defines the graphical representation a graph, a node or an edge. A graphics element must be included in a graph, node or edge element. Line, center and att elements are the only elements that can be contained in a graphics element. Line element is defined between two point elements and it is used to represent edges. A center element is a special point element to represent the central point of the graphical representation of a node. The att element permits to add information to the graphical representation. All these elements are inherited from GML[6].

3 LOGML (Log Markup Language)

Log reports are the compressed version of logfiles. Web masters in general save web server logs in several files. Usually each logfile contains a single day of information. Due to disk space limitation, old log data gets deleted to save new log information. Generally, web masters generate HTML reports of the logfiles and do not have problems keeping them for a long period of time as the HTML reports are an insignificant size. If a web master likes to generate reports for a large period of time, he has to combine several HTML reports to produce a final report. LOGML is conceived to make this task easier. Web masters can generate LOGML reports of logfiles and combine them on a regular basis without much effort. LOGML files can be combined with XSLT [26] to produce HTML reports. LOGML offers the flexibility to combine them with other XML applications, such as SVG [16], to produce graphics of the statistics of the reports. LOGML in addition can be combined with RDF [14] to provide some metadata information about the web server that is being analyzed. LOGML is based on XGMML that is a language to describe graphs. LOGML can be seen as a snapshot of the web site as the user visits web pages and traverses hyperlinks. LOGML also provides a succinct way to save the user sessions. In the W3C Working Draft "Web Characterization Terminology & Definitions Sheet", the user session is defined as "... a delimited set of user clicks across one of more Web servers" [18].

3.1 Structure of LOGML Documents

A typical LOGML Document has three sections. The root element is the logml element and it contains the three sections. The first section is a graph that describes the log graph of the visits of the users to web pages and hyperlinks. This section uses XGMML to describe the graph and the root element is the graph element. The second section is the additional information of log reports such as top visiting hosts, top user agents, top keywords, etc. The third section is the report of the user sessions. Each user session is a subgraph of the log graph. The subgraphs are reported as a list of edges that refer to the nodes of the log graph. Each edge of the user sessions also has a timestamp when the edge was traversed. This timestamp helps to compute the total time of the user session.

LOGML files are large files so example 4 shows part of a LOGML file.

Example 4

<?xml version="1.0"?>
<logml xmlns="http://www.cs.rpi.edu/LOGML"
       xmlns:xsi="http://www.w3.org/2000/10/XMLSchema-instance"
       xsi:schemaLocation="http://www.cs.rpi.edu/LOGML
       http://www.cs.rpi.edu/~puninj/LOGML/logml.xsd"
        start_date="12/Oct/2000:05:00:05" 
        end_date="12/Oct/2000:16:00:01">
<graph xmlns="http://www.cs.rpi.edu/XGMML"
       xmlns:lml="http://www.cs.rpi.edu/LOGML"
       xsi:schemaLocation="http://www.cs.rpi.edu/XGMML
       http://www.cs.rpi.edu/~puninj/XGMML/xgmml.xsd
       http://www.cs.rpi.edu/LOGML
       http://www.cs.rpi.edu/~puninj/LOGML/logml.xsd"
       directed="1">
<node id="234" label="http://www.cs.rpi.edu/~puninj/JAVA/projects/lfarrw.gif"
 lml:hits="1" weight="1">
<att name="title" value="No title"/>
<att name="mime" value="image/gif"/>
<att name="size" value="1291"/>
<att name="date" value="Sun Jun 11 02:14:28 2000"/>
<att name="code" value="200"/>
</node>
<node id="228" label="http://www.cs.rpi.edu/~puninj/XGMML/POSTER/IMG/pptgraph.gif" 
lml:hits="2" weight="2">
<att name="title" value="No title"/>
<att name="mime" value="image/gif"/>
<att name="size" value="27689"/>
<att name="date" value="Wed Sep 22 14:17:15 1999"/>
<att name="code" value="200"/>
</node>
....
<edge source="191" target="234" label="SRC IMG lfarrw.gif" lml:hits="1" weight="1">
<att value="image"/>
</edge>
<edge source="161" target="228" lml:hits="2" weight="2">
<att value="image"/>
</edge>
....
<edge source="550" target="561" lml:hits="1" weight="1" lml:indp="1"/>
<edge source="550" target="562" lml:hits="1" weight="1" lml:indp="1"/>
</graph>

<hosts count="35">
<host name="vamos.inria.fr" access_count="43" bytes="487397" html_pages="43"/>
<host name="kbl-ternzn1200.zeelandnet.nl" access_count="13" bytes="46354" 
html_pages="1"/>
....
</hosts>

<domains count="9">
<domain name="fr" access_count="44" bytes="488509" html_pages="44"/>
<domain name="unknown" access_count="25" bytes="388608" html_pages="16"/>
<domain name="com" access_count="21" bytes="229979" html_pages="19"/>
....
</domains>

<directories count="30">
<directory name="http://www.cs.rpi.edu/~puninj/XGMML" access_count="21" 
total_count="49" bytes="1116521"/>
<directory name="http://www.cs.rpi.edu/~puninj/TALK" access_count="19" 
total_count="22" bytes="91460"/>
....
</directories>

<userAgents count="23">
<userAgent name="xyro_(xcrawler@cosmos.inria.fr)" access_count="43" 
bytes="487397" html_pages="43"/>
<userAgent name="Mozilla/4.0 (compatible; MSIE 5.0; Windows 98; DigExt)" 
access_count="27" bytes="670815" html_pages="9"/>
....
</userAgents>

<hostReferers count="14">
<hostReferer name="No Referer" access_count="66" bytes="945527"/>
<hostReferer name="http://www.cs.rpi.edu" access_count="41" bytes="701097"/>
<hostReferer name="http://home.xnet.com" access_count="1" bytes="1112"/>
....
</hostReferers>

<referers count="11">
<referer name="No referer" access_count="66" bytes="945527"/>
<referer name="http://boss.cae.wisc.edu/hppd/hpux/Networking/WWW/xhtml-1.3/" 
access_count="1" bytes="35272" target="8"/>
<referer name="http://informant.dartmouth.edu/" access_count="1" bytes="1112"
 target="2"/>
....
</referers>

<keywords count="10" search_count="9">
<keyword name="java" count="3"/>
<keyword name="xhtml" count="2"/>
....
</keywords>

<summary 
 requests="132" sessions="6" bytes="1796173"
 html_pages="56" nhtml_pages="17" inline_objects="10" hyperlink_html="7" 
 hyperlink_nhtml="16"
 html_entry_pages="55" nhtml_entry_pages="4" unique_sites="35" unique_host_referers="8" 
 unique_se_referers="6"
 unique_external_url_referers="7" unique_internal_url_referers="4" unique_user_agents="23"
 requests_hour="12.00" requests_day="288.03" kbytes_day="159.48" kbytes_hour="3827.46"
 searches="9" unique_keywords="10">

<httpCode code="200" name="200 - OK " count="118" bytes="1793393" html_pages="83"/>
<httpCode code="301" name="301 - Moved Permanently" count="3" bytes="1058" html_pages="3"/>
<httpCode code="304" name="304 - Not Modified" count="6" bytes="0" html_pages="5"/>
<httpCode code="404" name="404 - Not Found" count="5" bytes="1722" html_pages="5"/>

<httpMethod name="GET" count="131" bytes="1796173" html_pages="95"/>
<httpMethod name="HEAD" count="1" bytes="0" html_pages="1"/>

<httpCode name="HTTP/1.0" count="97" bytes="1399288" html_pages="83"/>
<httpCode name="HTTP/1.1" count="35" bytes="396885" html_pages="13"/>

<dateStat>
<monthStat month="10" hits="132" bytes="1796173" html_requests="96"/>
<dayStat day="12" hits="132" bytes="1796173" html_requests="96"/>
<hourStat hour="5" hits="12" bytes="15622" html_requests="12"/>
<hourStat hour="6" hits="15" bytes="103280" html_requests="14"/>
<hourStat hour="7" hits="41" bytes="642786" html_requests="28"/>
<hourStat hour="8" hits="16" bytes="105435" html_requests="9"/>
<hourStat hour="10" hits="2" bytes="346" html_requests="2"/>
<hourStat hour="11" hits="7" bytes="54889" html_requests="5"/>
<hourStat hour="12" hits="22" bytes="505379" html_requests="14"/>
<hourStat hour="13" hits="2" bytes="1444" html_requests="2"/>
<hourStat hour="14" hits="12" bytes="364297" html_requests="7"/>
<hourStat hour="15" hits="3" bytes="2695" html_requests="3"/>
</dateStat>

</summary>

<userSessions count="2" max_edges="100" min_edges="2">
<userSession name="proxy.artech.com.uy" ureferer="No referer" 
entry_page="http://www.cs.rpi.edu/~puninj/XGMML/" start_time="12/Oct/2000:12:50:11" 
access_count="4">
<path count="3">
<uedge source="3" target="10" utime="12/Oct/2000:12:50:12"/>
<uedge source="3" target="21" utime="12/Oct/2000:12:51:41"/>
<uedge source="21" target="22" utime="12/Oct/2000:12:52:02"/>
</path>
</userSession>
<userSession name="207.234.33.12" 
ureferer="http://search.excite.com/search.gw?search=XHTML" 
entry_page="http://www.cs.rpi.edu/~puninj/TALK/head.html" 
start_time="12/Oct/2000:14:05:10" access_count="3">
<path count="2">
<uedge source="2" target="7" utime="12/Oct/2000:14:05:24"/>
<uedge source="2" target="8" utime="12/Oct/2000:14:06:14"/>
</path>
</userSession>
</userSessions>
</logml>

3.2 LOGML Valid Documents

A LOGML valid document is a well-formed XML document that can be validated against a LOGML DTD [7] or LOGML Schema [7]. The namespace for LOGML is: http://www.cs.rpi.edu/LOGML and the suffix for LOGML elements is lml:.

3.3 LOGML Elements and Attributes

The root element of a LOGML document is the logml element. The rest of the elements are classified with respect to the three sections of the LOGML document. The first section is the report of the log graph and we use the XGMML elements to describe this graph. The second section report the general statistics of the web server such as top pages, top referer URLs, top visiting user agents, etc. And, the last section reports the user sessions.

The global attributes are used by most of the LOGML elements and they are:

id - unique number to identify the elements of LOGML document
name - string to identify the elements of LOGML document
label - text representation of the LOGML element
access_count - number of times the web server has been accessed. For example, the number of times of a specific user agent accessed the web server.
total_count - total number of times that an element is found in a logfile. For example, the total count of a keyword.
bytes - number of bytes downloaded.
html_pages - number of HTML pages requested from the web server. For example, the number of html pages requested by a specific site.

The XGMML elements that we use to describe the log graph are graph, node, edge and att. We add the hits attribute to the node and edge elements to report the number of visits to the node (web page) and the number of traversals to the edge (hyperlink). The att element is used to report metadata information of the web page such as mime type and size of the file.

The elements of the second section are:

hosts, host - This host list is composed by a container hosts element whose attribute is the count of the host element inside of the hosts element. The host element is an empty element and contains information about the visiting site such as hostname, IP and number of bytes transferred by the site.
domains, domain - The domains element is a list of all domain visiting the web server. The domain is the suffix of the domain name of the sites. For example: edu is the domain of the site www.cs.rpi.edu.
directories, directory - The directories list contains the top directories of the web site that have most requested web pages. The directory is the prefix of the URI of the web page. For example: The directory of the web page: http://www.rpi.edu/dept/urp/find.html is http://www.rpi.edu/dept/urp
userAgents, userAgent - The list of user agents contains all user agents (browsers and/or spiders) that have made requests to the web server. The LOGML reader can refine this list to compute the top platforms and top web browsers since the User Agent name contains information about the platform and name of web browser.
referers, referer - The referers list contains two lists: The list of the top external referers and the list of the top internal referers. The external referers are the referers whose host are different than the web server. The host of the internal referers are the same as the web server.
hostReferers, hostReferer - The host referers list contains the top host referers of the web pages of the web server. This list combines the number of accesses of the referers with the same host.
keywords, keyword - Keywords are the searching words found in the URI referers of the search engines. Several keywords lists can be reported. Each keywords list is associated with a particular search engine.
summary - The summary element contains a brief overview of the essential information of the web server. This information is very important for web masters to know the efficiency of the web server. The summary attributes are:

requests - the total number of requests
sessions - the total number of user sessions
bytes - the total number of bytes transferred
html_pages - the total number of unique html pages
nhtml_pages - the total number of unique non html pages
inline_objects - the total number of unique inline objects. Inline objects are the objects inside of a html page such as images
hyperlinks_html - the total number of unique hyperlinks to html pages
hyperlinks_nhtml - the total number of unique hyperlinks to non html pages
html_entry_pages - the total number of unique html pages that are entry pages to the web site of the web server.
nhtml_entry_pages - the total number of unique non html pages that are entry pages to the web site of the web server.
unique_sites - the total number of unique visiting sites
unique_host_referers - the total number of the unique host referers to the web pages of the web server.
unique_se_referers - the total number of the unique search engines that access the web server.
unique_external_url_referers - the total number of unique external URI referers to the web pages of the web server
unique_internal_url_referers - the total number of unique internal URI referers to the web pages of the web server.
unique_user_agents - the total number of the unique user agents that access the web pages of the web server.
requests_hour - the number of requests per hour
requests_day - the number of requests per day
kbytes_hour - the number of kilobytes transferred per hour
kbytes_day - the number of kilobytes transferred per day
searches - the total number of searching requests
unique_keywords - the total number of unique keywords in the searching requests

httpCode - The httpCode element gives the summary of the HTTP status code of the requests
httpMethod - The httpMethod element gives the summary of the HTTP methods used by the web clients to communicate with the web server
httpVersion - The httpVersion element gives the summary of the HTTP version used by the web clients to communicate with the web server
dateStat, monthStat, dayStat and hourStat. - The date elements give the summary of the statistics by date of the requests

The third section of the LOGML document reports the user sessions and the LOGML element being used are:

userSessions, userSession - The userSessions element is the container element for the set of the user sessions. Each user session is described using the userSession, path and uedge elements where a path is the collection of hyperlinks that the user has traversed during the session.
path - The path element contains all hyperlinks that the user has traversed during the user session.
uedge - The uedge element reports a hyperlink that has been traversed during the user session. The source and the target attributes are reference to nodes of the Log Graph in the first section and the utime attribute is the timestamp where the user traversed this hyperlink

Example 5 is the report of one user session in a LOGML document:

Example 5

<userSession name="proxy.artech.com.uy" ureferer="No referer" 
entry_page="http://www.cs.rpi.edu/~puninj/XGMML/" start_time="12/Oct/2000:12:50:11" 
access_count="4">
<path count="3">
<uedge source="3" target="10" utime="12/Oct/2000:12:50:12"/>
<uedge source="3" target="21" utime="12/Oct/2000:12:51:41"/>
<uedge source="21" target="22" utime="12/Oct/2000:12:52:02"/>
</path>
</userSession>

4 LOGML Generator

We have written a simple LOGML Generator as part of the WWWPAL System. The LOGML Generator reads a common or extended log file and generates a LOGML file. The LOGML Generator also can read the webgraph (XGMML file) of the web site being analyzed and combine the information of the web pages and hyperlinks with the log information.

The information that we extract from the common logs is: host name or IP, date of the request, relative URI of the requested page, HTTP version, HTTP status code, HTTP method and bytes transferred to the web client. The extended log files contain additionally the absolute URI of the referer web page and a string that describes the User Agent (web browser or web crawler) that has made the request. These information is saved in a data structure to generate the LOGML Document. The LOGML Generator also can write HTML reports making this module a powerful tool for web administrators.

Several algorithms have been developed to find the user sessions in the log files [9,11,20]. A simple algorithm uses the IP or host name of the web client to identify a user. SpeedTracer [20] also checks the User Agent and date of the request to find the user session. Straight ways to find user session requires "cookies" or remote user identification [9]. LOGML Generator algorithm to find user sessions is very similar to the algorithm used by SpeedTracer. An user is identified by IP and User Agent. We only consider a User session if the user has traversed at least one hyperlink and a user session is considered finished when there are not more requests made by the user in a given period of time. The LOGML Generator also identifies spiders either by the User Agent name or by the high number of the requests in a brief period of time. Spiders are not considered as user sessions. User sessions are being reported as a set of hyperlinks between HTML pages. We can expand the user sessions inline objects using the log graph of the first section of the LOGML document. The hyperlinks are reported with the timestamp for Web Data Mining purposes.

We used the Graph Visualizer of WWWPal System to display the log graph of the LOGML document or any of the user sessions that has been identified in the log files. Figure 6 shows part of the log graph of the Rensselaer Info web site (http://www.rpi.edu/rpinfo/). The numbers on the edges are the times that a user has traversed that edge (hyperlink).

Figure 6: Log graph of RPI Info Website

Figure 7 shows the log graph of the Rensselaer News website (http://www.rpi.edu/web/News/). The number in the nodes are the times that a user has requested that node (web page). For visualization purposes just the main nodes of the log graph have been highlighted and the title of the web page displayed.

Figure 7: Log Graph of RPI News Magazine Website

5 Using LOGML for Web Data Mining

In this section, we propose solving a wide class of mining problems that arise in web data mining, using a novel, generic framework, which we term Frequent Pattern Mining (FPM). FPM not only encompasses important data mining techniques like associations and sequences, but at the same time generalizes the problem to include more complex patterns like tree mining and graph mining, that arise in complex domains like web mining. Thus the frequent subsets of association mining, and the frequent subsequences of sequence mining are some of the specific instances of FPM that have been studied in past work [1,28,15,8,29]. In general, however, we can discover increasingly complex structures from the same database. Examples of such complex patterns include frequent subtrees, frequent DAGs, frequent directed or undirected subgraphs, etc. As one increases the complexity of the structures to be discovered, one extracts more informative patterns.

The same underlying LOGML document that stores the web graph, as well as the user sessions, which are subgraphs of the web graph, can be used to extract increasingly complex and more informative patterns. Given a LOGML document extracted from the database of web access logs at a popular site, one can perform several mining tasks. The simplest is to ignore all link information from the user sessions, and to mine only the frequent sets of pages accessed by users. The next step can be to form for each user the sequence of links they followed, and to mine the most frequent user access paths. It is also possible to look at only the forward accesses of a user, and to mine the most frequently accessed subtrees at that site. Generalizing even further, a website can be modeled as a directed graph, since in addition to the forward hyperlinks, it can have back references, creating cycles. Given a database of user accesses (with full information about their traversal, including forward and backward links) one can discover the frequently occurring subgraphs.

In the rest of this section, we first formulate the FPM problem. We show how LOGML facilitates the creation of a database suitable for web mining. Using real examples we show our experimental results on one day of RPI logs, and we describe several increasingly complex mining tasks that can be performed on the same LOGML database.

5.1 Frequent Pattern Mining: Problem Formulation

FPM is a novel, generic framework for mining various kinds of frequent patterns. Consider a database $\cal D$ of a collection of structures, built out of a set of primitive items $\cal I$ . A structure represents some relationship among items or sets of items. For a given structure G, let $S \preceq G$ denote the fact that S is a substructure of G. If $S \preceq G$ we also say that G contains S. The collection of all possible structures composed of the set of items $\cal I$ forms a partially ordered set under the substructure relation $\preceq$ . A structure formed from k items is called a k-structure. Given a collection of structures, a structure is called maximal if it is not a substructure of any other structure in the set. We define the support of a structure G in a database $\cal D$ to be the number of structures in $\cal D$ that contain G. Alternately, if there is only one very large structure in the database, the support is the number of times G occurs as a substructure within it. We say that a structure is frequent if its support is more than a user-specified minimum support (min_sup) value. The set of frequent k-structures is denoted as ${\cal F}_k$ .

A structural rule is an expression $X \Rightarrow Y$ , where X and Y are structures. The support of the rule in the database of structures is the joint probability of X and Y, and the confidence is the conditional probability that a structure contains Y, given that it contains X. A rule is strong if its confidence is more than a user-specified minimum confidence (min_conf).

The frequent pattern mining task is to generate all structural rules in the database, which have a support greater than min_sup and have confidence greater than min_conf. This task can be broken into two main steps: 1) Find all frequent structures having minimum support and other constraints. This step is the most computationally and I/O intensive step, since the search space for enumeration of all frequent substructures is exponential in the worst case. The minimum support criterion is very successful in reducing the search space. In addition other constraints can be induced, such as finding maximal, closed or correlated substructures. 2) Generate all strong structural rules having minimum confidence. Rule generation is also exponential in the size of the longest substructure. However, this time we don't have to access the database; we only need the set of frequent structures.

5.2 Database Creation: LOGML to Web Mining

We designed the LOGML language to facilitate Web Mining. The LOGML document created from web logs has all the information we need to perform various FPM tasks. For structure mining from web logs, we mainly make use of two sections of the LOGML document. As described above, the first section contains the web graph, i.e., the actual structure of the web site in consideration. We use the web graph to obtain the page URLS and their node identifiers. For example, the example below shows a snippet of the (node id, URL) pairs (out of a total of 56623 nodes) we extracted from the web graph of the RPI computer science department:

1 http://www.cs.rpi.edu/
4 http://www.cs.rpi.edu/guide/machines/
6 http://www.cs.rpi.edu/courses/
8 http://www.cs.rpi.edu/current-events/
10 http://www.cs.rpi.edu/grad/
12 http://www.cs.rpi.edu/People/    
14 http://www.cs.rpi.edu/research/ 
16 http://www.cs.rpi.edu/undergrad/ 
31 http://www.cs.rpi.edu/guide/ 
...

For enabling web mining we make use of the third section of the LOGML document that stores the user sessions organized as subgraphs of the web graph. We have complete history of the user clicks including the time a page is requested. Each user session has a session id (the IP or host name), a path count (the number of source and destination node pairs) and the time a link is traversed. We simply extract the relevant information depending on the mining task at hand. For example if our goal is to discover frequent sets of pages accessed, we ignore all link information and note down the unique source or destination nodes in a user session. For example, let the user session have the following information in the LOGML document:

<userSession name=''ppp0-69.ank2.isbank.net.tr'' ...>
<path count=''6''>
<uedge source=''5938'' target=''16470''
utime=''24/Oct/2000:07:53:46''/>
<uedge source=''16470'' target=''24754''
utime=''24/Oct/2000:07:56:13''/>
<uedge source=''16470'' target=''24755''
utime=''24/Oct/2000:07:56:36''/>
<uedge source=''24755'' target=''47387''
utime=''24/Oct/2000:07:57:14''/>
<uedge source=''24755'' target=''47397''
utime=''24/Oct/2000:07:57:28''/>
<uedge source=''16470'' target=''24756''
utime=''24/Oct/2000:07:58:30''/>

We can then extract the set of nodes accessed by this user:

#format: user name, number of nodes accessed, node list 
ppp0-69.ank2.isbank.net.tr 7 5938 16470 24754 24755 47387 47397 24756

After extracting this information from all the user sessions we obtain a database that is ready to be used for frequent set mining, as we shall see below.

On the other hand if out task is to perform sequence mining, we look for the longest forward links, and generate a new sequence each time a back edge is traversed. Using a simple stack-based implementation all maximal forward node sequences can be found. For the example user session above we would get:

#format: user name, sequence id, node position, node accessed
ppp0-69.ank2.isbank.net.tr 1 1 5938 
ppp0-69.ank2.isbank.net.tr 1 2 16470 
ppp0-69.ank2.isbank.net.tr 1 3 24754

ppp0-69.ank2.isbank.net.tr 2 1 5938 
ppp0-69.ank2.isbank.net.tr 2 2 16470 
ppp0-69.ank2.isbank.net.tr 2 3 24755
ppp0-69.ank2.isbank.net.tr 2 4 47387

ppp0-69.ank2.isbank.net.tr 3 1 5938 
ppp0-69.ank2.isbank.net.tr 3 2 16470 
ppp0-69.ank2.isbank.net.tr 3 3 24755
ppp0-69.ank2.isbank.net.tr 3 4 47397

ppp0-69.ank2.isbank.net.tr 4 1 5938
ppp0-69.ank2.isbank.net.tr 4 2 16470
ppp0-69.ank2.isbank.net.tr 4 3 24756

For more complex mining task like tree or graph mining, once again the appropriate information can be directly read from the LOGML user sessions.

**Figure 1:** Site Graph and User Accesses
$\begin{figure}\centerline{\shadowbox{\psfig{figure=figs/SiteGraph.eps,height=2.25in,width=5in}}} \vspace{-0.15in}\vspace{-0.15in}\end{figure}$

For specific instances of the FPM paradigm in web mining, consider the example in Figure 1, which pictorially depicts the original web graph of a particular website. There are 7 pages, forming the set of primitive items ${\cal I} = \{A, B, C,D, E, F, G\}$ , connected with hyperlinks. Now the LOGML document already stores in a systematic manner the user sessions, each of them being a subgraph of the web graph. The figure shows the pages visited by 6 users. We'll see below how this user browsing information can be used for mining different kinds of increasingly complex substructures, starting with the frequently accessed pages, to the frequently traversed paths, to the frequent subtrees, etc.

**Figure 2:** Frequent Set Mining
$\psfig{figure=figs/set.eps,height=1.75in,width=2.75in}$

**Figure 3:** Frequent Sequence Mining
$\psfig{figure=figs/seq2.eps,height=1.75in,width=3in}$

5.2.1 Frequent Sets

This is the well known association rule mining problem [1]. Here the database $\cal D$ is a collection of transactions, which are simply subsets of primitive items $\cal I$ . Each structure in the database is a transaction, and $\preceq$ denotes the subset relation. The mining task, then, is to discover all frequent subsets in $\cal D$ . These subsets are called itemsets in association mining literature.

Consider the example web logs database shown in Figure 2. For each user (in Figure 1) we only record the pages accessed by them, ignoring the path information. The mining task is to find all frequently accessed sets of pages. Figure 2 shows all the frequent k-itemsets ${\cal F}_k$ that are contained in at least three user transactions, i.e., $min\_sup = 3$ . ABC, AF and CF, are the maximal frequent itemsets.

We applied the Eclat association mining algorithm [28] to a real LOGML document from the RPI web site. There were 200 user sessions with an average of 56 distinct nodes in each session. It took us 0.03s to do the mining. An example frequent set found is shown below:

FREQUENCY = 22 , NODE IDS =  25854 5938 25649 25650 25310 16511
        http://www.cs.rpi.edu/~sibel/poetry/poems/nazim_hikmet/turkce.html
        http://www.cs.rpi.edu/~sibel/poetry/sair_listesi.html
        http://www.cs.rpi.edu/~sibel/poetry/frames/nazim_hikmet_1.html
        http://www.cs.rpi.edu/~sibel/poetry/frames/nazim_hikmet_2.html
        http://www.cs.rpi.edu/~sibel/poetry/links.html
        http://www.cs.rpi.edu/~sibel/poetry/nazim_hikmet.html

5.2.2 Frequent Sequences

The problem of mining sequences [2,8,27] can be stated as follows: An event is simply an itemset made up of the items $\cal I$ . A sequence is an ordered list of events. A sequence $\alpha$ is denoted as $(\alpha_1\rightarrow\alpha_2\rightarrow\cdots \rightarrow\alpha_q)$ , where $\alpha_i$ is an event; the symbol $\rightarrow$ denotes a ``happens-after'' relationship. We say $\alpha$ is a subsequence (not necessarily consecutive) of another sequence $\beta$ , denoted as $\alpha\preceq \beta$ , if $\alpha$ is completely contained within $\beta$ .

The structure database $\cal D$ consists of a collection of sequences, and $\preceq$ denotes the subsequence relation. The mining goal is to discover all frequent subsequences. For example, consider the sequence database shown in Figure 3, by storing all paths from the starting page to a leaf (note: there are other ways of constructing user access paths; this is just one example). With minimum support of 3 we find that $A\rightarrow B$ , $A\rightarrow C$ , $C\rightarrow F$ are the maximal frequent sequences.

We applied the SPADE sequence mining algorithm [29] to a real LOGML document from the RPI web site. From the 200 user sessions, we obtain 8208 maximal forward sequences, with an average sequence size of 2. It took us 0.09s to do the mining. An example frequent sequence found is shown below:

FREQUENCY = 21 , NODE IDS =  37668 -> 5944 -> 25649 -> 31409
        http://www.cs.rpi.edu/~sibel/poetry/ ->
        http://www.cs.rpi.edu/~sibel/poetry/translation.html ->
        http://www.cs.rpi.edu/~sibel/poetry/frames/nazim_hikmet_1.html ->
        http://www.cs.rpi.edu/~sibel/poetry/poems/nazim_hikmet/english.html

**Figure 4:** Frequent Tree Mining
$\psfig{figure=figs/tree.eps,height=1.75in,width=2.75in}$

**Figure 5:** A General Site Graph
$\psfig{figure=figs/fullgraph.eps,height=1.75in,width=2.75in}$

5.2.3 Frequent Trees

We denote an ordered, labeled tree as T = (V_t, E_t), where V_t is the vertex set, and E_t are the edges or branches. We say that a tree S = (V_s, E_s) is a subtree of T, denoted as $S\preceq T$ , if and only if $V_s \subseteq V_t$ , and for all edges $e=(v_1, v_2) \in E_s$ , v₁ is an ancestor or descendent of v₂. Note that this definition is different from the usual definition of a subtree. In our case, we require that for any branch that appears in S, the two vertices must be on the same path from a root to some leaf. For example, in Figure 1 the tree S, with $V = \{C, G\}$ and $E =\{CG\}$ is a subtree of the site graph.

Given a database $\cal D$ of trees (i.e., a forest) on the vertex set $\cal I$ , the frequent tree mining problem [30] is to find all subtrees that appear in at least min_sup trees. For example, given the user access subtrees shown in Figure 1, we mine the frequent subtrees shown in Figure 4. There are two maximal frequent subtrees, $(V=\{C, F\}, E=\{CF\})$ and $(V=\{A,B, C\}, E=\{AB, AC\})$ . We already have an initial implementation of TreeMiner [30], an algorithm for mining frequent trees. We will apply it to the LOGML database in near future. .

5.2.4 Other Generalizations

It is instructive to compare the patterns returned by the above three tasks from a common web logs database. We started by ignoring all link information to obtain frequent sets of pages. We then found the frequent paths, and finally the frequently traversed subtrees. These tasks were arranged according to increasing order of complexity (and thus execution time), but at the same time in increasing order of information conveyed to the user. For example, in frequent set mining, we only know that the pages A, B, and C were frequently accessed. Sequence mining gives us partial sequence information about the order in which pages are traversed, e.g., $A\rightarrow B$ .But in tree mining, we obtain full knowledge about the relationships between the three pages, i.e, A is the root with two children B and C. Note only can one mine such patterns, but it is relatively easy in our framework based on the LOGML document information to apply constraints on the patterns as well. For example, a web site analyst might want to know only those patterns that occur within a short time window, or those that occur after long gaps between accesses, etc. All this information can directly be extracted from the edge times in the user sessions.

There are many other generalizations that are possible. For example, we can generalize the tree mining problem to directed acyclic graphs, and more generally to directed and undirected graphs. Continuing the web mining example, a general website can be modeled as a directed graph, since in addition to the forward hyperlinks, it can have back references, creating cycles. Figure 5 shows an example web graph. Given a database of user accesses (with full information about their traversal, including forward and backward links) one can discover the frequently occurring subgraphs, such as the one shown.

6 Web Characterization

Web Characterization is concerned with the patterns found in the web structure and web usage. The Web Consortium created the Web Characterization Activity group whose main task was to measure new aspects of the web. XGMML and LOGML are the languages to describe web structure and usage. Several web characteristics of the web sites can be obtained by applying style sheets (XSLT ) to XGMML and LOGML documents. Example 5 shows a simple XSLT that can be applied to a LOGML file and obtain the number of the requests of the web pages of a web site.

Example 5

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
   <xsl:output method="text"/>

   <xsl:template match="/">
      <xsl:apply-templates select="logml"/>
   </xsl:template>

   <xsl:template match="logml">
      <xsl:apply-templates select="graph"/>
   </xsl:template>

   <xsl:template match="graph">
      <xsl:apply-templates select="node"/>
   </xsl:template>

   <xsl:template match="node">
         <xsl:value-of select="@id"/>
         <xsl:text>     </xsl:text>
         <xsl:value-of select="@hits"/>
         <xsl:text>     </xsl:text>
         <xsl:value-of select="@label"/>
         <xsl:text>
</xsl:text>
   </xsl:template>

</xsl:stylesheet>

Once that the number of requests of the web pages are obtained from the LOGML file, this information can be plotted in a line graph as shown in Figure 8.

Figure 8: Plot of the Top Request of the RPI Computer Science Web Site (http://www.cs.rpi.edu/)

Several web characterizations have been reported [12] such as: Requested file popularity, File sizes, Periodic nature of HTTP traffic, Site popularity, Rate of Broken Links, Session time outs. All of them can be extracted from the XGMML and LOGML files either by applying style sheets (XSLT) or by programs using DOM [4] or SAX XML parsers.

7 Conclusion

In this paper, we define two new XML languages, XGMML and LOGML and a web usage mining application. XGMML is a graph file description format. and an ideal candidate to describe the structure of web site. Furthermore XGMML is a container for meta-data information. LOGML is an extension of XGMML to collect web usage. LOGML is not only a preprocessor for data mining application, but also used for web characterization and for report generation.

Future work includes obtaining user graph mining, as well as visualization of mined data using WWWPal system[13]. To perform web content mining, we need keyword information and content for each of the nodes. To obtain this information will involve analyzing each of the web pages and collecting relevant keywords. Work is under way to accomplish this task.

References

[1] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri Verkamo. Fast discovery of association rules. In U. Fayyad and et al, editors, Advances in Knowledge Discovery and Data Mining, pages 307-328. AAAI Press, Menlo Park, CA, 1996.

[2] R. Agrawal and R. Srikant.Mining sequential patterns. In 11th Intl. Conf. on Data Engg., 1995.

[3] R. Cooley, B. Mobasher, and J. Srivastava. Web Mining: Information and Pattern Discovery on the World Wide Web. In 8th IEEE Intl. Conf. on Tools with AI, 1997.

[4] W3C, Document Object Model (DOM), http://www.w3.org/DOM/

[5] Dublin Core Metadata for Resource Discovery, Internet RFC 2413. http://purl.oclc.org/dc/

[6] M. Himsolt. GML: A portable Graph File Format, Technical Report, Universität Passau, 94030 Passau, Germany, 1997.

[7] LOGML, Log Markup Language Specification, http://www.cs.rpi.edu/~puninj/LOGML/draft-logml.html

[8] H. Mannila, H. Toivonen, and I. Verkamo. Discovering frequent episodes in sequences. In 1st Intl. Conf. Knowledge Discovery and Data Mining, 1995.

[9] B. Mobasher et al., Web Mining: Pattern Discovery from World Wide Web Transactions, Technical Report 96-050, Department of Computer Science, University of Minnesota, Minneapolis (September 1996).

[10] Namespaces in XML, http://www.w3.org/TR/REC-xml-names.

[11] P. Pirolli, R. Rao, and J. Pitkow, Silk from a Sow's Ear: Extracting Usable Structures from the Web. In Proceedings of 1996 Conference on Human Factors in Computing Systems, pp. 118-125, 1996.

[12] J. Pitkow, Summary of WWW Characterizations, In Proc. Seventh International World Wide Web Conference, Brisbane, Australia, April 14-18, 1998

[13] J. Punin, M. Krishnamoorthy. WWWPal System - A System for Analysis and Synthesis of Web Pages. In Proceedings of the WebNet 98 Conference, Orlando, November, 1998.

[14] W3C, Resource Description Framework (RDF) Model and Syntax Specification . http://www.w3.org/TR/REC-rdf-syntax

[15] R. Srikant and R. Agrawal. Mining generalized association rules. In 21st VLDB Conf., 1995.

[16] W3C, Scalable Vector Graphics (SVG) 1.0 Specification, http://www.w3.org/TR/SVG/

[17] M. Thuring, J. Hannemann, J.M Haake. Designing for Comprehension: A Cognitive Approach to Hypermedia Development. Communications of the ACM, 38(8), 57-66, 1995.

[18] W3C, Web Characterization Terminology & Definitions Sheet, http://www.w3.org/1999/05/WCA-terms/

[19] webbot and Libwww ,W3C Sample Code Library, http://www.w3.org/Library/

[20] Wu K.L, Yu P.S., and Ballman A. Speed Tracer: A Web usage mining and analysis tool. In Internet Computing Vol 37. No 1 p89, 1997.

[21] XGMML, Extensible Graph Markup and Modeling Language Specification, http://www.cs.rpi.edu/~puninj/XGMML/draft-xgmml.html

[22] W3C, XHTML[tm] 1.0: The Extensible HyperText Markup Language, http://www.w3.org/TR/xhtml1

[23] W3C, XML Linking Language (XLink), http://www.w3.org/TR/xlink

[24] W3C, XML Schema Part 1: Structures, http://www.w3.org/TR/xmlschema-1

[25] W3C, XML Specification, http://www.w3.org/TR/REC-xml

[26] W3C, XSL, Extensible Stylesheet Language Specification, http://www.w3.org/TR/xsl/

[27] M. J. Zaki. Efficient enumeration of frequent sequences. In 7th Intl. Conf. on Information and Knowledge Management, November 1998.

[28] M. J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3):372-390, May-June 2000.

[29] M. J. Zaki. SPADE: An efficient algorithm for mining frequent sequences. Machine Learning Journal, 42(1/2), Jan/Feb 2001. Special issue on Unsupervised Learning.

[30] M. J. Zaki, T. Bingol, and R. Kulkarni. TREEMINER: Mining trees in a forest. Technical Report 00-x, Computer Science Dept., Rensselaer Polytechnic Institute, in preparation 2000.