This paper explores combinatorial optimization for problems of max-weight graph matching on multi-partite graphs, which arise in integrating multiple data sources. In the most common two-source case, it is often desirable for the final matching to be one-to-one; the database and statistical record linkage communities accomplish this by weighted bipartite graph matching on similarity scores. Such matchings are intuitively appealing: they leverage a natural global property of many real-world entity stores-that of being nearly deduped-and are known to provide significant improvements to precision and recall. Unfortunately, unlike the bipartite case, exact max-weight matching on multi-partite graphs is known to be NP-hard. Our two-fold algorithmic contributions approximate multi-partite max-weight matching: our first algorithm borrows optimization techniques common to Bayesian probabilistic inference; our second is a greedy approximation algorithm. In addition to a theoretical guarantee on the latter, we present comparisons on a real-world entity resolution problem from Bing significantly larger than typically found in the literature, on publication data, and on a series of synthetic problems. Our results quantify significant improvements due to exploiting multiple sources, which are made possible by global one-to-one constraints linking otherwise independent matching sub-problems. We also discover that our algorithms are complementary: one being much more robust under noise, and the other being simple to implement and very fast to run.

We consider a serious, previously-unexplored challenge facing almost all approaches to scaling up entity resolution (ER) to multiple data sources: the prohibitive cost of labeling training data for supervised learning of similarity scores for each pair of sources. While there exists a rich literature describing almost all aspects of pairwise ER, this new challenge is arising now due to the unprecedented ability to acquire and store data from online sources, interest in features driven by ER such as enriched search verticals, and the uniqueness of noisy and missing data characteristics for each source. We show on real-world and synthetic data that for state-of-the-art techniques, the reality of heterogeneous sources means that the number of labeled training data must scale quadratically in the number of sources, just to maintain constant precision/recall. We address this challenge with a brand new transfer learning algorithm which requires far less training data (or equivalently, achieves superior accuracy with the same data) and is trained using fast convex optimization. The intuition behind our approach is to adaptively share structure learned about one scoring problem with all other scoring problems sharing a data source in common. We demonstrate that our theoretically-motivated approach improves upon existing techniques for multi-source ER.

In practical data integration systems, it is common for the data sources being integrated to provide conflicting information about the same entity. Consequently, a major challenge for data integration is to derive the most complete and accurate integrated records from diverse and sometimes conflicting sources. We term this challenge the truth finding problem . We observe that some sources are generally more reliable than others, and therefore a good model of source quality is the key to solving the truth finding problem. In this work, we propose a probabilistic graphical model that can automatically infer true records and source quality without any supervision. In contrast to previous methods, our principled approach leverages a generative process of two types of errors (false positive and false negative) by modeling two different aspects of source quality. In so doing, ours is also the first approach designed to merge multi-valued attribute types. Our method is scalable, due to an efficient sampling-based inference algorithm that needs very few iterations in practice and enjoys linear time complexity, with an even faster incremental variant. Experiments on two real world datasets show that our new method outperforms existing state-of-the-art approaches to the truth finding problem.

User authored stories will always be the best stories, and authoring tools will continue to be developed. However, a digital lifetime capture permits storytelling via a lightweight markup structure, combined with location, sensor and usage data. In this paper we describe support in the MyLifeBits system for such an approach, along with some simple authoring tools.

Within five years, our personal computers with terabyte disk drives will be able to store everything we read, write, hear, and many of the images we see including video. Vannevar Bush outlined such a system in his famous 1945 Memex article [1]. For the last four years we have worked on MyLifeBits www.MyLifeBits.com http://www.MyLifeBits.com, a system to digitally store everything from one's life, including books, articles, personal financial records, memorabilia, email, written correspondence, photos(time, location taken), telephone calls, video, television programs, and web pages visited. We recently added content from personal devices that automatically record photos and audio.The project started with the capture of Bell's content [2], followed by an effort to explore the use of the SQL database for storage and retrieval. Work has continued along these lines to extend content capture from every useful source e.g. a meeting capture system. The second phase of the project includes the design of tools and links for annotation, collections, cluster analysis, facets for characterizing the content, creation of timelines and stories, and other inherent database related capabilities, e.g. the ability to pivot on an event or photo or person to retrieve linked information [3]. Ideally we would like to have a system that would read every document, extract meta-data(e.g. Dublin Core) and classify it using multiple ontologies, faceted classifications, or the relevant.While such a system has implications for future computing devices and their users, these systems will only exist if we can effectively utilize the vast personal stores. Although our system is exploratory, the Stuff I've Seen system [4] demonstrates the utility and necessity of easy search and access to one's own data. Other research efforts with similar goals relating to personal information include Haystack [5], LifeStreams [6], and the UK "Memories for Life" Grand Challenge.There are serious research issues beyond the problem of making the information useful through rapid and easy retrieval.The "Dear Appy" problem ("Dear Appy, My application, or platform, or media left me unreadable. Signed, Lost Data") is unsettling to archivists and computer professionals -and must be solved.Just navigating the stored life of individual would at first glance appear to take almost a lifetime to sift through. While we are making progress in the capture of less traditionally archived content(e.g. meetings, phone calls & video), automatic interpretation and index of voice are illusive. MyLifeBits is currently focused on retrieval including the hopefully automatic, addition of meta-data e.g. document type identification, high level knowledge. While such data is essential for the archivist, it is unclear how useful such meta-data is to a one's own information; without such higher level knowledge and concepts, the vast amount of raw bits may be completely unusable.The most cited problem of personal archives is the control of the content including personal security, together with joint ownership of content by other individuals and organizations. In many corporations, periodic expunging of documents is the standard. Similarly, the aspects of a person's life not available in public documents is owned by the organization and all documents may have to be tagged in such a way that it can be expunged, if necessary, when an individual is no longer part of the organization. The HPPA law in the US and even more stringent privacy laws in other counties have major implications for personal stores.

MyLifeBits is a project to fulfill the Memex vision first posited by Vannevar Bush in 1945. It is a system for storing all of one's digital media, including documents, images, sounds, and videos. It is built on four principles: (1) collections and search must replace hierarchy for organization (2) many visualizations should be supported (3) annotations are critical to non-text media and must be made easy, and (4) authoring should be via transclusion.

There are many scenarios in which the same data must be delivered over a packet switched network to a large set of receivers. The Internet enables efficient multipoint transmissions through IP multicast by allowing data transmission to all receivers with a single send. Most approaches to scalable reliable multicast utilize receiver-oriented retransmissions. Defining an API for receiver-oriented reliable multicast is difficult because it is not clear how to manage the sender's cache and to schedule repairs. We outline an approach to defining an API based on logical cache persistence that addresses these problems. We also we explore the issues involved in defining an API for reliable multicast protocol on the Internet that can scale to millions of receivers.

No abstract available.

This paper establishes some fundamental principles for the retrieval and storage of delay-sensitive multimedia data. Delay-sensitive data include digital audio, animations, and video. Retrieval of these data types from secondary storage has to satisfy certain time constraints in order to be acceptable to the user. The presentation is based on digital audio in order to provide intuition to the reader, although the results are applicable to all delay-sensitive data. A theoretical framework is developed for the real-time requirements of digital audio playback. We show how to describe these requirements in terms of the consumption rate of the audio data and the nature of the data-retrieval rate from secondary storage. Making use of this framework, bounds are derived for buffer space requirements for certain common retrieval scenarios. Storage placement strategies for multichannel synchronized data are then categorized and examined. The results presented in this paper are basic to any playback of delay-sensitive data and should assist the multimedia system designer in estimating hardware requirements and in evaluating possible design choices.