46289674
Applying On-line Bitmap Indexing to Reduce Counting Costs in Mining Association Rules
Abstract Counting costs have a great impact on efficiency of mining association rules in a large database of sales transactions. In this paper, we first formally analyze the facts that determine counting costs. Secondly, we present an on-line bitmap indexing technique to speed-up the counting process. Besides theoretical analysis, our implementation reports suggest that this indexing technique may reduce counting costs up to 50%, and almost at no costs.
17501980
Term Graph Model for Text Classification
Most existing text classification methods (and text mining methods at large) are based on representing the documents using the traditional vector space model. We argue that important information, such as the relationship among words, is lost. We propose a term graph model to represent not only the content of a document but also the relationship among the keywords. We demonstrate that the new model enables us to define new similarity functions, such as considering rank correlation based on PageRank-style algorithms, for the classification purpose. Our preliminary results show promising results of our new model.
4018890
Clustering Moving Objects for Spatio-temporal Selectivity Estimation
Many spatio-temporal applications involve managing and querying moving objects. In such an environment, predictive spatio-temporal queries become an important query class to be processed to capture the nature of moving objects. In this paper, we investigated the problem of selectivity estimation for predictive spatio-temporal queries. We propose a novel histogram technique based on a clustering paradigm. To avoid expensive computation costs, we developed linear time heuristics to construct such a histogram. Our performance study indicated that the new techniques improve the accuracy of the existing techniques by one order of magnitude.
6221918
Efficiently Matching Proximity Relationships in Spatial Databases
Spatial data mining recently emerges from a number of real applications, such as real-estate marketing, urban planning, weather forecasting, medical image analysis, road traffic accident analysis, etc. It demands for efficient solutions for many new, expensive, and complicated problems. In this paper, we investigate a proximity matching problem among clusters and features. The investigation involves proximity relationship measurement between clusters and features. We measure proximity in an average fashion to address possible nonuniform data distribution in a cluster. An efficient algorithm, for solving the problem, is proposed and evaluated. The algorithm applies a standard multistep paradigm in combining with novel lower and upper proximity bounds. The algorithm is implemented in several different modes. Our experiment results do not only give a comparison among them but also illustrate the efficiency of the algorithm.
14038708
Efficiently computing frequent tree-like topology patterns in a Web environment
Data mining has recently emerged in a number of real life applications, such as banking, supermarketing, and interneting. The authors investigate a novel data mining problem derived from the applications of WWW. They present an efficient algorithm for solving the problem. The initial implementation suggests that the algorithm is very efficient and scalable in practice.
1993887
Locating Motifs in Time-Series Data
Finding motifs in time-series is proposed to make clustering of time-series subsequences meaningful, because most existing algorithms of clustering time-series subsequences are reported meaningless in recent studies. The existing motif finding algorithms emphasize the efficiency at the expense of quality, in terms of the number of time-series subsequences in a motif and the total number of motifs found. In this paper, we formalize the problem as a continuous top-k motif balls problem in an m-dimensional space, and propose heuristic approaches that can significantly improve the quality of motifs with reasonable overhead, as shown in our experimental studies.
503545
Privacy-preserving clustering with distributed EM mixture modeling
Privacy and security considerations can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery can alleviate this problem. We present a technique that uses EM mixture modeling to perform clustering on distributed data. This method controls data sharing, preventing disclosure of individual data items or any results that can be traced to an individual site.
15723189
Impact of imperfect OCR on part-of-speech tagging
Part-of-speech (POS) tagging is the foundation of natural language processing (NLP) systems, and thus has been an active area of research for many years. However, one question remains unanswered: How will a POS tagger behave when the input text is not error-free? This issue can be of great importance when the text comes from imperfect sources like optical character recognition (OCR). This paper analyzes the performance of both individual POS taggers and combination systems on imperfect text. Experimental results show that a POS tagger's accuracy decreases linearly with the character error rate and the slope indicates a tagger's sensitivity to input text errors.
8724659
Estimating device availability in pervasive peer-to-peer environment
In pervasive computing environments, devices often communicate in a peer-to-peer manner, either for passing messages or collaboratively running applications. For any particular device, information about the availability of other devices can lead to more efficient communication and better execution of distributed tasks. For example, a device can distribute computation tasks to reliable devices and temporarily avoid unreliable ones. Since there usually is not a central server to coordinate or monitor the communication in such environment, a key technical challenge is for each individual device to predict the availability of other devices. In this paper, we describe some methods for predicting the availability of other devices using historic availability data of those devices obtained in routine usage. In this scheme, each device separately maintains data about the past communication with the other devices, and predicts current and future availability using the statistics of those data. These methods do not require any centralized monitoring or extra probing, and thus have very low computation cost. These characteristics make them suitable for small devices in a peer-to-peer environment.
16928019
Map Displays for Information Retrieval
The focus of this article is to develop a map display for to stack in the dark, without knowing what stacks that information retrieval. Through an examination of relawe have walked through. We can get a few books each tionships among visual displays, information retrieval, time and walk out of the library to see if the book we and browsing, advantages of visual displays for informaare searching for is among them. If not, we have to walk tion retrieval are characterized as (1) the ability to conin again, based on our knowledge and our previous experivey a large amount of information in a limited space, (2) the potential to reveal semantic relationships of terms ence, to a location where we hope the book would be. In and documents, and (3) the facilitation of browsing and this situation, success in finding a book greatly depends perceptual inferences on retrieval interfaces. These adon whether we can walk to the right place in the dark (to vantages are further demonstrated through a map disgenerate a good query), and whether we know how to play generated by a neural network’s self-organizing aladjust our locations until we get to the right place (to gorithm. The map display detects complex relationships among given documents, and reveals the relationships modify queries interactively) . through a spatial arrangement of terms abstracted from Can we turn on the light for such a library? Can we the documents. The map display also provides interdevelop some visible cues in our retrieval systems so that active tools to allow the user to interact with the underlywe can use our perception for information seeking in ing information. Examples of the map displays show that the digital environment? Answers to these questions may such map displays can be used both as an overview tool and an access or exploration tool, and the map displays reside in the recent advance of information technology. will likely increase the amount of information that the ‘‘Information processing has been evolving from numeriuser is willing to browse. cal computation to character handling, and now to visual information processing’’ (Kunii, 1989). As a result, visualization will become ‘‘the second computer revolution’’ Introduction (Friedhoff & Benzon, 1989). Computers are expected to be used to reveal associations and properties of electronic The world in which we live is a visual world. We look, information to allow people to use their visual capabilities we see, and we find things. Even for written information, for information seeking (Veith, 1988). we expect to see it on tangible media stored in visible locations. We have developed a whole set of perception This article discusses using some mapping techniques and association techniques to get what we need from the to create visual displays for textual information stored in environment. However, when we search information by the computer. The focus of the article is on the developcomputer, all the things, information, media, locations, ment of a map display for information retrieval. The map as well as their relationships, become invisible; all the display attempts to show both contents and semantic clues for visual perceptions and associations disappear. structures of a document space by mapping major conWe heavily rely on our competence to generate queries cepts and documents of a document space to a two-dimenand the computer’s ability to match the queries with inforsional map. It preserves, as faithfully as possible, documation stored in the computer. At best, when interaction ment semantic relationships and reveals these relationis involved, we can modify queries based on the retrieved ships through various visual components of the display. results of a previous query. This is like searching books By communicating a spatial metaphor to the user and in a library without light. We can walk around from stack making information in a document space graphically visible, the map display provides a visual guide to help the user perceive contents and structures of the document Received May 26, 1995; revised December 18, 1995; accepted Decemspace. ber 18, 1995. In the following, relationships among information retrieval, browsing, and visual displays are discussed first, q 1997 John Wiley & Sons, Inc.
8597703
Evaluation and Application of Recognition Confidence in OCR
Recognition confidence plays an important role in the selection of rejection threshold and the combination of multiple classifiers. In this paper, we first present a systematic theory on classifier's confidence, which includes the definition, the concept of generalized confidence, optimal rejection theorem and the relationship between confidence value and recognition rate. Then we propose a method for the evaluation of recognition confidence. The theory and method are strongly supported by the practice in handwritten numeral recognition and off-line handwritten Chinese character recognition.