This paper introduces techniques for reducing data dissemination costs of query subscriptions in a multicast environment. The reduction is achieved by merging queries with overlapping, but not necessarily equal, answers. The paper formalizes the query-merging problem and introduces a general framework and cost model for evaluating merging. We prove that the problem is NP-hard and propose exhaustive algorithms and three heuristic algorithms: the pair merging algorithm, the directed search algorithm, and the clustering algorithm. We develop a simulator, which uses geographical queries as a representative example for evaluating the different heuristics and show that the performance of our heuristics is close to optimal.

Finding information in a peer-to-peer system currently requires either a costly and vulnerable central index, or flooding the network with queries. We introduce the concept of routing indices (RIs), which allow nodes to forward queries to neighbors that are more likely to have answers. If a node cannot answer a query, it forwards the query to a subset of its neighbors, based on its local RI, rather than by selecting neighbors at random or by flooding the network by forwarding the query to all neighbors. We present three RI schemes: the compound, the hop-count, and the exponential routing indices. We evaluate their performance via simulations, and find that RIs can improve performance by one or two orders of magnitude vs. a flooding-based system, and by up to 100% vs. a random forwarding system. We also discuss the tradeoffs between the different RI schemes and highlight the effects of key design variables on system performance.

This paper examines query subscription merging in a distributed environment where multicast channels are used to deliver information. It describes methods for reducing the cost of delivering information by merging overlapping data in the query answers and by using the multicast channels effectively. 1 Introduction Ongoing advances in communications, including the proliferation of the Internet and intranets, the development of mobile and wireless networks, and the impending availability of high bandwidth links to the home, have fueled the development of a wide range of new information-centered applications. Many of these new applications involve data dissemination, that is, the delivery of data from a set of producers to a (typically) larger set of consumers. Examples of dissemination-based applications include information feeds (e.g., stock and sports tickers of news wires), traffic information systems, electronic newsletters, and entertainment delivery [FZ96]. Current subscription se...

Traditional server-based web applications allow access to server-hosted resources, but often exhibit poor responsiveness due to server load and network delays. Client-side web applications, on the other hand, provide excellent interactivity at the expense of limited access to server resources. The WebWriter II Editor, a direct manipulation HTML editor that runs in a web browser, uses both server-side and client-side processing in order to achieve the advantages of both. In particular, this editor downloads the document data structure to the browser and performs all operations locally. The user interface is based on HTML frames and includes individual frames for previewing the document and displaying general and specific control panels. All editing is done by JavaScript code residing in roughly twenty HTML pages that are downloaded into these frames as needed. Such a client-server architecture, based on frames, client-side data structures, and multiple JavaScript-enhanced HTML pages appears promising for a wide variety of applications. This paper describes this architecture, the Meteor Shower Application Architecture, and its use in the WebWriter II Editor. 1