In this work we describe an entity resolution project performed at Yad Vashem, the central repository of Holocaust-era information. The Yad Vashem dataset is unique with respect to classic entity resolution, by virtue of being both massively multi-source and by requiring multi-level entity resolution. With today's abundance of information sources, this project sets an example for multi-source resolution on a big-data scale. We discuss a set of requirements that led us to choose the MFIBlocks entity resolution algorithm in achieving the goals of the application. We also provide a machine learning approach, based upon decision trees to transform soft clusters into ranked clustering of records, representing possible entities. An extensive empirical evaluation demonstrates the unique properties of this dataset, highlighting the shortcomings of current methods and proposing avenues for future research in this realm.

Many real-world graphs have complex labels on the nodes and edges. Mining only exact patterns yields limited insights, since it may be hard to find exact matches. However, in many domains it is relatively easy to define a cost (or distance) between different labels. Using this information, it becomes possible to mine a much richer set of approximate subgraph patterns, which preserve the topology but allow bounded label mismatches. We present novel and scalable methods to efficiently solve the approximate isomorphism problem. We show that approximate mining yields interesting patterns in several real-world graphs ranging from IT and protein interaction networks to protein structures.

With the advent of the Internet, it is desirable to interpret and extract useful information from the Web. One major challenge in Web interface interpretation is to discover the semantic structure underlying a Web interface. Many heuristic approaches have been developed to discover and group semantically related interface objects. However, those approaches cannot solve the problem of nonuniformity satisfactorily and are not able to tag the semantic role of each object. Distinct from existing approaches, this paper develops a robust and formal approach to recovering interface semantics using graph grammars. Because of the distinct capability of spatial specifications in the abstract syntax, the spatial graph grammar (SGG) is selected to perform the semantic grouping and interpretation of segmented screen objects. Instead of analyzing HTML source codes, we apply an efficient image-processing technology to recognize atomic interface objects from the screenshot of an interface and produce a spatial graph, which records significant spatial relations among recognized objects. A spatial graph is more concise than its corresponding document object model structure and, thus, facilitates interface analysis and interpretation. Based on the spatial graph, the SGG parser recovers the hierarchical relations among interface objects.

A configuration management database (CMDB) can be considered to be a large graph representing the IT infrastructure entities and their inter-relationships. Mining such graphs is challenging because they are large, complex, and multi-attributed, and have many repeated labels. These characteristics pose challenges for graph mining algorithms, due to the increased cost of sub graph isomorphism (for support counting), and graph isomorphism (for eliminating duplicate patterns). The notion of pattern frequency or support is also more challenging in a single graph, since it has to be defined in terms of the number of its (potentially, exponentially many) embeddings. We present CMDB-Miner, a novel two-step method for mining infrastructure patterns from CMDB graphs. It first samples the set of maximal frequent patterns, and then clusters them to extract the representative infrastructure patterns. We demonstrate the effectiveness of CMDB-Miner on real-world CMDB graphs.

We introduce a new similarity measure that is insensitive to sub-pixel misregistration. The proposed measure is essential in some differences detection scenarios. For example, in a setting where a digital reference is compared to an image, where the imaging process introduces deformations that appear as non constant misregistration between the two images. Our goal is to ignore image differences that result from misregistration and detect only the true, albeit minute, defects. In order to define a misregistration insensitive similarity, we argue that a similarity measure must respect convex combinations. We show that the well known SSIM does not hold this property and propose a modified version of SSIM that respects convex combinations. We then use this measure to define Sub-Pixel misregistration aware SSIM (SPSSIM).

We consider the following problem. Suppose that a big amount of data is distributed among several parties, so that each party misses only few pieces of data. The parties wish to perform some global computation on the data while minimizing the communication between them. This situation is common in many real-life scenarios. A naive solution to this problem is to first perform a synchronization step, letting one party learn all pieces of data, and then let this party perform the required computation locally. We study the question of obtaining better solutions to the problem, focusing mainly on the case of computing low-degree polynomials via non-interactive protocols. We present interesting connections between this problem and the well studied cryptographic problem of secret sharing. We use this connection to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing. The relation with open problems from the area of secret sharing also provides evidence for the difficulty of resolving some of the questions we leave open.

We prove new lower bounds for nearest neighbor search in the Hamming cube.Our lower bounds are for randomized, two-sided error, algorithms in Yao's cell probe model.Our bounds are in the form of a tradeoff among the number of cells, the size of a cell, and the search time.For example, suppose we are searching among n points in the d dimensional cube, we use poly(n, d) cells, each containing poly(d, log n) bits.We get a lower bound of ~2(d/log n) on the search time, a significant improvement over the recent bound of ft(log d) of Borodin et al.This should be contrasted with the upper bound of O(loglogd) for approximate search (and O(1) for a decision version of the problem; our lower bounds hold in that case).By previous results, the bounds for the cube imply similar bounds for nearest neighbor search in high dimensional Euclidean space, and for other geometric problems.