Learned database indexes use machine learning algorithms to directly predict the location of a query key within a sorted key array, thereby eliminating index search overhead. Prior work shows learned indexes outperforming traditional indexes in both space and query time for one-dimensional data, especially for read-intensive workloads. Usually, learned indexes linearize the multi-dimensional data with a space-filling curve before generating the index.

Computing shortest paths is one of the most researched topics in algorithm engineering. Currently available algorithms compute shortest paths in mere fractions of a second on continental sized road networks. In the presence of unreliability, however, current algorithms fail to achieve results as impressive as for the static setting. In contrast to speed-up techniques for static route planning, current implementations for the stochastic on-time arrival problem require the computationally expensive step of solving convolution products. Running times can reach hours when considering large scale networks. We present a novel approach to reduce this immense computational effort of stochastic routing based on existing techniques for alternative routes. In an extensive experimental study, we show that the process of stochastic route planning can be speed-up immensely, without sacrificing much in terms of accuracy.

Stochastic route planning is a hard problem, since it deals with uncertain edge weights, usually modeled as probability distributions. Stochastic shortest path queries are very expensive, as they must compute convolutions of edge weight distributions, whose representations can have a major impact on query costs. Effective speedup techniques for shortest path queries exist for deterministic edge weights, but their extensions to stochastic settings have had limited success, and real-time stochastic routing queries remain beyond reach. We introduce the tiering technique for Contraction and Edge Hierarchies (CHs and EHs) to address this challenge. We divide the hierarchy into tiers, and represent edge weights in each tier in ways that permit effective tradeoffs between accuracy, convolution costs, and space use. We show how to use Gaussians to approximate histograms, and bound errors using the KL divergence and Hellinger distance measures. We develop Uncertain Contraction Hierarchies (UCHs) and Uncertain Edge Hierarchies (UEHs) using these methods, and show that they improve both CH and EH performance for three different stochastic query types: probabilistic budget routes, non-dominated routes, and routes to minimize the mean-risk objective. We evaluate our methods using real-world data from Mapbox Traffic Data for a section of Los Angeles. Finally, our results show that query times for EHs can be competitive with CHs for stochastic edge weights, contrary to current belief.

Electric Vehicle (EV) battery capacity is limited, so EV routing must trade off travel time for energy consumption, which grows quad-ratically with speed. Current multi-parameter EV routing methods assume accurate estimates of time and energy consumed, but current models for obtaining these estimates cannot capture this time-energy tradeoff in a sufficiently flexible way. We present a new approach to EV modeling that addresses such shortcomings. Conventional wisdom holds that models operating at finer time granularities yield better energy consumption estimates. We first show that such is not necessarily the case, by defining a new structuring abstraction for vehicle speed profiles called phases, which models energy consumption accurately at lower temporal granularity. We also address the challenge of generating speed profiles for planned trips with realistic variance in travel times and energy consumed. Our method combines the phase abstraction with Markov chains and kernel density estimation to learn these variations, and construct realistic vehicle speed profiles for real-world routes. Using 52 hours of driving data collected on a Nissan Leaf, we show that our model achieves a per-trip accuracy better than even that of current microscopic models and generates speed proiles that accurately model time and energy consumption at the trip level.

Current Bloom Filters tend to ignore Bayesian priors as well as a great deal of useful information they hold, compromising the accuracy of their responses. Incorrect responses cause users to incur penalties that are both application- and item-specific, but current Bloom Filters are typically tuned only for static penalties. Such shortcomings are problematic for all Bloom Filter variants, but especially so for Time-decaying Bloom Filters, in which the memory of older items decays over time, causing both false positives and false negatives. We address these issues by introducing inferential filters, which integrate Bayesian priors and information latent in filters to make penalty-optimal, query-specific decisions. We also show how to properly infer insertion times in such filters. Our methods are general, but here we illustrate their application to inferential time-decaying filters to support novel query types and sliding window queries with dynamic error penalties. We present inferential versions of the Timing Bloom Filter and Generalized Bloom Filter. Our experiments on real and synthetic datasets show that our methods reduce penalties for incorrect responses to sliding-window queries in these filters by up to 70% when penalties are dynamic.

Efficiently querying large trajectory datasets is a challenge of growing importance. Abstracting trajectory segments with minimum bounding boxes and indexing them in R-Trees results in a high false positive rate due to high dead space. Space filling curves (SFCs), which have excellent locality preserving and dimensionality reduction properties, have been shown to be effective for indexing points in space. However, they can yield a high false positive count and slow query times if used to index trajectory segments. Our work shows how to use SFCs to index trajectory polylines. In our experiments, the proposed method runs 2--15 times faster than other state-of-the-art approaches.

Consider objects moving in a road network (e.g., groups of people or delivery vehicles), who may be free to choose routes, yet be required to arrive at certain locations at certain times. Such objects may need to assemble in groups within the network (friends meet while visiting a city, vehicles need to exchange items or information) without violating arrival constraints. Planning for such assemblies is hard when the network or the number of objects is large. Conversely, discovering actual or potential assemblies of such objects is important in many surveillance, security, and law-enforcement applications. This can be hard when object arrival observations are sparse due to inadequate sensor coverage or object countermeasures. We propose the novel class of assembly queries to model these scenarios, and present a unified scheme that addresses both of these complementary challenges. Given a set of objects and arrival constraints, we show how to first obtain the set of all possible locations visited by each moving object (the travel corridor), and then determine all possible assemblies, including the participants, locations, and durations. We present a formal model for various tracking strategies and several algorithms for using these strategies. We achieve excellent performance on these queries by preprocessing the network, using Contraction Hierarchies. Experimental results on real-world road networks show that we can efficiently and rapidly infer assembly information for very large networks and object groups.

Cloud computing allows customers to outsource the burden of data management and benefit from economy of scale, but privacy concerns limit its reach. Even if the stored data are encrypted, access patterns may leak valuable information. Oblivious RAM (ORAM) protocols guarantee full access pattern privacy, but even the most efficient ORAMs proposed to date incur large bandwidth costs.

We consider the challenge of providing privacy-preserving access to data outsourced to an untrusted cloud provider. Even if data blocks are encrypted, access patterns may leak valuable information. Oblivious RAM (ORAM) protocols guarantee full access pattern privacy, but even the most efficient ORAMs to date require roughly L log2 N block transfers to satisfy an L-block query, for block store capacity N.

We present HM-ABE, a hierarchical multi-authority attribute-based encryption scheme with policy delegation that generalises current work significantly. Current methods require encryptors to build ciphertext access policies themselves, using attributes published by authority domains. This causes problems, both since authorities may not publish sensitive attributes, and since users may not understand their internal policies. We permit encryptors to delegate parts of their access policies to authorities, who can construct appropriate policies on their behalf, using sensitive attributes, if needed. Delegation can be recursive. Delegation helps encryptors build more accurate access policies, especially when they must include attributes from multiple authorities. HMABE greatly reduces the chances that ineligible users gain access to data, or that eligible users are denied. Delegation lets authorities hide sensitive attributes, while still allowing users indirect access to their semantics. We show that HM-ABE achieves recursive attribute delegation, selective attribute hiding, and prove that it is secure.

Text-based search queries reveal user intent to the search engine, compromising privacy. Topical Intent Obfuscation (TIO) is a promising new approach to preserving user privacy. TIO masks topical intent by mixing real user queries with dummy queries matching various different topics. Dummy queries are generated using a Dummy Query Generation Algorithm (DGA). We demonstrate various shortcomings in current TIO schemes, and show how to correct them. Current schemes assume that DGA details are unknown to the adversary. We argue that this is a flawed assumption, and show how DGA details can be used to construct efficient attacks on TIO schemes, using an iterative DGA as an example. Our extensive experiments on real data sets show that our attacks can flag up to 80% of dummy queries. We also propose HDGA, a new DGA that we prove to be immune to the attacks based on DGA semantics that we describe.

Privacy and security for outsourced databases are often provided by Precise Query Protocols (PQPs). In a PQP, records are individually encrypted by a client and stored on a server. The client issues encrypted queries, which are run under encryption at the server, and the server returns the exact set of encrypted tuples needed to satisfy the query. We propose a general attack against the privacy of all PQPs that support range queries, using query results to partially order encrypted records. Existing attacks that seek to order etuples are less powerful and depend on weaknesses specific to particular PQPs. Our novel algorithm identifies permissible positions (loci) for encrypted records by organizing range query results using PQ-trees. These results can then be used to infer attribute values of encrypted records. We propose equivocation and permutation entropy as privacy metrics, and give experimental results that show PQP privacy to be easily compromised by our attack.

Time-Decaying Bloom Filters are efficient, probabilistic data structures used to answer queries on recently inserted items. As new items are inserted, memory of older items decays. Incorrect query responses incur penalties borne by the application using the filter. Most existing filters may only be tuned to static penalties, and they ignore Bayesian priors and information latent in the filter.

We show how to execute range queries securely and efficiently on encrypted databases in the cloud. Current methods provide either security or efficiency, but not both. Many schemes even reveal the ordering of encrypted tuples, which, as we show, allows adversaries to estimate plaintext values accurately. We present the R̂-trees, a hierarchical encrypted index that may be securely placed in the cloud, and searched efficiently. It is based on a mechanism we design for encrypted halfspace range queries in ℝd, using Asymmetric Scalar-product Preserving Encryption. Data owners can tune the R̂-trees parameters to achieve desired security-efficiency tradeoffs. We also present extensive experiments to evaluate R̂-trees performance. Our results show that R̂-trees queries are efficient on encrypted databases, and reveal far less information than competing methods.

A region R is a dwell region for a moving object O if, given a threshold distance d and duration t, every point of R remains within distance d of O for at least time t. Clearly, points within R are likely to be of interest to O, so identification of O and R has applications in areas such as monitoring and surveillance, as well as to trajectory simplification. We propose an online algorithm to solve this problem, which can handle dynamic addition and deletion of data in logarithmic time. We assume an incoming stream of object positions, and maintain the upper and lower bounds for the radius of the smallest circle enclosing these positions, as points are added and deleted. These bounds allow us to greatly reduce the number of trajectory points we need to consider in the query, as well as to defer query evaluation. Our method can approximate the radius of the smallest circle enclosing a given sub trajectory within an arbitrarily small user defined factor. Our experiments show that the proposed method can scale up to hundreds of thousands of trajectories.

We show how to find regions of interest (ROIs) in trajectory databases. ROIs are regions where a large number of moving objects remain for at least a given time interval. Previous techniques use somewhat restrictive definitions for ROIs, and are parameter-dependent. They require sequential scanning of the entire dataset to find ROIs when the ROI parameters change. Our approach is parameter independent, so that the user can quickly identify ROIs under different parametric definitions without rescanning the whole database. We also generalize ROIs to be regions of arbitrary shape of some predefined density. We have tested our methods with large real and synthetic datasets to test the scalability and verify the output of our methods. Our methods give meaningful output and scale very well.

We present a framework for analyzing the effects of random and selective compromises (using order statistics) in sensor networks. We discuss the problem of ensuring data integrity at the source and during transit in sensor networks, and present an analysis of the reliability of reports from mobile collectors. No analysis has appeared in the literature of source integrity for mobile nodes, or of selective attacks in sensor networks. We address transit data integrity by presenting mGKE, a key establishment scheme for general group-based sensor deployments, and present a detailed analytical and experimental comparison of mGKE with current schemes. mGKE outperforms current methods in terms of resilience, connectivity, and memory and communication overhead.

We present a new adaptive and energy-efficient broadcast model to support flexible responses to client queries. Clients do not have to request documents by name, since they may know the characteristics of the documents but not the document names or IDs. In our model, clients specify requirements through attributes, and servers broadcast documents that match client requests at a prespecified level of similarity. A given document may satisfy several clients, so the server broadcasts a minimal set of documents that achieves a desired level of satisfaction in the client population. The server obtains randomized feedback from clients and adapts its broadcast program accordingly. Clients use a selective tune-in scheme based on approximate indexing to conserve energy. Our model captures client interest patterns efficiently and accurately and scales very well with the number of clients while reducing the overall client average waiting times. The selective tune-in scheme reduces client energy consumption greatly, with a modest wait time increase.

Applications such as traffic management and resource scheduling for location-based services commonly need to identify regions with high concentrations of moving objects. Such queries are called dense region queries in spatio-temporal databases, and desire regions in which the density of moving objects exceeds a given threshold. Current methods for addressing this important class of queries suffer from several drawbacks. For example, they may fail to find all dense regions, provide ambiguous answers, impose restrictions on size, or lack a notion of local density. We address these issues in this paper, starting with a new definition of dense regions. We show that we are able to answer dense region queries completely and uniquely using this definition. Dense regions in our approach may have arbitrary shape and size, as well as local density guarantees. We present two methods, the first, an exact method, and the second, an approximate method. We demonstrate through extensive experiments that our exact method is efficient and is superior to current approaches. Our approximate method runs orders of magnitude faster than our exact method, at the cost of a tolerable loss of accuracy.

Mechanisms for data access and payment are central to the success of content delivery systems. However, not much attention has been paid to the issues of dishonest intermediaries (brokers) or client collusion with dishonest brokers. We propose protocols to verify broker honesty for data accesses under standard security assumptions in such systems. Analytical and experimental results show that our protocols are robust against replay and fabrication attacks, and are consistently able to identify broker dishonesty.

Complex queries on trajectory data are increasingly common in applications involving moving objects. MBR or grid-cell approximations on trajectories perform suboptimally since they do not capture the smoothness and lack of internal area of trajectories. We describe a parametric space indexing method for historical trajectory data, approximating a sequence of movement functions with single continuous polynomial. Our approach works well, yielding much finer approximation quality than MBRs. We present the PA-tree, a parametric index that uses this method, and show through extensive experiments that PA-trees have excellent performance for offline and online spatio-temporal range queries. Compared to MVR-trees, PA-trees are an order of magnitude faster to construct and incur I/O cost for spatio-temporal range queries lower by a factor of 2-4. SETI is faster than our method for index construction and timestamp queries, but incurs twice the I/O cost for time interval queries, which are much more expensive and are the bottleneck in online processing. Therefore, the PA-tree is an excellent choice for both offline and online processing of historical trajectories

Mobile sinks are already used in static sensor networks to facilitate data collection or network management, but it is possible in such networks for mobile sinks to be compromised and mount various insider attacks. Some schemes have been devised recently to limit the privileges of mobile sinks appropriately, but these are secure only when the number of compromised mobile sinks or sensors is below a network-wide threshold. This threshold is determined by a sensor's memory, and is usually too small. We introduce dynamic Merkle trees, and show how to use them to restrict and verify the privilege of mobile sinks. Unlike current schemes, our scheme allows all sensors in a region to simultaneously verify mobile sink privileges, and does not assume a network-wide limit on the number of node compromises. As our security analysis shows, our approach is safe from fabrication attacks, impersonation attacks and replay attacks. Further, our performance analysis shows that we incur very low communication, computation, and storage overheads.

In IEEE 802.11 based ad hoc networks, by simply manipulating the back-off timers and/or wait times prior to transmission, malicious nodes can cause a drastically reduced allocation of bandwidth to well-behaved nodes. This can result in causing bandwidth starvation and hence, a denial of service to legitimate nodes. We propose a combination of deterministic and statistical methods that facilitate detection of such misbehavior. With our approach, each of the nodes is made aware of the pseudo-random sequences that dictate the back-off times of all its one-hop neighbors. A blatant violation of the timer is thus, immediately detected. In certain cases, a node may be unable to monitor the activities of its neighbor and therefore deterministically ascertain if the neighbor is misbehaving. To cope with such cases, we propose a statistical inference method, wherein based on an auto-regressive moving average (ARMA) of observations of the system state, a node is able to estimate if its neighbor is indulging in misbehavior. Simulation results show that with our methods, it is possible to detect a malicious node with a probability close to one. Furthermore, the probability of false alarms is lower than 1%.

Abstract — Sensor deployments may be static, but researchers have recently been making a case for mobile collector nodes to enhance data acquisition. Since mobile nodes are often more privileged, their compromise can give the adversary a significant advantage. Hence, security mechanisms for such networks must tolerate mobile node compromises. Unlike static sensors, which communicate mostly with their neighbors, mobile nodes may communicate with nodes all over the network. Hence, key establishment is a much harder challenge with mobile nodes. We first analyze the impact of mobile collector compromises on the reliability of data received by the base station, and the circumstances under which reliability can be guaranteed. Second, we present mGKE, a key predistribution scheme for very general group-based sensor deployments. mGKE allows any pair of neighboring sensors to establish a unique pairwise key, regardless of sensor density or distribution. It is also usable by mobile collectors. Our analysis and evaluation show the superiority of mGKE over current methods in terms of resilience, connectivity, communication overhead, and memory requirements. I.

We present a power-efficient scheme to deliver time sensitive data packets in sensor networks. Data generated by sensors are frequently time sensitive in applications such as hazard monitoring systems, traffic controlling systems and battlefield commanding systems. Such data are associated with end-to-end deadlines, within which they must reach the base station. We make two contributions in this work. First, we propose a novel load-balanced routing scheme that distributes data packets evenly among the nodes relaying data towards the base station, avoiding bottlenecks and increasing the likelihood that packets will meet their deadlines. Second, we propose a method of grouping smaller packets into larger ones by delaying data transmissions at the relaying nodes whenever slack times are positive. Our packet grouping scheme significantly reduces packet transmissions, reduces congestion, and saves power in the sensor network. We verify the effectiveness of our approach through extensive simulations using the ns-2 simulation package

We present the Internet key service (IKS), a distributed architecture for authenticated distribution of public keys, layered on secure DNS (DNSSEC). Clients use DNSSEC to securely discover the identities of the relevant IKS servers, and send key lookup or management requests directly to these servers using a special-purpose protocol. Clients authenticate keys retrieved from IKS servers using key commitments published in DNSSEC IKS derives its authentication authority from the authority DNS domains have over Internet names. The IKS architecture is loosely coupled with DNS to minimize overhead on DNS servers. We also present RIKS, a prototype IKS implementation

Location-dependent data are central to many emerging applications, ranging from traffic information services to sensor networks. The standard pull- and push-based data dissemination models become unworkable since the data volumes and number of clients are high.We address this problem using locale covers, a subset of the original set of locations of interest, chosen to include at least one location in a suitably defined neighborhood of any client. Since location-dependent values are highly correlated with location, a query can be answered using a location close to the query point.We show that location-dependent queries may be answered satisfactorily using locale covers, with small loss of accuracy. Our approach is independent of locations and speeds of clients, and is applicable to mobile clients.

We present a group-based key predistribution scheme, GKE, which enables all pairs of neighboring sensors to establish a unique pairwise key, regardless of sensor density or distribution. Since pairwise keys are unique, security in GKE degrades gracefully as the number of compromised nodes increases. In addition, GKE is very efficient since it requires only localized communication to establish pairwise keys, significantly reducing communication overheads. Our security analysis and performance evaluation show that GKE performs very well in terms of resilience, connectivity, communication overhead and memory requirements

We introduce the vTree, an index structure for efficient processing of spatiotemporal queries over sets of objects moving along complex trajectories. The vTree is a tiered structure, and partitions space at different granularities at different tiers. It uses two novel strategies to enhance the performance of spatiotemporal queries. First, it groups objects by velocity, and indexes objects from each group at an appropriate tier in the vTree, to localize the loss of precision induced by fast objects. Second, it accommodates complex trajectories by controlled replication of object descriptors at each tier. These features permit vTree indices to remain useful for longer time durations, and to support very efficient query processing. Our algorithms for vTree joins are designed to limit the portions of index and data space explored, as well as to maximize locality within the portion of space explored.

We present a novel coding-based technique for answering spatial and spatiotemporal queries on objects moving along a system of curves on the plane such as many road networks. We handle join, range, intercept, and other spatial and spatiotemporal queries under these assumptions, with distances being measured along the trajectories. Most work to date has studied the significantly simpler case of objects moving in straight lines on the plane. Our work is an advance toward solving the problem in its more general form.Central to our approach is an efficient coding technique, based on hypercube embedding, for assigning labels to nodes in the network. The Hamming distance between codes corresponds to the physical distance between nodes, so that we can determine shortest distances in the network extremely quickly. The coding method also efficiently captures many properties of the network relevant to spatial and spatiotemporal queries. Our approach also yields a very effective spatial hashing method for this domain. Our analytical results demonstrate that our methods are space- and time-efficient.We have studied the performance of our method for large planar graphs designed to represent road networks. Experiments show that our methods are efficient and practical.

We characterize the performance of difference coding for compressing sets and database relations through an analysis of the problem of estimating the number of bits needed for storing the spacings between values in sets of integers. We provide analytical expressions for estimating the effectiveness of difference coding when the elements of the sets or the attribute fields in database tuples are drawn from the uniform and Zipf distributions. We also examine the case where a uniformly distributed domain is combined with a Zipf distribution, and with an arbitrary distribution. We present limit theorems for most cases, and probabilistic convergence results in other cases. We also examine the effects of attribute domain reordering on the compression ratio. Our simulations show excellent agreement with theory.

In contemporary machine control systems, the monitoring functions are developed and tested separately, requiring additional time and effort for their integration into a machine control system. Also, the software for most contemporary controllers is fixed and very application-dependent, so the system may not run correctly after such integration since the algorithms are time-sensitive. We show how to modularize machine tool control systems with object-oriented concepts. We define a set of software components and system services for reuse, present some system guidelines based on simulations and test analyses to help users implement controllers that satisfy real-time constraints. We present the integration of broken tool detection functionality into an existing three axis motion controller, and demonstrate that the integration requires minimal effort and skill, and that the hard real-time constraints for broken tool signal processing can be satisfied with our software architecture.

Hierarchies provide scalability in large networks and are integral to many widely-used protocols and applications. Previous approaches to constructing hierarchies have typically either assumed static hierarchy configuration, or have used bottom-up construction methods. We describe how to construct hierarchies in a top-down fashion, and show that our method is much more efficient than bottom-up methods. We also show that top-down hierarchy construction is a better choice when administrative policy constraints are imposed on hierarchy formation.

Existing methods for spatial joins require pre-existing spatial indices or other precomputation, but such approaches are inefficient and limited in generality. Operand data sets of spatial joins may not all have precomputed indices, particularly when they are dynamically generated by other selection or join operations. Also, existing spatial indices are mostly designed for spatial selections, and are not always efficient for joins. This paper explores the design and implementation of seeded trees, which are effective for spatial joins and efficient to construct at join time. Seeded trees are R-tree-like structures, but divided into seed levels and grown levels. This structure facilitates using information regarding the join to accelerate the join process, and allows efficient buffer management. In addition to the basic structure and behavior of seeded trees we present techniques for efficient seeded tree construction, a new buffer management strategy to lower I/O costs, and theoretical analysis for choosing algorithmic parameters. We also present methods for reducing space requirements and improving the stability of seeded tree performance with no additional I/O costs. Our performance studies show that the seeded tree method outperforms other tree-based methods by far both in terms of the number disk pages accessed and weighted I/O costs. Further, its performance gain is stable across different input data, and its incurred CPU penalties are also lower.

Clusters of identical intermediate servers are often created to improve availability and robustness in many domains. The use of proxy servers for the World Wide Web (WWW) and of rendezvous points in multicast routing are two such situations. However, this approach can be inefficient if identical requests are received and processed by multiple servers. We present an analysis of this problem, and develop a method called the highest random weight (HRW) mapping that eliminates these difficulties. Given an object name and a set of servers, HRW maps a request to a server using the object name, rather than any a priori knowledge of server states. Since HRW always maps a given object name to the same server within a given cluster, it may be used locally at client sites to achieve consensus on object-server mappings. We present an analysis of HRW and validate it with simulation results showing that it gives faster service times than traditional request allocation schemes such as round-robin or least-loaded, and adapts well to changes in the set of servers. HRW is particularly applicable to domains in which there are a large number of requestable objects, there is a significant probability that a requested object will be requested again, and the CPU load due to any single object can be handled by a single server. HRW has now been adopted by the multicast routing protocols PIMv2 and CBTv2 as its mechanism for routers to identify rendezvous points/cores.

This paper describes Cicero, a set of language constructs to allow constructive protocol specifications. Unlike other protocol specification languages, Cicero gives programmers explicit control over protocol execution, and facilitates both sequential and parallel implementations, especially for protocols above the transport-layer. It is intended to be used in conjunction with domain-specific libraries, and is quite different in philosophy and mode of use from existing protocol specification languages. A feature of Cicero is the use of event patterns to control synchrony, asynchrony, and concurrency in protocol execution, which helps programmers build robust protocol implementations. Event-pattern driven execution also enables implementers to exploit parallelism of varying grains in protocol execution. Event patterns can also be translated into other formal models, so that existing verification techniques may be used.

We explore the constraints of a new problem: that of coordinating network troubleshooting among peer administrative domains and untrusted observers. Allowing untrusted observers permits any entity to report problems, whether it is a network operations center (NOC), end-user, or application. Our goals are to define the inter-domain coordination problem clearly, and to develop an architecture which allows observers to report problems and receive timely feedback, regardless of their own locations and identities. By automating this process, we also relieve human bottlenecks at help desks and NOCs whenever possible. We present a doubleshooting methodology for coordinating problem diagnosis, and describe GDT, a distributed protocol which realizes this methodology.

Recent multicast routing protocol proposals such as protocol independent multicast (PIM) and core-based trees (CBT) have been based on the notion of group-shared trees. Since construction of a minimal-cost tree spanning for all members of a group is difficult, they rely on center-based trees and distribute packets from all sources over a single shortest-path tree rooted at some center. PIM and CBT provisionally use administrative selection or simple heuristics for locating the center of a group but do not preclude the use of other methods that provide an ordered list of centers. Other previously proposed heuristics typically require knowledge of the complete network topology, a requirement which is not always practical for a distributed problem such as Internet routing. We investigate the problem of finding a good center in a distributed fashion, study various heuristics for automating center selection, and examine their applicability to real-world networks. We also propose several new algorithms which we feel to be more practical than existing methods. We present simulation results on hierarchical and nonhierarchical networks showing that of the methods potentially feasible in the Internet multicast backbone, ours offer the best results in terms of cost and delay, and they incur low overhead.

Disk I/O has long been a performance bottleneck for very large databases. Database compression can be used to reduce disk I/O bandwidth requirements for large data transfers. The authors explore the compression of large statistical databases and propose techniques for organizing the compressed data such that standard database operations such as retrievals, inserts, deletes and modifications are supported. They examine the applicability and performance of three methods. Two of these are adaptions of existing methods, but the third, called tuple differential coding (TDC), is a new method that allows conventional access mechanisms to be used with the compressed data to provide efficient access. They demonstrate how the performance of queries that involve large data transfers can be improved with these database compression techniques.

The widening performance gap between CPUs and disks is significant for hash join performance. Most current hash join methods try to reduce the volume of data transferred between memory and disk. In this paper, we try to reduce hash-join times by reducing random I/O. We study how current algorithms incur random I/O, and propose a new hash join method, Seq/sup +/, that converts much of the random I/O to sequential I/O. Seq/sup +/ uses a new organization for hash buckets on a disk, and larger input and output buffer sizes. We introduce the technique of batch writes to reduce the bucket-write cost, and the concepts of write- and read-groups of hash buckets to reduce the bucket-read cost. We derive a cost model for our method and present formulas for choosing various algorithm parameters, including input and output buffer sizes. Our performance study shows that the new hash join method performs many times better than current algorithms under various environments. Since our cost functions underestimate the cost of current algorithms and overestimate the cost of Seq/sup +/, the actual performance gain of Seq/sup +/ is likely to be even greater.

Multicast routing protocol proposals such as PIM and CBT have been based on the notion of group-shared trees. Since the construction of a minimal-cost tree spanning all members of a group is difficult, they rely on center-based trees, and distribute packets from all sources over a single shortest-path tree rooted at some center. While PIM and CBT provisionally use administrative selection of centers or trivial heuristics for locating the center of a group, they do not preclude the use of other methods as long as they provide an ordered list of centers. Other previously proposed heuristics typically require knowledge of the complete network topology, a requirement which is not always practical for a distributed problem such as Internet routing. In this paper we investigate the problem of finding a good center in distributed fashion, study various heuristics for automating center selection, and examine their applicability to real-world networks. We also propose several new algorithms which we feel to be more practical than existing methods. We present simulation results showing that of the methods potentially feasible in the Internet multicast backbone, ours offer the best results in terms of cost and delay.

We examine how to apply the hash-join paradigm to spatial joins, and define a new framework for spatial hash-joins. Our spatial partition functions have two components: a set of bucket extents and an assignment function, which may map a data item into multiple buckets. Furthermore, the partition functions for the two input datasets may be different.We have designed and tested a spatial hash-join method based on this framework. The partition function for the inner dataset is initialized by sampling the dataset, and evolves as data are inserted. The partition function for the outer dataset is immutable, but may replicate a data item from the outer dataset into multiple buckets. The method mirrors relational hash-joins in other aspects. Our method needs no pre-computed indices. It is therefore applicable to a wide range of spatial joins.Our experiments show that our method outperforms current spatial join algorithms based on tree matching by a wide margin. Further, its performance is superior even when the tree-based methods have pre-computed indices. This makes the spatial hash-join method highly competitive both when the input datasets are dynamically generated and when the datasets have pre-computed indices.

Many new remote procedure calls (RPC) systems are being built to meet different application requirements, and much development effort has been spent on redoing significant parts of the RPC system. This paper describes URPC, a toolkit for prototyping new RPC systems. It allows programmers to provide high-level implementations of RPC semantics and to customize supporting RPC services, such as stub generation and name service, to match the requirements of different RPC semantics. This approach increases flexibility in constructing new RPC systems and greatly reduces coding effort. In addition, this approach allows application-specific optimization by increasing the semantic content of individual RPC calls through customization, as well as by allowing programmers to import protocol machine implementations. Thus, the generated prototype RPC implementations can perform as fast as native RPCs.

Given a statistical database containing a set of summary tables, this paper examines the complexity of retrieving data from the database in order to satisfy a query.In particular, we consider the case when the query cannot be directly satisfied via a single summary table and requires two or more summary tables.We show that a system of linear equations can be constructed from a set of summary tables whose solution(s) satisfy a query in oarying degrees.We

One approach to distributed mutual exclusion algorithms is the use of quorums. Quorum-based algorithms offer the advantage of protocol symmetry, spreading effort and responsibility uniformly across the distributed system. In this paper, we present an O(logn) algorithm to generate coterie templates of near-optimal O(n/sup 0.63/) size. Coterie templates are generic quorum structures that exhibit several desirable properties such as fault tolerance, symmetry and low storage cost. In addition, coteries can be instantiated from the template to reflect desirable network characteristics.

Data compression is one way to alleviate the I/O bottleneck problem faced by I/O-intensive applications such as databases. However, this approach is not widely used because of the lack of suitable database compression techniques. In this paper, we design and implement a novel database compression technique based on vector quantization (VQ). VQ is a data compression technique with wide applicability in speech and image coding, but it is not directly suitable for databases because it is lossy. We show how one may use a lossless version of vector quantization to reduce database space storage requirements and improve disk I/O bandwidth.>

We consider multiprocessing systems where processes make independent, Poisson distributed resource requests with mean arrival time 1. We assume that resources are not released. It is shown that the expected deadlock time is never less than 1, no matter how many processes and resources are in the system. Also, the expected number of processes blocked by deadlock time is one-half more than half the number of initially active processes. We obtain expressions for system statistics such as expected deadlock time, expected total processing time, and system efficiency, in terms of Abel sums. We derive asymptotic expressions for these statistics in the case of systems with many processes and the case of systems with a fixed number of processes. In the latter, generalizations of the Ramanujan Q -function arise. we use singularity analysis to obtain asymptotics of coefficients of generalized Q -functions.

Implementing efficient communication protocols is an important task in building distributed systems, but is complicated by the difficulties of dealing with complex multi-thread interactions and timing-related bugs. The paper describes Cicero, a set of language constructs designed to alleviate these difficulties. Cicero uses the notion of event patterns (C. V Ravishankar and R. Finkel, 1989) to help programmers build robust protocol implementations. Event patterns provide structure for controlling synchrony, asynchrony, and concurrency in protocol execution, and also allow implementers to exploit parallelism of varying grains. Event patterns can be translated into other formal models, so that existing verification techniques may be used. Our prototype implementation indicates that the total overhead imposed by event patterns accounts for less than 5% of the overall latency for protocols above the transport layer on single-processor implementations.>

Existing methods for spatial joins assume the existence of indices for the participating data sets. This assumption is not realistic for applications involving multiple map layer overlays or for queries involving non-spatial selections. In this paper, we explore a spatial join method that dynamically constructs index trees called seeded trees at join time. This methods uses knowledge of the data sets involved in the join process.

A common approach to improving the performance of statistical query processing is to use precomputed results. Another lower-level approach would be to redesign the storage structure for statistical databases. This avenue is relatively unexplored. The objective of this paper is to present a physical storage structure for statistical databases, whose design is motivated by the characteristics of statistical queries. We show that our proposal enhances multi-attribute clustering efficiency, and improves the performance of statistical and aggregational queries. This customized structure reduces the amount of I/O incurred statistical query processing, thus decreasing the response time.>

This paper presents a mechanism that facilitates and enhances the use of independently administered remote network servers in the presence of server interface heterogeneity. The mechanism is designed under the client-service model, which extends the client-server model with an abstraction of service to decouple abstract server capabilities from concrete server interface specifics such as server interface binding protocols and the interface operation invocation protocols. The mechanism selects servers, accommodates server interface heterogeneity, and handles server access failures as per the abstract server capabilities desired by the client. It could return the identity of the server used for each service access invocation to facilitate billing, refining service specifications, and reporting server-specific errors. This paper also illustrates a C library interface to this mechanism, and describes a language veneer over the C programming language demonstrating how a typed procedural language could be extended by a few language constructs to support the mechanism under the client-service model. In this language, server capabilities are referenced by abstract data type (ADT) objects, and are accessed by invoking the objects' interface operations using a call-by-value-result paradigm.>

Remote procedure call (RPC) is the most popular paradigm used today to build distributed systems and applications. As a consequence, the term "RPC" has grown to include a range of vastly different protocols above the transport layer. A resulting problem is that programs often use different RPC protocols, cannot be interconnected directly, and building a solution for each case in a large heterogeneous environment is prohibitively expensive. We describe the design of a system that can synthesize programs (RPC agents) to accommodate RPC heterogeneities. Because of its synthesis capability, the system also facilitates the design and implementation of new RPC protocols through rapid prototyping. We have built a prototype system to validate the design and to estimate the agent development costs and cross-RPC performance. The evaluation shows that the synthesis approach provides a more general solution than existing approaches do, and with lower software development and maintenance costs, while maintaining reasonable cross-RPC performance.>

Much effort has gone into studying navigation algorithms for mobile-robot systems. However, although mobile-robot systems often suffer from a lack of adequate on-board memory and communication bandwidth, little work has been done on techniques to solve these problems. Two algorithm-implementation strategies are examined to solve the memory-limitation and communication-bandwidth-limitation problems associated with the navigation of single or multiple robots in large dynamic environments. On-board main-memory-management mechanisms, cache policies, auxiliary-memory data structures, and two path planners are explored by simulations based on a new navigation algorithm. One- and two-level caches with one- and two-level planning, respectively, are investigated; these can easily be extended to schemes with more levels. The authors' results show that among the seven (three local and four global) cache policies studied, the predicted-window, aisle, and via-point policies overcame the above limitations without compromising robot performance. Therefore, one or more of these three policies can be used with implementation strategies to deal with the memory-limitation and communication-bandwidth-limitation problems encountered in real-world mobile-robot navigation. The authors' results can also be very useful in the domain of Intelligent Vehicle Highway Systems (IVHS), where the main memory of the on-board computer may be too small to hold all of the road network and other useful information.>

In this paper, we develop algorithms to achieve optimal processor allocation for pipelined hash joins in a multiprocessor-based database system. A pipeline of hash joins is composed of several stages, each of which is associated with one join operation. The whole pipeline is executed in two phases: (1) the table-building phase, and (2) the tuple-probing phase. We focus on the problem of allocating processors to the stages of a pipeline to minimize the query execution time. We formulate the processor allocation problem as a two-phase mini-max optimization problem, and develop three optimal allocation schemes under three different constraints. The effectiveness of our problem formulation and solution is verified through a detailed tuple-by-tuple simulation of pipelined hash joins. Our solution scheme is general and applicable to any optimal resource allocation problem formulated as a two-phase mini-max problem.

Abstract In this paper we describe the design and implementation of an integrated monitoring and debugging system for a distributed real‐time computer system. The monitor provides continuous, transparent monitoring capabilities throughout a real‐time system's lifecycle with bounded, minimal, predictable interference by using software support. The monitor is flexible enough to observe both high‐level events that are operating system‐ and application‐specific, as well as low‐level events such as shared variable references. We present a novel approach to monitoring shared variable references that provides transparent monitoring with low overhead. The monitor is designed to support tasks such as debugging realtime applications, aiding real‐time task scheduling, and measuring system performance. Since debugging distributed real‐time applications is particularly difficult, we describe how the monitor can be used to debug distributed and parallel applications by deterministic execution replay.

Three of the most important issues in exploiting network servers concern how to specify services so that service-server bindings can be changed dynamically without disturbing clients, how to make clients resilient to network or server failure, and how to accommodate server protocol heterogeneity to provide a single system view to the clients. A service acquisition mechanism is presented for solving these issues. This mechanism is designed under a client/service model in which the abstraction of service is a first-class entity. The components of the mechanism are discussed.>