waashk/dblp huggingface dataset:
organizing structured web sources by query schemas: a clustering approach. in the recent years, the web has been rapidly "deepened" with the prevalence of databases online. on this deep web, many sources are <i>structured</i> by providing structured query interfaces and results. organizing such structured sources into a domain hierarchy is one of the critical steps toward the integration of heterogeneous web sources. we observe that, for structured web sources, query schemas <i>ie</i>, attributes in query interfaces) are discriminative representatives of the sources and thus can be exploited for source characterization. in particular, by viewing query schemas as a type of categorical data, we abstract the problem of source organization into the clustering of categorical data. our approach hypothesizes that "homogeneous sources" are characterized by the same hidden generative models for their schemas. to find clusters governed by such statistical distributions, we propose a new objective function, <i>model-differentiation</i>, which employs principled hypothesis testing to maximize statistical heterogeneity among clusters. our evaluation over hundreds of real sources indicates that (1) the schema-based clustering accurately organizes sources by object domains <i>eg</i>, books, movies), and (2) on clustering web query schemas, the model-differentiation function outperforms existing ones, such as likelihood, entropy, and context linkages, with the hierarchical agglomerative clustering algorithm.
compact reachability labeling for graph-structured data. testing reachability between nodes in a graph is a well-known problem with many important applications, including knowledge representation, program analysis, and more recently, biological and ontology databases inferencing as well as xml query processing. various approaches have been proposed to encode graph reachability information using node labeling schemes, but most existing schemes only work well for specific types of graphs. in this paper, we propose a novel approach, hlss(hierarchical labeling of sub-structures), which identifies different types of substructures within a graph and encodes them using techniques suitable to the characteristics of each of them. we implement hlss with an efficient two-phase algorithm, where the first phase identifies and encodes strongly connected components as well as tree substructures, and the second phase encodes the remaining reachability relationships by compressing dense rectangular submatrices in the transitive closure matrix. for the important subproblem of finding densest submatrices, we demonstrate the hardness of the problem and propose several practical algorithms. experiments show that hlss handles different types of graphs well, while existing approaches fall prey to graphs with substructures they are not designed to handle.
quasi-dynamic two-phase locking. among the plethora of concurrency control algorithms that have been proposed and analyzed, two-phase locking (2pl) has been adapted as the industry de facto standard concurrency control. in accord, current research in concurrency control is focusing on enhancing the scalability of 2pl performance in highly concurrent and contentious environments. this is especially needed in future on-line transaction processing systems, where thousand transaction per second performance will be required.static locking (sl) and dynamic locking (dl) are two famous adaptations of 2pl that are used under different degrees of data contention. in this paper, we offer our observation that 2pl is indeed a family of methods, of which sl and dl are extreme case members. further, we argue for and verify the existence of other 2pl member methods that, under variable conditions, outperform sl and dl. we propose two novel schemes which we categorize as quasi-dynamic two-phase locking on account of their behavior in comparison with dynamic/static two-phase locking. we present a simulation study of the performance of the proposed schemes and their comparison to dynamic and static locking methods.
how foreign function integration conquers heterogeneous query processing. with the emergence of application systems which encapsulate databases and related application components, pure data integration using, for example, a federated database system is not possible anymore. instead, access via predefined functions is the only way to get data from an application system. as a result, retrieval of such heterogeneous and encapsulated data sources needs the combination of generic query as well as predefined function access. in this paper, we present a middleware approach supporting such a novel and extended kind of integration. starting with the overall architecture, we explain the functionality and cooperation of its core components: a federated database system and a workflow management system connected via a wrapper. afterwards, we concentrate on essential aspects of query processing across these heterogeneous components focusing on the impact of the functions included. we discuss the operations the wrapper should provide in order to extend the workflow system's native functionality. in addition to selection and projection, these operations could include aggregation and the support of subqueries. moreover, we point out modifications to the traditional cost model needed to consider the cost estimates for the function calls as well.
syynx solutions: practical knowledge management in a medical environment. in this paper we describe the knowledge management approach for the biomedical scientific community developed by syynx solutions gmbh [1].
from bits and bytes to information and knowledge. unstructured data is a valuable source of information and implicit knowledge. yet, the bits and bytes of, e.g., text, image, or click-stream data need to be interpreted in order to transform them into business intelligence and actionable information. clearly, this process needs to be automated to the largest possible extend in order to be scalable to the typical volumes of data. one way to accomplish this is through the use of machine learning and statistical modelling techniques. this talk will provide an overview of recent progress and new trends in machine learning and discuss their relevance for developing intelligent tools for search, information filtering, categorization, and knowledge extraction.
sql text parsing for information retrieval. the concept of using a relational database to perform information retrieval (ir) search functions is well established. prior work demonstrates the capability to perform common functions and advanced ranking algorithms using standard, unchanged sql. the previous work does not address the preprocessing of unstructured text within the relational model. in fact, the parsing of the unstructured data into a structured data set was done outside of the database, usually using sequential programming languages such as c. this work proves that ir preprocessing does not require proprietary application code to build the framework necessary for searching document databases. furthermore, the resulting environment is relational and integrates with other data sources within an organization.
efficient mining of association rules in text databases. in this paper, we propose two new algorithms for mining association rules between words in text databases. the characteristics of text databases are quite different from those of retail transaction databases, and existing mining algorithms cannot handle text databases efficiently because of the large number of itemsets (i.e., words) that need to be counted. two well-known mining algorithms, apriori algorithm and direct hashing and pruning (dhp) algorithm, are evaluated in the context of mining text databases, and are compared with the new proposed algorithms named multipass-apriori (m-apriori) and multipass-dhp (m-dhp). it has been shown that the proposed algorithms have better performance for large text databases.
indexing text data under space constraints. an important class of queries is the like predicate in sql. in the absence of an index, like queries are subject to performance degradation. the notion of indexing on substrings (or <i>q</i>-grams) has been explored earlier without sufficient consideration of efficiency. <i>q</i>-grams are used to prune away rows that do not qualify for the query. the problem is to identify a finite number of grams subject to storage constraint that gives maximal pruning for a given query workload. our contributions include: i) a formal problem definition, that produces results within a provable error bound, ii) performance evaluation of the application of the novel method to real data, and iii) parallelization of the algorithm, scaling considerations and a proposal to handle scaling issues.
an optimal construction of invalidation reports for mobile databases. mobile computing is characterized by frequent disconnection, limited communication capability, narrow bandwidth, etc. caching can play a vital role in mobile computing by reducing the amount of data transferred. in order to reuse caches after short disconnections, invalidation reports are broadcasted to clients to help update/invalidate their caches. detailed reports may not be desirable because they can be very long and consume large bandwidth. on the other hand, false invalidations may set in if detailed timing information of updates is not provided in the report. in this research, we aim to reduce the false invalidation rates of the reports. it is found that false invalidation rates are closely related to clients' reconnection patterns (i.e., the distribution of the time spans between disconnections and reconnections). by using newton's method, we show how a report with a minimal false invalidation rate can be constructed for any given disconnection pattern.
integrating dct and dwt for approximating cube streams. for time-relevant multi-dimensional data sets (mds), users usually pose a huge amount of data due to the large dimensionality, and approximating query processing has emerged as a viable solution. specifically, the cube streams handle mdss in a continuous manner. traditional cube approximation focuses on generating single snapshots rather than continuous ones. to address this issue, the application of generating snapshots for cube streams, called scs, is investigated in this paper. such an application collects data events for cube streams on-line and generates snapshots with limited resources in order to keep the approximated information in synopsis memory for further analysis. as compared to olap applications, the scs ones are subject to much more resource constraints for both processing time and memory and cannot be dealt with by existing methods due to the limited resources. in this paper, the dawa algorithm, standing for a hybrid algorithm of dct for data and discrete wavelet transform, is proposed to approximate the cube streams. the dawa algorithm combines the advantage of high compression rate from dwt and that of low memory cost from dct. consequently, dawa costs much smaller working buffer and outperforms both dwt-based and dct-based methods in execution efficiency. also, it is shown that dawa provides answers of good quality for scs applications with a small working buffer and short execution time. the optimality of algorithm dawa is theoretically proved and also empirically demonstrated by our experiments.
the effectiveness study of various music information retrieval approaches. in this paper, we describe the ultima project which aims to construct a platform for evaluating various approaches of music information retrieval. two kinds of approaches are adopted in this project. these approaches differ in various aspects, such as representations of music objects, index structures, and approximate query processing strategies. for a fair comparison, we propose a measurement of the retrieval effectiveness by recall-precision curves with a scaling factor adjustment. finally, the performance study of the retrieval effectiveness based on various factors of these approaches is presented.
classification algorithms for netnews articles. we propose several algorithms using the vector space model to classify the news articles posted on the netnews according to the newsgroup categories. the baseline method combines the terms of all the articles of each newsgroup in the training set to represent the newsgroups as single vectors. after training, the incoming news articles are classified based on their similarity to the existing newsgroup categories. we propose to use the following techniques to improve the classification performance of the baseline method: (1) use routing (classification) accuracy and the similarity values to refine the training set; (2) update the underlying term structures periodically during testing; and (3) apply k-means clustering to partition the newsgroup articles and represent each newsgroup by k vectors. our test collection consists of the real news articles and the 519 subnewsgroups under the rec newsgroup of netnews in a period of 3 months. our experimental results demonstrate that the technique of refining the training set reduces from one-third to two-thirds of the storage. the technique of periodical updates improves the routing accuracy ranging from 20% to 100% but incurs runtime overhead. finally, representing each newsgroup by k vectors (with k = 2 or 3) using clustering yields the most significant improvement in routing accuracy, ranging from 60% to 100%, while causing only slightly higher storage requirements.
a near optimal algorithm for generating broadcast programs on multiple channels. in a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. data broadcast has become an excellent method for efficient data dissemination. in this paper, the problem for generating a broadcast program of a set of data items with the associated access frequencies on multiple channels is explored. in our approach, an expected average access time of the broadcast data items is first derived. the broadcast program is then generated, which minimizes the expected average access time. simulation is performed to compare the performance of our approach with two existing approaches. the result of the experiments shows that our approach outperforms others and is in fact close to the optimal.
indexing techniques for wireless data broadcast under data clustering and scheduling. this paper investigates power conserving indexing techniques for data disseminated on a broadcast channel. a hybrid indexing method combining strengths of the signature and the index tree techniques is presented. different from previous studies, our research takes into consideration two important data organization factors, namely, clustering and scheduling. cost models for index, signature and hybrid methods are derived by taking into account various data organizations accommodating these two factors. based on our analytical comparisons, the signature and the hybrid indexing techniques are the best choices for power conserving indexing of various data organizations on wireless broadcast channels.
mining undiscovered public knowledge from complementary and non-interactive biomedical literature through semantic pruning. two complementary and non-interactive literature sets of articles, when they are considered together, can reveal useful information of scientific interest not apparent in either of the two document sets. swanson called the existence of such knowledge, undiscovered public knowledge (udpk). this paper proposes a semantic-based mining model for udpk. our method replaces manual ad-hoc pruning with using semantic knowledge from the biomedical ontologies. using the semantic types and semantic relationships of the biomedical concepts, our prototype system can identify the relevant concepts collected from medline and generate the novel hypothesis between these concepts. the system successfully replicates swanson's two famous discoveries: raynaud disease/fish oils and migraine/magnesium. compared with previous approaches, our methods generate much fewer but more relevant novel hypotheses, and require much less human intervention in the discovery procedure.
comparison of interestingness functions for learning web usage patterns. livelink is a collaborative intranet, extranet and e-business application that enables employees and business partners of an organization to capture, share and reuse business information and knowledge. the usage of the livelink software has been recorded by the livelink web server in its log files. we present an application of data mining techniques to the livelink web usage data. in particular, we focus on how to find interesting association rules and sequential patterns from the livelink log files. a number of interestingness measures are used in our application to identify interesting rules and patterns. we present a comparison of these measures based on the feedback from domain experts. some of the interestingness measures are found to be better than others.
exploring group mobility for replica data allocation in a mobile environment. the growth in wireless communication technologies attracts a considerable amount of attention in mobile ad-hoc networks. since mobile hosts in an ad-hoc network usually move freely, the topology of the network changes dynamically and disconnection occurs frequently. these characteristics make a mobile ad-hoc network be likely to be separated into several disconnected partitions, and the data accessibility is hence reduced. several schemes are proposed to alleviate the reduction of data accessibility by replicating data items. however, little research effort was elaborated upon exploiting the group mobility where the group mobility refers to the phenomenon that several mobile nodes tend to move together. in this paper, we address the problem of replica allocation in a mobile ad-hoc network by exploring group mobility. we first analyze the group mobility model and derive several theoretical results. in light of these results, we propose a replica allocation scheme to improve the data accessibility. several experiments are conducted to evaluate the performance of the proposed scheme. the experimental results show that the proposed scheme is able to not only obtain higher data accessibility but also produce lower network traffic than prior schemes.
a new permutation approach for distributed association rule mining. privacy preserving distributed data mining has become a promising research area. this paper addresses the problem of association rule mining where the global database is vertically partitioned. when transactions are distributed in different sites, scalar product is a feasible tool to discover frequent itemsets. we present a new protocol to compute scalar product between two parties with a permutation approach. we analyze the protocol in detail and demonstrate its effectiveness and high privacy properties, and compare it to other published protocols.
compression schemes for differential categorical stream clustering. stream data analysis differs significantly from traditional data processing. to process the data online the algorithm has to work in one pass, incorporating new data into a model maintained in main memory. storing a model or synopsis of processed data in the memory, which we call "data compression", is an important technique in both incremental and differential stream mining. this paper proposes several data compression schemes in one-pass categorical data clustering, and demonstrates their performance on synthetic and real data. our compression schemes can efficiently generate compact representations of original data, so as to enable the algorithm to process streams at high speed and detect the changes in underlying data. the example algorithm based on these compression schemes achieves good accuracy in short execution time.
binary interpolation search for solution mapping on broadcast and on-demand channels in a mobile computing environment. we explore in this paper the problem of dynamic data and channel allocations with the number of communication channels and the number of data items given. it is noted that the combined use of broadcast and on-demand channels can utilize the bandwidth effectively for data dissemination in a mobile computing environment. we first derive the an-alytical models of the expected delays when the data are requested through the broadcast and on-demand channels. then, we transform this problem into to a guided search problem. in light of the theoretical properties derived, we devise an algorithm based on binary interpolation search, referred to as algorithm bis, to obtain solutions of high quality efficiently. in essence, algorithm bis is guided to explore the solution space with higher likelihood to be the optimal first, thereby leading to an efficient and effective search. it is shown by our simulation results that the solution obtained by algorithm bis is of very high quality and is in fact very close to the optimal one. sensitivity analysis on several parameters, including the number of data items and the number of communication channels, is conducted.
industrial evaluation of a highly-accurate academic ir system. in this paper we report the results of an independent experimental evaluation of an information retrieval (ir) system developed at the illinois institute of technology (iit). the system, which is called the advanced information retrieval engine (aire), consists of a set of tools and utilities providing indexing, extraction, searching and visualization. we evaluated aire on three data sets from the text retrieval conference (trec) - trec 8, 9 and 10. overall, our results indicate that aire is a highly accurate ir system. compared with results published by iit, in our experiments aire consistently scored higher in recall. aire also scored higher in precision, but only for automatic tasks. in manual tasks, aire scored lower in precision in our experiments, but we attributed that to factors external to aire. our final conclusion is that aire is a highly accurate ir system.
emerging data management systems: close-up and personal. conventional data management occurs primarily in centralized servers or in well-interconnected distributed systems. these are removed from their end users, who interact with the systems mostly through static devices to obtain generic services around main-stream applications: banking, retail, business management, etc. several recent advances in technologies, however, give rise to a new breed of applications, which change altogether the user experience and sense of data management. very soon several such systems will be in our pockets, many more in our homes, the kitchen appliances, our clothes, etc. how would these systems operate? many system and user aspects must be approached in novel ways, while several new issues come up and need to be addressed for the first time. highlights include personalization, privacy, information trading, annotation, new interaction devices and corresponding interfaces, visualization, etc. in this talk, we take a close look at and give a very personal guided tour to this emerging world of data management, offering some thoughts on how the new technical challenges might be approached.
group formation mechanisms for transactions in isis. distributed toolkits like isis provide means of replicating data but not means for making it persistent. this makes the use of transactions desirable, even in non-database applications. using isis can alleviate the programming cost of distributed transaction processing the multi-phase commit protocols. using the isis transaction tool, however, imposes additional cost, and we examine the effect of group formation strategies on the overhead. the paper presents three different group formation mechanisms in isis and compares the costs associated with them.