28335756
A template model for multidimensional inter-transactional association rules
Abstract. Multidimensional inter-transactional association rules extend the traditional association rules to describe more general associations among items with multiple properties across transactions. “After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away” is an example of such rules. Since the number of potential inter-transactional association rules tends to be extremely large, mining inter-transactional associations poses more challenges on efficient processing than mining traditional intra-transactional associations. In order to make such association rule mining truly practical and computationally tractable, in this study we present a template model to help users declare the interesting multidimensional inter-transactional associations to be mined. With the guidance of templates, several optimization techniques, i.e., joining, converging, and speeding, are devised to speed up the discovery of inter-transactional association rules. We show, through a series of experiments on both synthetic and real-life data sets, that these optimization techniques can yield significant performance benefits.
3420296
Parameter Free Bursty Events Detection in Text Streams
Text classification is a major data mining task. An advanced text classification technique is known as partially supervised text classification, which can build a text classifier using a small set of positive examples only. This leads to our curiosity whether it is possible to find a set of features that can be used to describe the positive examples. Therefore, users do not even need to specify a set of positive examples. As the first step, in this paper, we formalize it as a new problem, called hot bursty events detection, to detect bursty events from a text stream which is a sequence of chronologically ordered documents. Here, a bursty event is a set of bursty features, and is considered as a potential category to build a text classifier. It is important to know that the hot bursty events detection problem, we study in this paper, is different from TDT (topic detection and tracking) which attempts to cluster documents as events using clustering techniques. In other words, our focus is on detecting a set of bursty features for a bursty event. In this paper, we propose a new novel parameter free probabilistic approach, called feature-pivot clustering. Our main technique is to fully utilize the time information to determine a set of bursty features which may occur in different time windows. We detect bursty events based on the feature distributions. There is no need to tune or estimate any parameters. We conduct experiments using real life data, a major English newspaper Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005 in Hong Kong, and show that the parameter free feature-pivot clustering approach can detect the bursty events with a high success rate.
17946266
Reverse link capacity of SIR-based power-controlled CDMA systems with antenna arrays
SUMMARY In this paper, reverse link capacity, in terms of user capacity, of a code-division multiple access (CDMA) system with both beamforming and antenna diversity under a multipath environment is analyzed and compared. Signal-tointerference ratio (SIR) based power control is assumed in the system. Antenna elements are divided into several groups to achieve antenna diversity gain. Antenna elements in a group are closely spaced to perform beamforming in order to suppress the own-cell and other-cell interference, while those groups are widely spaced to achieve the diversity gain. Based on the comparison, a most efficient use of the antenna array according to the distribution of antenna elements among the groups is obtained. Instead of using tedious iterative methods to evaluate user capacity, a simple closed-form capacity expression with respect to antenna diversity and beamforming gains, a target SIR and the CDMA processing gain is derived. Numerical results indicate significant capacity improvement with the antenna array. Copyright # 2003 John Wiley & Sons, Ltd.
8043010
Low power network processor design using clock gating
Network processors (NPs) have emerged as successful platforms to providing both high performance and flexibility in building powerful routers. Typical NPs incorporate multiprocessing and multi-threading to achieve maximum parallel processing capabilities. We observed that under low incoming traffic rates, most processing elements (PEs) in NPs are nearly idle and yet still consume dynamic power. This paper develops a low power technique to reduce the activities of PEs according to the varying traffic volume. We propose to monitor the average number of idle threads in a time window, and gate off the clock network of unused PEs when a subset of PEs is enough to handle the network traffic. We show that our technique brings significant reduction in power consumption (up to 30%) of NPs with no packet loss and little impact to the overall throughput.
15858355
Asymptotics of Efficiency Loss in Competitive Market Mechanisms
We consider the loss of efficiency in competitive market mechanisms used to allocate network resources. We model large heterogeneous populations of users assuming that each user has a random utility function. We show that if the utility functions are bounded, the competitive equilibrium will be nearly as efficient as the social optimum with high probability as the number of users increases. This is the case for inelastic capacity as well as elastic capacity, under some standard assumptions. This result extends to a network setup where sources and destinations are picked at random. If, however, the utility functions are not bounded, then the loss of efficiency does not converge to zero. Collaborating simulations are also presented.
5943191
Reliability measurement: from theory to practice
The gap between theory and practice of reliability measurement in software design is discussed, and key issues that underlie reliability measurement's evolution from theory to practice are presented. A panel discussion in which reliability measurement's salient issues, basic concepts, and underlying theory are outlined is included. Reliability measurement's role in the development life cycle is also discussed.<<ETX>>
5051372
Processing queries by linear constraints
The emergence of several new application domains for databases has introduced the need for more efficient complex query handling than databases currently support. These application domains include On-Line AnalyticaIProcessing(OLAP), Geographical Information Systems (GIS), and scientific databases. This paper focuses attention on a form of selection query, expressible in SQL but not evaluated efficiently by current DBMSs, with wide applicability in these new problem domains. We introduce a processing strategy for this class of queries, which we call queries by linear constraints (QBLC). This processing strategy can be implemented with a wide variety of multidimensional indexing structures that include the R-?&ee variants, the k-d-B-pee, the Buddy-Tree, and many more. Note that any processing strategy meant for general database use must guarantee that all correct auswers are returned. Therefore, all numerical techniques we employ uphold &is guarantee. Thus the most distinguishing characteristic of this processing strategy is its safe handling of numerical error (which can result in the dismissal of valid answers). This paper presents several theoretical results about our processing strategy, and the results of several experiments which show that the processing cost of selection queries by linear constraints can be reduced dramatically by using our processing strategy. ‘This work was partially supported by a David and Lucile Packard Foundation Fellowship in Science and Engineering, a Presidential Young Investigator Award, NASA Research Grant NAGW-3921, and OFtD grant 144ET33. . . ., Permission to make digital/hard copies of aIt or part of this mate&l for persons1 or classmom use is grsnted without fee provided thst the copies are not made or distributed for profit or commerckd advulbge, &e copyd&t notice, the title ofthe publication and its d&e appear, and notice is given that WPyright is by permission ofthe ACM, Inc. To copy othe-rwise, to republish tc~ post on servers or to redistribute to I&, requires specific pen&ion and/or fee PODS ‘ 97 Tucson Arizona IJSA ~pyri&t 1997 ACM O-89791-910-6/97/05 ..$xso Raghu Ramakrishnan Computer Sciences Department University of Wisconsin-Madison 1210 W. Dayton St., Madison, WI 53706