52828756
Fast computation of database operations using graphics processors
We present new algorithms for performing fast computation of several common database operations on commodity graphics processors. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are essential computational components of typical database, data warehousing, and data mining applications. While graphics processing units (GPUs) have been designed for fast display of geometric primitives, we utilize the inherent pipelining and parallelism, single instruction and multiple data (SIMD) capabilities, and vector processing functionality of GPUs, for evaluating boolean predicate combinations and semi-linear queries on attributes and executing database operations efficiently. Our algorithms take into account some of the limitations of the programming model of current GPUs and perform no data rearrangements. Our algorithms have been implemented on a programmable GPU (e.g. NVIDIA's GeForce FX 5900) and applied to databases consisting of up to a million records. We have compared their performance with an optimized implementation of CPU-based algorithms. Our experiments indicate that the graphics processor available on commodity computer systems is an effective co-processor for performing database operations.
11841640
Accelerating Profile Queries in Elevation Maps
Elevation maps are a widely used spatial data representation in geographical information systems (GIS). Paths on elevation maps can be characterized by profiles, which describe relative elevation as a function of distance. In this research, we address the inverse of this mapping - given a profile, how to efficiently find paths that could have generated it. This is called the profile query problem. Profiles have a wide variety of uses that include registering tracking information, or even other maps, to a given map. We describe a probabilistic model to characterize the maximal likelihood that a point lying on a path matches the query profile. Propagation of such probabilities to neighboring points can effectively prune the search space. This model enables us to efficiently answer queries of arbitrary profiles with user-specified error tolerances. When compared to existing spatial index methods, our approach supports more flexible queries with orders of magnitude speedup.
62615149
Mining Asynchronous Periodic Patterns in Time Series Data
Periodicy detection in time series data is a challenging problem of great importance in many applications. Most previous work focused on mining synchronous periodic patterns and did not recognize the misaligned presence of a pattern due to the intervention of random noise. In this paper, we propose a more flexible model of asynchronous periodic pattern that may be present only within a subsequence and whose occurrences may be shifted due to disturbance. Two parameters min/spl I.bar/rep and max/spl I.bar/dis are employed to specify the minimum number of repetitions that is required within each segment of nondisrupted pattern occurrences and the maximum allowed disturbance between any two successive valid segments. Upon satisfying these two requirements, the longest valid subsequence of a pattern is returned. A two-phase algorithm is devised to first generate potential periods by distance-based pruning followed by an iterative procedure to derive and validate candidate patterns and locate the longest valid subsequence. We also show that this algorithm cannot only provide linear time complexity with respect to the length of the sequence but also achieve space efficiency.
28890
Extension of Lower Probabilities and Coherence of Belief Measures
Coherence is an important concept which is introduced and discussed in a new mathematics branch, Imprecise Probability Theory. By using the Choquet integral, belief measures can be extended to be coherent lower previsions on the linear space consisting of all bounded functions. As a special case, we establish that all belief measures are coherent imprecise probabilities.
19868872
Management Assistance for Work First via a Dynamic Website
The purpose of the Work First project is to assist the state Dept. of Health and Human Services (DHHS) staff and each county Dept. of Social Services (DSS) across the state in the management of welfare reform initiatives. Work First is the cash assistance program in NC. One important objective is to encourage and support program managers to use data on outcomes to assess their performance. This is accomplished by providing them with easy to use and easy to understand comprehensive information on the experiences of families and individuals that have received assistance through their agency over time.
14969897
Dynamic adaptive file management in a local area network
In light of advances in processor and networking technology, especially the emergence of network attached disks, the traditional client-server architecture of file systems has become suboptimal for many computation/data intensive applications. We introduce a revised architecture for file management employing network attached storage: the dynamic file server environment (Dynamo). Dynamo introduces two main architectural innovations: to provide high scalability, the file management functions are mainly performed cooperatively by the clients in the system. Furthermore, data is transferred directly to the client's cache from network-attached disks, thus avoiding copies from a disk to the server buffer and then over the network to the client. Secondly, Dynamo uses a cooperative cache management which employs a decentralized lottery-based page replacement strategy. We show via performance benchmarks run on the Dynamo system and simulation results how this architecture increases the system's adaptability, scalability and cost performance.
6564567
Stabbing the sky: efficient skyline computation over sliding windows
We consider the problem of efficiently computing the skyline against the most recent N elements in a data stream seen so far. Specifically, we study the n-of-N skyline queries; that is, computing the skyline for the most recent n (/spl forall/n/spl les/N) elements. Firstly, we developed an effective pruning technique to minimize the number of elements to be kept. It can be shown that on average storing only O(log/sup d/ N) elements from the most recent N elements is sufficient to support the precise computation of all n-of-N skyline queries in a d-dimension space if the data distribution on each dimension is independent. Then, a novel encoding scheme is proposed, together with efficient update techniques, for the stored elements, so that computing an n-of-N skyline query in a d-dimension space takes O(log N+s) time that is reduced to O(d log log N+s) if the data distribution is independent, where s is the number of skyline points. Thirdly, a novel trigger based technique is provided to process continuous n-of-N skyline queries with O(/spl delta/) time to update the current result per new data element and O(log s) time to update the trigger list per result change, where /spl delta/ is the number of element changes from the current result to the new result. Finally, we extend our techniques to computing the skyline against an arbitrary window in the most recent N element. Besides theoretical performance guarantees, our extensive experiments demonstrated that the new techniques can support on-line skyline query computation over very rapid data streams.
9657581
k-anycast game in selfish networks
Conventionally, the majority of network routing protocols assume that every network terminal or link forwards data for others without any deviation. However, this may not be true when the terminals or links are owned by individual selfish users, who always tries to maximize their own benefits instead of faithfully following a prescribed protocol. In this paper, we propose a new routing protocol, called k-anycast routing, that works well even if network links (or terminals or both) are selfish. In our protocol, the source node first finds a tree that spans k receivers out of a set of possible receivers and pay the relay links to compensate their costs. We prove that every relay link follows the routing protocol: it maximizes its profit when it declares its actual cost
41218825
Relaxed game chromatic number of graphs
This paper discusses a coloring game on graphs. Let k, d be non-negative integers and C a set of k colors. Two persons, Alice and Bob, alternately color the vertices of G with colors from C, with Alice having the first move. A color i is legal for an uncolored vertex x if by coloring x with color i, the subgraph of G induced by those vertices of color i has maximum degree at most d. Each move of Alice or Bob colors an uncolored vertex with a legal color. The game is over if either all vertices are colored, or no more vertices can be colored with a legal color. Alice's goal is to produce a legal coloring which colors all the vertices of G, and Bob's goal is to prevent this from happening. We shall prove that if G is a forest, then for k = 3, d ≥ 1, Alice has a winning strategy. If G is an outerplanar graph, then for k = 6 and d ≥ 1, Alice has a winning strategy.
7654975
Using low-discrepancy sequences and the Crofton formula to compute surface areas of geometric models
The surface area of a geometric model, like its volume, is an important integral property that needs to be evaluated frequently and accurately in practice. In this paper, we present a new quasi-Monte Carlo method using low-discrepancy sequences for computing the surface area of a 3D object. We show that the new method is more efficient than a Monte Carlo method using pseudo-random numbers. This method is based on the Cauchy ‐ Crofton formula from integral geometry, and it computes the surface area of a 3D body B by counting the number of intersection points between the boundary surface of B and a set of straight lines in E 3 . Low discrepancy sequences are used to generate the set of lines in E 3 to reduce the estimation errors that would be caused by using statistically uniformly distributed lines. We study and compare two different methods for generating 3D random lines, and demonstrate their validity theoretically and experimentally. Experiments suggest that the new quasi-Monte Carlo method is also more efficient than the conventional approach based on surface tessellation. q 2002 Elsevier Science Ltd. All rights reserved.
3416923
Efficient Computation of the Skyline Cube
Skyline has been proposed as an important operator for multi-criteria decision making, data mining and visualization, and user-preference queries. In this paper. we consider the problem of efficiently computing a SKYCUBE, which consists of skylines of all possible non-empty subsets of a given set of dimensions. While existing skyline computation algorithms can be immediately extended to computing each skyline query independently, such "shared-nothing" algorithms are inefficient. We develop several computation sharing strategies based on effectively identifying the computation dependencies among multiple related skyline queries. Based on these sharing strategies, two novel algorithms, Bottom-Up and Top-Down algorithms, are proposed to compute SKYCUBE efficiently. Finally, our extensive performance evaluations confirm the effectiveness of the sharing strategies. It is shown that new algorithms significantly outperform the naive ones.