Attribute value extraction refers to the task of identifying values of an attribute of interest from product information. It is an important research topic which has been widely studied in e-Commerce and relation learning. There are two main limitations in existing attribute value extraction methods: scalability and generalizability. Most existing methods treat each attribute independently and build separate models for each of them, which are not suitable for large scale attribute systems in real-world applications. Moreover, very limited research has focused on generalizing extraction to new attributes.

In this paper, we consider the problem of constructing a comprehensive database of events taking place around the world. Events include small hyper-local events like farmer's markets, neighborhood garage sales, as well as larger concerts and festivals. Designing a high-precision and high-recall event extractor from unstructured pages across the whole web is a challenging problem. We cannot resort overly to domain-specific strategies since it needs to work on all web pages, including on new domains; we need to account for variations in page layouts and structure across websites. Further, we need to deal with low-quality pages on the web with limited structure. We have built an ML-powered extraction system to solve this problem, using schema.org annotations as training data. Our extraction system operates in two phases. In the first phase, we generate raw event information from individual web pages. To do this, an \em event page classifier predicts if a web page contains any event information; this is then followed by a \em single/multiple classifier that decides if the page contains a single event or multiple events; the first phase concludes by applying \em event extractors that extract the key fields of a public event (the title, the date/time information, and the location information). In the second phase, we further improve the extraction quality via three novel algorithms, \em repeated patterns, \em event consolidation and \em wrapper induction, which are designed to use the raw event extractions as input and generate events whose quality is significantly higher. We evaluate our extraction models on two large scale publicly available web corpus, Common Crawl and ClueWeb12. Experimental analysis shows that our methodology achieves over 95% extraction precision and recall on both datasets.

We offer a novel classification of voting methods popular in social choice theory. Our classification is based on the more general problem of rank aggregation in which, beyond electing a winner, we also seek to compute an aggregate ranking of all the candidates; moreover, our classification is offered from a computational perspective---based on whether or not the voting method generalizes to an aggregation algorithm guaranteed to produce solutions that are near optimal in minimizing the distance of the aggregate ranking to the voters' rankings with respect to one of three well-known distance measures: the Kendall tau, the Spearman footrule, and the Spearman rho measures. We show that methods based on the average rank of the candidates (Borda counting), on the median rank of the candidates, and on the number of pairwise-majority wins (Copeland) all satisfy the near-optimality criterion with respect to each of these distance measures. On the other hand, we show that natural extensions of each of plurality voting, single transferable voting, and Simpson--Kramer minmax voting do not satisfy the near-optimality criterion with respect to these distance measures.

We investigate a class of methods that we call "social sampling," where participants in a poll respond with a summary of their friends' putative responses to the poll. Social sampling leads to a novel trade-off question: the savings in the number of samples(roughly the average degree of the network of participants) vs. the systematic bias in the poll due to the network structure.

We demonstrate how a recent model of social networks ("Affiliation Networks", [21]) offers powerful cues in local routing within social networks, a theme made famous by sociologist Milgram's "six degrees of separation" experiments. This model posits the existence of an "interest space" that underlies a social network; we prove that in networks produced by this model, not only do short paths exist among all pairs of nodes but natural local routing algorithms can discover them effectively. Specifically, we show that local routing can discover paths of length O(log2 n) to targets chosen uniformly at random, and paths of length O(1) to targets chosen with probability proportional to their degrees. Experiments on the co-authorship graph derived from DBLP data confirm our theoretical results, and shed light into the power of one step of lookahead in routing algorithms for social networks.

In the last decade, structural properties of several naturally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution.

No abstract available.

We initiate a novel study of clustering problems. Rather than specifying an explicit objective function to optimize, our framework allows the user of clustering algorithm to specify, via a first-order formula, what constitutes an acceptable clustering to them. While the resulting genre of problems includes, in general, NP-complete problems, we highlight three specific first-order formulae, and provide efficient algorithms for the resulting clustering problems.

We show that the Multicut, Sparsest-Cut, and Min-2CNF ≡ Deletion problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of $$\Omega(\sqrt{\log \log n}).$$

We provide a comprehensive picture of how to compare partial rankings, that is, rankings that allow ties. We propose several metrics to compare partial rankings and prove that they are within constant multiples of each other.

We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF/spl equiv/DELETION problems are NP-hard to approximate within every constant factor, assuming the unique games conjecture of Khot [STOC, 2002]. A quantitatively stronger version of the conjecture implies inapproximability factor of /spl Omega/(log log n).

We propose a novel mechanism for routing and bandwidth allocation that exploits the selfish and rational behavior of flows in a network. Our mechanism leads to allocations that simultaneously optimize throughput and fairness criteria. We analyze the performance of our mechanism in terms of the induced Nash equilibrium. We compare the allocations at the Nash equilibrium with throughput-optimal allocations as well as with fairness-optimal allocations. Our mechanism offers a smooth trade-off between these criteria, and allows us to produce allocations that are approximately optimal with respect to both. Our mechanism is also fairly simple and admits an efficient distributed implementation.

We develop an algorithmic framework to decompose a collection of time-stamped text documents into semantically coherent threads. Our formulation leads to a graph decomposition problem on directed acyclic graphs, for which we obtain three algorithms --- an exact algorithm that is based on minimum cost flow and two more efficient algorithms based on maximum matching and dynamic programming that solve specific versions of the graph decomposition problem. Applications of our algorithms include superior summarization of news search results, improved browsing paradigms for large collections of text-intensive corpora, and integration of time-stamped documents from a variety of sources. Experimental results based on over 250,000 news articles from a major newspaper over a period of four years demonstrate that our algorithms efficiently identify robust threads of varying lengths and time-spans.

We introduce the Multi-Structural Database, a new data framework to support efficient analysis of large, complex data sets. An instance of the model consists of a set of data objects, together with a schema that specifies segmentations of the set of data objects according to multiple distinct criteria (e.g., into a taxonomy based on a hierarchical attribute). Within this model, we develop a rich set of analytical operations and design highly efficient algorithms for these operations. Our operations are formulated as optimization problems, and allow the user to analyze the underlying data in terms of the allowed segmentations.

Mining massive temporal data streams for significant trends, emerging buzz, and unusually high or low activity is an important problem with several commercial applications. In this paper, we propose a framework based on relational records and metric spaces to study such problems. Our framework provides the necessary mathematical underpinnings for this genre of problems, and leads to efficient algorithms in the stream/sort model of massive data sets (where the algorithm makes passes over the data, computes a new stream on the fly, and is allowed to sort the intermediate data). Our algorithm makes novel use of metric approximations in the data stream context, and highlights the role of hierarchical organization of large data sets in designing efficient algorithms in the stream/sort model.

We propose an efficient and scalable scheme for bandwidth reservation and monitoring. Our scheme is based on a reserve-and-refresh strategy [I. Stoica and Hui Zhang, 19994], [S. Machiraju et al., 2002], where each flow is periodically refreshed in its initial reservation. We propose novel algorithms to handle various forms of misbehavior, e.g., attempting to refresh more than what was reserved (control plane), exceeding reservations (data plane). Our solutions are based on data stream algorithms that are extremely efficient in terms of memory requirements and time required to process each packet. Specifically, we compute very short sketches of packet traffic with which we can provably guarantee that no more than a tiny fraction of the bandwidth is lost to misbehaving flows. Since our solutions are robust, incrementally deployable, and have very low time/space requirements, we believe they are ideally suited for supporting QoS, flow and congestion control, and more generally, for bandwidth management in active network architectures.

Equitable bandwidth allocation is essential when QoS requirements and purchasing power vary among users. To this end, we present a mechanism for bandwidth allocation based on differential pricing. In our model, the QoS vs. cost trade-off induces a minimum acceptable allocation, a maximum acceptable allocation, and a unique optimal allocation for each user. We analyze the fairness and truthfulness properties of our mechanism from a game-theoretic perspective. We show that it produces allocations that provably satisfy a variant of the classical notion of max-min fairness. It ensures that flows with higher QoS requirements need to pay at higher rates to increase their likelihood of being served. Furthermore, the Nash equilibrium induced by our mechanism leads to allocations that are comparable to "socially optimal" allocations; hence users gain very little by being untruthful.

We present a graph-theoretic approach to discover storylines from search results. Storylines are windows that offer glimpses into interesting themes latent among the top search results for a query; they are different from, and complementary to, clusters obtained through traditional approaches. Our framework is axiomatically developed and combinatorial in nature, based on generalizations of the maximum induced matching problem on bipartite graphs. The core algorithmic task involved is to mine for signature structures in a robust graph representation of the search results. We present a very fast algorithm for this task based on local search. Experiments show that the collection of storylines extracted through our algorithm offers a concise organization of the wealth of information hidden beyond the first page of search results.

Rank aggregation has recently been proposed as a useful abstraction that has several applications, including meta-search, synthesizing rank functions from multiple indices, similarity search, and classification. In database applications (catalog searches, fielded searches, parametric searches, etc.), the rankings are produced by sorting an underlying database according to various fields. Typically, there are a number of fields that each have very few distinct values, and hence the corresponding rankings have many ties in them. Known methods for rank aggregation are poorly suited to this context, and the difficulties can be traced back to the fact that we do not have sound mathematical principles to compare two partial rankings, that is, rankings that allow ties.In this work, we provide a comprehensive picture of how to compare partial rankings, We propose several metrics to compare partial rankings, present algorithms that efficiently compute them, and prove that they are within constant multiples of each other. Based on these concepts, we formulate aggregation problems for partial rankings, and develop a highly efficient algorithm to compute the top few elements of a near-optimal aggregation of multiple partial rankings. In a model of access that is suitable for databases, our algorithm reads essentially as few elements of each partial ranking as are necessary to determine the winner(s).

We propose a novel approach to performing efficient similarity search and classification in high dimensional data. In this framework, the database elements are vectors in a Euclidean space. Given a query vector in the same space, the goal is to find elements of the database that are similar to the query. In our approach, a small number of independent "voters" rank the database elements based on similarity to the query. These rankings are then combined by a highly efficient aggregation algorithm. Our methodology leads both to techniques for computing approximate nearest neighbors and to a conceptually rich alternative to nearest neighbors.

We show the following new lower bounds in two concrete complexity models:

The social impact from the World Wide Web cannot be underestimated, but technologies used to build the Web are also revolutionizing the sharing of business and government information within intranets. In many ways the lessons learned from the Internet carry over directly to intranets, but others do not apply. In particular, the social forces that guide the development of intranets are quite different, and the determination of a "good answer" for intranet search is quite different than on the Internet. In this paper we study the problem of intranet search. Our approach focuses on the use of rank aggregation, and allows us to examine the effects of different heuristics on ranking of search results.

Motivated by several applications, we introduce various distance measures between "top k lists." Some of these distance measures are metrics, while others are not. For each of these latter distance measures, we show that they are "almost" a metric in the following two seemingly unrelated aspects: (i) they satisfy a relaxed version of the polygonal (hence, triangle) inequality, and (ii) there is a metric with positive constant multiples that bound our measure above and below. This is not a coincidence---we show that these two notions of almost being a metric are the same. Based on the second notion, we define two distance measures to be equivalent if they are bounded above and below by constant multiples of each other. We thereby identify a large and robust equivalence class of distance measures. Besides the applications to the task of identifying good notions of (dis)similarity between two top k lists, our results imply polynomial-time constant-factor approximation algorithms for the rank aggregation problem with respect to a large class of distance measures. (A correction for this article has been appended to the pdf file.)

For every constant $\epsilon > 0$, we obtain a $2^{O(n(1/2 + 1/\epsilon))}$ time randomized algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of $n^{3 + \epsilon}$.

We present a 2/sup O(n)/ time Turing reduction from the closest lattice vector problem to the shortest lattice vector problem. Our reduction assumes access to a subroutine that solves SVP exactly and a subroutine to sample short vectors from a lattice, and computes a (1+/spl epsi/)-approximation to CVP As a consequence, using the SVP algorithm from (Ajtai et al., 2001), we obtain a randomized 2[O(1+/spl epsi//sup -1/)n] algorithm to obtain a (1+/spl epsi/)-approximation for the closest lattice vector problem in n dimensions. This improves the existing time bound of O(n!) for CVP achieved by a deterministic algorithm in (Blomer, 2000).

We use tools and techniques from information theory to study communication complexity problems in the one-way and simultaneous communication models. Our results include: (1) a tight characterization of multi-party one-way communication complexity for product distributions in terms of VC-dimension and shatter coefficients; (2) an equivalence of multi-party one-way and simultaneous communication models for product distributions; (3) a suite of lower bounds for specific functions in the simultaneous communication model, most notably an optimal lower bound for the multi-party set disjointness problem of Alon et al. (1999) and for the generalized addressing function problem of Babai et al. (1996) for arbitrary groups. Methodologically, our main contribution is rendering communication complexity problems in the framework of information theory. This allows us access to the powerful calculus of information theory and the use of fundamental principles such as Fano's inequality and the maximum likelihood estimate principle.

We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on the communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving (conditional) information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.

Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model [16, 2] is a natural setting to design efficient algorithms. We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation to within a factor of ffl. The best space bound we achieve for this problem is O(log n log log n) through a deterministic algorithm. In contrast, we derive an \\Omega\\Gamma n) lower bound for randomized exact computation for this problem; thus approximation is essential. For the more general problem of approximating the number of inversions between two permutations, we obtain a randomized O( p n log n)-space algorithm. For approximating the number of inversions in a general list, we give a randomized O( p n log 2 n)-space two-pass algorithm. In contrast, we derive \\Omega\\Gamma n) lower bounds for deterministic approximate computation for these problems; thus randomization is essential. All our algorithms use only O(log n) time per data item. Our result for approximating the number of inversions in a permutation is unique and surprising in the following aspect: all of the existing streaming algorithms require randomization in a crucial way, whereas our algorithms are deterministic! 1

Algorithmic tools for searching and mining the Web are becoming increasingly sophisticated and vital. In this context, algorithms that use and exploit structural information about the Web perform better than generic methods in both efficiency and reliability.We present an extensive characterization of the graph structure of the Web, with a view to enabling high-performance applications that make use of this structure. In particular, we show that the Web emerges as the outcome of a number of essentially independent stochastic processes that evolve at various scales. A striking consequence of this scale invariance is that the structure of the Web is "fractal"---cohesive subregions display the same characteristics as the Web at large. An understanding of this underlying fractal nature is therefore applicable to designing data services across multiple domains and scales.We describe potential applications of this line of research to optimized algorithm design for Web-scale data analysis.

We present a randomized 2^{O(n)} time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. The best known time upper bound for this problem was 2^{O(n\log n)} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.

We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form \genfunc, where \domain and \range are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x_i that any sampling algorithm needs to query to approximate f(x_1,\ldots,x_n).We define two quantitative properties of functions --- the it block sensitivity and the minimum Hellinger distance --- that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds.We also point out some connections between sampling and streaming algorithms and lossy compression schemes.

We consider the problem of combining ranking results from various sources. In the context of the Web, the main applications include building meta-search engines, combining ranking functions, selecting documents based on multiple criteria, and improving search precision through word associations. We develop a set of techniques for the rank aggregation problem and compare their performance to that of well-known methods. A primary goal of our work is to design rank aggregation techniques that can e ectively combat \\spam, " a serious problem in Web searches. Experiments show that our methods are simple, e cient, and e ective.

The Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical observations on the Web. Our graph models differ from the traditional G/sub n,p/ models in two ways: 1. Independently chosen edges do not result in the statistics (degree distributions, clique multitudes) observed on the Web. Thus, edges in our model are statistically dependent on each other. 2. Our model introduces new vertices in the graph as time evolves. This captures the fact that the Web is changing with time. Our results are two fold: we show that graphs generated using our model exhibit the statistics observed on the Web graph, and additionally, that natural graph models proposed earlier do not exhibit them. This remains true even when these earlier models are generalized to account for the arrival of vertices over time. In particular, the sparse random graphs in our models exhibit properties that do not arise in far denser random graphs generated by Erdos-Renyi models.

The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow exponentially with time. There are many reasons—mathematical, sociological, and commercial—for studying the evolution of this graph. We first review a set of algorithms that operate on the Web graph, addressing problems from Web search, automatic community discovery, and classification. We then recall a number of measurements and properties of the Web graph. Noting that traditional random graph models do not explain these observations, we propose a new family of random graph models.

Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P, that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck. We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some nonlinear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems.

We show how to construct proof systems for NP languages where a deterministic polynomial-time verifier can check membership, given any N/sup (2/3)+/spl epsi// bits of an N-bit witness of membership. We also provide a slightly superpolynomial time proof system where the verifier can check membership, given only N/sup (1/2)+/spl epsi// bits of an N-bit witness. These pursuits are motivated by the work of Gal et. al. (1997). In addition, we construct proof systems where a deterministic polynomial-time verifier can check membership, given an N-bit string that agrees with a legitimate witness on just (N/2)+N/sup (4/5)+/spl epsi// bits. Our results and framework have applications for two related areas of research in complexity theory: proof systems for NP, and the relative power of Cook reductions and Karp-Levin type reductions. Our proof techniques are based on algebraic coding theory and small sample space constructions.

We show that the problem of deciding whether a given rational lattice L has a vector of length less than some given value r is NP-hard under randomized reductions, even under the promise that L has exactly zero or one vector of length less than r.

The authors consider the problem of designing self-testers/self-correctors for functions defined by linear recurrences. They present the first complete package of efficient and simple self-testers, self-correctors, and result-checkers for such functions. The results are proved by demonstrating an efficient reduction from this problem to the problem of testing linear functions over certain matrix groups. The tools include spectral analysis of matrices over finite fields, and various counting arguments that extend known techniques. The matrix twist yields simple and efficient self-testers for all linear recurrences. They also show a technique of using convolution identities to obtain very simple self-testers and self correctors. Their techniques promise new and efficient ways of testing VLSI chips for applications in control engineering, signal processing, etc. An interesting consequence of their methods is a completely new and randomness-efficient self-tester for polynomials over finite fields and rational domains. In particular the self-tester for polynomials over rational domains overcomes a main drawback of the result of Rubinfeld and Sudan (1992)-the need for a test domain of much larger size and of much finer precision.