18437356
Index-based approximate XML joins
XML data integration tools are facing a variety of challenges for their efficient and effective operation. Among these is the requirement to handle a variety of inconsistencies or mistakes present in the data sets. We study the problem of integrating XML data sources through index assisted join operations, using notions of approximate match in the structure and content of XML documents as the join predicate. We show how a well known and widely deployed index structure, namely the R-tree, can be adopted to improve the performance of such operations. We propose novel search and join algorithms for R-trees adopted to index XML document collections. We also propose novel optimization objectives for R-tree construction, making R-trees better suited for this application.
2350428
Interoperable strategies in automated trust negotiation
Automated trust negotiation is an approach to establishing trust between strangers through the exchange of digital credentials and the use of access control policies that specify what combinations of credentials a stranger must disclose in order to gain access to each local service or credential. We introduce the concept of a trust negotiation protocol, which defines the ordering of messages and the type of information messages will contain. To carry out trust negotiation, a party pairs its negotiation protocol with a trust negotiation strategy that controls the exact content of the messages, i.e., which credentials to disclose, when to disclose them, and when to terminate a negotiation. There are a huge number of possible strategies for negotiating trust, each with different properties with respect to speed of negotiations and caution in giving out credentials and policies. In the autonomous world of the Internet, entities will want the freedom to choose negotiation strategies that meet their own goals, which means that two strangers who negotiate trust will often not use the same strategy. To date, only a tiny fraction of the space of possible negotiation strategies has been explored, and no two of the strategies proposed so far will interoperate. In this paper, we define a large set of strategies called the disclosure tree strategy (DTS) family. Then we prove that if two parties each choose strategies from the DTS family, then they will be able to negotiate trust as well as if they were both using the same strategy. Further, they can change strategies at any point during negotiation. We also show that the DTS family is closed, i.e., any strategy that can interoperate with every strategy in the DTS family must also be a member of the DTS family. We also give examples of practical strategies that belong to the DTS family and fit within the TrustBuilder architecture and protocol for trust negotiation.
1690622
Aggregate Query Answering on Anonymized Tables
Privacy is a serious concern when microdata need to be released for ad hoc analyses. The privacy goals of existing privacy protection approaches (e.g., k-anonymity and l-diversity) are suitable only for categorical sensitive attributes. Since applying them directly to numerical sensitive attributes (e.g., salary) may result in undesirable information leakage, we propose privacy goals to better capture the need of privacy protection for numerical sensitive attributes. Complementing the desire for privacy is the need to support ad hoc aggregate analyses over microdata. Existing generalization-based anonymization approaches cannot answer aggregate queries with reasonable accuracy. We present a general framework of permutation-based anonymization to support accurate answering of aggregate queries and show that, for the same grouping, permutation-based techniques can always answer aggregate queries more accurately than generalization-based approaches. We further propose several criteria to optimize permutations for accurate answering of aggregate queries, and develop efficient algorithms for each criterion.
15013952
Policy migration for sensitive credentials in trust negotiation
Trust negotiation is an approach to establishing trust between strangers through the bilateral, iterative disclosure of digital credentials. Under automated trust negotiation, access control policies are associated with sensitive credentials to control under what circumstances those credentials can be disclosed. Ideally, the information in a user's sensitive credential should not be known by others unless the corresponding policy is satisfied. However, the original model for user interaction in trust negotiation has pitfalls which can be easily exploited to infer one's private information, even if access control policies are strictly enforced. To preserve one's privacy, a more flexible interaction model for trust negotiation is required. On the other hand, it is also desirable for two parties to be able to establish trust whenever possible. There is potentially a conflict between privacy preservation and the assurance of a successful trust negotiation. In this paper, we identify the situation where sensitive information can be inferred through observing one's behavior in trust negotiation. Then we propose policy migration as one approach to preventing such inference. Compared to previously proposed approaches, policy migration has a low management overhead, and provides a nice balance between inference prevention and guarantees of success in trust establishment. We also discuss the limitations of policy migration, and possible directions for more comprehensive solutions.
2722770
Preventing attribute information leakage in automated trust negotiation
Automated trust negotiation is an approach which establishes trust between strangers through the bilateral, iterative disclosure of digital credentials. Sensitive credentials are protected by access control policies which may also be communicated to the other party. Ideally, sensitive information should not be known by others unless its access control policy has been satisfied. However, due to bilateral information exchange, information may flow to others in a variety of forms, many of which cannot be protected by access control policies alone. In particular, sensitive information may be inferred by observing negotiation participants' behavior even when access control policies are strictly enforced.In this paper, we propose a general framework for the safety of trust negotiation systems. Compared to the existing safety model, our framework focuses on the actual information gain during trust negotiation instead of the exchanged messages. Thus, it directly reflects the essence of safety in sensitive information protection. Based on the proposed framework, we develop policy databases as a mechanism to help prevent unauthorized information inferences during trust negotiation. We show that policy databases achieve the same protection of sensitive information as existing solutions without imposing additional complications to the interaction between negotiation participants or restricting users' autonomy in defining their own policies.
625233
Routing XML queries
In file-sharing P2P networks, a fundamental problem is that of identifying databases that are relevant to user queries. This problem is referred to as the location problem in P2P literature. We propose a scalable solution to the location problem in a data-sharing P2P network, consisting of a network of XML database nodes and XML router nodes, and make the following contributions. We develop the internal organization and routing protocols for the XML router nodes, to enable scalable XPath query and update processing, under the open and the agreement cooperation models between nodes. Since router nodes tend to be memory constrained, we facilitate a space/performance tradeoff by permitting aggregated routing states, and developing algorithms for generating and using such aggregated information. We experimentally demonstrate the scalability of our approach, and the performance of our query and update protocols, using a detailed simulation model, varying key design parameters.
1794794
Service Selection Algorithms for Composing Complex Services with Multiple QoS Constraints
One of the promises of the service-oriented architecture (SOA) is that complex services can be composed using individual services. Individual services can be selected and integrated either statically or dynamically based on the service functionalities and performance constraints. For many distributed applications, the runtime performance (e.g. end-to-end delay, cost, reliability and availability) of complex services are very important. In our earlier work, we have studied the service selection problem for complex services with only one QoS constraint. This paper extends the service selection problem to multiple QoS constraints. The problem can be modelled in two ways: the combinatorial model and the graph model. The combinatorial model defines the problem as the multi-dimension multi-choice 0-1 knapsack problem (MMKP). The graph model defines the problem as the multi-constraint optimal path (MCOP) problem. We propose algorithms for both models and study their performances by test cases. We also compare the pros & cons between the two models.
61674575
Collaborative tracking of multiple targets
Coalescence, meaning the tracker associates more than one trajectories to some targets while loses track for others, is a challenging problem for visual tracking of multiple targets, especially when similar targets move close or present occlusions. Existing approaches that are based on joint data association are confronted by the combinatorial complexity due to the concatenation of the state spaces of individual targets. This paper presents a novel collaborative approach with linear complexity to the coalescence problem. The basic idea is the collaborative inference mechanism, in which the estimate of an individual target is not only determined by its own observation and dynamics, but also through the interaction and collaboration with the estimates of its adjacent targets, which leads to a competition mechanism that enables different targets to compete for the common image observations. The theoretical foundation of the new approach is based on Markov networks. Variational analysis of this Markov network reveals a mean field approximation to the posterior density of each target, therefore provides a computationally efficient way for such a difficult inference problem. In addition, a mean field Monte Carlo (MFMC) algorithm is designed to achieve Bayesian inference by simulating the competition among a set of low dimensional particle filters. Compared with the existing solutions, the proposed new collaborative approach stands out by its effectiveness and low computational cost to the coalescence problem, as pronounced in the extensive experiments.
7315404
Service selection algorithms for Web services with end-to-end QoS constraints
Web services are new forms of Internet software that can be universally deployed and invoked using standard protocols. Services from different providers can be integrated into a composite service regardless of their locations, platforms, and/or execution speeds to implement complex business processes and transactions. In this paper, we study the end-to-end QoS issues of composite services by utilizing a QoS broker that is responsible for selecting and coordinating the individual service component. We design the service selection algorithms used by QoS brokers to construct the optimal composite service. The objective of the algorithms is to maximize the user-defined utility function value while meeting the end-to-end delay constraint. We propose two solution approaches to the service selection problem: the combinatorial approach, by modeling the problem as the Multiple Choice Knapsack Problem (MCKP), and the graph approach, by modeling the problem as the constrained shortest path problem in the graph theory. We study efficient solutions for each approach.
46251955
Service Selection Algorithms for Web Services with End-to-End QoS Constraints
Web services are new forms of Internet software that can be universally deployed and invoked using standard protocol. Services from different providers can be integrated to provide composite services. In this paper, we study the end-to-end QoS issues of composite service by utilizing a QoS broker that is responsible for coordinating the individual service component to meet the quality constraint. We design the service selection algorithms used by QoS brokers to meet end-to-end QoS constraints. The objective of the algorithms is to maximize the user-defined utility while meeting the end-to-end delay constraint. We model the problem as the multiple choice knapsack problem (MCKP) and provide efficient solutions. The algorithms are tested for their performance.
584843
Identifying Error-Prone Software&#8212;An Empirical Study
A major portion of the effort expended in developing commercial software today is associated with program testing. Schedule and/ or resource constraints frequently require that testing be conducted so as to uncover the greatest number of errors possible in the time allowed. In this paper we describe a study undertaken to assess the potential usefulness of various product-and process-related measures in identifying error-prone software. Our goal was to establish an empirical basis for the efficient utilization of limited testing resources using objective, measurable criteria. Through a detailed analysis of three software products and their error discovery histories, we have found simple metrics related to the amount of data and the structural complexity of programs to be of value for this purpose.