waashk/dblp huggingface dataset:
discovering approximate keys in xml data. keys are very important in many aspects of data management, such as guiding query formulation, query optimization, indexing, etc. we consider the situation where an xml document does not come with key definitions, and we are interested in using data mining techniques to obtain a representation of the keys holding in a document. in order to have a compact representation of the set of keys holding in a document, we define a partial order on the set of all key expressions. this order is based on an analysis of the properties of absolute and relative keys for xml. given the existence of the partial order, only a reduced set of key expressions need to be discovered.due to the semistructured nature of xml documents, it turns out to be useful to consider keys that hold in "almost" the whole document, that is, they are violated only in a small part of the document. to this end, the support and confidence of a key expression are also defined, and the concept of approximate key expression is introduced. we give an efficient algorithm to mine a reduced set of approximate keys from an xml document.
inferring document similarity from hyperlinks. assessing semantic similarity between text documents is a crucial aspect in information retrieval systems. in this work, we propose to use hyperlink information to derive a similarity measure that can then be applied to compare any text documents, with or without hyperlinks. as linked documents are generally semantically closer than unlinked documents, we use a training corpus with hyperlinks to infer a function a,b → sim(a,b) that assigns a higher value to linked documents than to unlinked ones. two sets of experiments on different corpora show that this function compares favorably with okapi matching on document retrieval tasks.
categorizing web queries according to geographical locality. web pages (and resources, in general) can be characterized according to their geographical locality. for example, a web page with general information about wildflowers could be considered a global page, likely to be of interest to a geographically broad audience. in contrast, a web page with listings on houses for sale in a specific city could be regarded as a local page, likely to be of interest only to an audience in a relatively narrow region. similarly, some search engine queries (implicitly) target global pages, while other queries are after local pages. for example, the best results for query [wildflowers] are probably global pages about wildflowers such as the one discussed above. however, local pages that are relevant to, say, san francisco are likely to be good matches for a query [houses for sale] that was issued by a san francisco resident or by somebody moving to that city. unfortunately, search engines do not analyze the geographical locality of queries and users, and hence often produce sub-optimal results. thus query [wildflowers] might return pages that discuss wildflowers in specific u.s. states (and not general information about wildflowers), while query [houses for sale] might return pages with real estate listings for locations other than that of interest to the person who issued the query. deciding whether an unseen query should produce mostly local or global pages---without placing this burden on the search engine users---is an important and challenging problem, because queries are often ambiguous or underspecify the information they are after. in this paper, we address this problem by first defining how to categorize queries according to their (often implicit) geographical locality. we then introduce several alternatives for automatically and efficiently categorizing queries in our scheme, using a variety of state-of-the-art machine learning tools. we report a thorough evaluation of our classifiers using a large sample of queries from a real web search engine, and conclude by discussing how our query categorization approach can help improve query result quality.
on the complexity of computing peer agreements for consistent query answering in peer-to-peer data integration systems. peer-to-peer (p2p) data integration systems have recently attracted significant attention for their ability to manage and share data dispersed over different peer sources. while integrating data for answering user queries, it often happens that inconsistencies arise, because some integrity constraints specified on peers' global schemas may be violated. in these cases, we may give semantics to the inconsistent system by suitably "repairing" the retrieved data, as typically done in the context of traditional data integration systems. however, some specific features of p2p systems, such as peer autonomy and peer preferences (e.g., different source trusting), should be properly addressed to make the whole approach effective. in this paper, we face these issues that were only marginally considered in the literature. we first present a formal framework for reasoning about autonomous peers that exploit individual preference criteria in repairing the data. the idea is that queries should be answered over the best possible database repairs with respect to the preferences of all peers, i.e., the states on which they are able to find an agreement. then, we investigate the computational complexity of dealing with peer agreements and of answering queries in p2p data integration systems. it turns out that considering peer preferences makes these problems only mildly harder than in traditional data integration systems.
the role of variance in term weighting for probabilistic information retrieval. in probabilistic approaches to information retrieval, the occurrence of a query term in a document contributes to the probability that the document will be judged relevant. it is typically assumed that the weight assigned to a query term should be based on the expected value of that contribution. in this paper we show that the degree to which observable document features such as term frequencies are expected to vary is also important. by means of stochastic simulation, we show that increased variance results in degraded retrieval performance. we further show that by decreasing term weights in the presence of variance, this degradation can be reduced. hence, probabilistic models of information retrieval must take into account not only the expected value of a query term's contribution but also the variance of document features.
consistent query answering under key and exclusion dependencies: algorithms and experiments. research in consistent query answering studies the definition and computation of "meaningful" answers to queries posed to inconsistent databases, i.e., databases whose data do not satisfy the integrity constraints (ics) declared on their schema. computing consistent answers to conjunctive queries is generally conp-hard in data complexity, even in the presence of very restricted forms of ics (single, unary keys). recent studies on consistent query answering for database schemas containing only key dependencies have analyzed the possibility of identifying classes of queries whose consistent answers can be obtained by a first-order rewriting of the query, which in turn can be easily formulated in sql and directly evaluated through any relational dbms. in this paper we study consistent query answering in the presence of key dependencies and exclusion dependencies. we first prove that even in the presence of only exclusion dependencies the problem is conp-hard in data complexity, and define a general method for consistent answering of conjunctive queries under key and exclusion dependencies, based on the rewriting of the query in datalog with negation. then, we identify a subclass of conjunctive queries that can be first-order rewritten in the presence of key and exclusion dependencies, and define an algorithm for computing the first-order rewriting of a query belonging to such a class of queries. finally, we compare the relative efficiency of the two methods for processing queries in the subclass above mentioned. experimental results, conducted on a real and large database of the computer science engineering degrees of the university of rome "la sapienza", clearly show the computational advantage of the first-order based technique.
intelligent creation of notification events in information systems: concept, implementation and evaluation. an important feature of information systems is the ability to inform users about changes of the stored information. therefore, systems have to 'know' what changes a user wants to be informed about. this is well known from the field of publish-/subscribe architectures. in this paper, we propose a solution for information system designers of how to extend their information model in a way that the notification mechanism can consider semantic knowledge when determining which parties to inform. two different kinds of implementations are introduced and evaluated: one based on aspect oriented programming (aop), the other one based on traditional database triggers. the evaluation of both approaches leads to a combined approach preserving the advantages of both techniques, using model driven architecture (mda) to create the triggers from a uml model enhanced with stereotypes.
efficient data dissemination using locale covers. location-dependent data are central to many emerging applications, ranging from traffic information services to sensor networks. the standard pull- and push-based data dissemination models become unworkable since the data volumes and number of clients are high. we address this problem using locale covers, a subset of the original set of locations of interest, chosen to include at least one location in a suitably defined neighborhood of any client. since location-dependent values are highly correlated with location, a query can be answered using a location close to the query point. typical closeness measures might be euclidean distance, or a k-nearest neighbor criterion. we show that location-dependent queries may be answered satisfactorily using locale covers. our approach is independent of locations and speeds of clients, and is applicable to mobile clients. we also introduce a nested locale cover scheme that ensures fair access latencies, and allows clients to refine the accuracy of their information over time. we also prove two important results: one regarding the greedy algorithm for sensor covers and the other pertaining to randomized locale covers for k-nearest neighbor queries.
exposing the vagueness of query results on partly inaccessible databases. query processing on partly inaccessible databases generally does not yield exact, but vague result sets. a good notion of vague sets fulfills two aims: it keeps the degree of vagueness of the query result as small as possible, and it clarifies the degree of and the reasons for the vagueness to the end user. the first goal requires a good internal representation, while the second goal requires a good external representation of a vague set. in this paper, we present a novel calculus for expressive vague sets that meets both requirements. this is the first approach that is well suited for both internal and external representation of vagueness induced by partial inaccessibility. it consists of a data representation that is capable of holding all the necessary information. complementary, we have accordingly adapted the usual query language operations. these adaptations are independent of a concrete query language, to make them applicable to most existing query languages. the adapted operations minimize the vagueness of the result, propagate the reasons of uncertainty of the individual vague candidates, and compute an expressive description of the missing elements.
exact match search in sequence data using suffix trees. we study suitable indexing techniques to support efficient exact match search in large biological sequence databases. we propose a suffix tree (st) representation, called sta-df, as an alternative to the array representation of st (sta) proposed in [7] and utilized in [18]. to study the performance of sta and sta-df, we develop a memory efficient st-based exact match (stem) search algorithm. we implemented stem and both representations of st and conducted extensive experiments. our results indicate that the sta and sta-df representations are very similar in construction time, storage utilization, and search time using stem. in terms of the access patterns by stem, our results show that compared to sta, the sta-df representation exhibits better spatial and sequential locality of reference. this suggests that sta-df would require less number of disk i/os, and hence is more amenable to efficient and scalable disk-based computation.
decentralized coordination of transactional processes in peer-to-peer environments. business processes executing in peer-to-peer environments usually invoke web services on different, independent peers. although peer-to-peer environments inherently lack global control, some business processes nevertheless require global transactional guarantees, i.e., atomicity and isolation applied at the level of processes. this paper introduces a new decentralized serialization graph testing protocol to ensure concurrency control and recovery in peer-to-peer environments. the uniqueness of the proposed protocol is that it ensures global correctness without relying on a global serialization graph. essentially, each transactional process is equipped with partial knowledge that allows the transactional processes to coordinate. globally correct execution is achieved by communication among dependent transactional processes and the peers they have accessed. in case of failures, a combination of partial backward and forward recovery is applied. experimental results exhibit a significant performance gain over traditional distributed locking-based protocols with respect to the execution of transactions encompassing web service requests.
integrating a part relationship into an open oodb system using metaclasses. the part-whole semantic relationship (the part relationship, for short) is an important modeling primitive in many advanced application domains such as manufacturing, design, and document processing. in this paper, we examine the problem of integrating such a construct into an oodb system. specifically, two questions are addressed in this regard. this first is: can a part relationship be made an intrinsic construct of an existing oodb system without having to rewrite a substantial portion of the system? the second: can an &ldquo;open&rdquo; oodb system which claims to support such an integration really do so, and, more specifically, can the integration be done using a metaclass mechanism which purports to bring extensibility to the vodak model language (vml)?to demonstrate that both questions can be answered &ldquo;yes,&rdquo; we introduce and discuss the details of a custom vml metaclass&mdash;the &ldquo;holonymicmeronymic&rdquo; metaclass&mdash;which we have built. this metaclass comprises two items, an &ldquo;instance&rdquo; type and an &ldquo;instance-instance&rdquo; type. together, the two endow the classes of a part hierarchy and their instances with structure and behavior consistent with our comprehensive part relationship model and the notions of &ldquo;part&rdquo; and &ldquo;whole.&rdquo; complete descriptions of each of these two aspects of the metaclass are presented and their effect on schema construction and database usage is discussed.
alternatives to the k-means algorithm that find better clusterings. we investigate here the behavior of the standard k-means clustering algorithm and several alternatives to it: the k-harmonic means algorithm due to zhang and colleagues, fuzzy k-means, gaussian expectation-maximization, and two new variants of k-harmonic means. our aim is to find which aspects of these algorithms contribute to finding good clusterings, as opposed to converging to a low-quality local optimum. we describe each algorithm in a unified framework that introduces separate cluster membership and data weight functions. we then show that the algorithms do behave very differently from each other on simple low-dimensional synthetic datasets and image segmentation tasks, and that the k-harmonic means method is superior. having a soft membership function is essential for finding high-quality clusterings, but having a non-constant data weight function is useful also.
feature-based recommendation system. the explosive growth of the world-wide-web and the emergence of e-commerce has led to the development of recommender systems--a personalized information filtering technology used to identify a set of n items that will be of interest to a certain user. user-based and model-based collaborative filtering are the most successful technology for building recommender systems to date and is extensively used in many commercial recommender systems. the basic assumption in these algorithms is that there are sufficient historical data for measuring similarity between products or users. however, this assumption does not hold in various application domains such as electronics retail, home shopping network, on-line retail where new products are introduced and existing products disappear from the catalog. another such application domains is home improvement retail industry where a lot of products (such as window treatments, bathroom, kitchen or deck) are custom made. each product is unique and there are very little duplicate products. in this domain, the probability of the same exact two products bought together is close to zero. in this paper, we discuss the challenges of providing recommendation in the domains where no sufficient historical data exist for measuring similarity between products or users. we present feature-based recommendation algorithms that overcome the limitations of the existing top-n recommendation algorithms. the experimental evaluation of the proposed algorithms in the real life data sets shows a great promise. the pilot project deploying the proposed feature-based recommendation algorithms in the on-line retail web site shows 75% increase in the recommendation revenue for the first 2 month period.
intelligent metasearch engine for knowledge management. the explosive growth of available information sources and the resulting information overload pose several problems for users in many business organizations and educational institutions. first, searching through several information sources, one at a time, is a source of enormous frustration for users. second, top-ranked documents in search results are frequently irrelevant to what users are interested in. to address these problems, we have developed ixmeta™, a powerful metasearch engine that gathers, evaluates, ranks, and reports the most relevant results from multiple information sources, including library catalogs, proprietary databases, intranets, and web search engines. in addition to basic metasearch capabilities, ixmetafind uses personalization and clustering techniques to find the most relevant results for users. in this paper, we briefly describe technologies used in ixmetafind and present pinpoint™ from sagebrush corporation, the smart research tool™ in the kindergarten through twelfth grade (k-12) school environment. pinpoint showcases ixmetafind in the knowledge management domain of the k-12 school environment.
logicbase: a deductive database system prototype. a deductive database system prototype, logicbase, has been developed, with an emphasis on efficient compilation and query evaluation of application-oriented recursions in deductive databases. the system identifies different classes of recursions and compiles recursions into chain or psuedo-chain forms when appropriate. queries posed to the compiled recursions are analyzed systematically with efficient evaluation plans generated and executed, mainly based on a chained-based query evaluation method. the system has been tested using sophisticated recursions and queries with satisfactory performance. this paper introduces the general design principles and implementation techniques of the system and discusses its strength and limitations.
using navigation data to improve ir functions in the context of web search. as part of the process of delivering content, devices like proxies and gateways log valuable information about the activities and navigation patterns of users on the web. in this study, we consider how this navigation data can be used to improve web search. a query posted to a search engine together with the set of pages accessed during a search task is known as a search session. we develop a mixture model for the observed set of search sessions, and propose variants of the classical em algorithm for training. the model itself yields a type of navigation-based query clustering. by implicitly borrowing strength between related queries, the mixture formulation allows us to identify the "highly relevant" urls for each query cluster. next, we explore methods for incorporating existing labeled data (the yahoo! directory, for example) to speed convergence and help resolve low-traffic clusters. finally, the mixture formulation also provides for a simple, hierarchical display of search results based on the query clusters. the effectiveness of our approach is evaluated using proxy access logs for the outgoing lucent proxy.
cooperative caching by mobile clients in push-based information systems. recent advances in computer and wireless communication technologies have increased interest in push-based information systems in which a server repeatedly broadcasts data to clients through a broadband channel. in this paper, assuming an environment where clients in push-based information systems construct ad hoc networks, we propose three caching strategies in which clients cooperatively cache broadcast data items. these strategies shorten the average response time for data access by replacing cached items based on their access frequencies, the network topology, and the time remaining until each item is broadcast next. we also show the results of simulation experiments conducted to evaluate the performance of our proposed strategies.
order checking in a cpoe using event analyzer. in this paper we present our experience in applying event analyzer, a processing engine we have developed to extract patterns from a sequence of events, in the checking of medical orders of a cpoe system. we present some extensions we have implemented in event analyzer in order to fulfill the needs of those orders checking, as well as some performance evaluation results. we also outline some problems we are facing now to adapt event analyzer's pattern detection engine to support streaming orders in an on-line cpoe checking system.
event analyzer: a tool for sequential data processing. in this paper we present a tool called event analyzer that processes events that compose a sequence. we present the data model in which event analyzer is based, as well as its query language that allows the expression of complex patterns to be searched over the sequence of events. the event analyzer has been developed and it now integrates the fujitsu symfoware e-business intelligence suite premium.
the semantic web: managing knowledge for planet earth. the semantic web (sweb) is a vision - actually, a number of visions - which is beginning to show some signs of potential reality. the core of the vision is a synergy between machine-accessible knowledge and the global reach of the web. the deployment of knowledge technologies on a planet-wide open network brings new challenges and opportunities, many of them not yet fully realized. this talk briefly surveys the current state of play in sweb standards and technology, including some of the rather heated controversies, and tries to give a high-level view of some of these challenges and opportunities. some traditional hard problems in km may largely evaporate; but new ones will take their place.