No abstract available.

We introduce the heap-on-top (hot) priority queue data structure that combines the multilevel bucket data structure of Denardo and Fox with a heap. Our data structure has superior operation bounds than either structure taken alone. We use the new data structure to obtain an improved bound for Dijkstra's shortest path algorithm. We also discuss a practical implementation of hot queues. Our experimental results in the context of Dijkstra's algorithm show that this implementation of hot queues performs very well and is more robust than implementations based only on heap or multilevel bucket data structures.

this paper is to study and validate the use of the kinetic data structures proposed in [BGH97] in practice. The implementation and experimental evaluation of such structures brings to light several important issues which were not addressed in the original paper. For instance, KDSs implement the continuous maintenance of the function of interest through a discrete-event simulation. The calculation of the event times poses numerical difficulties which raise questions about the integrity of the structure if nearby events should happen out of order, or if the time of an event changes when recalculated. Also, the algorithmic measures for evaluating the quality of KDSs in [BGH97] are all worst-case measures, which may not reflect behavior under ordinary motions which occur in practice. It may well be that simple data structures do better in such situations. In order to study these issues, we have compared the KDSs of [BGH97] with simpler variants under various common data/motion distributions, each meant to generate a different amount of

Clustering is increasing in importance, but linear-and even constant-time clustering algorithms are often too slow for real-time applications.A simple way to speed up clustering is to speed up the distance calculations at the heart of clustering routines.We study two techniques for improving the cost ofdistance calculations, LSI and trrmcation, and determine both how much these techniques speed up clustering and how much they affect the quality of the resulting clusters.We find that the speed increase is significant whilesurprisingly -the quality of clustering is not adversely affected.We conclude that truncation yields clusters as good as those produced by full-profile clustering while offering a significant speed advantage.

Methods exist for comtant-time clustering of corpus subsets selected via Scatter/Gather browsing [3].In thii paper we expand on those techniqum, giving an algorithm for alrnostconstant-time clustering of arbitrary corpus subsets.This algorithm is never slower than clustering the document set from scratch, and for medium-sised and large sets it is significantly faster.ThE algorithm ia USSM for clustering arbitrary subsets of large corpora -obtained, for instance, by a boolean search -quickly enough to be useful in an interactive setting.

One of the most well-studied problems in data mining is mining for association rules in market basket data. Association rules, whose significance is measured via support and confidence, are intended to identify rules of the type, “A customer purchasing item A often also purchases item B.” Motivated by the goal of generalizing beyond market baskets and the association rules used with them, we develop the notion of mining rules that identify correlations (generalizing associations), and we consider both the absence and presence of items as a basis for generating rules. We propose measuring significance of associations via the chi-squared test for correlation from classical statistics. This leads to a measure that is upward closed in the itemset lattice, enabling us to reduce the mining problem to the search for a border between correlated and uncorrelated itemsets in the lattice. We develop pruning strategies and devise an efficient algorithm for the resulting problem. We demonstrate its effectiveness by testing it on census data and finding term dependence in a corpus of text documents, as well as on synthetic data.