Recent papers have claimed that the result of K-means clustering for time series subsequences (STS clustering) is independent of the time series that created it. Our paper revisits this claim. In particular, we consider the following question: Given several time series sequences and a set of STS cluster centroids from one of them (generated by the K-means algorithm), is it possible to reliably determine which of the sequences produced these cluster centroids? While recent results suggest that the answer should be NO, we answer this question in the affirmative.We present cluster shape distance, an alternate distance measure for time series subsequence clusters, based on cluster shapes. Given a set of clusters, its shape is the sorted list of the pairwise Euclidean distances between their centroids. We then present two algorithms based on this distance measure, which match a set of STS cluster centroids with the time series that produced it. While the first algorithm creates DQG reuse this term more smaller "fingerprints" for the sequences, the second is more accurate. In our experiments with a dataset of 10 sequences, it produced a correct match 100% of the time.Furthermore, we offer an analysis that explains why our cluster shape distance provides a reliable way to match STS clusters to the original sequences, whereas cluster set distance fails to do so. Our work establishes for the first time a strong relation between the result of K-means STS clustering and the time series sequence that created it, despite earlier predictions that this is not possible.

Spatial aggregation is an important class of queries for geoaware spatial sensor database applications. Given a set of spatial regions, it involves the aggregation of dynamic sensor readings over each of these regions simultaneously. Nested spatial aggregation involves one more level of aggregation, combining these aggregates into a single aggregate value. We show that spatial aggregate values can often be computed in-network, rather than waiting until the partial aggregate records reach the root as is now the case. This decreases the amount of communication involved in query evaluation, thereby reducing the network's power consumption. We describe an algorithm that allows us to determine when an aggregate record for any spatial region is ready to be evaluated in-network, based on decorating the routing tree with region leader lists. We also identify several important scenarios, such as nested spatial aggregation and filtering predicates, when the savings from our approach are expected to be particularly great.

We describe our experience with CQA/CDB, a prototype rational linear constraint database. First, we show that the standard semantics of constraint databases lead to an anomaly when queried in the presence of missing attributes. In CQA/CDB, this anomaly is avoided by enriching the CDB relational schema, resulting in heterogenous databases. Then, we present spatial databases as a special case of heterogenous databases and extend constraint query algebras (CQAs) with two additional spatial operators, proving that the resulting language is safe for linear constraints.

In this paper, we study constraint databases with variable independence conditions (vics). Such databases occur naturally in the context of temporal and spatiotemporal database applications. Using computational geometry techniques, we show that variable independence is decidable for linear constraint databases. We also present a set of rules for inferring vics in relational algebra expressions. Using vics, we define a subset of relational algebra that is closed under restricted aggregation.

Evolutionary computation (EC) and intelligence are closely related. Adaptability can be considered an indispensable aspect of intelligence; in turn, interaction of an agent with its environment is necessary for adaptation. Interaction is fundamental to EC at multiple levels, and an interactive viewpoint enhances our understanding of EC principles. Interaction is based on a stream-based rather than string-based view of computation, modeled mathematically by coinduction and coalgebras. It forces us to rethink some fundamental assumptions of computer science. The challenge of building intelligent systems can be better met by accepting a paradigm shift from traditional algorithmic models of computation toward interaction, with all its implications.

We discuss the issue of adding aggregation to constraint databases. Previous work has shown that, in general, adding aggregates to constraint databases results in languages that are not closed. We show that by imposing a natural restriction, called variable independence (which is a generalization of the assumptions underlying the classical relational model of data) on the schema, we can guarantee that a restricted version of the language with aggregation is closed. We illustrate our approach in the context of linear constraint databases. 1 Introduction Constraint databases [KKR90] are a natural generalization of the relational model of data by allowing infinite relations that are finitely representable using constraints. Constraint databases find numerous applications in spatial [BJM93, BK95, BLLM95, PVdBVG94, VGVG95] and temporal databases [Cho94]. Generalizing aggregation operators to constraint databases has been identified as one of the most important open research issues in this...

Global register allocation and spilling is commonly performed by solving a graph coloring problem. In this paper we present a new coherent set of heuristic methods for reducing the amount of spill code generated. This results in more efficient (and shorter) compiled code. Our approach has been compared to both standard and priority-based coloring algorithms, universally outperforming them.