46023466
Finding Interesting Associations without Support Pruning
Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar Web documents, clustering, and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide analysis of the algorithms developed and conduct experiments on real and synthetic data to obtain a comparative performance analysis.
2577694
Efficient acoustic index for music retrieval with various degrees of similarity
Content-based music retrieval research has mostly focused on symbolic data rather than acoustical data. Given that there are no general-purpose transcription algorithms that can convert acoustical data into musical scores, new methods are needed to do music retrieval on acoustical data. In this paper, we review some existing methods on contentbased music retrieval, discuss different definitions of music similarity, and present a new framework to perform music indexing and retrieval. The framework is based on an earlier prototype we developed, with significant improvements.In our framework known as MACSIS, each audio file is broken down into small segments and converted into feature vectors. All vectors are stored in a high-dimensional indexing structure called LSH, a probabilistic indexing scheme that makes use of multiple hashing instances in parallel. At retrieval time, small segments of audio matches are retrieved from the index and pieced together using the Hough Transform technique, and results are used as the basis to rank candidate matches.
1218659
Efficient discovery of error-tolerant frequent itemsets in high dimensions
We present a generalization of frequent itemsets allowing for the notion of errors in the itemset definition. We motivate the problem and present an efficient algorithm that identifies error-tolerant frequent clusters of items in transactional data (customer-purchase data, web browsing data, text, etc.). The algorithm exploits sparseness of the underlying data to find large groups of items that are correlated over database records (rows). The notion of transaction coverage allows us to extend the algorithm and view it as a fast clustering algorithm for discovering segments of similar transactions in binary sparse data. We evaluate the new algorithm on three real-world applications: clustering high-dimensional data, query selectivity estimation and collaborative filtering. Results show that the algorithm consistently uncovers structure in large sparse databases that other traditional clustering algorithms fail to find.
14199867
Peer-to-peer architecture for content-based music retrieval on acoustic data
In traditional peer-to-peer search networks, operations focus on properly labeled files such as music or video, and the actual search is often limited to text tags. The explosive growth of available multimedia documents in recent years calls for more flexible search capabilities, namely search by content. Most content-based search algorithms are computationally intensive, making them inappropriate for a peer-to-peer environment. In this paper, we discuss a content-based music retrieval algorithm that can be decomposed and parallelized efficiently. We present a peer-to-peer architecture for such a system that makes use of spare resources among subscribers, with protocols that dynamically redistribute load in order to maximize throughput and minimize inconvenience to subscribers. Our framework can be extended beyond the music retrieval domain and adapted to other scenarios where resource pooling is desired, as long as the underlying algorithm satisfies certain conditions.
6654135
Finding interesting associations without support pruning
Association rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of interest are relationships that occur very frequently. However, there are a number of applications, such as data mining, identification of similar Web documents, clustering and collaborative filtering, where the rules of interest have comparatively few instances in the data. In these cases, we must look for highly correlated items, or possibly even causal relationships between infrequent items. We develop a family of algorithms for solving this problem, employing a combination of random sampling and hashing techniques. We provide an analysis of the algorithms developed and conduct experiments on real and synthetic data to obtain a comparative performance analysis.
18362603
Apply cluster and grid computing on parallel 3D rendering
A cluster is a collection of independent and cheap machines, used together as a supercomputer to provide a solution. In this paper, a PC cluster consisting of one master node and nine disk-less slave nodes (10 processors), is proposed and built for parallel rendering purposes. The system architecture and benchmark performances of this cluster are also presented. Internet computing and grid technologies promise to change the way we tackle complex problems. They will enable large-scale aggregation and sharing of computational, data and other resources across institutional boundaries. Harnessing these new technologies effectively will transform scientific disciplines ranging from high-energy physics to the life sciences. Also, in this paper, we construct two heterogeneous PC clusters for parallel rendering purpose and install Linux Red Hat 9 on each PC cluster. Then, these clusters are set to the different subnet. Therefore, we use the grid middleware lambdaobus ToolKit, to connect these two clusters to form a grid computing environment on multiple Linux PC clusters. We also install the SUN Grid Engine, to manage and monitor incoming or outgoing computing jobs and schedule the job to achieve high performance computing and high CPU utilization. The system architecture and benchmark performances of this cluster are also presented
6473756
A vector space model for automatic indexing
In a document retrieval, or other pattern matching environment where stored entities (documents) are compared with each other or with incoming patterns (search requests), it appears that the best indexing (property) space is one where each entity lies as far away from the others as possible; in these circumstances the value of an indexing system may be expressible as a function of the density of the object space; in particular, retrieval performance may correlate inversely with space density. An approach based on space density computations is used to choose an optimum indexing vocabulary for a collection of documents. Typical evaluation results are shown, demonstating the usefulness of the model.
36980746
Decision tree construction for data mining on grid computing
Decision tree is one of the frequently used methods in data mining for searching prediction information. Due to its characteristics which are suitable for parallelism, it has been widely adopted in high performance field and developed into various parallel decision tree algorithms to deal with huge data and complex computation. Following the development of other technology fields, grid computing is regarded as the extension of PC cluster and therefore it future research development is highly valued. This new wave of Internet application is the 3rd generation of Internet applications following the traditional Internet and Web application. We have presented a grid-based decision tree architecture, and hope it can be applied on both parallel and sequential algorithms for the decision tree applications. Also, based on the scope and model of data mining applied in grid environment as well as user equivalent perspective, grid roles can be categorized into three types. We are hoping that through these definitions, software developers can define clear system processes and differentiate the application scope for software applications. To fulfil our architecture, we first apply an existing parallel decision tree algorithm-SPRINT algorithm in the grid environment. The performance and differences in many other areas are compared using different sizes of dataset. The experimental results are used for future reference and further development.
14357839
Clustering-training for Data Stream Mining
Mining data streams has attracted much attention recently. Labeled samples needed by most current stream classification methods are more difficult and expensive to obtain than unlabeled ones. This paper proposed a semi-supervised learning algorithm - clustering-training to utilize the unlabeled samples. It uses clustering to select confidently unlabeled samples, and uses them to re-train the classifier incrementally. Experiments on synthetic and real data set showed the effectiveness of the proposed algorithm
46320705
Intelligent Internet searching engine based on hybrid simulated annealing
The World Wide Web (WWW) based Internet services have become a major channel for information delivery. For the same reason, information overload also has become a serious problem to the users of such services. It has been estimated that the amount of information stored on the Internet doubled every 18 months. The speed of increase of home pages can be even faster, some people estimated that it doubled every six months. Therefore, a scalable approach to support Internet searching is critical to the success of Internet services and other current or future National Information Infrastructure (NII) applications. We discuss using a modified version of simulated annealing algorithm to develop an intelligent personal spider (agent), which is based on automatic textual analysis of the Internet documents and hybrid simulated annealing.