nils-herrmann/clean_scirepeval huggingface dataset:
Finding nearest neighbors in growth-restricted metrics

Most research on nearest neighbor algorithms in the literature has been focused on the Euclidean case. In many practical search problems however, the underlying metric is non-Euclidean. Nearest neighbor algorithms for general metric spaces are quite weak, which motivates a search for other classes of metric spaces that can be tractably searched.In this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. These metrics satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant. Spaces of this kind may occur in networking applications, such as the Internet or Peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces.
Semantic Navigation Through Semi-structured Information

This flexible and generic data model presents several opportunities for improving information retrieval. Searches for information generally involve a dialogue between the user and the computer. The user starts somewhere and follows a sequence of navigation steps (e.g., issuing a query, looking at the results, refining the search parameters, etc.) until the desired information is found. A user interface can help this navigation process by suggesting useful steps to be taken next, such as specifying particular ways to refine the query.
Observations on the Dynamic Evolution of Peer-to-Peer Networks

A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate for an infinite time, performance measures based on runtime are uninformative; instead, we must study the rate at which nodes consume resources in order to maintain the system state.This "maintenance bandwidth" depends on the rate at which nodes tend to enter and leave the system. In this paper, we formalize this dependence. Having done so, we analyze the Chord peer-to-peer protocol. We show that Chord's maintenance bandwidth to handle concurrent node arrivals and departures is near optimal, exceeding the lower bound by only a logarithmic factor. We also outline and analyze an algorithm that converges to a correct routing state from an arbitrary initial condition.
Haystack: A Platform for Creating, Organizing and Visualizing Information Using RDF

The Resource Definition Framework (RDF) is designed to support agent communication on the Web, but it is also suitable as a framework for modeling and storing personal information. Haystack is a personalized information repository that employs RDF in this manner. This flexible semistructured data model is appealing for several reasons. First, RDF supports ontologies created by the user and tailored to the user's needs. At the same time, system ontologies can be specified and evolved to support a variety of high-level functionalities such as flexible organization schemes, semantic querying, and collaboration. In addition, we show that RDF can be used to engineer a component architecture that gives rise to a semantically rich and uniform user interface. We demonstrate that by aggregating various types of users' data together in a homogeneous representation, we create opportunities for agents to make more informed deductions in automating tasks for users. Finally, we discuss the implementation of an RDF information store and a programming language specifically suited for manipulating RDF.
INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery

The decreasing cost of computing technology is speeding the deployment of abundant ubiquitouscomputation and communication. With increasingly large and dynamic computing environments comes the challenge of scalable resource discovery, where client applications search for resources (services, devices, etc.) on the network by describing some attributesof what they are looking for. This is normally achieved through directory services (also called resolvers), which store resource information and resolve queries. This paper describes the design, implementation, and evaluation of INS/Twine, an approach to scalable intentional resource discovery, where resolvers collaborate as peers to distribute resource information and to resolve queries. Our system maps resources to resolvers by transforming descriptions into numeric keys in a manner that preserves their expressiveness, facilitates even data distribution and enables efficient query resolution. Additionally, INS/Twine handles resource and resolver dynamism by treating all data as soft-state.
Infranet: Circumventing Web Censorship and Surveillance

An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to surreptitiously retrieve sensitive content via cooperating Web servers distributed across the global Internet. These Infranet servers provide clients access to censored sites while continuing to host normal uncensored content. Infranet uses a tunnel protocol that provides a covert communication channel between its clients and servers, modulated over standard HTTP transactions that resemble innocuous Web browsing. In the upstream direction, Infranet clients send covert messages to Infranet servers by associating meaning to the sequence of HTTP requests being made. In the downstream direction, Infranet servers return content by hiding censored data in uncensored images using steganographic techniques. We describe the design, a prototype implementation, security properties, and performance of Infranet. Our security analysis shows that Infranet can successfully circumvent several sophisticated censoring techniques.
Parallel processor scheduling with delay constraints

We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on the jobs, and both communication and precedence delays impose relative timing constraints on dependent jobs. The combination of these two types of timing constraints naturally models the instruction scheduling problem that occurs during software compilation for state-of-the-art VLIW (Very Long Instruction Word) processors and multiprocessor parallel machines.
We present the first known polynomial-time algorithm for the case where the precedence constraint graph is a forest of in-trees (or a forest of out-trees), the number of machines m is fixed, and the delays (which are a function of both the job pair and the machines on which they run) are bounded by a constant D.
Our algorithm relies on a new structural theorem for scheduling jobs with arbitrary precedence constraints. Given an instance with many independent dags, the theorem shows how to convert, in linear time, a schedule S for only the largest dags into a complete schedule that is either optimal or has the same makespan as S.
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms

We present an experimental study of different variants of theamortized <i>O</i>(log<sup>2</sup> <i>n</i>)-time fully-dynamicconnectivity algorithm of Holm, de Lichtenberg, and Thorup(STOC'98). The experiments build upon experiments provided byAlberts, Cattaneo, and Italiano (SODA'96) on the randomizedamortized <i>O</i>(log<sup>3</sup> <i>n</i>) fully-dynamicconnectivity algorithm of Henzinger and King (STOC'95). Ourexperiments shed light upon similarities and differences betweenthe two algorithms. We also present a slightly modified version ofthe Henzinger-King algorithm that runs in <i>O</i>(log<sup>2</sup><i>n</i>) time, which resulted from our experiments.
Wide-area cooperative storage with CFS

The Cooperative File System (CFS) is a new peer-to-peer read-only storage system that provides provable guarantees for the efficiency, robustness, and load-balance of file storage and retrieval. CFS does this with a completely decentralized architecture that can scale to large systems. CFS servers provide a distributed hash table (DHash) for block storage. CFS clients interpret DHash blocks as a file system. DHash distributes and caches blocks at a fine granularity to achieve load balance, uses replication for robustness, and decreases latency with server selection. DHash finds blocks using the Chord location protocol, which operates in time logarithmic in the number of servers.CFS is implemented using the SFS file system toolkit and runs on Linux, OpenBSD, and FreeBSD. Experience on a globally deployed prototype shows that CFS delivers data to clients as fast as FTP. Controlled tests show that CFS is scalable: with 4,096 servers, looking up a block of data involves contacting only seven servers. The tests also demonstrate nearly perfect robustness and unimpaired performance even when as many as half the servers fail.
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is ${\sharp {\cal P}}$-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and $1/\epsilon$ an estimate for the failure probability that is accurate to within a relative error of $1\pm\epsilon$ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of $k$-connectivity, strong connectivity in directed Eulerian graphs and $r$-way disconnection, and to evaluating the Tutte polynomial are also described. 
This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger,  (1999), pp. 492--514].
Chord: A scalable peer-to-peer lookup service for internet applications

A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
Learning Markov networks: maximum bounded tree-width graphs

Markov networks are a common class of graphical models used in machine learning. Such models use an undirected graph to capture dependency information among random variables in a joint probability distribution. Once one has chosen to use a Markov network model, one aims to choose the model that “best explains” the data that has been observed—this model can then be used to make predictions about future data.
We show that the problem of learning a maximum likelihood Markov network given certain observed data can be reduced to the problem of identifying a maximum weight low-treewidth graph under a given input weight function. We give the first constant factor approximation algorithm for this problem. More precisely, for any fixed treewidth objective k, we find a treewidth-k graph with an f(k) fraction of the maximum possible weight of any treewidth-k graph.
Building peer-to-peer systems with chord, a distributed lookup service

We argue that the core problem facing peer-to-peer Systems is locating documents in a decentralized network and propose Chord, a distributed lookup primitive. Chord provides an efficient method of locating documents while placing few constraints on the applications that use it. As proof that Chord's functionality is useful in the development of peer-to-peer applications, we outline the implementation of a peer-to-peer file sharing system based on Chord.
A scalable location service for geographic ad hoc routing

GLS is a new distributed location service which tracks mobile node locations. GLS combined with geographic forwarding allows the construction of ad hoc mobile networks that scale to a larger number of nodes than possible with previous work. GLS is decentralized and runs on the mobile nodes themselves, requiring no fixed infrastructure. Each mobile node periodically updates a small set of other nodes (its location servers) with its current location. A node sends its position updates to its location servers without knowing their actual identities, assisted by a predefined ordering of node identifiers and a predefined geographic hierarchy. Queries for a mobile node's location also use the predefined identifier ordering and spatial hierarchy to find a location server for that node.
Experiments using the ns simulator for up to 600 mobile nodes show that the storage and bandwidth requirements of GLS grow slowly with the size of the network. Furthermore, GLS tolerates node failures well: each failure has only a limited effect and query performance degrades gracefully as nodes fail and restart. The query performance of GLS is also relatively insensitive to node speeds. Simple geographic forwarding combined with GLS compares favorably with Dynamic Source Routing (DSR): in larger networks (over 200 nodes) our approach delivers more packets, but consumes fewer network resources.
MIT 2000-10 Software Technologies for Wireless Communication and Multimedia Networks

As communication penetrates into more aspects of daily life, the number of specialpurpose devices, networks, and systems is increasing rapidly. At the same time, computation technologies are producing increasingly powerful general-purpose devices and systems. These two trends raise an interesting research problem, namely, how to design multiple-purpose communication devices and systems that efficiently adapt general capabilities to specific tasks. Adaptable devices and systems would
Dynamic Graph Algorithms with Applications

First we review amortized fully-dynamic polylogarithmic algorithms for connectivity, minimum spanning trees (MST), 2-edge- and biconnectivity. Second we discuss how they yield improved static algorithms: connectivity for constructing a tree from homeomorphic subtrees, 2-edge connectivity for finding unique matchings in graphs, and MST for packing spanning trees in graphs. 
 
The application of MST for spanning tree packing is new and when boot-strapped, it yields a fully-dynamic polylogarithmic algorithm for approximating general edge connectivity within a factor √2+o(1). 
 
Finally, on the more practical side, we will discuss how output sensitive algorithms for dynamic shortest paths have been applied successfully to speed up local search algorithms for improving routing on the internet, roughly doubling the capacity.
Minimum cuts in near-linear time

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs.  We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an <italic>m</italic>-edge, <italic>n</italic>-vertex graph with high probability in <italic>O</italic>(m log<supscrpt>3</supscrpt>  <italic>n</italic>) time. We also give a simpler randomized algorithm that finds <italic>all</italic> minimum cuts with high probability in O(<italic>m</italic> log<supscrpt>3</subscrpt> <italic>n</italic>) time. This variant has an optimal <italic>RNC</italic> parallelization.  Both variants improve on the previous best time bound of <italic>O<italic>(<italic>n<italic><supscrpt>2</supscrpt> log<supscrpt>3</supscrpt> <italic>n<italic>). Other applications of the tree-packing approach are new, nearly tight bounds on the number of <italic>near-minimum</italic> cuts a graph may have and a new data structure for representing them in a space-efficient manner.
Building Steiner trees with incomplete global knowledge

A networking problem of present-day interest is that of distributing a single data item to multiple clients while minimizing network usage. Steiner tree algorithms are a natural solution method, but only when the set of clients requesting the data is known. We study what can be done without this global knowledge, when a given vertex knows only the probability that any other client wishes to be connected, and must simply specify a fixed path to the data to be used in case it is requested. Our problem is an example of a class of network design problems with concave cost functions (which arise when the design problem exhibits economies of scale). In order to solve our problem, we introduce a new version of the facility location problem: one in which every open facility is required to have some minimum amount of demand assigned to it. We present a simple bicriterion approximation for this problem, one which is loose in both assignment cost and minimum demand, but within a constant factor of the optimum for both. This suffices for our application. We leave open the question of finding an algorithm that produces a truly feasible approximate solution.
MIT 9904-08 Haystack : Per-User Information Environments

The Haystack project is investigating the ways in which electronic infrastructure can be used to triangulate among the different knowledges of an individual, of collegial communities to which we belong, and of the world at large. Its infrastructure consists of a community of independent, interacting information repositories, each customized to its individual user. It provides automated data gathering (through active observation of user activity), customized information collection, and adaptation to individual query needs. It also facilities inter-haystack collaboration, exposing (public subsets of) the tremendous wealth of individual knowledge that each of us currently has locked up in our personal information spaces. The Haystack-NTT project involves augmenting its customization, learning and adaptation, and inter-haystack communication.
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense” instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimumk-way cut with and without specified terminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree?(n), although our algorithms solve most of these problems so long as the average degree is?(n). Denseness for nongraph problems is defined similarly. The unified framework begins with the idea ofexhaustive sampling:picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certainsmoothinteger programs, where the objective function and the constraints are “dense” polynomials of constant degree.
Rounding algorithms for a geometric embedding of minimum multiway cut

Given an undirected graph with edge costs and a subset of k ≥ 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. T his problem is Max-SNP hard. Recently Calinescu, Karloff, and Rabani (STOC’98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3/2 − 1/k)-approximation algorithm. In this paper, we study their geometric relaxation. In parti cular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k = 3, we show the integrality gap is 12/11, giving tight upper and lower bounds. That is, we exhibit a family of graphs with integrality gaps arbit rarily close to 12/11 and give an algorithm that finds a cut of value 12/11 times the relaxation value. Our lower bound shows that this is the best
Approximation schemes for minimizing average weighted completion time with release dates

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).
Random Sampling in Cut, Flow, and Network Design Problems

We use random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, that arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph with high probability. This makes sampling effective for problems involving cuts in graphs. We present fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding minimum cuts and maximum flows in unweighted, undirected graphs. Our cut-approximation algorithms extend unchanged to weighted graphs while our weighted-graph flow algorithms are somewhat slower. Our approach gives a general paradigm with potential applications to any packing problem. It has since been used in a near-linear time algorithm for finding minimum cuts, as well as faster cut and flow algorithms. Our sampling theorems also yield faster algorithms for several other cut-based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our methods also improve the efficiency of some parallel cut and flow algorithms. Our methods also apply to the network design problem, where we wish to build a network satisfying certain connectivity requirements between vertices. We can purchase edges of various costs and wish to satisfy the requirements at minimum total cost. Since our sampling theorems apply even when the sampling probabilities are different for different edges, we can apply randomized rounding to solve network design problems. This gives approximation algorithms that guarantee much better approximations than previous algorithms whenever the minimum connectivity requirement is large. As a particular example, we improve the best approximation bound for the minimum k-connected subgraph problem from 1.85 to [math not displayed].