Data Mining: An Overview from a Database Perspective <s> Focusing methods <s> A very promising idea for fast searching in traditional and multimedia databases is to map objects into points in k-d space, using k feature-extraction functions, provided by a domain expert [25]. Thus, we can subsequently use highly fine-tuned spatial access methods (SAMs), to answer several types of queries, including the 'Query By Example' type (which translates to a range query); the 'all pairs' query (which translates to a spatial join [8]); the nearest-neighbor or best-match query, etc.However, designing feature extraction functions can be hard. It is relatively easier for a domain expert to assess the similarity/distance of two objects. Given only the distance information though, it is not obvious how to map objects into points.This is exactly the topic of this paper. We describe a fast algorithm to map objects into points in some k-dimensional space (k is user-defined), such that the dis-similarities are preserved. There are two benefits from this mapping: (a) efficient retrieval, in conjunction with a SAM, as discussed before and (b) visualization and data-mining: the objects can now be plotted as points in 2-d or 3-d space, revealing potential clusters, correlations among attributes and other regularities that data-mining is looking for.We introduce an older method from pattern recognition, namely, Multi-Dimensional Scaling (MDS) [51]; although unsuitable for indexing, we use it as yardstick for our method. Then, we propose a much faster algorithm to solve the problem in hand, while in addition it allows for indexing. Experiments on real and synthetic data indeed show that the proposed algorithm is significantly faster than MDS, (being linear, as opposed to quadratic, on the database size N), while it manages to preserve distances and the overall structure of the data-set. <s> BIB001 </s> Data Mining: An Overview from a Database Perspective <s> Focusing methods <s> We present a hierarchical algorithm, HierarchyScan, that efficiently locates one-dimensional subsequences within a collection of sequences of arbitrary length. The subsequences identified by HierarchyScan match a given template pattern in a scale- and phase-independent fashion. The idea is to perform correlation between the stored sequences and the template in the transformed domain hierarchically. Only those subsequences whose maximum correlation value is higher than a predefined threshold will be selected. The performance of this approach is compared to the sequential scanning and an order-of-magnitude speedup is observed. <s> BIB002
Ester et al.  ] pointed out some drawbacks of the CLARANS clustering algorithm 62] and proposed new techniques to improve its performance. First, CLARANS assumes that the objects to be clustered are all stored in main memory. This assumption may not be valid for large databases and disk-based methods could be required. This drawback is alleviated by integrating CLARANS with e cient spatial access methods, like R*-tree 11]. R*-tree supports the focusing techniques that Ester et al. proposed to reduce the cost of implementing CLARANS. Ester et al. showed that the most computationally expensive step of CLARANS is calculating the total distances between the two clusters. Thus, they proposed two approaches to reduce the cost of this step. The rst one is to reduce the number of objects considered. A centroid query returns the most central object of a leaf node of the R*-tree where neighboring points are stored. Only these objects are used to compute the medoids of the clusters. Thus, the number of objects taken for consideration is reduced. This technique is called focusing on representative objects. The drawback is that some objects, which may be better medoids, are not considered, but the sample is drawn in the way which still enables good quality of clustering. The other technique to reduce computation is to restrict the access to certain objects that do not actually contribute to the computation, with two di erent focusing techniques: focus on relevant clusters, and focus on a cluster. Using the R*-tree structure, computation can be performed only on pairs of objects that can improve the quality of clustering instead of checking all pairs of objects as in the CLARANS algorithm. Ester et al. applied the focusing on representative objects to a large protein database to nd a segmentation of protein surfaces so as to facilitate the so-called docking queries. They reported that when the focusing technique was used the e ectiveness (the average distance of the resulting clustering) decreased just from 1.5% to 3.2% whereas the e ciency (CPU time) increased by a factor of 50. where N is the number of points in the subcluster,LS is the linear sum on N points, i.e., P N i=1Xi , and SS is the square sum of data points, i.e., P N i=1Xi 2 . The Clustering Features are su cient for computing clusters and they constitute an e cient storage information method as they summarize information about the subclusters of points instead of storing all points. A CF tree is a balanced tree with two parameters: branching factor B and threshold T. The branching factor speci es the maximum number of children. The threshold parameter speci es the maximum diameter of subclusters stored at the leaf nodes. By changing the threshold value we can change the size of the tree. The non-leaf nodes are storing sums of their children's CFs, and thus, they summarize the information about their children. The CF tree is build dynamically as data points are inserted. Thus, the method is an incremental one. A point is inserted to the closest leaf entry (subcluster). If the diameter of the subcluster stored in the leaf node after insertion is larger than the threshold value, then, the leaf node and possibly other nodes are split. After the insertion of the new point, the information about it is passed towards the root of the tree. One can change the size of the CF tree by changing the threshold. If the size of the memory that is needed for storing the CF tree is larger than the size of the main memory, then a larger value of threshold is speci ed and the CF tree is rebuilt. The rebuild process is performed by building a new tree from the leaf nodes of the old tree. Thus, the process of rebuilding the tree is done without the necessity of reading all the points. Therefore, for building the tree, data has to be read just once. Some heuristics and methods are also introduced to deal with outliers and improve the quality of CF trees by additional scans of the data. 7 Pattern-based Similarity Search Next, we discuss data mining techniques based on pattern-based similarity search. When searching for similar patterns in a temporal or spatial-temporal database, two types of queries are usually encountered in various data mining operations: Object-relative similarity query (i.e., range query or similarity query) in which a search is performed on a collection of objects to nd the ones that are within a user-de ned distance from the queried object. All-pair similarity query (i.e., spatial join) where the objective is to nd all the pairs of elements that are within a user-speci ed distance from each other. Signi cant progress has recently been made in sequence matching for temporal databases   BIB001  BIB002  and for speech recognition techniques such as dynamic time warping 81]. Two types of similarity queries for temporal data have emerged thus far: whole matching 1] in which the target sequence and the sequences in the database have the same length; subsequence matching 29] in which the target sequence could be shorter than the sequences in the database and the match can occur at any arbitrary point. Various approaches proposed in the literature di er in the following aspects. The rst one is the similarity measure chosen. The second is whether the comparison is performed in time domain vs transformed domain. The third is the generality of the approach whether subsequence of arbitrary length, scaling and translation are allowed in the matching. Finally, di erent techniques have been explored to reduce the number of comparisons or search space during mining.