Vertex is a Wrapper Induction system developed at Yahoo! for extracting structured records from template-based Web pages. To operate at Web scale, Vertex employs a host of novel algorithms for (1) Grouping similar structured pages in a Web site, (2) Picking the appropriate sample pages for wrapper inference, (3) Learning XPath-based extraction rules that are robust to variations in site structure, (4) Detecting site changes by monitoring sample pages, and (5) Optimizing editorial costs by reusing rules, etc. The system is deployed in production and currently extracts more than 250 million records from more than 200 Web sites. To the best of our knowledge, Vertex is the first system to do high-precision information extraction at Web scale.

Detecting constraint violations in large-scale distributed systems has recently attracted plenty of attention from the research community due to its varied applications (security, network monitoring, etc.). Communication efficiency of these systems is a critical concern and determines their practicality. In this paper, we introduce a new set of methods called non-zero slack schemes to implement distributed SUM queries efficiently. We show, both analytically and empirically, that these methods can lead to a considerable reduction in the amount of communication. We propose three adaptive non-zero slack schemes that adapt to changing data distributions; our best scheme is a lightweight reactive scheme that probabilistically adjusts local constraints based on the occurrence of certain events (using only a periodic probability estimation). We conduct an extensive experimental study using real-life and synthetic data sets, and show that our non-zero slack schemes incur significantly less communication overhead compared to the state of the art zero slack scheme (over a 60% savings).

Monitoring is an issue of primary concern in current and next gen-eration networked systems. For example, the objective of sensor networks is to monitor their surroundings for a variety of differ-ent applications like atmospheric conditions, wildlife behavior, and troop movements among others. Similarly, monitoring in data net-works is critical not only for accounting and management, but also for detecting anomalies and attacks. Such monitoring applications are inherently continuous and distributed, and must be designed to minimize the communication overhead that they introduce. In this context we introduce and study a fundamental class of problems called “thresholded counts ” where we must return the aggregate frequency count of an event that is continuously monitored by dis-tributed nodes with a user-specified accuracy whenever the actual count exceeds a given threshold value. In this paper we propose to address the problem of thresholded counts by setting local thresholds at each monitoring node and initi-ating communication only when the locally observed data exceeds these local thresholds. We explore algorithms in two categories: static thresholds and adaptive thresholds. In the static case, we consider thresholds based on a linear combination of two alternate strategies, and show that there exists an optimal blend of the two strategies that results in minimum communication overhead. We further show that this optimal blend can be found using a steep-est descent search. In the adaptive case, we propose algorithms that adjust the local thresholds based on the observed distributions of updated information in the distributed monitoring system. We use extensive simulations not only to verify the accuracy of our algorithms and validate our theoretical results, but also to evalu-ate the performance of the two approaches. We find that both ap-proaches yield significant savings over the naive approach of per-forming processing at a centralized location. 1.

Time Sliced Optical Burst Switching is a proposed variant of optical burst switching, in which switching is done in the time domain, rather than the wavelength domain. This eliminates the need for wavelength converters, the largest single cost component of systems that switch in the wavelength domain. We examine some of the key design issues for routers that implement time sliced optical packet switching. In particular, we focus on the design of the Optical Time Slot Interchangers (OTSIs) needed to effect the required time domain switching. We introduce a novel nonblocking OTSI design and also show how blocking OTSIs can be used to implement the required switching operations. We study the performance of systems using blocking OTSIs and demonstrate that near ideal statistical multiplexing performance can be achieved using even quite inexpensive, blocking OTSI designs. These results suggest that optical technology may one day be able to provide a cost-effective alternative to electronics in packet switching systems.

Optical burst switching (OBS) is an experimental network technology that enables the construction of very high-capacity routers, using optical data paths and electronic control. We study wavelength converting switches using tunable lasers and wavelength grating routers, that are suitable for use in OBS systems and evaluate their performance. We show how the routing problem for these switches can be formulated as a combinatorial puzzle or game, in which the design of the game board corresponds to the pattern of permutation used at the input sections of the switch. We use this to show how the permutation pattern affects the performance of the switch, and to facilitate the design of permutation patterns that yield the best performance. We give upper bounds on the number of different wavelength channels that can be routed through such switches (regardless of the permutation pattern), and show that for 2×2 switches, there is a simple permutation pattern that achieves these bounds. For larger switches, randomized permutation patterns produce the best results. We study the performance of optical burst switches using wavelength converting switches based on several different permutation patterns. We also present a novel routing algorithm called the most available wavelength assignment and evaluate its benefits in improving the switch throughput. Our results show that for a typical configuration, the switch with the best permutation pattern has more than 87% of the throughput of a fully nonblocking switch.

Optical burst switching (OBS) is an experimental network technology that enables the construction of very high capacity routers, using optical data paths and electronic control. In this paper, we study two designs for wavelength converting switches that are suitable for use in optical burst switching systems and evaluate their performance. Both designs use tunable lasers to implement wavelength conversion. One is a strictly nonblocking design, that also requires optical crossbars. The second substitutes wavelength grating routers (WGR) for the optical crossbars, reducing cost, but introducing some potential for blocking. We show how the routing problem for the WGR-based switches can be formulated as a combinatorial puzzle or game, in which the design of the game board corresponds to the pattern of interconnections used to join the input sections of the switch to the output sections. We use this to show how the interconnection pattern affects the performance of the switch, and to facilitate the design of interconnection patterns that yield the best performance. Our results show that for a typical switch configuration, the WGR-based design can deliver more than 87% of the throughput of a fully nonblocking switch.