9724637
Selecting Stars: The k Most Representative Skyline Operator
Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of selecting k skyline points so that the number of points, which are dominated by at least one of these k skyline points, is maximized. We first present an efficient dynamic programming based exact algorithm in a 2d-space. Then, we show that the problem is NP-hard when the dimensionality is 3 or more and it can be approximately solved by a polynomial time algorithm with the guaranteed approximation ratio 1-1/e. To speed-up the computation, an efficient, scalable, index-based randomized algorithm is developed by applying the FM probabilistic counting technique. A comprehensive performance evaluation demonstrates that our randomized technique is very efficient, highly accurate, and scalable.
4916717
Building Data Synopses Within a Known Maximum Error Bound
The constructions of Haar wavelet synopses for large data sets have proven to be useful tools for data approximation. Recently, research on constructing wavelet synopses with a guaranteed maximum error has gained attention. Two relevant problems have been proposed: One is the size bounded problem that requires the construction of a synopsis of a given size to minimize the maximum error. Another is the error bounded problem that requires a minimum sized synopsis be built to satisfy a given error bound. The optimum algorithms for these two problems take O(N2) time complexity. In this paper, we provide new algorithms for building error-bounded synopses. We first provide several property-based pruning techniques, which can greatly improve the performance of optimal error bounded synopses construction. We then demonstrate the efficiencies and effectiveness of our techniques through extensive experiments.
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.
3994784
Error minimization for approximate computation of range aggregates
Histogram techniques are widely used in commercial database management systems for an estimation of query results. Recently, they have been also used in approximately, processing database queries, especially aggregation queries. Existing research results in this area have been mainly focused on constructing a histogram to approximately represent, as accurate as possible on an intuitive base, the original data frequencies. We propose a novel histogram construction method aiming to minimize the average approximate aggregation errors; and we have developed an efficient algorithm to construct near optimal histograms to achieve this goal. Our experiment results showed that the new histogram construction techniques lead to more accurate results than those by existing histogram techniques, and also out-perform the existing wavelet techniques.
3022359
CVSSearch: searching through source code using CVS comments
CVSSearch is a tool that searches for fragments of source code by using CVS comments. CVS is a version control system that is widely used in the open source community. Our search tool takes advantage of the fact that a CVS comment typically describes the lines of code involved in the commit and this description will typically hold for many future versions. In other words, CVSSearch allows one to better search the most recent version of the code by looking at previous versions to better understand the current version. In this paper we describe our algorithm for mapping CVS comments to the corresponding source code, present a search tool based on this technique, and discuss preliminary feedback.
4018890
Clustering Moving Objects for Spatio-temporal Selectivity Estimation
Many spatio-temporal applications involve managing and querying moving objects. In such an environment, predictive spatio-temporal queries become an important query class to be processed to capture the nature of moving objects. In this paper, we investigated the problem of selectivity estimation for predictive spatio-temporal queries. We propose a novel histogram technique based on a clustering paradigm. To avoid expensive computation costs, we developed linear time heuristics to construct such a histogram. Our performance study indicated that the new techniques improve the accuracy of the existing techniques by one order of magnitude.
36931032
A Roof Edge Detection Model
We have generalized the Mumford-Shah model to obtain a new model capable of detecting roof edges. In this new model, we have assumed a piecewise planar surface for each bounded region. We have also shown that this new model is less dependent on the scale parameter ν than the original Mumford-Shah model. We have proved that the gradient projection method can produce the minimal energy. The validity of the new model is demonstrated by experimental results.
13853728
A power-optimized joint source channel coding for scalable video streaming over wireless channel
Scalable video streaming over wireless link is a very challenging task due to the time-varying characteristics of wireless channel and limited battery resource in handheld devices. This paper first describes a general approach for joint source channel coding (JSCC) with optimal power consumption. Then, an end-to-end power-optimized architecture for video streaming is presented. Therein the channel-adaptive hybrid UEP (unequal error protection) and ARQ (automatic repeat request) scheme is proposed to achieve the minimal power consumption. Simulation results demonstrate the effectiveness of our proposed scheme.
26270441
Performance limits of the innovations-based detection algorithm
A theoretical evaluation of the performance limits of the innovations-based detection algorithm, which provides an adaptive algorithm for discriminating between two hypotheses parameterized as autoregressive (AR) models, is presented. Two particular cases are considered. One pertains to a situation in which the variance of the interference (modeled as an AR process) acting alone is known a priori. The other pertains to a situation in which no such knowledge is available. Detailed computer simulations are carried out to confirm the practical validity of the theory. >
9830436
A Flexible Conversational Dialog System for MP3 Player
In recent years, an increasing number of new devices have found their way into the cars we drive. Speech-operated devices in particular provide a great service to drivers by minimizing distraction, so that they can keep their hands on the wheel and their eyes on the road. This presentation will demonstrate our latest development of an in-car dialog system for an MP3 player designed under a joint research effort from Bosch RTC, VW ERL, Stanford CSLI, and SRI STAR Lab funded by NIST ATP [Weng et al 2004] with this goal in mind. This project has developed a number of new technologies, some of which are already incorporated in the system. These include: end-pointing with prosodic cues, error identification and recovering strategies, flexible multi-threaded, multi-device dialog management, and content optimization and organization strategies. A number of important language phenomena are also covered in the system's functionality. For instance, one may use words relying on context, such as 'this,' 'that,' 'it,' and 'them,' to reference items mentioned in particular use contexts. Different types of verbal revision are also permitted by the system, providing a great convenience to its users. The system supports multi-threaded dialogs so that users can diverge to a different topic before the current one is finished and still come back to the first after the second topic is done. To lower the cognitive load on the drivers, the content optimization component organizes any information given to users based on ontological structures, and may also refine users' queries via various strategies. Domain knowledge is represented using OWL, a web ontology language recommended by W3C, which should greatly facilitate its portability to new domains.The spoken dialog system consists of a number of components (see Fig. 1 for details). Instead of the hub architecture employed by Communicator projects [Senef et al, 1998], it is developed in Java and uses a flexible event-based, message-oriented middleware. This allows for dynamic registration of new components. Among the component modules in Figure 1, we use the Nuance speech recognition engine with class-based ngrams and dynamic grammars, and the Nuance Vocalizer as the TTS engine. The Speech Enhancer removes noises and echo. The Prosody module will provide additional features to the Natural Language Understanding (NLU) and Dialogue Manager (DM) modules to improve their performance.The NLU module takes a sequence of recognized words and tags, performs a deep linguistic analysis with probabilistic models, and produces an XML-based semantic feature structure representation. Parallel to the deep analysis, a topic classifier assigns top n topics to the utterance, which are used in the cases where the dialog manager cannot make any sense of the parsed structure. The NLU module also supports dynamic updates of the knowledge base.The CSLI DM module mediates and manages interaction. It uses the dialogue-move approach to maintain dialogue context, which is then used to interpret incoming utterances (including fragments and revisions), resolve NPs, construct salient responses, track issues, etc. Dialogue states can also be used to bias SR expectation and improve SR performance, as has been performed in previous applications of the DM. Detailed descriptions of the DM can be found in [Lemon et al 2002; Mirkovic & Cavedon 2005].The Knowledge Manager (KM) controls access to knowledge base sources (such as domain knowledge and device information) and their updates. Domain knowledge is structured according to domain-dependent ontologies. The current KM makes use of OWL, a W3C standard, to represent the ontological relationships between domain entities. Protege (http://protege.stanford.edu), a domain-independent ontology tool, is used to maintain the ontology offline. In a typical interaction, the DM converts a user's query into a semantic frame (i.e. a set of semantic constraints) and sends this to the KM via the content optimizer.The Content Optimization module acts as an intermediary between the dialogue management module and the knowledge management module during the query process. It receives semantic frames from the DM, resolves possible ambiguities, and queries the KM. Depending on the items in the query result as well as the configurable properties, the module selects and performs an appropriate optimization strategy.Early evaluation shows that the system has a task completion rate of 80% on 11 tasks of MP3 player domain, ranging from playing requests to music database queries. Porting to a restaurant selection domain is currently under way.
10598810
An orthogonal genetic algorithm for multimedia multicast routing
Many multimedia communication applications require a source to send multimedia information to multiple destinations through a communication network. To support these applications, it is necessary to determine a multicast tree of minimal cost to connect the source node to the destination nodes subject to delay constraints on multimedia communication. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes an orthogonal genetic algorithm for multimedia multicast routing. Its salient feature is to incorporate an experimental design method called orthogonal design into the crossover operation. As a result, it can search the solution space in a statistically sound manner and it is well suited for parallel implementation and execution. We execute the orthogonal genetic algorithm to solve two sets of benchmark test problems. The results indicate that for practical problem sizes, the orthogonal genetic algorithm can find near optimal solutions within moderate numbers of generations.