waashk/dblp huggingface dataset:
forest trees for on-line data. this paper presents an hybrid adaptive system for induction of forest of trees from data streams. the ultra fast forest tree system (ufft) is an incremental algorithm, with constant time for processing each example, works online, and uses the hoeffding bound to decide when to install a splitting test in a leaf leading to a decision node. our system has been designed for continuous data. it uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. the number of examples required to evaluate the splitting criteria is sound, based on the hoeffding bound. for multiclass problems, the algorithm builds a binary tree for each possible pair of classes, leading to a forest of trees. during the training phase the algorithm maintains a short term memory. given a data stream, a fixed number of the most recent examples are maintained in a data-structure that supports constant time insertion and deletion. when a test is installed, a leaf is transformed into a decision node with two descendant leaves. the sufficient statistics of these leaves are initialized with the examples in the short term memory that will fall at these leaves. we study the behavior of ufft in different problems. the experimental results shows that ufft is competitive against a batch decision tree learner in large and medium datasets.
learning decision trees from dynamic data streams. this paper presents a system for induction of forest of functional trees from data streams able to detect concept drift. the ultra fast forest of trees (ufft) is an incremental algorithm, that works online, processing each example in constant time, and performing a single scan over the training examples. it uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. for multi-class problems the algorithm grows a binary tree for each possible pair of classes, leading to a forest of trees. decision nodes and leaves contain naive-bayes classifiers playing different roles during the induction process. naive-bayes in leaves are used to classify test examples, naive-bayes in inner nodes can be used as multivariate splitting-tests if chosen by the splitting criteria, and used to detect drift in the distribution of the examples that traverse the node. when a drift is detected, all the sub-tree rooted at that node will be pruned. the use of naive-bayes classifiers at leaves to classify test examples, the use of splitting-tests based on the outcome of naive-bayes, and the use of naive-bayes classifiers at decision nodes to detect drift are directly obtained from the sufficient statistics required to compute the splitting criteria, without no additional computations. this aspect is a main advantage in the context of high-speed data streams. this methodology was tested with artificial and real-world data sets. the experimental results show a very good performance in comparison to a batch decision tree learner, and high capacity to detect and react to drift.
discretization from data streams: applications to histograms and data mining. in this paper we propose a new method to perform incremental discretization. the basic idea is to perform the task in two layers. the first layer receives the sequence of input data and keeps some statistics on the data using many more intervals than required. based on the statistics stored by the first layer, the second layer creates the final discretization. the proposed architecture processes streaming examples in a single scan, in constant time and space even for infinite sequences of examples. we experimentally demonstrate that incremental discretization is able to maintain the performance of learning algorithms in comparison to a batch discretization. the proposed method is much more appropriate in incremental learning, and in problems where data flows continuously, as in most of the recent data mining applications.
semi-supervised outlier detection. outlier detection has been extensively researched in the context of unsupervised learning. but the learning results are not always satisfactory, which can be significantly improved using supervision of some labeled points. in this paper, we are concerned with employing supervision of limited amount of label information to detect outliers more accurately. the key of our approach is an objective function that punishes poor clustering results and deviation from known labels as well as restricts the number of outliers. the outliers can be found as a solution to the discrete optimization problem regarding the objective function. by this way, this method can detect meaningful outliers that can not be identified by existing unsupervised methods.
location dependent query proxy. in a mobile environment, the result of queries often depends on the client's location. these queries are called location dependent queries (ldq). applying the concept of caching to ldqs provides a means for efficient processing when queries exhibit both semantic similarity and spatial locality. existing ldq caching schemes require database (db) servers to provide validity regions (vr) for ldq results, which introduces significant processing and/or storage overhead. as a result, db servers may only provide the validity information conditionally or do not provide it at all. we propose a novel ldq proxy scheme that can estimate the vr if db servers do not provide such information. the simulation results show that the ldq proxy reduces both the ldq response time and the database workload.
editorial message: technical track on geometric computing and reasoning. geometric computing and reasoning (gcr) is a new track of sac and it is dedicated to the recent trends in the domain of geometric constraint solving and automated, or computer aided, deduction in geometry.
quality-driven evaluation of trigger conditions on streaming time series. for many applications, it is important to evaluate trigger conditions on time series streams. in a resource constrained environment, users' needs should ultimately decide how the evaluation system balances the competing factors such as evaluation speed, result precision, and load shedding level. this paper presents a basic framework for evaluation algorithms that takes user-specified quality requirements into consideration. three optimization algorithms, each under a different set of quality requirements, are developed in the framework: (1) minimize the response time given accuracy requirements and without load shedding; (2) minimize the load shedding given a response time limit and accuracy requirements; and (3) minimize one type of accuracy errors given a response time limit and without load shedding. experiments show that these optimization algorithms effectively achieve their optimization goals while satisfying the corresponding user-specified quality requirements.
analysis of distributed routing balancing behavior. distributed routing balancing (drb) is a method developed to uniformly balance communication traffic over the interconnection network. drb takes a similar approach to communications as load balancing does to processes in a distributed environment. the key ideas behind drb are to distribute communication load based on limited and load-controlled path expansion, in order to maintain low message latency. in this paper, we present an exhaustive evaluation of drb that shows that the method presents low overhead and is robust with respect to the accuracy of the monitoring information it uses, and we compare its latency performance against other state-of-the-art routing methods.
concurrency control for distributed cooperative engineering applications. distributed cooperative engineering applications require consistent and long-term sharing of large volumes of data, which may cause conflicts due to concurrent read/write operations. therefore designing concurrency control for underlying middleware systems is a difficult issue.current transactional solutions, even if based on an optimistic approach, do not solve the problem because such applications access shared data for long periods of time performing a large number of read/write operations. typically, a large set of modifications has to be discarded and this is unacceptable given the amount of work lost.in this paper, we describe the design and implementation of concurrency control mechanisms aimed at both reducing the amount of such conflicts and supporting the consistent long-term sharing of data. the mechanism of visibility depth allows the programmer to specify the consistency of shared data w.r.t. different sets of sites. we also provide other mechanisms: private-copy that allows data to be read/written without being considered as part of a transaction and reordering transaction history to avoid transaction aborts. we evaluate these techniques on a prototypical middleware system called perdis and show that: (i) the concurrency control mechanisms are well adapted to support long-lived data sharing in local or wide-area networks, and (ii) performance is acceptable.
evaluating the use of profiling by a region-based register allocator. in a region-based compilation framework, the compiler builds regions to provide the best compilation unit for scheduling and optimization. the compiler uses execution frequency information gained from profiling to place frequently executed blocks in the same region. this paper investigates the use of profiling in a region-based compilation framework and measures its impact on the register allocation phase. the profiling information can be used by the register allocator to assign values to physical registers based on the execution frequency of the regions. register allocation can be performed on the most frequently executed regions first so that any spilling that occurs causes memory accesses in less frequently executed regions. the experimental study indicates that profile assisted region formation and register allocation can result in code that executes faster than the code that was compiled without using profiling information and the amount of spill code executed can be reduced significantly.
delay-based circuit authentication and applications. we describe a technique to reliably identify individual integrated circuits (ics), based on a prior delay characterization of the ic.we describe a circuit architecture for a key card for which authentication is delay based, rather than based on a digital secret key. we argue that key cards built in this fashion are resistant to many known kinds of attacks.since the delay of ics can vary with environmental conditions such as temperature, we develop compensation schemes and show experimentally that reliable authentication can be performed in the presence of significant environmental variations.the delay information that is extracted from the ic can also be used to generate keys for use in classical cryptographic primitives. applications that rely on these keys for security would be less vulnerable to physical attack.
incorporating fuzziness in xml and mapping fuzzy relational data into fuzzy xml. in this paper, we present an approach for incorporating fuzzy and imprecise data in xml documents. we describe the ways to introduce fuzziness using both possibility theory and similarity relations. we then show how to map the data from a fuzzy relational database into a fuzzy xml document, with the corresponding xml schema. this approach will aid in liberating the data stored in fuzzy relational databases onto the web as fuzzy xml documents.
modeling of component-based adaptive distributed applications. a challenge in distributed system design is to cope with the dynamic nature of the execution environment. in this paper, we present an approach for modeling adaptation of component based distributed applications. the approach supports component-based design of different variants of the applications, and a framework for selecting proper variants based on the current state of the execution environment and the user preferences. xml is used as the specification language. transformation of the xml based design specifications to programming languages like java is also discussed.
a framework for data mining and kdd. the kdd process is a non-trivial, iterative, interactive and multi-step process, that requires the development of a unifying model. this model have to ensure an uniform description of data and patterns and the control of the manipulation of the data and patterns. thus, the model defines operations within the pattern and data, as well as transition operations between data and patterns.this paper proposes a framework consisting of a model view, a data view and a process view. it focuses on the model and data view. the model view contains a set of mining models, which contain all information of a data mining result, that are based on constraints. the proposed model algebra uses concepts of constraint databases as well as collective and parallel data mining. the whole process is supported by using operations between data and model view.
an initial investigation of test driven development in industry. test driven development (tdd) is a software development practice in which unit test cases are incrementally written prior to code implementation. in our research, we ran a set of structured experiments with 24 professional pair programmers. one group developed code using tdd while the other a waterfall-like approach. both groups developed a small java program. we found that the tdd developers produced higher quality code, which passed 18% more functional black box test cases. however, tdd developer pairs took 16% more time for development. a moderate correlation between time spent and the resulting quality was established upon analysis. it is conjectured that the resulting high quality of code written using the tdd practice may be due to the granularity of tdd, which may encourage more frequent and tighter verification and validation. lastly, the programmers which followed a waterfall-like process often did not write the required automated test cases after completing their code, which might be indicative of the tendency among practitioners toward inadequate testing. this observation supports that tdd has the potential of increasing the level of testing in the industry as testing as an integral part of code development.
combining state and model-based approaches for mobile agent load balancing. an approach for dynamic load balancing of mobile agents is described. we demonstrate this approach for a multi-agent system operating on an active digital library composed of multi-spectral images of the earth, as part of the synthetic aperture radar atlas (sara)[25]. in the proposed architecture specialized stationary agents are used to gather system state information and make decisions on the distribution of mobile agents among the servers. our approach is based on a combination of a state and model-based approaches to load balancing.
a scalable algorithm for high-quality clustering of web snippets. we consider the problem of partitioning, in a highly accurate and highly efficient way, a set of n documents lying in a metric space into k non-overlapping clusters. we augment the well-known furthest-point-first algorithm for k-center clustering in metric spaces with a filtering scheme based on the triangular inequality. we apply this algorithm to web snippet clustering, comparing it against strong baselines consisting of recent, fast variants of the classical k-means iterative algorithm. our main conclusion is that our method attains solutions of better or comparable accuracy, and does this within a fraction of the time required by the baselines. our algorithm is thus valuable when, as in web snippet clustering, either the real-time nature of the task or the large amount of data make the poorly scalable, traditional clustering methods unsuitable.
an information theoretic histogram for single dimensional selectivity estimation. we study the problem of one dimensional selectivity estimation in relational databases. we introduce a new type of histogram based on information theory. we compare our histogram against a large number of other techniques and on a wide array of datasets. we observe our histograms to have the overall best accuracy on the real datasets. we also observe that the accuracy ranking of all methods varies significantly across datasets. as such, we observe results not consistent with several conclusions drawn in past literature. thus, we believe a gap exists in the past accuracy characterization.
high performance xsl-fo rendering for variable data printing. high volume print jobs are getting more common due to the growing demand for personalized documents. in this context, variable data printing (vdp) has become a useful tool for marketers who need to customize messages for each customer in promotion materials or marketing campaigns. vdp allows the creation of documents based on a template with variable and static portions. the rendering engine must be capable of transforming the variable portion into a resulting composed format, or pdl (page description language) such as pdf, ps or svg. the amount of variable content in a document is dependant on the publication layout. in addition, the features and the amount of the content to be rendered may vary according to the data loaded from the database. therefore, the rendering process is invoked repeatedly and it can quickly become a bottleneck, especially in a production environment, compromising the entire document generation. in this scenario, high performance techniques appear to be an interesting alternative to increase the rendering phase throughput. this paper introduces a portable and scalable parallel solution for the apache's rendering tool fop (formatting objects processor) which is used to render variable content expressed in xsl-fo (extensible stylesheet language-formatting objects). xsl-fo is extracted from a print job expressed in ppml (personalized print markup language), which is, in turn, obtained by the merging variable data in a template. the vdp template is expressed using ppml/t (personalized print markup language template).
mining sequences with temporal annotations. in this paper we propose an extension of the sequence mining paradigm to (temporally-)annotated sequential patterns, where each transition in a sequential pattern is annotated with a typical transition time derived from the source data. then, we present a basic solution for the novel mining problem based on the combination of sequential pattern mining and clustering, and assess this solution on two realistic datasets, illustrating how potentially useful patterns of the new form are extracted.
challenges in the compilation of a domain specific language for dynamic programming. many combinatorial optimization problems in biosequence analysis are solved via dynamic programming. to increase programming productivity and program reliability, a domain specific language embedded in haskell has been suggested. we point out several shortcomings of this approach, and report on some challenges in the (ongoing) project of migrating this domain specific language from its host language to a directly compiled implementation. most of these challenges are domain specific optimizations, which not only improve significant constant factors of runtime and space requirements, but also affect asymptotic efficiency. we report on our solutions to some of these problems, and point out others that are still open.
dynamic service discovery and mediation in the insurance industry. businesses today are facing increasing pressure to innovate and deliver more value to their customers and partners. unfortunately, hard-wired, silo-based it applications and infrastructures are aging and inflexible, making it very difficult, expensive and time consuming to modify business practices and processes. service oriented architecture (soa) has addressed many of these issues, but still has major shortcoming with regard to data mediation and service selection.
multiclass text categorization for automated survey coding. survey coding is the task of assigning a symbolic code from a predefined set of such codes to the answer given in response to an open-ended question in a questionnaire (aka survey). we formulate the problem of automated survey coding as a text categorization problem, i.e. as the problem of learning, by means of supervised machine learning techniques, a model of the association between answers and codes from a training set of pre-coded answers, and applying the resulting model to the classification of new answers. in this paper we experiment with two different learning techniques, one based on na&iuml;millve bayesian classification and the other one based on multiclass support vector machines, and test the resulting framework on a corpus of social surveys. the results we have obtained significantly outperform the results achieved by previous automated survey coding approaches.
an efficient data structure for decision rules discovery. the increasing amount of information available is encouraging the search for efficient techniques to improve the data mining methods, especially those which consume great computational resources. we present a novel structure, called ees, which helps the data mining algorithms which generate decision rules to reduce the aforementioned cost. given that decision rules establish conditions for database attributes, ees stores the information in such a way that the search can be carried out by attributes instead of by examples. ees could be useful for any method which generates decision rules. moreover, it is of particular interest when the search for the solution involves a great many hypothetical solutions. thus, this structure is designed for speeding up the rule-evaluation process in methods based on evolutionary algorithms. the traditional structure, based on vectors of examples (in which the database is stored) is evaluated and compared with ees, including the costs for a stratified set of cases. finally, the experimental results demonstrate the quality of our proposal, reducing the computational cost by approximately 50%.
memory issues in frequent itemset mining. during the past decade, many algorithms have been proposed to solve the frequent itemset mining problem, i.e. find all sets of items that frequently occur together in a given database of transactions. although very efficient techniques have been presented, they still suffer from the same problem. that is, they are all inherently dependent on the amount of main memory available. moreover, if this amount is not enough, the presented techniques are simply not applicable anymore, or significantly need to pay in performance. in this paper, we give a rigorous comparison between current state of the art techniques and present a new and simple technique, based on sorting the transaction database, resulting in a sometimes more efficient algorithm for frequent itemset mining using less memory.
developing the extended enterprise with the fadee. in realizing business-to-business integration, much communication among persons with different backgrounds is needed. we affirm that enterprise architecture descriptions are an important part of the necessary communication in information systems development and maintenance. this article is about categorizing the models that describe business-to-business integration (b2bi) practices, and identifying the numerous ways b2bi issues could and should be described. the framework we propose is based on lessons learnt from proven architecture description frameworks. the zachman framework forms the basis of the framework for the architectural description of the extended enterprise (the fadee) presented in this paper. it changes the communication between cio and ceo, what results in more involvement of the cio in the strategy making process.