Clustering Algorithms for Web-Based Data Mining Searches

Introduction and Significance of the Study

Clustering in algorithms employs abstract categories for pattern matching and pattern recognition procedures used in data mining searches of web documents. With the rapid advances in data mining software technology now taking place, website managers and search engine designers have begun to struggle to maintain efficiency in "mining" for patterns of information and user behavior. Part of the problem is the enormous amount of data being generated, making real-time search of web document databases difficult. Real-time searching is critical for real-time problem solving, high-level document searches, and prevention of database security breaches.

The analysis of this problem will be followed by a detailed description of weaknesses in data mining methods, with suggestions for a reduction of preprocessing to improve performance of search engine algorithms, and a recommendation of an optimum algorithm for this task.

The first investigators who gave serious thought to the problem of algorithm speed were researchers in the area of database searches. The field is still in its infancy; most of the tools and techniques used for data mining today come from related fields such as pattern recognition, statistics, and complexity theory. Only recently have researchers from these various fields been interacting to solve mining and timing issues.

Data mining is a knowledge discovery process that uses algorithms and advanced statistical models to analyze data in accordance with a set or sets of rules, as determined by the particular current application. Data mining methods may be classified according to the functions they perform, the class of application they are used in, or the domain of the search (e.g., the Internet is now a common domain for data mining searches). On the whole, data mining models fall into three basic categories: classification, associations and sequencing, and data clustering. "Clustering" assembles documents into related groups, or clusters, without relying on predefined categories. It essentially provides a visual map of the documents, with links between related documents, making it easy to browse through a collection, extracting multiple documents or a particular topic. The principal scholarly contribution of this study will be a refinement of the testing procedures for clustering algorithms, and a conclusion regarding the optimum algorithm for online real-time searches of web document databases.

The data mining process is inherently iterative: the output of one step may be sent as feedback to a previous step, as well as to the next step in the process. These steps are categorized into data pre-processing and discovered knowledge post-processing groupings. There are various techniques available to perform these tasks—classification, association, and clustering—the last of which is the focus of the present study. Data classification and association are appropriate to many data mining projects where pre-defined rules or concept categories exist, but many abstract problems require the creation of new abstract categories in order to provide the substructure for a more focused search. If the rule set is derived directly from the audit data, any slight deviations from the pattern scheme may go undetected; conversely, minor deviations from "normal behavior" can trigger false alarms. Abstract categories can mitigate this problem.

For this project design, the procedure calls for algorithms to be selected on the basis of the common feature of abstract categories for clustering data, for the purpose of classifying data according to a generic category scheme.

The principal components of the research design are the following:

The operating system (Windows XP); the laboratory computer (a generic PC of 2.0 gigahertz processing speed); the data structures (data clustering algorithms identifying abstract categories, where data is parsed by the algorithm to yield search results); the experimental procedure (testing of the algorithms for elapsed time); evaluation of results of the speed trials (time series analysis); and conclusions (analysis of the optimum algorithm designs and recommendations for research applications).

Class Description (Classification) — Summarization of a collection of data (class characterization). Class description includes summary properties such as count, sum, and average, as well as data dispersion measures such as variance and quartiles.

Association (Detection of Relations) — Association relationships or correlations among a set of items, expressed in rule form showing frequently occurring attribute-value conditions within a given data set. Association analysis is researched with efficient algorithms, including level-wise a priori search, mining multiple-level and multi-dimensional associations, mining associations for numerical, categorical, and interval data, meta-pattern directed or constraint-based mining, and mining correlations.

Clustering — Identifies embedded clusters in data, where a cluster is a collection of "similar" data objects as expressed by distance functions. Data mining research has focused on high-quality and scalable clustering methods for large databases and multi-dimensional data warehouses.

Time-Series Analysis — Analyzes large sets of time-series data, searching for similar sequences or sub-sequences and mining sequential patterns, periodicities, trends, and deviations.

The methodology employed in this project is experimental analysis, with the objective of testing the feasibility of abstract category data clustering algorithms for a real-world web application. In order to perform this test, a group of five linear-time clustering algorithms will be applied to a sample group of online web documents, simulating the activities of a web search engine looking for similar words, phrases, or sequences in a large database of web articles, publications, and records. The five techniques compared are K-Means, Single Pass, Fractionation, Buckshot, and Suffix Tree clustering algorithms.

The procedure is to measure the execution time of the test algorithms in clustering data sets consisting of whole documents, excerpts, and keywords of a fixed quantity and size. The tests are performed on a standard desktop personal computer running Microsoft Windows XP at a processing speed of at least 1 gigahertz, to simulate the real-world activities of a conventional office worker or librarian doing a document search. Times are recorded for a series of 10 tests repeated for the same group size and number of files, in order to determine the optimum clustering algorithm for real-time online web document searches.

The proposed design method is to conduct a speed trial analysis of the various designs currently used in search engine algorithms. The initial evaluation will be followed by an analysis of the weaknesses in current algorithms and suggestions for improvement. The study comprises five chapters: Introduction/Statement of Problem, Review of Literature, Alternative Solutions, Feasibility Tests, and Evaluation and Implementation. Future testing will be performed through the implementation of the selected algorithm in a regular application of web-based document searches by a librarian's search engine.

The purpose of this study is to conduct research that will analyze and improve the use of data clustering techniques in creating abstract categories in algorithms, allowing data analysts to conduct more efficient execution of large-scale searches. Increasing the efficiency of the search process requires detailed knowledge of abstract categories, pattern matching techniques, and their relationship to search engine speed.

Data mining involves the use of search engine algorithms looking for hidden predictive information, patterns, and correlations within large databases. The technique of data clustering divides datasets into mutually exclusive groups. The distance between groups is measured with respect to all available variables, versus variables that are specific predictors, to produce "abstract categories" for analysis. Search engine algorithms and user audit trails are complex, leading to time-consuming quests for specific information. It is anticipated that the proposed study will identify the most efficient and effective data clustering algorithms for this purpose.

The methodology employed is an empirical analysis of speed tests conducted on groups of similar algorithms. The execution time of the algorithms will be measured for clustering sets consisting of whole documents, excerpts, and keywords of a fixed number.

The distribution of all activity types in the search will be determined. Common features are identified within the system, and categories for clustering and classification are developed. At this stage, an abstract format or generic classification for the data can be developed, revealing how data are organized and where improvements are possible. Structural relationships within data can be revealed by such detailed analysis.

The final deliverable will be the search time trial results and the conclusions drawn with respect to the optimum algorithm designs. A definitive direction for the development of future design work is considered a desirable outcome.

Quality assurance will be implemented through systematic review of the experimental procedures and analysis of the test results. Achieving the goals stated at the delivery dates, performance of the tests, and successful completion of the project as determined by the committee members will provide quality assurance to the research outcomes.

Background and Review of Literature

Data clustering is a technique employed for the purpose of analyzing statistical data sets. Clustering is the classification of objects with similarities into different groups. This is accomplished by partitioning data into different groups, known as clusters, so that the elements in each cluster share some common trait, usually proximity according to a defined distance measure. Essentially, the goal of clustering is to identify distinct groups within a dataset, and then place the data within those groups according to their relationships with each other.

One of the main points of document clustering is that it is not so much a matter of finding the documents on the web — that is what search engines are for. A clustering algorithm is more concerned with how information is displayed: in what order results appear, what is considered relevant to the query, and what broad categories can be progressively narrowed. Search engines perform well when the user has a specific query and knows exactly what words will yield the desired results. However, the user is presented with a ranked list of questionable relevance, because the results include anything containing the queried word, and the only metric is the number of times that word appears in the document. With a good clustering program, the user is instead presented with multiple avenues of inquiry organized into broad groups that become more specific as selections are made.

Clustering exploits similarities between the documents to be clustered. The similarity of two documents is computed as a function of distance between the corresponding term vectors for those documents. Of the various measures used to compute this distance, the cosine measure has proved the most reliable and accurate. [10]

Data clustering algorithms come in two basic types: hierarchical and partitional. In partitional approaches, searches are matched against designated clusters, and the documents in the highest-scoring clusters are returned as results. When a hierarchy processes a query, it moves down the tree along the highest-scoring branches until it achieves the predetermined stopping condition. The sub-tree where the stopping condition is satisfied is then returned as the result of the search. Both strategies rely on variations of the near-neighbor search. In this search, nearness is determined by the similarity measure used to generate the clusters. Cluster search techniques are comparable to direct near-neighbor searches and are both evaluated in terms of precision and recall.

The evidence suggests that cluster search techniques are only slightly better than direct near-neighbor searches, and the former can even be less effective than the latter in certain circumstances. Because of the quadratic running times necessary, clustering algorithms are often slow and unsuitable for extremely large-volume tasks.

Hierarchical algorithms start with established clusters, then create new clusters based upon the relationships of the data within the set. They can do this in one of two ways: from the bottom up or from the top down. These two methods are known as agglomerative and divisive, respectively. Agglomerative algorithms start with the individual elements in the set as clusters, then merge them into successively larger clusters. Divisive algorithms start with the entire dataset in one cluster and then break it up into successively smaller clusters. Because hierarchical algorithms must analyze all the relationships inherent in the dataset, they tend to be costly in terms of time and processing power.

Partitional algorithms determine the clusters at one time, at the beginning of the clustering process. Once the clusters have been created, each element of the dataset is analyzed and placed within the cluster closest to it. Partitional algorithms run much faster than hierarchical ones, which allows them to be used in analyzing large datasets, but they have disadvantages as well. Generally, the initial choice of clusters is arbitrary and does not necessarily comprise all of the actual groups that exist within a dataset. Therefore, if a particular group is missed in the initial clustering decision, the members of that group will be placed within the clusters closest to them according to the predetermined parameters of the algorithm. In addition, partitional algorithms can yield inconsistent results — the clusters determined by the algorithm in one run will probably differ from those generated in the next run on the same dataset.

Of the five algorithms examined in this paper, two are hierarchical and three are partitional. The two hierarchical methods are suffix tree and single pass. The suffix tree is "a compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents." [1] It is a divisive method; it begins with the dataset as a whole and divides it into progressively smaller clusters, each composed of a node with suffixes branching off of it like leaves. Single-pass clustering, on the other hand, is an agglomerative, or bottom-up, method. It begins with a single cluster, and then analyzes each element in turn to determine whether it falls within a current cluster, or places it in a new cluster, depending on the similarity threshold set by the analyst.

The three partitional algorithms are K-Means, Buckshot, and Fractionation. K-Means derives its clusters based upon longest-distance calculations of the elements in the dataset, then assigns each element to the closest centroid. Buckshot partitioning starts with a random sampling of the dataset, then derives the centers by placing the other elements within the randomly chosen clusters. Fractionation is a more careful clustering algorithm that divides the dataset into smaller and smaller groups through successive iterations of the clustering subroutine. [2] Fractionation requires more processing power, and therefore more time.

Clustering is a methodology for more effective search and retrieval functions pertaining to datasets, and it has been investigated in great depth in the literature. The principle is straightforward — documents with a high degree of similarity will automatically be sought by the same query. By automatically placing documents in groups based upon similarity (i.e., clusters), the search is effectively broadened.

The Buckshot algorithm is simple in design and intent. It chooses a small random sampling of the documents in the database and then applies the cluster routine to them. The centers of the clusters generated by the subroutine are returned. This use of a rectangular time clustering algorithm makes the Buckshot method fast. The tradeoff is that Buckshot is not deterministic, since it initially relies on a random sampling process. Repeated use of this algorithm can return different clusters than previous searches, although it is maintained that repeated trials generate clusters similar in quality to the previous set. [2]

Fractionation algorithms find centers by initially breaking the corpus of documents into a set number of buckets of predetermined size. The cluster subroutine is then applied to each bucket individually, breaking the contents of the bucket into yet smaller groups within it. This process is repeated until a set number of groups is found, and these are the k centers. This method is analogous to building a branching tree from the bottom up, with leaves as individual documents and the centers (clusters) as the roots. The best fractionation methods sort the dataset based on a word index key (e.g., based on words in common between two documents).

It is important to note that both Buckshot and Fractionation rely on a clustering subroutine. Both algorithms are designed to find the initial centers but rely on a separate algorithm to do the actual clustering of individual documents. This subroutine can itself be agglomerative or divisive; however, in practice it tends to be an agglomerative hierarchical algorithm.

Buckshot applies the cluster subroutine to a random sampling of the dataset to determine the centers, while the Fractionation algorithm uses repeated applications of the subroutine over groups of fixed size in order to find the centers. Fractionation is considered more accurate, while Buckshot is much faster, making it more suitable for searching in real time on the web. [2]

After the centers have been determined, each algorithm proceeds to place the documents with their nearest center. After this step is completed, the resulting partitions are refined into better clusters, either by a simple move-to-nearest protocol or by techniques known as split (dividing a poorly defined cluster into two distinct groups) and join (merging two similar clusters). This step suffers from the same time and accuracy constraints as the initial centering — the more accurate join and split functions are much more time-consuming than move-to-nearest, but are much more reliable in their results.

One recent study has described a method of parallelizing the Buckshot algorithm for more efficient and speedy document clustering. [3] Parallel processing has been proven as an effective method of maintaining acceptable clustering times. Parallel processing has also been successfully applied to spherical K-Means partitioning as well as single-pass partitioning. [4, 5] In those cases, parallelizing the partitioning algorithm resulted in a near-linear speedup in processing time.

Fractionation has also been refined and improved since its creation. Another study used fractionation in a different way — instead of establishing the desired number of clusters initially, the number of clusters was determined by refining the meta-observations provided by the initial partitioning into buckets of equal size. [6] The study also introduced fractionation as a model-based hierarchy and applied a new derivative process called refractionation. Model-based fractionation goes beyond reliance on simple characterization of clusters through a mean, incorporating all important statistics including mean, covariance, and observations per cluster. Refractionation consists of repeated applications of fractionation, thereby refining the placement of groups and allowing for more accurate and reliable clustering.

The original K-Means algorithm presented by MacQueen (1967) has since been refined. [7] The new version can deal with ellipse-shaped data clusters as well as ball-shaped ones, and does not suffer from the dead-unit problem that plagued the earlier K-Means algorithm. In addition, the new K-Means algorithm performs proper clustering without pre-determining the exact cluster number. In experimental runs, it has proven to be both efficient and accurate.

Suffix trees were introduced in a paper by Zamir and Etzioni (1998). [8] Suffix Tree Clustering (STC) is an incremental algorithm that runs in linear time. Instead of treating a document as a collection of words, STC treats each document as a string. The string analogy allows the suffix tree to analyze relationships between word proximities from document to document. Documents are therefore grouped together by common phrases and words and delivered in the form of a suffix tree for ease of browsing. This results in a highly relevant hierarchy of documents.

Since the primary focus of this paper is on clustering as a means of searching the web, there are several important criteria to consider when evaluating algorithms for this purpose. [8]

Relevance: The method ought to produce clusters that group documents relevant to the user's query separately from irrelevant ones.

Browsable summaries: The user needs to determine at a glance whether a cluster's contents are of interest. The method must produce concise and accurate descriptions of the clusters so that the user is not merely replacing sifting through ranked lists with sifting through clusters.

Overlap: Since documents have multiple topics, it is important that documents not be confined to a single cluster.

Snippet-tolerance: The method ought to produce high-quality clusters even when it only has access to the snippets returned by the search engine, as most users are unwilling to wait for original documents to be downloaded from the web.

Speed: A patient user might sift through 100 ranked documents in a set of returned results. Clustering should allow the user to browse through at least an order of magnitude more documents. Therefore the clustering method ought to be able to cluster up to one thousand snippets in a few seconds.

Incrementality: To save time, the method should start to process each snippet as it is received from the web.

Agglomerative Hierarchical Clustering (AHC) algorithms are generally slow. Within this classification, single-link and group-average methods are faster than complete-link methods, but in either case the slow running times preclude their practicality in large-scale web searches. One of the hindrances to AHC methods is the halting criteria of the algorithm, which are generally based upon predetermined constants. When searching the web, the variability and diversity of documents makes sensitivity to halting criteria a hindrance, often resulting in poor accuracy of retrieved information.

Algorithms that run in linear time are the ones most likely to meet the speed requirements inherent in searching the web. Since this requirement is core to the principle of the paper, all the algorithms chosen for this study run in linear time.

K-Means algorithms have an important advantage — unlike AHC methods, K-Means can place documents in multiple clusters, thereby allowing for overlap between document topics. The main drawback to K-Means is that the best results are achieved when the desired clusters are spherical when considered in relation to the similarity measure in use. [8] The algorithm does not deal well with data in other shapes, such as ellipticals.

Single Pass suffers from the same disadvantage concerning spherical data and the similarity measure as K-Means. In addition, it is order-dependent and prone to producing large clusters, which would in turn need to be clustered again, slowing down processing speed. [8]

Buckshot and Fractionation are fast, linear-time operating algorithms first introduced by Cutting et al. (1992) as part of a method described as Scatter/Gather. Fractionation is capable of approximating the method of the AHC — however, instead of the search being global, it is locally bounded. It suffers from the same downfall as the AHC in that the predetermined halting criteria can corrupt the precision of the search, and it also does not perform well in areas with many outliers. [8]

Buckshot is a permutation of the K-Means algorithm that draws an initial sampling of the data and then builds clusters around the sampled documents. This method can miss small clusters, as the random sampling may not be representative of smaller groups within the dataset. Also, like Fractionation, Buckshot is not incremental. [8]

Of the five algorithms under scrutiny, the only one that treats a document as a string is the Suffix Tree. The other four treat each document as a collection of disjointed words, meaning the order of words has no importance. This causes a considerable amount of important information to be lost in the search process. Phrases have been used to supplement word-based indexing in information retrieval projects. Lexical atoms and syntactic phrases have been shown to improve accuracy without a corresponding cost in recall. Simple statistical approaches have also been used successfully to generate phrases. [8]

Suffix Tree Clustering is a linear-time clustering algorithm based on identifying documents and grouping them by phrases that the documents in the set have in common. The algorithm recognizes a phrase as an ordered sequence of one or more words. A base cluster is defined as a set of documents that contain the same phrase. [8]

STC is organized into three logical steps. The first step is document cleaning, where a light stemming algorithm is used to reduce prefixes and suffixes, convert plural forms to singular, and strip non-word tokens such as numbers and symbols. The original document strings are preserved so that the full document can be displayed on command. The second step is to identify the base clusters, which is equated with creating an inverted index of phrases for the document collection. This results in the Suffix Tree (first introduced by Zamir et al., 1997), a data structure that can be constructed in time linear to the number of documents in the dataset and can also be constructed incrementally as documents are being read. The third step is to combine base clusters that have many similarities between their respective sets. Since documents can have multiple phrases in common, it is imperative for the algorithm to recognize nearly identical clusters and merge them to prevent a proliferation of redundant clusters. This step is accomplished by merging clusters that have a high level of overlap.

Five defining characteristics of suffix trees [8]: A suffix tree is a rooted, directed tree. Each internal node has at least two children. Each edge is labeled with a non-empty substring of the document collection. The label of a node is defined as the concatenation of the edge-labels on the path from the root to the node. No two edges out of the same node can have edge-labels that begin with the same word. For each suffix of the document collection, there exists a suffix node whose label equals that suffix.

Each node of a suffix tree consists of the documents connected to that node and the phrase they have in common. The label of the node is represented by the common phrase, and the descendants of the suffix node are comprised of the documents that contain the labeling phrase. All base clusters are nodes and are represented as such on the suffix tree. [8]

The Suffix Tree algorithm is incremental. Each document is read, cleaned, and then inserted into the appropriate base cluster, or placed in a newly created cluster if the similarity threshold is exceeded. Then each base cluster is recalculated and redistributed according to the same principles of similarity.

The final clusters created by the STC method are scored and sorted by the scores of their base clusters and the amount of overlap. Each cluster is then displayed according to the number of documents it contains and the phrases of the base clusters.

The STC algorithm does not require the user to specify the number of clusters before the search — the clusters are produced incrementally according to the dictates of the algorithm. It does require specification of the similarity threshold. STC has a markedly less sensitive response to the similarity threshold compared to AHC methods. In this way, STC is much more forgiving with respect to the initial specifications of the search.

Data clustering algorithms are designed to address one or more problematic factors, such as high dimensionality, efficiency, scalability with data size, sensitivity to noise in the data, and identification of clusters in various shapes. K-Means and other partitioning methods can result in the breakup of genuine clusters. Hierarchical approaches fail to handle convex and elongated cluster shapes. Density-based algorithms are extremely sensitive to noise in the data. [9]

The need for input parameters is the most pressing problem in clustering methods. Many algorithms, especially hierarchical ones, require the number of clusters to be arbitrarily selected at the beginning of the process. Even when this is not the case, the parameters of the algorithm can greatly influence the outcome of the process.

Parameters are considered beneficial in some cases, such as when they provide a means to incorporate domain knowledge into the clustering process. This is especially true when the number of clusters is preselected and fixed. However, in many cases the optimal values for the parameters are far from clear and must be arrived at by the tiresome process of trial and error. In cases where the number of dimensions is greater than three, this results in an inordinate amount of time on the part of the user, thus inviting the use of an automated process. Domain knowledge can be represented by the definition of similarity functions that measure the degree of similarity between data points for the purpose of clustering them. [9]

The basic idea of partitioning is intuitive in nature, and the process of partitioning generally seeks to achieve optimal performance through iterative means. All partitioning methods have comparable clustering qualities. The major difficulties of these methods are: the number of clusters to be found must be specified before the process (requiring at least some domain knowledge beforehand, which is often unavailable); difficulty in determining clusters with a large variance in size; and the fact that the method is only suitable for concave clusters. [9] A hierarchical clustering algorithm produces a dendrogram representing the nested grouping relationship of objects in the dataset.

The main distinguishing characteristic among hierarchical approaches is the measure of similarity between individual clusters and the underlying modeling of those clusters. These algorithms are costly in terms of time and computational power, so many are initiated with a sampling of the dataset that is then clustered. This leaves the end results as a direct function of the initial sampling. While this helps with computational speed, if there are many small clusters within the dataset, the sampling is likely to miss them. [9]

Dennis et al. [10] placed current web searching technology into four broad classifications: Unassisted keyword search, in which one or more search terms are entered and the search engine returns a ranked list of document summaries (e.g., Google or AltaVista); Assisted keyword search, in which the search engine produces results based on the user's initial inquiry (e.g., Vivisimo); Directory-based search, in which the information space is divided into a hierarchy of categories and the user navigates from broad to specific classes (e.g., Yahoo); and Query-by-example, in which the user selects an interesting document snippet, which is then used as the basis for a new query.

Meyer zu Eissen and Stein specify the major criteria for a successful search engine. [10] The ideal search engine process has three stages: first, an initialization phase based on the plain unassisted keyword search paradigm; second, a categorization phase similar to the directory-based search paradigm; and third, a refinement phase that may combine aspects of assisted keyword search and the query-by-example paradigm.

Documents are commonly represented as vector space models. In this model, each document is represented by a point in space that roughly corresponds with the union of the primary words in the document. The process includes filtering out common words (such as pronouns and conjunctions), ignoring words unique to the document, and stemming words to reduce them to canonical form. Once this is done, the document can be expressed as vectors, which are then used to plot a point in virtual space representing that specific document. The words of the document are also weighted; without this provision, the more commonly a word appears in a document, the more important it is considered — which is often not actually the case. Conversely, words that appear infrequently in a document are considered discriminatory, serving as a distinguishing feature for that document. [10]

As shown in the work of Zamir et al. [8], the feasibility of searching web results is heavily influenced by the ability to preserve accuracy when clustering based only upon the snippets returned to a search engine. Their results found that almost the same accuracy was present when using snippets only as opposed to the whole document. This alleviates the need for the computer to download the entire document for the express purpose of measuring similarities with other documents. In general, each algorithm was slightly more accurate when using the entire document, but the accuracy achieved with snippets was much higher than expected. In the case of the K-Means algorithm, it actually performed better using snippets instead of the whole document.

The facts revealed in the literature review can be summarized in a few key points. Data clustering is an essential step in making web-based searches more user-friendly and productive. Data clustering operates by attempting to measure how alike documents are and then sorting them into groups based upon content. The more accurate a clustering algorithm is, the slower it works, because it must examine more relationships in greater detail. There are many different algorithms to choose from; this study encompasses a review of five of the most successful and popular clustering algorithms.

K-Means clustering is a partitional algorithm that works in linear time. It calculates the centers to be used in clustering through an analysis of maximum distance relationships between documents in the dataset. Single Pass clustering is an incremental algorithm that develops its clusters through calculations based upon the vector differences ascribed to the documents in the dataset. Buckshot is a clustering method that takes a random sampling of documents to use as the centers. Fractionation is an algorithm that divides the entire dataset into fixed-size buckets that are each clustered by the clustering subroutine, and then the clusters are merged or split according to similarity. Suffix Tree Clustering is a hierarchical algorithm that runs in linear time and provides an intuitive browsing platform in the form of the suffix tree.