We study the problem of continuous maintenance of range sum heat maps over dynamically updating data objects. The range sum (RS) here refers to the sum of the weights of the data objects enclosed by a given range (rectangle) R. Range sum problems are useful in spatio-temporal data analytics and decision making processes. Recent studies on range sum problems focus on computing the MaxRS query, which finds a location to place a rectangle R such that its RS is maximized. In real applications, knowing only the location with the maximum RS may be insufficient, because decision making is a multi-factor process where maximizing the RS may just be one of the factors. It is also important to gain an overview of the RS distribution at different locations, so that decisions can be made based on global knowledge. We therefore propose to compute a range-sum heat map that visualizes the RS value for every location in a data space. Considering that data objects may be inserted into or removed from the data space dynamically, we further study the continuous maintenance of range-sum heat maps over dynamically updating data objects. We adapt algorithms to compute range-sum heat maps and to perform heat map updates. We build a demo system to showcase the usefulness of range sum heat maps and the effectiveness of the adapted algorithms.

The topics of tracking moving objects and moving shapes have been extensively researched in multiple communities – from Moving Objects Databases (MOD) and spatio-temporal data management, through image/video processing and traffic management, to environmental and ecology studies. This paper gives a summary of the topics discussed in the advanced seminar on tracking objects and shapes, as well as an overview of its proposed structure. After a brief introduction and motivation-survey of different research fields and societal applications, the first part of the seminar will give a historic survey of the fundamental techniques for tracking mobile objects. The second part will give an overview of the approaches popular in MOD and spatiotemporal data management communities (tracking and querying, streaming data, map-matching, etc.). The third part is the central one – discussing the issues and solutions in distributed tracking of moving objects and shapes: from topological predicates and trends detection, through tracking deformable shapes, to specifics of indoor tracking. The fourth major part is intended to be a "potpourri-style" review of different application contexts and the popular approaches for tracking individual objects and shapes – spanning from collective motion analysis in social networks and animal herds, through toxic elements, pollutants, and geoprocesses (landslides), to different approaches for visual analytics in this context. The main objective of this advanced seminar is to provide a cohesive overview of the different perspectives on motion tracking; the corresponding approaches for its effective management; and possibilities for other research directions

This work presents a system for augmenting the functionality of Yelp-like recommendation sites by enabling users to search for places bounded by travel-time when using public transportation, and modifying recommendations based on updated weather conditions. Using public transport, although is cheaper and efficient, entails that only fixed places of boarding/exiting may be used which, in turn, implies walking to (from) a particular location from (to) a given station. Given the impact of the weather on the mood and activities, preferences for a certain type of services may need to be dynamically adjusted based on the current weather or the near-future forecast, modulo travel-routes to preferred locations. In this work, we develop a model to predict a user's preferred mode of transport (car, or public transit) from their old check-ins and incorporate the weather context into the recommendation process. We use event-based modeling to control the extent of walking depending on user-defined tolerance information and live weather conditions. We implemented a web application (both desktop and mobile platforms), utilizing existing tools such as Google Maps Direction API and Open Weather Map API for retrieving real-time information.

This work addresses the problem of efficient distributed detection and tracking of mobile and evolving/deformable spatial shapes in Wireless Sensor Networks (WSN). The shapes correspond to contiguous regions bounding the locations of sensors in which the readings of the sensors satisfy a particular threshold-based criterion related to the values of a physical phenomenon that they measure. We formalize the predicates representing the shapes in such settings and present detection algorithms. In addition, we provide a light-weight protocol and aggregation methods for energy-efficient distributed execution of those algorithms. Another contribution of this work is that we developed efficient techniques for detecting a co-occurrence of shapes within a given proximity from each other. Our experiments demonstrate that, when compared to the centralized techniques -- which is, predicates being detected in a dedicated sink -- as well as distributed periodic contours construction, our methodologies yield significant energy/communication savings.

This paper addresses the problem of efficient intrusion detection for mobile devices via correlating the user’s location and time data. We developed two statistical profiling approaches for modeling the normal spatio–temporal behavior of the users: one based on an empirical cumulative probability measure and the other based on the Markov properties of trajectories. An anomaly is detected when the probability of a particular (location, time) evolution matching the normal behavior of a given user becomes lower than a certain threshold, determined by controlling the recall rate of the model of the normal user’s behavior. We used compression techniques to reduce processing overhead while maintaining high accuracy. Our evaluation based on the Reality Mining and Geolife data sets shows that the proposed system is capable of detecting a potential intrusion within 15 min and with 94 % accuracy.

We address the problem of efficient detection of destination-related motion trends in Wireless Sensor Networks (WSN) where tracking is done in collaborative manner among the sensor nodes participating in location detection. In addition to determining a single location, applications may need to detect whether certain properties are true for the (portion of the) entire trajectories. Transmitting the sequence of (location, time) values to a dedicated sink and relying on the sink to detect the validity of the desired properties is a brute-force approach that generates a lot of communication overhead. We present an in-network distributed algorithm for efficient detecting of the Continuously Moving Towards predicate with respect to a given destination that is either a point or a region with polygonal boundary. Our experiments demonstrate that the proposed approaches yield substantial savings when compared to the brute-force one.

Trajectories representing the motion of moving objects are typically obtained via location sampling, e.g. using GPS or road-side sensors, at discrete time-instants. In-between consecutive samples, nothing is known about the whereabouts of a given moving object. Various models have been proposed (e.g., sheared cylinders; spacetime prisms) to represent the uncertainty of the moving objects both in unconstrained Euclidian space, as well as road networks. In this paper, we focus on representing the uncertainty of the objects moving along road networks as time-dependent probability distribution functions, assuming availability of a maximal speed on each road segment. For these settings, we introduce a novel indexing mechanism -- UTH (Uncertain Trajectories Hierarchy), based upon which efficient algorithms for processing spatio-temporal range queries are proposed. We also present experimental results that demonstrate the benefits of our proposed methodologies.

This work addresses the problem of geographic routing in the presence of holes or voids in wireless sensor networks. We postulate that, once the boundary of the hole has been established, relying on the existing algorithms for bypassing it may cause severe depletion of the energy reserves among the nodes at (or near) that boundary. This, in turn, may soon render some of those nodes useless for any routing (and/or sensing) purposes, thereby effectively enlarging the size of the pre-existing hole. To extend the lifetime of the nodes along the boundary of a given hole, we propose two heuristic approaches which aim at relieving some of the routing load of the boundary nodes. Towards that, our approaches propose that some of the routes that would otherwise need to bypass the hole along the boundary, should instead start to deviate from their original path further from the hole. Our experiments demonstrate that the proposed approaches not only increase the lifetime of the nodes along the boundary of a given hole, but also yield a more uniform depletion of the energy reserves in its vicinity.

We investigate the benefits of incorporating the semantics of the problem into the query processing algorithms in multicore settings. We present and evaluate three heuristics for processing spatio-temporal range queries in multicore settings, and demonstrate that significant speed-ups can be achieved, when compared to the (semi) naive approach which relies on the compiler to generate the multicore-compatible code.

We address the problem of extending the lifetime of wireless sensor networks using multi-path routing based on a family of flexible routes with soft quality of service guarantees in terms of the packets’ delivery latency. We introduce a methodology based on Bezier curves as guiding trajectories in the routing process and we address the balancing of the workload among neighboring nodes. An added benefit, due to the flexibility of the Bezier curves, is that the shapes of the (alternate) routes can be constructed in a manner that prolongs the lifetime of the nodes in the vicinity of a given source/sink. We describe a forwarding algorithm, where the relay nodes can determine locally the Bezier curve they belong to and which requires only the transmission of the so-called control points that determine the shape of one (boundary) curve. We also show how our forwarding algorithm can be adapted to incorporate the sleep-schedule of the individual nodes, thereby further prolonging the networks’ lifetime. Our simulations demonstrate that the Bezier-based routing algorithms can yield significant improvements in the networks’ overall lifetime.

This work addresses the problem of principal node selection during the tracking process in Wireless Sensor Networks (WSNs). In a typical tracking scenario, the location of a mobile unit is determined via collaborative trilateration by the nodes that have the tracked object within their sensing range. One of the participants in the trilateraion---the tracking principal---is in charge of transmitting the location and time information to a designated sink. However, as the moving object changes its location, a new principal needs to be determined and handed off the task of the subsequent sensing, trilateration and transmission to the sink. We observe that in many WSN applications in which sensing/sampling needs to be combined with multihop transmission and, possibly, in-network aggregation, the typical processing is organized in synchronized intervals, called epochs. We postulate that taking the semantics of the epoch into consideration is important when selecting tracking principals and we present efficient algorithmic solutions towards this goal. Our experiments demonstrate that the proposed approach can yield significant reduction in the number of hand-offs between consecutive tracking principals, when compared to previous works.

For high-density networks, several studies have proposed field-based routing paradigms to uniformly distribute the traffic load throughout the network. However, as network density decreases, we observe major shortcomings of the current state-of-the-art: (i) fewer number of neighbors reduce the number of available paths and leads to path merging and (ii) the paths directed towards the border of the network merge into a single path. These path merging effects decrease significantly the energy balance, and as consequence, the lifetime of the network. In this paper, we propose a novel mechanism to enable a better load balancing for single-source and multiple-source scenarios. Our evaluations demonstrate that by using the proposed methodology, the network lifetime can be prolonged between 30% and 40%.

Processing spatio-temporal queries pertaining to the whereabouts of a large number of mobile entities has traditionally been the topic of the Moving Objects Databases (MOD)research. More recently, due to the advances in sensing and communication technologies, part of the Wireless Sensor Networks(WSN) applications have focused on tracking of mobile objects. These two observations are enough of to warrant a "call" for a confluence of two relatively new but established disciplines. However we observe that a research field of its own right and, historically older than both MOD and WSN - traffic/transportation management - can also capitalize on merging the existing experiences for its own information fusion desiderata In this talk, we will overview applications from seemingly disparate domains and identify their commonalities in terms of the spatio-temporal contexts, and we will discuss how a reactive behavior with pro-active consequences can be efficiently used for large-scale management of mobile data and meta-data.

This work addresses the problem of processing continuous nearest neighbor (NN) queries for moving objects trajectories when the exact position of a given object at a particular time instant is not known, but is bounded by an uncertainty region. As has already been observed in the literature, the answers to continuous NN-queries in spatio-temporal settings are time parameterized in the sense that the objects in the answer vary over time. Incorporating uncertainty in the model yields additional attributes that affect the semantics of the answer to this type of queries. In this work, we formalize the impact of uncertainty on the answers to the continuous probabilistic NN-queries, provide a compact structure for their representation and efficient algorithms for constructing that structure. We also identify syntactic constructs for several qualitative variants of continuous probabilistic NN-queries for uncertain trajectories and present efficient algorithms for their processing.

This work addresses the problem of processing spatio-temporal range queries when the mobile entities are tracked in Wireless Sensor Network (WSN). We demonstrate that in many realistic settings, depending on the parameters of a given range query, the tracking of a particular moving object may not be needed past certain thresholds in space and/or time. We also propose and analyze distributed data-reduction techniques for the purpose of reducing the energy consumption due to communication.

This work addresses the problem of managing the reactive behavior in Wireless Sensor Networks (WSN). We consider settings in which the occurrence of a particular event, detected in a state that satisfies a given condition, should fire the execution of an action. We observe that in WSN settings, both the event and condition may pertain to some continuous phenomena that are monitored by distinct groups of nodes and, in addition, their respective detection may impose an extra communication overhead, if a correct executional behavior is desired in terms of firing the action. Towards that end, we propose the concept of a {\it meta trigger},which essentially translates a particular request, so that the communication overhead among the entities participating in its processing is minimized. We discuss a proof-of-concept implementation which demonstrates the benefits of the proposed methodology on an actual small-size network, and we present a detailed simulation-based experimental evaluation in large-scale networks. Our experiments indicate that the meta-triggers can yield substantial savings in the energy (and bandwidth) expenditures of the network, while preserving the intended executional correctness.

This work presents the SIDnet, a simulation-based environment for applications development in wireless sensor networks settings. It enables run-time interactions with the network for the purpose of observing the behavior of algorithms protocols in the presence of various conditions such as phenomena fluctuations, or a sudden loss of service both at an individual node, as well as a collection of nodes.

We address the problem of performing efficient similarity join for large sets of moving objects trajectories. Unlike previous approaches which use a dedicated index in a transformed space, our premise is that in many applications of location-based services, the trajectories are already indexed in their native space, in order to facilitate the processing of common spatio-temporal queries, e.g., range, nearest neighbor etc. We introduce a novel distance measure adapted from the classic Frechet distance, which can be naturally extended to support lower/upper bounding using the underlying indices of moving object databases in the native space. This, in turn, enables efficient implementation of various trajectory similarity joins. We report on extensive experiments demonstrating that our methodology provides performance speed-up of trajectory similarity join by more than 50% on average, while maintaining effectiveness comparable to the well-known approaches for identifying trajectory similarity based on time-series analysis.

The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic.

This work addresses the problem of obtaining the degree of similarity between trajectories of moving objects. Typically, a Moving Objects Database (MOD) contains sequences of (location, time) points describing the motion of individual objects, however, they also implicitly storethe velocity -- an important attribute describing the dynamics the motion. Our main goal is to extend the MOD capability with reasoning about how similar are the trajectories of objects, possibly moving along geographically different routes. We use a distance function which balances the lack of temporal-awareness of the Hausdorff distance with the generality (and complexity of calculation) of the Fréchet distance. Based on the observation that in practice the individual segments of trajectories are assumed to have constant speed, we provide efficient algorithms for: (1) optimal matching between trajectories; and (2) approximate matching between trajectories, both under translations and rotations, where the approximate algorithm guarantees a bounded error with respect to the optimal one.

This work tackles the problem of answer-aggregation for continuous spatio-temporal range queries in distributed settings. We assume a grid-like coverage of the spatial universe of discourse, in which each cell is governed by a Base Station (BS) that communicates with the mobile users in its zone, and is also equipped with a server that has Moving Objects Database (MOD) capabilities. The MOD server stores the data for the moving objects in a given cell, processes the continuous queries pertaining to that cell, and is connected to the MOD servers in the neighboring cells. We demonstrate that, when a range query that spans over more than one cell needs to have its answer computed for a user located in a particular cell, by intelligently combining the transmission and the aggregation of the partial results, substantial improvements can be achieved at the global level. Towards this end, we present the BORA (Bresenham-based Overlay for Routing and Aggregation) tree, which is used to combine the transmission and local data aggregation along the routes to the destination of the query's answer.

This work addresses the problem of extending the lifetime of a wireless sensor network, when a bounded delay on receiving the packets is acceptable for a given sink node. The temporal threshold for the Quality of Data (QoD) tolerance is specified with respect to the time that it takes for the packets to travel from the source to the sink along an optimal route. For these settings, we propose a methodology that enables controlling the spatio-temporal load balancing among the sensors around the optimal route. Given the QoD threshold, we use it to derive a set of parameterized Bezier curves which serve as alternate routes between the (source,sink) pair, relieving the nodes along the optimal route, while ensuring a bound on the delay of packets delivery. We provide experimental results which demonstrate that our proposed methodology can prolong the sensor networks’ lifetime for various definitions of the concept of a "lifetime" in the existing literature.

We present our prototype system, OMCAT, which optimizes the reevaluation of a set of pending continuous spatio-temporal queries on trajectory data, when some of the trajectories are affected by traffic abnormalities reported. The key observation that motivates OMCAT is that an abnormality in a given geographical region may cause changes to the answers of queries pertaining to future portions of affected trajectories. We investigate the sources of context-switching costs at various levels and propose solutions that utilize the correlation of several context dimensions to orchestrate the reevaluation of the queries. OMCAT, fully implemented on top of an existing Object Relational Database Management System - Oracle 9i, demonstrates that our techniques can substantially reduce the response time during query answer update.

This work addresses the problem of efficient reactive management of topological predicates in MOD (Moving Objects Databases) settings. Detecting the satisfiability of such predicates in mobile and dynamic environments requires management of continuous and persistent conditions. We introduce two dynamical topological predicates: moving-along and moving-towards and we present efficient algorithmic solutions for their processing. Based on this, we subsequently take a deeper insight in the behavioral aspects of a MOD which manages them and we argue that the traditional ECA (Event Condition Action) paradigm, while it may ensure correct behavior, is not well-suited for enabling the users to declaratively specify some of the parameters that may affect the efficiency aspect of the reactive behavior. Towards this end, we introduce the (ECA)2 (Evolving and Context-Aware Event-Condition-Action) paradigm as a tool for specification of the triggers used by a MOD that handles requests which span over a time-interval in dynamic environments.

A variety of mining and analysis problems --- ranging from association-rule discovery to contingency table analysis to materialization of certain approximate datacubes --- involve the extraction of knowledge from a set of categorical count data. Such data can be viewed as a collection of "transactions," where a transaction is a fixed-length vector of counts. Classical algorithms for solving count-data problems require one or more computationally intensive passes over the entire database and can be prohibitively slow. One effective method for dealing with this ever-worsening scalability problem is to run the algorithms on a small sample of the data. We present a new data-reduction algorithm, called EASE, for producing such a sample. Like the FAST algorithm introduced by Chen et al., EASE is especially designed for count data applications. Both EASE and FAST take a relatively large initial random sample and then deterministically produce a subsample whose "distance" --- appropriately defined --- from the complete database is minimal. Unlike FAST, which obtains the final subsample by quasi-greedy descent, EASE uses epsilon-approximation methods to obtain the final subsample by a process of repeated halving. Experiments both in the context of association rule mining and classical χ2 contingency-table analysis show that EASE outperforms both FAST and simple random sampling, sometimes dramatically.

Web++ is a prototype system that supports user transparent wide area replication of resources in order to improve the response time and reliability of the HTTP service. Our architecture is based on smart clients, and can be dynamically downloaded as mobile code into a user's application, presents a number of advantages. Clients keep track of the average HTTP latency that they experience from various servers and use that information in order to make to choose the replica of a resource that is expected to deliver the best response time for them. The clients also provide feedback on the observed request latencies to the servers, which allows helps the servers to determine which resources should be replicated and what would be the best locations for the replicas. We describe in this paper a distributed server-initiated approach for resource replication in which all servers can decide autonomously whether to replicate resources and the locations where the replicas should be allocated. In addition to the novel use of smart clients, our algorithm also avoids keeping track of complex network topologies by using the concept of logical segments. We present the results of experiments that show that our algorithm for resource allocation scale well with respect to the number of servers and the number of replicated resources.

We present FAST (finding associations from sampled transactions), a refined sampling-based mining algorithm that is distinguished from prior algorithms by its novel two-phase approach to sample collection. In phase I a large sample is collected to quickly and accurately estimate the support of each item in the database. In phase II, a small final sample is obtained by excluding "outlier" transactions in such a manner that the support of each item in the final sample is as close as possible to the estimated support of the item in the entire database. We propose two approaches to obtaining the final sample in phase II: trimming and growing. The trimming procedure starts from the large initial sample and removes outlier transactions until a specified stopping criterion is satisfied. In contrast, the growing procedure selects representative transactions from the initial sample and adds them to an initially empty data set.

Processing applications with a large number of dimensions has been a challenge for the KDD community. Feature selection, an effective dimensionality reduction technique, is an essential pre-processing method to remove noisy features. In the literature only a few methods have been proposed for feature selection for clustering, and almost all these methods are 'wrapper' techniques that require a clustering algorithm to evaluate candidate feature subsets. The wrapper approach is largely unsuitable in real-world applications due to its heavy reliance on clustering algorithms that require parameters such as the number of clusters, and the lack of suitable clustering criteria to evaluate clustering in different subspaces. In this paper we propose a 'filter' method that is independent of any clustering algorithm. The proposed method is based on the observation that data with clusters has a very different point-to-point distance histogram to that of data without clusters. By exploiting this we propose an entropy measure that is low if data has distinct clusters and high if it does not. The entropy measure is suitable for selecting the most important subset of features because it is invariant with the number of dimensions, and is affected only by the quality of clustering. Extensive performance evaluation over synthetic, benchmark, and real datasets shows its effectiveness.

This paper introduces FAST, a novel two-phase sampling-based algorithm for discovering association rules in large databases. In Phase I a large initial sample of transactions is collected and used to quickly and accurately estimate the support of each individual item in the database. In Phase II these estimated supports are used to either trim "outlier" transactions or select "representative" transactions from the initial sample, thereby forming a small final sample that more accurately reflects the statistical characteristics (i.e., itemset supports) of the entire database. The expensive operation of discovering association rules is then performed on the final sample. In an empirical study, FAST was able to achieve 90--95% accuracy using a final sample having a size of only 15--33% of that of a comparable random sample. This efficiency gain resulted in a speedup by roughly a factor of 10 over previous algorithms that require expensive processing of the entire database --- even efficient algorithms that exploit sampling. Our new sampling technique can be used in conjunction with almost any standard association-rule algorithm, and can potentially render scalable other algorithms that mine "count" data.

We address the problem of assigning nonpartitioned files in a parallel I/O system where the file accesses exhibit Poisson arrival rates and fixed service times. We present two new file assignment algorithms based on open queuing networks which aim at minimizing simultaneously the load balance across all disks, as well as the variance of the service time at each disk. We first present an off-line algorithm, Sort Partition, which assigns to each disk file with similar access time. Next, we show that, assuming that a perfectly balanced file assignment can be found for a given set of files, Sort Partition will find the one with minimal mean response time. We then present an on-line algorithm, Hybrid Partition, that assigns groups of files with similar service times in successive intervals while guaranteeing that the load imbalance at any point does not exceed a certain threshold. We report on synthetic experiments which exhibit skew in file accesses and sizes and we compare the performance of our new algorithms with the vanilla greedy file allocation algorithm.

We developed Web++, a prototype system based on user-transparent geographic replication which aims at improving the response time and the reliability of the HTTP service. Web++ extends the current Web client/server architecture with additional capabilities. The extension is provided via Java servlets at the server side and applets at the client side. The servlets pre-process the requested documents such that each logical URL is replaced by a list of physical URLs corresponding to the list of the resource's replica. An applet is automatically downloaded to the client machines together with the first request of each new user session. For subsequent requests within a user session, the applet chooses the physical URT, that corresponds to a resource held by an available server that is expected to deliver the best response time for the server.

The response time of DSS (decision support system) queries is typically several orders of magnitude higher than the response time of OLTP (online transaction processing) queries. Since DSS queries are often submitted interactively, techniques for reducing their response time are becoming increasingly important. We argue that caching of query results is one such technique particularly well suited to the DSS environment. We have designed a query cache manager for such an environment. The cache manager can lookup query results from the cache either based on an exact query match or using a query split algorithm to efficiently find query results which subsume the submitted query. The cache manager dynamically maintains the cache content by deciding whether a newly generated query result should be admitted to the cache and if so, which query results should be evicted from the cache to free space for the new query result. The decisions are aimed at minimizing the query response time. The decisions are explicitly based on a cost function that considers the execution cost of each query, the size of each query result, the reference frequency to each result, the cost of maintenance of each result due to updates of the base tables, and the frequency of such updates. Experimental evaluation shows that our cache manager can improve performance on TPC-D like workloads.

Caching at proxy servers is one of the ways to reduce the response time perceived by World Wide Web users. Cache replacement algorithms play a central role in the response time reduction by selecting a subset of documents for caching, so that a given performance metric is maximized. At the same time, the cache must take extra steps to guarantee some form of consistency of the cached documents. Cache consistency algorithms enforce appropriate guarantees about the staleness of the cached documents. We describe a unified cache maintenance algorithm, LNC-R-WS-U, which integrates both cache replacement and consistency algorithms. The LNC-R-WS-U algorithm evicts documents from the cache based on the delay to fetch each document into the cache. Consequently, the documents that took a long time to fetch are preferentially kept in the cache. The LNC-R-W3-U algorithm also considers in the eviction consideration the validation rate of each document, as provided by the cache consistency component of LNC-R-WS-U. Consequently, documents that are infrequently updated and thus seldom require validations are preferentially retained in the cache. We describe the implementation of LNC-R-W3-U and its integration with the Apache 1.2.6 code base. Finally, we present a trace-driven experimental study of LNC-R-W3-U performance and its comparison with other previously published algorithms for cache maintenance.

Semantic integration and data integration are two main processes that multidatabase systems need to employ in order to support interoperability. Both these processes involve uncertainty when attribute correspondences and global IDs are unknown or imprecise. The role-set approach is a new conceptual framework for data integration in multidatabase systems that maintains the materialization autonomy of local database systems by presenting the answer to a query as a set of sets representing the distinct intersections between the relations corresponding to the various roles played by an entity. In this article, we present an approach for dynamic database integration and query processing in the absence of information about attribute correspondences and global IDs. We define different types of equivalence conditions for the construction of global IDs. We propose a strategy based on ranked role-sets that makes use of an automated semantic integration procedure based on neural networks to determine candidate global IDs. The data integration and query processing steps then produce a number of role-sets, ranked by the similarity of the candidate IDs. © 1998 John Wiley & Sons, Inc.

We present a model for data reorganization in parallel disk systems that is geared toward load balancing in an environment with periodic access patterns. Data reorganization is performed by disk cooling, i.e., migrating files or extents from the hottest disks to the coldest ones. We develop an approximate queueing model for determining the effective arrival rates of cooling requests and discuss its use in assessing the costs versus benefits of cooling actions.

Most data mining research has focused on generating rules within databases containing structured values while essentially ignoring the potentially valuable information that exists in the unstructured blocks of text. This paper suggests an approach for generating association rules that relates structured data values to concepts extracted from unstructured data. Our approach involves the use of an extended concept hierarchy (ECH) to maintain parent, child, and sibling relationships between concepts. This structure allows us to generate rules that relate a given concept in the ECH and a given structured attribute value to the neighbors of the given concept in the ECH. We also describe an efficient implementation of the ECH that keeps track of concepts and pointers to documents associated with them. Experimental results on documents from the ABI/Inform Information Retrieval System are presented. 1 Introduction With the abundant amounts of information available to businesses today, an urg...

The role-set approach is a new conceptual framework for data integration in multidatabase systems that maintains the materialization autonomy of local database systems and provides users with more accurate information. The role-set approach presents the answer to a query as a set of relations where the distinct intersections between the relations correspond to the various roles played by an entity. The authors show how the basic role-based approach can be extended in the absence of information about the multidatabase keys (global IDs). They propose a strategy based on ranked role-sets that makes use of a semantic integration procedure based on neural networks to determine candidate global IDs. The data integration and query processing steps then produce a number of role-sets, ranked by the similarity of the candidate IDs.

We present a continuous deadlock detection and resolution algorithm in distributed database systems.Our algorithm maintains an augmented transaction wait-for graph at each site and uses a modified priority-based probe generation scheme in order to detect local deadlocks without transmitting any intra-site deadlock detection messages, to minimize the number of inter-site messages sent for detection of global deadlocks and also for the early detection of global deadlocks that might occur in the future without transmitting detection messages repeatedly.The augmented transaction wait-for graph contains, in addition to lock-wait information, information about message-wait relationships among agents of a transaction, probes received from other sites and transitive wait-for relationships among transactions.Global deadlocks are declared whenever a transitive wait-for relationship from an agent of a global transaction is constructed for some agent of the transaction.

Distributed query processing algorithms usually perform data reduction by using a semijoin program but the problem with these approaches is that they still require an explicit join of the reduced relations an the final phase. We introduce an efficient algorithm for join processing in distributed database systems that makes use of bipartite graphs in order to reduce data communication costs and local processing costs. The bipartite graphs represent the tuples that can be joined in two relations taking into account also the reduction state of the relations. This algorithm fully reduces the relations at each site. We then present a partitioning algorithm for response time optimization that takes into account the system configuration, i.e., the additional resources available. We also report on the results of a set of experiments that show that our algorithms outperform a number of the recently proposed methods for total processing time and response time minimization.

Presents a simulation-based performance analysis of a concurrent file reorganization algorithm. We examine the effect on throughput of (a) buffer size, (b) degree of reorganization, (c) write probability of transactions, (d) multiprogramming level, and (e) degree of clustered transactions. The problem of file reorganization that we consider involves altering the placement of records on pages of a secondary storage device. In addition, we want this reorganization to be done in place, i.e. using the file's original storage space for the newly reorganized file. Our approach is appropriate for a non-in-place reorganization as well. The motivation for such a physical change, i.e. record clustering, is to improve the database system's performance, i.e. minimizing the number of page accesses made in answering a set of queries. There are numerous record clustering algorithms, but they usually do not solve the entire problem, i.e., they do not specify how to efficiently reorganize the file to reflect the clustering assignment that they determine. In previous work, we have presented an algorithm that is a companion to general record clustering algorithms, i.e. it actually transforms the file. In this work we show through simulation that our algorithm, when run concurrently with user transactions, provides an acceptable level of overall database system performance.>

A Multidatabase System (MDBS) is a software package that integrates a number of pre-existing, au-tonomous and heterogeneous Local Database Systems (LDBS). Ensuring the consistency of global transac-tions in the case of failures is a difficult problem due to heterogeneity and to the presence of local transac-tions at the recovering LDBSS. We present a recovery scheme for MDBS that guarantees the correctness of persistent data in the presence of transaction failures, MDBS failures or site failures. Our scheme employs a global commit protocol which can be supported at minimum cost and ensures a higher degree of local autonomy as compared to alternative schemes.

The authors presents performance analysis of a concurrent file reorganization algorithm. They examined the effect of buffer size, degree of reorganization, and write probability of transactions on system throughput. The problem of file reorganization considered involves altering the placement of records on pages on a secondary storage device. This reorganization must be done in-place. The approach is appropriate for a non-in-place reorganization. The motivation for such a physical change is to improve the database system's performance, by minimizing the number of page accesses made in answering a set of queries. It is shown through simulation that the algorithm, when run concurrently with user transactions, provides an acceptable level of overall database system performance. >

The authors address the deadlock problem in sequential transaction processing where the strict two-phase locking and the multiple granularity locking protocol with five lock modes are used. The scheduling policy honors lock requests in a first-in-first-out basis except for lock conversions. As a basic tool, a direct graph model called the holder/wire-transaction waited-by graph (H/W-TWBG) is introduced to capture the precise status of systems in terms of deadlock. The properties of H/W-TWBG are presented. Based on H/W-TWBG, the identification principles of the victim candidates are established in a deadlock cycle, and a periodic deadlock detection and resolution algorithm which has a reasonable time and storage complexity is preserved. One important feature of the deadlock resolution scheme is that some deadlocks can be resolved without aborting any transaction.>

An algorithm for deadlock detection and resolution in sequential transaction processing is presented. Two-phase locking is assumed for ensuring serializability, the lock requests obey the granularity locking protocol, and each granule may be locked in one of the following lock modes: IS, IX, S, SIX and X. For each object, lock requests are honored according to a first-come-first-served basis except for lock conversions. The basic idea for the deadlock detection resolution is in the construction of a new direct graph called a holder/waiter-transaction waited-by graph. The authors establish guidelines for the identification of a victim in a deadlock cycle and propose a resolution algorithm whose time and space requirements are reasonable and whose solution is near optimal.>

Large arrays of small disks are being considered as a promising approach to high performance 1/0 architectures.In this paper we deal with the problem of data placement in such a disk array.The prevalent approach is to decluster large files across a number of disks so as to minimize the access time to a file and balance the 1/0 load across the disks.The data placement problem entails determining the number of disks and the set of disks across which a file is declustered.Unlike previous work, this paper does not assume that all files are allocated at the same time but rather considers dynamic file creations, This makes the placement problem considerably harder because each placement decision has to take into account the current allocation state and the access frequencies of the disks and the existing files.As a result, file creation may involve partial reorganization on one or more disks.The paper proposes heuristic algorithms for the placement of dynamically created files.The algorithms provide a good compromise between maximizing 1/0 performance of the disk array and minimizing the work invested in partial reorganizations.The paper presents preliminary performance results of various alternative algorithms under a synthetic workload.

We present an efficient heuristic algorithm for record clustering that can run on a SIMD machine. We introduce the P-tree, and its associated numbering scheme, which in the split phase allows each processor independently to compute the unique cluster number of a record satisfying an arbitrary query. We show that by restricting ourselves in the merge phase to combining only sibling clusters, we obtain a parallel algorithm whose speedup ratio is optimal in the number of processors used. Finally, we report on experiments showing that our method produces substantial savings in an enviornment with relatively little overlap among the queries.

We examine the problem of broadcasting in a point-to-point computer network where a message, originated by one node, is transmitted to all nodes, subject to the restriction that an informed node can call only one of its neighbors Auring a given time unit. A dynamic programming formulation for optimal broadcasting in general networks is given, and an exact algorithm based on it is developed. Since this algorithm is not very efficient for larger networks, we present a number of heuristics for achieving efficient near-optimal algorithms. In particular, we discuss in detail a class of heuristics which require finding at each step a least-weight maximum matching in a bipartite graph.

Article Free Access Share on Storage mappings for multidimensional linear dynamic hashing Authors: Mohamed Ouksel Northwestern University, Evanston, Illinois Northwestern University, Evanston, IllinoisSearch about this author , Peter Scheuermann Northwestern University, Evanston, Illinois Northwestern University, Evanston, IllinoisSearch about this author Authors Info & Claims PODS '83: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1983Pages 90–105https://doi.org/10.1145/588058.588071Published:21 March 1983Publication History 31citation335DownloadsMetricsTotal Citations31Total Downloads335Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The typical design process for the relational database model develops the conceptual schema and each of the external schemas separately and independently from each other. This paper proposes a new design methodology that constructs the conceptual schema in such a way that overlappings among external schemas are reflected. If the overlappings of external schemas do not produce transitivity at the conceptual level, then with our design method, the relations in the external schemas can be realized as a join over independent components. Thus, a one-to-one function can be defined for the mapping between tuples in the external schemas to tuples in the conceptual schema. If transitivity is produced, then we show that no such function is possible and a new technique is introduced to handle this special case.

Performance modelling of data base systems requires taking into consideration the complex interactions between the different physical design parameters and the system workload parameters. In order to facilitate a data base designer in evaluating various implementation strategies, a simulation language is presented which has three distinct components (1) data definition (2) query definition and (3) mapping to storage definition. A number of features characterize this type of descriptive mechanism. First, the system workload parameters (1 and 2) must be described in terms of statistical distributions, which implies that the storage structure is subject to the same stochastic variability. Secondly, the level of detail required to describe mappings to storage for simulation purposes is lower than that required by standard data definition or mapping languages. The process of embedding a structure in storage is decomposed into a number of steps, each introducing additional implementation oriented details.

Set theory and algebra are convenient tools which have been used quite extensively to describe data bases from the logical point of view. We carry this approach one step further, by observing that the semantics of the connectivities at the encoding level can be conveyed with the same formalism. To provide for the actual binding with the physical device level we introduce the notion of an address space function, which describes various degrees of relative positioning on physical devices. This methodology is developed with an eye towards a special purpose simulation language for data base systems and allows not only for the representation of data at different hierarchical levels, but also at various degrees of detail, as desired by the simulator.