109 research outputs found
Real-time Analysis of Critical Nodes in Network Cores
No full textThe articulation points and bridges of a connected network are, respectively, the vertices and the edges whose removal disconnects the network. However, not all the articulation points (resp. bridges) are equal: from the graph theoretic perspective, there is no difference whether the removal of a vertex (resp. bridge) disconnects only one vertex from the rest of the network, or it cuts the network in two pieces. But in the monitoring of a huge network, it makes a difference. We present a real-time algorithm, analyzed in the (semi-)streaming model of computation, that is able to identify a core subset of the articulation points (resp. bridges), i.e. the ones whose removal has a big impact on the network: these are the critical nodes (resp. edges) of the network. We complement our work with an experimental evaluation of the algorithm against ten years of samples of the Autonomous System network, that confirms the effectiveness of our approach
Data processing: Reflections on ethics
No full textEthics-related aspects are becoming prominent in data management, thus the current processes for searching, querying, or analyzing data should be designed is such a way as to take into account the social problems their outcomes could bring about. In this paper we provide reections on the unavoidable ethical facets entailed by all the steps of the information life-cycle, including source selection, knowledge extraction, data integration and data analysis. Such reections motivated us to organize the First International Workshop on Processing Information Ethically (PIE)
Ethical Dimensions for Data Quality
No full textData quality is a typical ethical requirement: we could never trust a piece of information if it did
not have the typical data quality properties. Yet, we can also assert the opposite: that data should
conform to a high ethical standard, for it to be considered of good quality. Hence, the satisfaction of
the ethical requirements is actually necessary to assert the quality of a dataset, and in this paper we
propose to introduce the most common ethical requirements as dimensions of quality, grouped in an
Ethics Cluster. By now, we are more than aware that the Internet, and the worldwide extent of the
usage of IT and computers, have generated a plethora of datasets in all kinds of application areas;
this data can correspond to useful information only if it is of good quality, and let us emphasize
that it can be profitable to society only if its usage conforms to ethical principles. With a somehow
more constructive and dynamic viewpoint, in this paper we discuss the dimensions of ethics in
connection with the various phases of what we call the information extraction process [20], that is,
the process of (i) identifying the data sources containing the information of interest, (ii) collecting
the corresponding data and integrating them in order to produce a unique dataset, and (iii) applying
the appropriate information extraction methods (from the application of a simple query up to
a complex statistical, machine learning or data mining analysis). We thus advocate the need to
extend the well-established data quality framework in [5] to incorporate ethics explicitly
Real-time Anomalies Detection and Analysis of Network Structure, with application to the Autonomous System Network.
No full textThe structural analysis is the very basic tool for understanding the properties of a network. In this paper we present a (customizable) tool, able to compute in real-time the most important connectivity properties of a network, modeled as an undirected graph: connected and biconnected components, articulation points and bridges. The algorithm underlying the tool has been theoretically analyzed in the (semi-)streaming model, and has been tested with graphs up to hundreds of millions nodes and billions edges. The tool, therefore, can be employed to monitor traffic flows in medium and large networks, at real-time, and detect possible anomalies. As an application, we provide results about the structural properties of ten years of samples of the Autonomous System network, obtained from the Univ. of Oregon Route Views project, that (once again) shows the ubiquitous presence of power-law distribution
CERTEM: Explaining and Debugging Black-box Entity Resolution Systems with CERTA
No full textEntity resolution (ER) aims at identifying record pairs that refer to the same real-world entity. Recent works have focused on deep learning (DL) techniques, to solve this problem. While such works have brought tremendous enhancements in terms of effectiveness in solving the ER problem, understanding their matching predictions is still a challenge, because of the intrinsic opaqueness of DL based solutions. Interpreting and trusting the predictions made by ER systems is crucial for humans in order to employ such methods in decision making pipelines. We demonstrate certem an explanation system for ER based on certa, a recently introduced explainability framework for ER, that is able to provide both saliency explanations, which associate each attribute with a saliency score, and counterfactual explanations, which provide examples of values that can flip a prediction. In this demonstration we will showcase how certem can be effectively employed to better understand and debug the behavior of state-of-the-art DL based ER systems on data from publicly available ER benchmarks
Efficient and effective ER with progressive blocking
No full textBlocking is a mechanism to improve the efficiency of entity resolution (ER) which aims to quickly prune out all non-matching record pairs. However, depending on the distributions of entity cluster sizes, existing techniques can be either (a) too aggressive, such that they help scale but can adversely affect the ER effectiveness, or (b) too permissive, potentially harming ER efficiency. In this paper, we propose a new methodology of progressive blocking (pBlocking) to enable both efficient and effective ER, which works seamlessly across different entity cluster size distributions. pBlocking is based on the insight that the effectiveness–efficiency trade-off is revealed only when the output of ER starts to be available. Hence, pBlocking leverages partial ER output in a feedback loop to refine the blocking result in a data-driven fashion. Specifically, we bootstrap pBlocking with traditional blocking methods and progressively improve the building and scoring of blocks until we get the desired trade-off, leveraging a limited amount of ER results as a guidance at every round. We formally prove that pBlocking converges efficiently (O(nlog 2n) time complexity, where n is the total number of records). Our experiments show that incorporating partial ER output in a feedback loop can improve the efficiency and effectiveness of blocking by 5× and 60%, respectively, improving the overall F-score of the entire ER process up to 60%
A meta-algorithm for finding large k-plexes
No full textWe focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration
BEER: Blocking for Effective Entity Resolution
No full textBlocking is a key component of Entity Resolution (ER) that aims to improve efficiency by quickly pruning out non-matching record pairs. However, depending on the noise in the dataset and the distribution of entity cluster sizes, existing techniques can be either (a) too aggressive, such that they help scale but can adversely affect the ER effectiveness, or (b) too permissive, potentially harming ER efficiency. We propose a new methodology of progressive blocking that enables both efficient and effective ER and works across different entity cluster size distributions without manual fine tuning. In this paper, we demonstrate BEER (Blocking for Effective Entity Resolution), the first end-to-end system that leverages intermediate ER output in a feedback loop to refine the blocking result in a data-driven fashion, thereby enabling effective entity resolution. BEER allows the user to explore the different components of the ER pipeline, analyze the effectiveness of alternative blocking techniques and understand the interaction between blocking and ER. BEER supports visualization of the different entities present in a block, explains the change in blocking output with every round of feedback and allows the end-user to interactively compare different techniques. BEER has been developed as open-source software; the code and the demonstration video are available at beer-system.github.io
Engineering color barcode algorithms for mobile applications
No full textThe wide availability of on-board cameras in mobile devices and the increasing demand for higher capacity have recently sparked many new color barcode designs. Unfortunately, color barcodes are much more prone to errors than black and white barcodes, due to the chromatic distortions introduced in the printing and scanning process. This is a severe limitation: the higher the expected error rate, the more redundancy is needed for error correction (in order to avoid failures in barcode reading), and thus the lower the actual capacity achieved. Motivated by this, we design, engineer and experiment algorithms for decoding color barcodes with high accuracy. Besides tackling the general trade-off between error correction and data density, we address challenges that are specific to mobile scenarios and that make the problem much more complicated in practice. In particular, correcting chromatic distortions for barcode pictures taken from phone cameras appears to be a great challenge, since pictures taken from phone cameras present a very large variation in light conditions. We propose a new barcode decoding algorithm based on graph drawing methods, which is able to run in few seconds even on low-end computer architectures and to achieve nonetheless high accuracy in the recognition phase. The main idea of our algorithm is to perform color classification using force-directed graph drawing methods: barcode elements which are very close in color will attract each other, while elements that are very far will repulse each other. © 2014 Springer International Publishing
- …
