nils-herrmann/clean_scirepeval huggingface dataset:
Deterministic network coding by matrix completion

We present a new deterministic algorithm to construct network codes for multicast problems, a particular class of network information ow problems. Our algorithm easily generalizes to several variants of multicast problems. Our approach is based on a new algorithm for maximum-rank completion of mixed matrices---taking a matrix whose entries are a mixture of numeric values and symbolic variables, and assigning values to the variables so as to maximize the resulting matrix rank. Our algorithm is faster than existing deterministic algorithms and can operate over a smaller field.
Xenon: An RDF Stylesheet Ontology

information to bear from diverse sources t o automate tedious processes for the user is a key tenet of th e Semantic Web vision. In previous papers we argued that visualizi ng semantically-connected corpora is not only a prime example of one of these processes but is also a critical probl em that must be solved to gain acceptance from the broader community as to the benefits of RDF. In this paper we elaborate on the specific topic of ontologies for describing how resources should b e presented to the user. We propose the creation of an RDF stylesh eet language, reusing many of the key ideas of the XSL Transformations language (XSLT), but incorporating the requirement that when multiple ontologies are used in the description of a resource to be presented, multiple stylesheets, potentially from d ifferent authors, will need to be composed. This notion of enabling heterogeneous composition motivates the definition of our basic building blo ck concepts of view and lens. In addition to abstractly characterizing our notion of an RDF stylesheet, we also describe o ur concrete instantiation of these ideas in the Xenon ontology. Finally, we give a concrete example illustrating how our styles heet mechanisms enable developers to easily produce both HTML- based and custom rich client-based browsers for het erogeneous datasets.
OverCite: A Cooperative Digital Research Library

CiteSeer is a well-known online resource for the computer science research community, allowing users to search and browse a large archive of research papers. Unfortunately, its current centralized incarnation is costly to run. Although members of the community would presumably be willing to donate hardware and bandwidth at their own sites to assist CiteSeer, the current architecture does not facilitate such distribution of resources. OverCite is a proposal for a new architecture for a distributed and cooperative research library based on a distributed hash table (DHT). The new architecture will harness resources at many sites, and thereby be able to support new features such as document alerts and scale to larger data sets.
Brief announcement: on the expected overpayment of VCG mechanisms in large networks

The VCG mechanism for buying a path from s to t in a network with selfish edges, selects the lowest-cost path (LCP) and pays each edge e on the path the edge’s cost plus a bonus equal to the increase in cost of the lowest-cost path from s to t if edge e were omitted from the graph G, that is payment(e, s, t) = cost(e)+LCP (G− e, s, t)− LCP (G, s, t). These payments are unacceptably high in some graphs containing two node-disjoint paths, and there are few positive results which prove small upper bounds on the expected payments in large and more realistic networks [4, 1]. In this paper, we give an improvement on the VCG overpayment bound of Mihail, Papadimitriou and Saberi  for random graphs. As a corollary, we show that the overpayment is not necessarily correlated with the competitiveness of a graph (measured, for example, by the number of node-disjoint paths between a source-destination pair ), and it is not necessarily correlated with the size of the graph, contrary to the conjecture in Mihail et al.  that the overpayment in random graphs Gn,p is Θ(1/np). Our results show that the overpayment is low when there are two almost equally short paths between the source and destination; the presence of more edges or more competition does not necessarily reduce it and may even hurt it.
Magnet: supporting navigation in semistructured data environments

With the growing importance of systems containing arbitrary semi-structured relationships, the need for supporting users searching in such repositories has grown. Currently support for users' search needs either has required domain-specific user interfaces or has required users to be schema experts. We have developed a general-purpose tool that offers users helpful navigation and refinement options for seeking information in these semistructured repositories. We show how a tool can be built without requiring domain-specific assumptions about the information being explored. In addition to describing a general approach to the problem, we provide a set of natural, general-purpose refinement tactics, many generalized from past work on textual information retrieval.
Incremental exploratory visualization of relationships in large codebases for program comprehension

As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this demonstration, we present a tool, Relo that supports users' understanding by allowing interactive exploration of code. As the developer explores relationships found in the code, Relo builds and automatically manages a visualization mirroring the developer's mental model, allowing them to group viewed artifacts or use the viewed items to ask the system for further exploration suggestions.
Network Coding for Wireless Applications: A Brief Tutorial

The advent of network coding promises to change many aspects of networking. Network coding moves away from the classical approach of networking, which treats networks as akin to physical transportation systems. We overview some of the main features of network coding that are most relevant to wireless networks. In particular, we discuss the fact that random distributed network coding is asymptotically optimal for wireless networks with and without packet erasures. These results are extremely general and allow packet loss correlation, such as may occur in fading wireless channels. The coded network lends itself, for multicast connections, to a cost optimization which not only outperforms traditional routing tree-based approaches, but also lends itself to a distributed implementation and to a dynamic implementation when changing conditions, such as mobility, arise. We illustrate the performance of such optimization methods for energy efficiency in wireless networks and propose some new directions for research in the area.
Thresher: automating the unwrapping of semantic content from the World Wide Web

We describe Thresher, a system that lets non-technical users teach their browsers how to extract semantic web content from HTML documents on the World Wide Web. Users specify examples of semantic content by highlighting them in a web browser and describing their meaning. We then use the tree edit distance between the DOM subtrees of these examples to create a general pattern, or wrapper, for the content, and allow the user to bind RDF classes and predicates to the nodes of these wrappers. By overlaying matches to these patterns on standard documents inside the Haystack semantic web browser, we enable a rich semantic interaction with existing web pages, "unwrapping" semantic data buried in the pages' HTML. By allowing end-users to create, modify, and utilize their own patterns, we hope to speed adoption and use of the Semantic Web and its applications.
DoS: Fighting fire with fire

We consider DoS attacks on servers in which attackers’ requests are indistinguishable from legitimate requests. Most current defenses against this class of attack rely on legitimate users in aggregate having more of some resource (CPU cycles, memory cycles, human attention, etc.) than attackers. A server so defended asks prospective clients to prove their legitimacy by spending some of this resource. We adopt this general approach but use bandwidth as the constrained resource. Specifically, we argue that when a server is attacked, it should: (1) prevent overloading by limiting the incoming rate of requests (and dropping all others) and (2) encourage its legitimate clients to fight back with aggressive retransmission. This approach forces all clients to spend bandwidth to receive service, and the legitimate clients, with their greater aggregate bandwidth, will receive the bulk of the service.
Subjective-Cost Policy Routing

We study a model of path-vector routing in which nodes’ routing policies are based on subjective cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate the minimum cost closely. These hardness results hold even for very restricted classes of subjective costs. We then consider a model in which the subjective costs are based on the relative importance nodes place on a small number of objective cost measures. We show that a small number of confluent routing trees is sufficient for each node to have a route that nearly minimizes its subjective cost. We show that this scheme is trivially strategy proof and that it can be computed easily with a distributed algorithm. Furthermore, we prove a lower bound on the number of trees required to contain a (1 + )-approximately optimal route for each node and show that our scheme is nearly optimal in this respect.
Semantic Web Applications

Although a lot of information has become readily accessible and necessary for daily work, the current infrastructure for managing information is ill-suited for information-oriented activities: information and functionality is scattered across applications and websites, making it difficult to aggregate and reuse just the right set of content and operations required for unique user tasks. In this paper we discuss a collection of tools built into the Haystack information management platform that address many of the shortcomings of current applications, and allow composing reusable fragments of information from the Semantic Web and the operations that manipulate them into a task workspace tailored to the user and the task. Users can change the workspace to immediately meet changing requirements to easily include, remove or reuse information in multiple tasks simultaneously. The time that a user invests for the initial setup and occasional updates to the workspace is amortized over the numerous times he or she returns to the task, and all relevant information resources are co-located and ready to use.
Piggy Bank: Experience the Semantic Web Inside Your Web Browser

The Semantic Web Initiative envisions a Web wherein information is offered free of presentation, allowing more effective exchange and mixing across web sites and across web pages. But without substantial Semantic Web content, few tools will be written to consume it; without many such tools, there is little appeal to publish Semantic Web content. 
 
To break this chicken-and-egg problem, thus enabling more flexible informa-tion access, we have created a web browser extension called Piggy Bankthat lets users make use of Semantic Web content within Web content as users browse the Web. Wherever Semantic Web content is not available, Piggy Bank can invoke screenscrapers to re-structure information within web pages into Semantic Web format. Through the use of Semantic Web technologies, Piggy Bank provides direct, immediate benefits to users in their use of the existing Web. Thus, the ex-istence of even just a few Semantic Web-enabled sites or a few scrapers already benefits users. Piggy Bank thereby offers an easy, incremental upgrade path to users without requiring a wholesale adoption of the Semantic Web's vision. 
 
To further improve this Semantic Web experience, we have created Semantic Bank, a web server application that lets Piggy Bank users share the Semantic Web information they have collected, enabling collaborative efforts to build so-phisticated Semantic Web information repositories through simple, everyday's use of Piggy Bank.
Toward using the network as a switch: on the use of TDM in linear optical networks

A common problem in optical networking is that the large quantity of raw bandwidth available in such networks is often difficult to access. We show that time-division multiplexing (TDM) can be used to operate bus and ring architectures in a manner akin to a switch. Doing so substantially reduces the amount of hardware [particularly, add-drop multiplexers (ADMs)] needed to utilize fully the available bandwidth in a range of optical networks. We show that a significant fraction (and in some cases all) of the bandwidth available to the system can be utilized even if each node in the system has only a single ADM. Our approach is probabilistic in nature, using generalizations of the Birkhoff-von Neumann statistical multiplexing approaches that have been successful in switching theory. Our techniques rely on decompositions of fractional matchings (for architectures without erasures) and fractional interval graph colorings (for architectures with erasures) into integral matchings and colorings.
Using linear programming to Decode Binary linear codes

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.
Network coding for wireless applications

The advent of network coding promises to change many aspects of networking. Network coding moves away from the classical approach of networking, which treats networks as akin to physical transportation systems. We overview some of the main features of network coding that are most relevant to wireless networks. In particular, we discuss the fact that random distributed network coding is asymptotically optimal for wireless networks with and without packet erasures. These results are extremely general and allow packet loss correlation, such as may occur in fading wireless channels. The coded network lends itself, for multicast connections, to a cost optimization which not only outperforms traditional routing tree-based approaches, but also lends itself to a distributed implementation and to a dynamic implementation when changing conditions, such as mobility, arise. We illustrate the performance of such optimization methods for energy efficiency in wireless networks and propose some new directions for research in the area.
Personalized Semantic Web Application Development by End Users

Although a lot of information has become readily accessible and necessary for daily work, the current infrastructure for managing information is ill-suited for information-oriented activities: information and functionality are scattered across applications and websites, making it difficult to aggregate and reuse just the right set of content and operations required for unique user tasks. We discuss a collection of tools built into the Haystack platform that address many of the shortcomings of current applications, and allow composing reusable fragments of information and associated operations and views from the Semantic Web into a task workspace tailored to the user and the task. Users can change the workspace to immediately meet changing requirements to easily include, remove or reuse information in multiple tasks simultaneously. The time that a user invests for the initial setup and occasional updates to the workspace is amortized over the numerous times he or she returns to the task, and all relevant information resources are co-located and ready to use.
Arpeggio: Metadata Searching and Content Sharing with Chord

Arpeggio is a peer-to-peer file-sharing network based on the Chord lookup primitive. Queries for data whose metadata matches a certain criterion are performed efficiently by using a distributed keyword-set index, augmented with index-side filtering. We introduce index gateways, a technique for minimizing index maintenance overhead. Because file data is large, Arpeggio employs subrings to track live source peers without the cost of inserting the data itself into the network. Finally, we introduce postfetching, a technique that uses information in the index to improve the availability of rare files. The result is a system that provides efficient query operations with the scalability and reliability advantages of full decentralization, and a content distribution system tuned to the requirements and capabilities of a peer-to-peer network.
Incremental exploratory visualization of relationships in large codebases for program comprehension

As software systems grow in size and use more third-party libraries and frameworks, the need for developers to understand unfamiliar large codebases is rapidly increasing. In this poster, we present a tool, Relo that supports users' understanding by allowing interactive exploration of code. As the developer explores relationships found in the code, Relo builds and automatically manages a visualization mirroring the developer's mental model, allowing them to group viewed artifacts or use the viewed items to ask the system for further exploration suggestions.
Haystack: A General-Purpose Information Management Tool for End Users Based on Semistructured Data

We posit that a semistructured data model offers the right balance of rich structure and flexible (or lack of) schema allowing naive end users to record information in whatever form makes it easy for them to manage. We describe our Haystack system, which exposes the richness and flexibility of the data model while offering the user natural, traditional interfaces that shield them from the specifics of schemas, tuples, and database queries. We outline research challenges that remain to be addressed.
Simple efficient load balancing algorithms for peer-to-peer systems

Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give two new load-balancing protocols whose provable performance guarantees are within a constant factor of optimal. Our protocols refine the consistent hashing data structure that underlies the Chord (and Koorde) P2P network. Both preserve Chord's logarithmic query time and near-optimal data migration cost.Consistent hashing is an instance of the distributed hash table (DHT) paradigm for assigning items to nodes in a peer-to-peer system: items and nodes are mapped to a common address space, and nodes have to store all items residing closeby in the address space.Our first protocol balances the distribution of the key address space to nodes, which yields a load-balanced system when the DHT maps items "randomly" into the address space. To our knowledge, this yields the first P2P scheme simultaneously achieving O(log n) degree, O(log n) look-up cost, and constant-factor load balance (previous schemes settled for any two of the three).Our second protocol aims to directly balance the distribution of items among the nodes. This is useful when the distribution of items in the address space cannot be randomized. We give a simple protocol that balances load by moving nodes to arbitrary locations "where they are needed." As an application, we use the last protocol to give an optimal implementation of a distributed data structure for range searches on ordered data.
Collections: flexible, essential tools for information management

While collections-aggregation mechanisms such as folders, buddy lists, photo albums, etc.-clearly play a central role in information management, the potential benefits of true first class support for collections are masked by disparate implementations that force users to pay attention to technological distinctions such as application, format, and protocol. We argue that systems should expose a single unified concept of collection and that concepts such as portals, cross-application projects, customized menus, and e-mail-task unification come about naturally as a result of our abstraction. In addition, uniform support for collections brings about a new set of capabilities for supporting creative processes. We discuss a prototype implementation of this abstraction in our Haystack system, give several examples of why we believe our abstraction is useful in everyday information management, and present some preliminary results from user studies that support our hypotheses.
The perfect search engine is not enough: a study of orienteering behavior in directed search

This paper presents a modified diary study that investigated how people performed personally motivated searches in their email, in their files, and on the Web. Although earlier studies of directed search focused on keyword search, most of the search behavior we observed did not involve keyword search. Instead of jumping directly to their information target using keywords, our participants navigated to their target with small, local steps using their contextual knowledge as a guide, even when they knew exactly what they were looking for in advance. This stepping behavior was especially common for participants with unstructured information organization. The observed advantages of searching by taking small steps include that it allowed users to specify less of their information need and provided a context in which to understand their results. We discuss the implications of such advantages for the design of personal information management tools.