OpenRaiser/Intern-Atlas huggingface dataset:
On the complexity of computing peer agreements for consistent query answering in peer-to-peer data integration systems
Authors: Gianluigi Greco, Francesco Scarcello
Venue: CIKM
Year: 2005

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.
Consistent query answering under key and exclusion dependencies: algorithms and experiments
Authors: Luca Grieco, Domenico Lembo, Riccardo Rosati, Marco Ruzzi
Venue: CIKM
Year: 2005

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. Copyright 2005 ACM.
Intelligent creation of notification events in information systems: concept, implementation and evaluation
Authors: Michael Guppenberger, Burkhard Freitag
Venue: CIKM
Year: 2005

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.
Exact match search in sequence data using suffix trees
Authors: Mihail Halachev, Nematollaah Shiri, Anand Thamildurai
Venue: CIKM
Year: 2005

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
Authors: Klaus Haller, Heiko Schuldt, Can Türker
Venue: CIKM
Year: 2005

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.
Order checking in a CPOE using event analyzer
Authors: Lilian Harada, Yuuji Hotta
Venue: CIKM
Year: 2005

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.
Compact reachability labeling for graph-structured data
Authors: Hao He, Haixun Wang, Jun Yang, Philip S. Yu
Venue: CIKM
Year: 2005

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.
SyynX solutions: practical knowledge management in a medical environment
Authors: Christian Herzog, Gianpiero Liuzzi, Mario Diwersy
Venue: CIKM
Year: 2005

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
Authors: Thomas Hofmann
Venue: CIKM
Year: 2005

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.
Integrating DCT and DWT for approximating cube streams
Authors: Ming-Jyh Hsieh, Ming-Syan Chen, Philip S. Yu
Venue: CIKM
Year: 2005

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.
Mining undiscovered public knowledge from complementary and non-interactive biomedical literature through semantic pruning
Authors: Xiaohua Hu, Illhoi Yoo, Min Song, Yanqing Zhang, Il-Yeol Song
Venue: CIKM
Year: 2005

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.
A new permutation approach for distributed association rule mining
Authors: Yiqun Huang, Zhengding Lu, Heping Hu
Venue: CIKM
Year: 2005

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.
Emerging data management systems: close-up and personal
Authors: Yannis E. Ioannidis
Venue: CIKM
Year: 2005

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.
Accurately extracting coherent relevant passages using hidden Markov models
Authors: Jing Jiang, ChengXiang Zhai
Venue: CIKM
Year: 2005

In this paper, we present a principled method for accurately extracting coherent relevant passages of variable lengths using HMMs. We show that with appropriate parameter estimation, the HMM method outperforms a number of strong baseline methods on two data sets.
Kalchas: a dynamic XML search engine
Authors: Rasmus Kaae, Thanh-Duy Nguyen, Dennis Nørgaard, Albrecht Schmidt
Venue: CIKM
Year: 2005

This paper outlines the system architecture and the core data structures of Kalchas, a fulltext search engine for XML data with emphasis on dynamic indexing, and identifies features worth demonstrating. The concept of dynamic index implies that the aim is to re ect the creation of, deletion of, and updates to relevant files in the search index as early as possible. This is achieved by a number of techniques, including ideas drawn from partitioned B-Trees and inverted indices. The actual ranked retrieval of document is implemented with XML-specific query operators for lowest common ancestor queries.A live demonstration will discuss Kalchas' behaviour in typical use cases, such as interactive editing sessions and bulk loading large amounts of static files as well as querying the contents of the indexed files; it tries to clarify both the short-comings and the advantages of the method.
Web-centric language models
Authors: Jaap Kamps
Venue: CIKM
Year: 2005

We investigate language models for informational and navigational web search. Retrieval on the web is a task that differs substantially from ordinary ad hoc retrieval. We perform an analysis of prior probability of relevance for a wide range of non-content features, shedding further light on the importance of non-content features for web retrieval. This directly explains the success or failure of various techniques, e.g., why the link topology is particularly helpful to single out important sites. Language models can naturally incorporate multiple document representations, as well as non-content information. For the former, we employ mixture language models based on document full-text, incoming anchor-text, and document titles. For the latter, we study a range of priors based on document length, URL structure, and link topology. We look at three types of topics--distillation, home page, and named page--as well as for a mixed query set. We find that the mixture models lead to considerable improvement of retrieval effectiveness for all topic types. The web-centric priors generally lead to further improvement of retrieval effectiveness.
Structured queries in XML retrieval
Authors: Jaap Kamps, Maarten Marx, Maarten de Rijke, Börkur Sigurbjörnsson
Venue: CIKM
Year: 2005

Document-centric XML is a mixture of text and structure. With the increased availability of document-centric XML content comes a need for query facilities in which both structural constraints and constraints on the content of the documents can be expressed. How does the expressiveness of languages for querying XML documents help users to express their information needs? We address this question from both an experimental and a theoretical point of view. Our experimental analysis compares a structure-ignorant with a structure-aware retrieval approach using the test-suite of the 2004 edition of the INEX XML retrieval evaluation initiative. Theoretically, we create mathematical models of users' knowledge of a set of documents and define query languages which exactly fit these models. One of these languages corresponds to an XML version of fielded search, the other to the INEX query language. Our main findings are: First, while structure is used in varying degrees of complexity, over half of the queries can be expressed in a fielded-search like format which does not use the hierarchical structure of the documents. Second, structure is used as a search hint, and not a strict requirement, when judged against the underlying information need. Third, the use of structure in queries functions as a precision enhancing device.
Establishing value mappings using statistical models and user feedback
Authors: Jaewoo Kang, Tae Sik Han, Dongwon Lee, Prasenjit Mitra
Venue: CIKM
Year: 2005

In this paper, we present a "value mapping" algorithm that does not rely on syntactic similarity or semantic interpretation of the values. The algorithm first constructs a statistical model (e.g., co-occurrence frequency or entropy vector) that captures the unique characteristics of values and their co-occurrence. It then finds the matching values by computing the distances between the models while refining the models using user feedback through iterations. Our experimental results suggest that our approach successfully establishes value mappings even in the presence of opaque data values and thus can be a useful addition to the existing data integration techniques.
Query workload-aware overlay construction using histograms
Authors: Georgia Koloniari, Yannis Petrakis, Evaggelia Pitoura, Thodoris Tsotsos
Venue: CIKM
Year: 2005

Peer-to-peer(p2p) systems over an efficient means of data sharing among a dynamically changing set of a large number of a tonomous nodes.Each node in a p2p system is connected with a small number of other nodes thus creating an overlay network of nodes. A query posed at a node is routed through the overlay network towards nodes hosting data items that satisfy it. In this paper, we consider building overlays that exploit the query workload so that nodes are clustered based on their results to a given query workload. The motivation is to create overlays where nodes that match a large number of similar queries are a fewlinks apart. Query frequency is also taken into account so that popular queries have a greater effect on the formation of the overlay than unpopular ones. We focus on range selection queries and se histograms to estimate the query results of each node. Then, nodes are clustered based on the similarity of their histograms. To this end,we introd ce a workload-aware edit distance metric between histograms that takes into account the query workload. Our experimental results show that workload-aware overlays increase the percentage of query results returned for a given number of nodes visited as compared to both random (i.e., unclustered)overlays and non workload-aware clustered overlays (i.e., overlays that cluster nodes based solely on the nodes' content).
Leveraging collective knowledge
Authors: Henry Kon, Michael Hoey
Venue: CIKM
Year: 2005

As more organizations begin to deploy taxonomies for categorization and faceted search, the cost of producing these knowledge models is becoming the largest expense on a project. At a cost of 200 - 300 dollars per topic, manually developing subject area taxonomies does not scale for any but the smallest of projects. This paper will discuss an approach called Orthogonal Corpus Indexing ( OCI ). OCI leverages existing published knowledge in the subject area of the taxonomy model. This knowledge is algorithmically mapped into multiple taxonomies via the OCI algorithm. The resulting taxonomy costs are 1/ 100th of the cost of manual methods and are created with embedded rule sets for categorization engines. This paper will discuss the theory of OCI, its practical use as well as examples of knowledge management techniques that are possible when taxonomies are large, detailed and inexpensive.
Y!Q: contextual search at the point of inspiration
Authors: Reiner Kraft, Farzin Maghoul, Chi-Chao Chang
Venue: CIKM
Year: 2005

Contextual search tries to better capture a user's information need by augmenting the user's query with contextual information extracted from the search context (for example, terms from the web page the user is currently reading or a file the user is currently editing).This paper presents Y!Q---a first of its kind large-scale contextual search system---and provides an overview of its system design and architecture. Y!Q solves two major problems. First, how to capture high quality search context. Second, how to use that context in a way to improve the relevancy of search queries. To address the first problem, Y!Q introduces an information widget that captures precise search context and provides convenient access to its functionality at the point of inspiration. For example, Y!Q can be easily embedded into web pages using a web API, or it can be integrated into a web browser toolbar. This paper provides an overview of Y!Q's user interaction design, highlighting its novel aspects for capturing high quality search context.To address the second problem, Y!Q uses a semantic network for analyzing search context, possibly resolving ambiguous terms, and generating a contextual digest comprising its key concepts. This digest is passed through a query planner and rewriting framework for augmenting a user's search query with relevant context terms to improve the overall search relevancy and experience. We show experimental results comparing contextual Y!Q search results side-by-side with regular Yahoo! web search results. This evaluation suggests that Y!Q results are considered significantly more relevant.The paper also identifies interesting research problems and argues that contextual search may represent the next major step in the evolution of web search engines.