2070842
Distributed Network Querying with Bounded Approximate Caching
As networks continue to grow in size and complexity, distributed network monitoring and resource querying are becoming increasingly difficult. Our aim is to design, build, and evaluate a scalable infrastructure for answering queries over distributed measurements, at reduced costs (in terms of both network traffic and query latency) while maintaining required precision. In this infrastructure, each network node owns a set of numerical measurements and actively maintains bounds on these values cached at other nodes. We can answer queries approximately, using bounds from nearby caches to avoid contacting the owners directly. We focus on developing efficient and scalable techniques to place, locate, and manage bounded approximate caches across a large network. We have developed two approaches: One uses a recursive partitioning of the network space to place caches in a static, controlled manner, while the other uses a locality-aware distributed hash table to place caches in a dynamic and decentralized manner. In this paper, we focus on the latter approach. Experiments over a large-scale emulated network show that our techniques are very effective in reducing query costs while generating an acceptable amount of background traffic; they are also able to exploit various forms of locality that are naturally present in queries, and adapt to volatility of measurements.
214792426
TIP: a temporal extension to Informix
Commercial relational database systems today provide only limited temporal support. To address the needs of applications requiring rich temporal data and queries, we have built TIP (Temporal Information Processor), a temporal extension to the Informix database system based on its DataBlade technology. Our TIP DataBlade extends Informix with a rich set of datatypes and routines that facilitate temporal modeling and querying. TIP provides both C and Java libraries for client applications to access a TIP-enabled database, and provides end-users with a GUI interface for querying and browsing temporal data.
7776820
Scalable continuous query processing by tracking hotspots
This paper considers the problem of scalably processing a large number of continuous queries. We propose a flexible framework with novel data structures and algorithms for group-processing and indexing continuous queries by exploiting potential overlaps in query predicates. Our approach partitions the collection of continuous queries into groups based on the clustering patterns of the query ranges, and then applies specialized processing strategies to those heavily-clustered groups (or hotspots). To maintain the partition dynamically, we present efficient algorithms that maintain a nearly optimal partition in nearly amortized logarithmic time. We show how to use the hotspots to scalably process large numbers of continuous select-join and band-join queries, which are much more challenging than simple range selection queries. Experiments demonstrate that this approach can improve the processing throughput by orders of magnitude. As another application of hotspots, we show how to use them to build a high-quality histogram for intervals in linear time.
11503542
Monitoring Continuous Band-Join Queries over Dynamic Data
A continuous query is a standing query over a dynamic data set whose query result needs to be constantly updated as new data arrive. We consider the problem of constructing a data structure on a set of continuous band-join queries over two data sets R and S, where each band-join query asks for reporting the set { (r,s)∈ R× S | a≤ r–s≤ b} for some parameters a and b, so that given a data update in R or S, one can quickly identify the subset of continuous queries whose results are affected by the update, and compute changes to these results. 
 
We present the first nontrivial data structure for this problem that simultaneously achieves subquadratic space and sublinear query time. This is achieved by first decomposing the original problem into two independent subproblems, and then carefully designing data structures suitable for each case, by exploiting the particular structure in each subproblem. 
 
A key step in the above construction is a data structure whose performance increases with the degree of clusteredness of the band-joins being indexed. We believe that this structure is of independent interest and should have broad impact in practice. We present the details in [1].
12872505
Value-Based Notification Conditions in Large-Scale Publish/Subscribe Systems
We address the problem of providing scalable support for subscriptions with personalized value-based notification conditions in wide-area publish/subscribe systems. Notification conditions can be fine-tuned by subscribers, allowing precise and flexible control of when events are delivered to the subscribers. For example, a user may specify that she should be notified if and only if the price of a particular stock moves outside a "radius" around her last notified value. Naive techniques for handling notification conditions are not scalable. It is challenging to share subscription processing and notification dissemination of subscriptions with personalized value-based notification conditions, because two subscriptions may see two completely different sequences of notifications even if they specify the same radius. We develop and experimentally evaluate scalable processing and dissemination techniques for these subscriptions. Our approach uses standard network substrates for notification dissemination, and avoids pushing complex application processing into the network. Compared with other alternatives, our approach generates orders of magnitude lower network traffic, and incurs lower server processing cost.
14448318
On Suspending and Resuming Dataflows
Consider a long-running, resource-intensive query Q running on a database management system (DBMS). Suppose another task T with much higher priority arrives, and we need to process T as quickly as possible and with all available resources. Ideally, the system should suspend the execution of Q, quickly release all resources held by Q, and start T using all resources. Query Q can be resumed once T finishes execution, ideally without losing any significant fraction of the work that Q had done prior to suspend. Beyond supporting mixed-priority DBMS workloads, suspend/resume of queries, or dataflows in general, is important in many other settings: Utility and grid: Dataflows now run frequently on computational utilities and grids composed of autonomous resources. When the owner of resources wants to use them, dataflows running on these resources must release control quickly, and migrate to other resources. Software rejuvenation: Benefits of software rejuvenation, the practice of rebooting enterprise computing systems regularly, are now recognized widely. Reboot is critical when performance degrades due to resource exhaustion caused by resource leaks. Suspend and resume is important in this setting because (1) the challenge of predicting completion times accurately makes it difficult to schedule task completion to match a rejuvenation schedule; (2) when performance degrades, it may not be cost-effective to wait for all dataflows to complete before rebooting.
5715843
A Cautionary Tale
Recently we have been investigating various methods for improving the retrieval of documents. One frequently used context for such studies is to work with a known database and set of queries, where sufficient work has previously been done to establish an "official" set of relevant documents for each query. Working within such a context, we have discovered at least one instance wherein the combination of the document descriptions in the database, the query, and the set of documents deemed relevant foredooms our attempts at retrieval improvement to failure. This note is to caution other researchers against such possibilities, and to recommend that the database in question, that of the National Physical Laboratory (NPL), as represented on Virginia Disk 1, be retired from use.
8365397
Input modeling when simple models fail
A simulation model is composed of inputs and logic; the inputs represent the uncertainty or randomness in the system, while the logic determines how the system reacts to the uncertain elements. Simple input models, consisting of independent and identically distributed sequences of random variates from standard probability distributions, are included in every commercial simulation language. Software to fit these distributions to data is also available. In this tutorial we describe input models that are useful when simple models are not.
1498767
Clustering by pattern similarity in large data sets
Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.
815725
Virtual Execution Environments: Support and Tools
In today's dynamic computing environments, the available resources and even underlying computation engine can change during the execution of a program. Additionally, current trends in software development favor the flexibility and cost-effectiveness of dynamically loaded components and libraries. Because of these trends, there has been increased research interest in virtual execution environments (VEEs) for delivering adaptable software suitable for today's rapidly changing, heterogeneous computing environments. In this project, we have been investigating tools and techniques to support implementation of VEEs using software dynamic translation (SDT). This paper highlights some of our recent results. One significant result is that we have developed novel translation techniques that reduce the memory and runtime overhead of SDT to negligible levels. We have also developed innovative debugging and instrumentation tools for SDT-based software environments. Together, these results make SDT-based systems viable for solving a wide range of pressing problems. The paper concludes with a discussion of how SDT may offer a solution to one such problem-inherent process variation in emerging chip multiprocessors.
1138265
A Fault-Tolerant Dynamic Channel Allocation Scheme for Enhancing QoS in Cellular Networks
In cellular networks. it is vital to allocate communica­ tion channels efficiently because the bandwidth allocated for cellular communication is limited. When mobile hosts move from one cell to another cell. to provide uninterrupted service. the new cell should have enough channels to sup­ pan the ongoing communication of the mobile hosts that moved into the cell. If channels are statically allocated. as is the case in current cellular networks. a cell may run out of channels when large number of mobile hosts move to a cell. thus degrading the quality of service. To over­ come this problem. dynamic channel allocation approaches have been proposed. Under dynamic channel allocation. channels are allocated to cells on demand. thus increasing channel utilization and hence improving the quality of ser­ vice. Such channel allocation approaches fall under two categories. namely. centralized and distributed. Central­ ized approaches are neither scalable nor reliable. while dis­ lributed approaches have the potential to be both reliable and scalable. In this paper, we present a distributed dy­ namic channel allocation scheme for cellular networks that is fault tolerant. Our approach can tolerate the failure of mobile nodes as well as static nodes and enhance the qual­ ity of service by making efficient reuse of channels.