HKUST Institutional Repository
(5.016 recursos)
Repository of Hong Kong University of Science and Technology. Managed by the HKUST Library.
Mostrando recursos 1 - 20 de 151
1.
Slot index spatial join - Mamoulis, Nikos; Papadias, Dimitris
Efficient processing of spatial joins is very important due to their high cost and frequent application in spatial databases and other areas involving multidimensional data. This paper proposes slot index spatial join (SISJ), an algorithm that joins a nonindexed data set with one indexed by an R-tree. We explore two optimization techniques that reduce the space requirements and the computational cost of SISJ and we compare it, analytically and experimentally, with other spatial join methods for two cases: 1) when the nonindexed input is read from disk and 2) when it is an intermediate result of a preceding database operator...
2.
Cost models for overlapping and multi-version structures - Tao, Yufei; Papadias, Dimitris; Zhang, Jun
Overlapping and multi-version techniques are two popular frameworks that transform an ephemeral index into a multiple logical-tree structure in order to support versioning databases. Although both frameworks have produced numerous efficient indexing methods, their performance analysis is rather limited; as a result there is no clear understanding about the behavior of the alternative structures and the choice of the best one, given the data and query characteristics. Furthermore, query optimization based on these methods is currently impossible. These are serious problems due to the incorporation of overlapping and multi-version techniques in several traditional (e.g., financial) and emerging (e.g., spatio-temporal) applications....
3.
Indexing and retrieval of historical aggregate information about moving objects - Papadias, Dimitris; Tao, Yufei; Zhang, Jun; Mamoulis, Nikos; Shen, Qiongmao; Sun, Jimeng
Spatio-temporal databases store information about the positions of individual objects over time. In many applications however, such as traffic supervision or mobile communication systems, only summarized data, like the average number of cars in an area for a specific period, or phones serviced by a cell each day, is required. Although this information can be obtained from operational databases, its computation is expensive, rendering online processing inapplicable. A vital solution is the construction of a spatiotemporal data warehouse. In this paper, we describe a framework for supporting OLAP operations over spatiotemporal data. We argue that the spatial and temporal dimensions...
4.
Multiway spatial joins - Mamoulis, Nikos; Papadias, Dimitris
Due to the evolution of Geographical Information Systems, large collections of spatial data having various thematic contents are currently available. As a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inputs become more common. Although several algorithms have been proposed for computing the result of pairwise spatial joins, limited work exists on processing and optimization of multiway spatial joins. In this paper we review pairwise spatial join algorithms and show how they can be combined for multiple inputs. In addition, we explore the application of synchronous...
5.
Deformable contours : modeling and extraction - Lai, Kok F.; Chin, Roland T.
This paper considers the problem of modeling and extracting arbitrary deformable contours from noisy images. We propose a global contour model based on a stable and regenerative shape matrix, which is invariant and unique under rigid motions. Combined with Markov random field to model local deformations, this yields prior distribution that exerts influence over a global model while allowing for deformations. We then cast the problem of extraction into posterior estimation and show its equivalence to energy minimization of a generalized active contour model. We discuss pertinent issues in shape training, energy minimization, line search strategies minimax regularization and initialization...
6.
Match propagation for image-based modeling and rendering - Lhuillier, Maxime; Quan, Long
This paper presents a quasi-dense matching algorithm between images based on match propagation principle. The algorithm starts from a set of sparse seed matches, then propagates to the neighboring pixels by the best-first strategy, and produces a quasi-dense disparity map. The quasi-dense matching aims at broad modeling and visualization applications which rely heavily on matching information. Our algorithm is robust to initial sparse match outliers due to the best-first strategy; It is efficient in time and space as it is only output sensitive; It handles half-occluded areas because of the simultaneous enforcement of newly introduced discrete 2D gradient disparity limit...
7.
Automated analysis of nerve-cell images using active contour models - Fok, Ying-Lun; Chan, Joseph; Chin, Roland T.
The number of nerve fibers (axons) in a nerve, the axon size and shape can all be important neuroanatomical features in understanding different aspects of nerves in the brain. However, the number of axons in a nerve is typically in the order of tens of thousands and a study of a particular aspect of the nerve often involves many nerves. Potentially meaningful studies are often prohibited by the huge number involved when manual measurements have to be employed. A method that automates the analysis of axons from electronmicrographic images is presented. It begins with a rough identification of all the...
8.
Computer supported argumentation and collaborative decision making : the HERMES system - Karacapilidis, Nikos; Papadias, Dimitris
Collaborative Decision Making problems can be addressed through argumentative discourse and collaboration among the users involved. Consensus is achieved through the process of collaboratively considering alternative understandings of the problem, competing interests, priorities and constraints. The application of formal modeling and analysis tools to solve the related processes is impossible before the problem can be articulated in a concise and agreed upon manner. This paper describes HERMES, a system that augments classical decision making approaches by supporting argumentative discourse among decision makers. It is fully implemented in Java and runs on the Web, thus providing relatively inexpensive access to a...
9.
Indexing techniques for wireless data broadcast under data clustering and scheduling - Hu, Qinglong; Lee, Wang-Chien; Lee, Dik Lun
This paper investigates power conserving indexing techniques for data disseminated on a broadcast channel. A hybrid indexing method combining strengths of the signature and the index tree techniques is presented. Different from previous studies, our research takes into consideration two important data organization factors, namely, clustering and scheduling. Cost models for index, signature and hybrid methods are derived by taking into account various data organizations accommodating these two factors. Based on our analytical comparisions, the signature and the hybrid indexing techniques are the best choices for power conserving indexing of various data organizations on wireless broadcast channels.
10.
Optimal channel allocation for data dissemination in mobile computing environments - Hu, Qinglong; Lee, Dik Lun; Lee, Wang-Chien
This paper discusses wireless channel allocation problem for data dissemination in mobile computing systems. Methods for accessing data through broadcast and on-demand channels are described. We provide analytical models and cost formulae for the exclusive broadcast channels and the exclusive on-demand channels and propose a dynamic channel allocation algorithm for optimizing system performance. Our performance evaluation shows that dynamic channel allocation significantly improves system performance and the channel allocation algorithm gives us the optimal solution for various system parameter settings.
11.
Power conservative multi-attribute queries on data broadcast - Hu, Qinglong; Lee, Wang-Chien; Lee, Dik Lun
In this paper, we study power conservation techniques for multi-attribute queries on wireless data broadcast channels. Indexing data on broadcast channels can improve client filtering capability, while clustering and scheduling can reduce both access time and tune-in time. Thus, indexing techniques should be coupled with clustering and scheduling methods to reduce the battery power consumption of mobile computers. In this study, three indexing schemes for multi-attribute queries, namely, index tree, signature, and hybrid index, are discussed. We develop cost models for these three indexing schemes and evaluate their performance based on multi-attribute queries on wireless data broadcast channels.
12.
Performance evaluation of a wireless hierarchical data dissemination system - Hu, Qinglong; Lee, Wang-Chien; Lee, Dik Lun
Various techniques have been developed to improve the performance of wireless information services. Techniques such as information broadcasting, caching of frequently accessed data, and point-to-point channels for pull-based data requests are often used to reduce data access time. To efficiently utilize information broadcast, indexing and scheduling schemes are employed for the organization of data broadcast. Most of the studies in the literature focused either on individual technique or a combination of them with some restrictive assumptions. There is no study considering these techniques working together in an integrated manner. In this paper, we propose a dynamic data delivery model for...
13.
Processing location-dependent queries in a multi-cell wireless environment - Zheng, Baihua; Lee, Dik Lun
We develop several methods for scheduling location-dependent queries when clients cross cell boundaries in a multi-cell wireless environment. Our study is based on a common scenario where data objects are stationary while clients, which issue the queries, are mobile. For query processing, we use Voronoi Diagrams to construct an index and a semantic cache for improving data reusability. For handoff clients, we propose three scheduling methods, namely, the prioiity method, the intelligent method, and the hybrid method to improve performance. A simulation is conducted to study the performance of the methods.
14.
Path dictionary : a new approach to query processing in object-oriented databases - Lee, Wang-Chien; Lee, Dik Lun
We present a new access method, called the path dictionary index (PDI) method, for supporting nested queries on object-oriented databases. PDI supports object traversal and associative search, respectively, with a path dictionary and a set of attribute indexes built on top of the path dictionary. We discuss issues on indexing and query processing in object-oriented databases, describe the operations of the new mechanism, develop cost models for its storage overhead and query and update costs, and compare the new mechanism to the path index method. The result shows that the path dictionary index method is significantly better than the path...
15.
Approximate spatio-temporal retrieval - Papadias, Dimitris; Mamoulis, Nikos; Delis, Vasilis
This paper proposes a framework for the handling of spatio-temporal queries with inexact matches, using the concept of relation similarity. We initially describe a binary string encoding for 1D relations that permits the automatic derivation of similarity measures. We then extend this model to various granularity levels and many dimensions, and show that reasoning on spatio-temporal structure is significantly facilitated in the new framework. Finally, we provide algorithms and optimization methods for four types of queries: (i) object retrieval based on some spatio-temporal relations with respect to a reference object, (ii) spatial joins, i.e., retrieval of object pairs that satisfy...
16.
A planner called R - Lin, Fangzhen
System R was competed at the AIPS-2000 competition, and it was the only planner that was competed in both the automatic and hand-tailered tracks. This article is a short and informal description of this planner.
17.
Minimal cost replication of dynamic web contents under flat update delivery - Tang, Xueyan; Chanson, Samuel T.
Dynamic web contents are generated by running application programs on base data which often change frequently. Geographically replicating the applications that construct these contents (including the programs and the related data they access) is an effective approach to improve their access latency. To maintain the freshness of an object replica, the new version of the object either has to be fetched from remote servers or be reconstructed locally when the origin copy is updated. This paper presents a theoretical study on geographical replication of dynamic web contents with the objective of minimizing the consistency management costs in terms of update...
18.
The minimal cost distribution tree problem for recursive expiration-based consistency management - Tang, Xueyan; Chanson, Samuel T.
The expiration-based scheme is widely used to manage the consistency of cached and replicated contents such as web objects. In this approach, each replica is associated with an expiration time beyond which the replica has to be validated. While the expiration-based scheme has been investigated in the context of a single replica, not much work has been done on its behaviors with respect to multiple replicas. To allow for efficient consistency management, it is desirable to organize the replicas into a distribution tree, where a lower level replica seeks validation with a higher level replica when its lifetime expires. This...
19.
On strongest necessary and weakest sufficient conditions - Lin, Fangzhen
Given a propositional theory T and a proposition q, sufficient condition of q is one that will make q true under T, and a necessary condition of q is one that has to be true for q to be true under T. In this paper, we propose a notion of strongest necessary and weakest sufficient conditions. Intuitively the strongest necessary condition of a proposition is the most general consequence that we can deduce from the proposition under the given theory, and the weakest sufficient condition is the most general abduction that we can make from the proposition under the given...
20.
Compiling causal theories to successor state axioms and STRIPS-like systems - Lin, Fangzhen
We describe a system for specifying the effects of actions. Unlike those commonly used in AI planning, our system uses an action description language that allows one to specify the effects of actions using domain rules, which are state constraints that can entail new action effects from old ones. Declaratively, an action domain in our language corresponds to a nonmonotonic causal theory in the situation calculus. Procedurally, such
an action domain is compiled into a set of logical theories, one for each action in the domain, from which fully instantiated successor state-like axioms and STRIPS-like systems are then generated. We expect...
1.
