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 276
1.
Hill climbing algorithms for content-based retrieval of similar configurations - Papadias, Dimitris
The retrieval of stored images matching an input configuration is an important form of content-based retrieval. Exhaustive processing (i.e., retrieval of the best solutions) of configuration similarity queries is, in general, exponential and fast search for sub-optimal solutions is the only way to deal with the vast (and ever increasing) amounts of multimedia information in several real-time applications. In this paper we discuss the utilization of hill climbing heuristics that can provide very good results within limited processing time. We propose several heuristics, which differ on the way that they search through the solution space, and identify the best ones...
2.
Content-based retrieval using heuristic search - Papadias, Dimitris; Mantzourogiannis, Marios; Kalnis, Panagiotis; Mamoulis, Nikos; Ahmad, Ishfaq
The fast growth of multimedia information in image and video databases has triggered research on efficient retrieval methods. This paper deals with structural queries, a type of content-based retrieval where similarity is not defined on visual properties such as color and texture, but on object relations in space. We propose the application of heuristic algorithms which provide good, but not necessarily optimal, solutions in a pre-determined time period, and compare our approach with systematic search methods which are guaranteed to find optimal solutions but require exponential time in the worst case. The quality of the output is calculated using a...
3.
Hierarchical constraint satisfaction in spatial databases - Papadias, Dimitris; Kalnis, Panagiotis; Mamoulis, Nikos
Several content-based queries in spatial databases and geographic information systems (GISs) can be modelled and processed as constraint satisfaction problems (CSPs). Regular CSP algorithms, however, work for main memory retrieval without utilizing indices to prune the search space. This paper shows how systematic and local search techniques can take advantage of the hierarchical decomposition of space, preserved by spatial data structures, to efficiently guide search. We study the conditions under which hierarchical constraint satisfaction outperforms traditional methods with extensive experimentation.
4.
Improving search using indexing : a study with temporal CSPs - Mamoulis, Nikos; Papadias, Dimitris
Most studies concerning constraint satisfaction problems (CSPs) involve variables that take values from small domains. This paper deals with an alternative form of temporal CSPs; the number of variables is relatively small and the domains are large collections of intervals. Such situations may arise in temporal databases where several types of queries can be modeled and processed as CSPs. For these problems, systematic CSP algorithms can take advantage of temporal indexing to accelerate search. Directed search versions of chronological backtracking and forward checking are presented and tested. Our results show that indexing can drastically improve search performance.
5.
Processing and optimization of multiway spatial joins using R-trees - Papadias, Dimitris; Mamoulis, Nikos; Theodoridis, Yannis
One of the most important types of query processing in spatial databases and geographic information systems is the spatial join, an operation that selects, from two relations, all object pairs satisfying some spatial predicate. A multiway join combines data originated from more than two relations. Although several techniques have been proposed for pairwise spatial joins, only limited work has focused on multiway spatial join processing. This paper solves multiway spatial joins by applying systematic search algorithms that exploit R-trees to efficiently guide search, without building temporary indexes or materializing intermediate results. In addition to general methodologies, we propose cost models...
6.
Integration of spatial join algorithms for processing multiple inputs - Mamoulis, Nikos; Papadias, Dimitris
Several techniques that compute the join between two spatial datasets have been proposed during the last decade. Among these methods, some consider existing indices for the joined inputs, while others treat datasets with no index, providing solutions for the case where at least one input comes as an intermediate result of another database operator. In this paper we analyze previous work on spatial joins and propose a novel algorithm, called slot index spatial join (SISJ), that efficiently computes the spatial join between two inputs, only one of which is indexed by an R-tree. Going one step further, we show how...
7.
Query processing in spatial network databases - Papadias, Dimitris; Zhang, Jun; Mamoulis, Nikos; Tao, Yufei
Despite the importance of spatial networks in real-life applications, most of the spatial database literature focuses on Euclidean spaces. In this paper we propose an architecture that integrates network and Euclidean information, capturing pragmaatic constraints. Based on this architecture, we develop a Euclidean restriction and a network expansion framework that take advantage of location and connectivity to efficiently prune the search space. These frameworks are successfully applied to the most popular spatial queries, namely nearest neighbors, range search, closest pairs and e-distance joins, in the context of spatial network databases.
8.
Continuous nearest neighbor search - Tao, Yufei; Papadias, Dimitris; Shen, Qiongmao
A continuous nearest neighbor query retrieves the nearest neighbor (NN) of every point on a line segment (e.g., find all my nearest gas stations during my route from point s to point e). The result contains a set of tuples, such that point is the NN of all points in the corresponding interval. Existing methods for continuous nearest neighbor search are based on the repetitive application of simple NN algorithms, which incurs significant overhead. In this paper we propose techniques that solve the problem by performing a single query for the whole input segment. As a result the...
9.
An adaptive peer-to-peer network for distributed caching of OLAP results - Kalnis, Panagiotis; Ng, Wee Siong; Ooi, Beng Chin; Papadias, Dimitris; Tan, Kian-Lee
Peer-to-Peer (P2P) systems are becoming increasingly popular as they enable users to exchange digital information by participating in complex networks. Such systems are inexpensive, easy to use, highly scalable and do not require central administration. Despite their advantages, however, limited work has been done on employing database systems on top of P2P networks. Here we propose the PeerOLAP architecture for supporting On-Line Analytical Processing queries. A large number of low-end clients, each containing a cache with the most useful results, are connected through an arbitrary P2P network. If a query cannot be answered locally (i.e. by using the cache contents...
10.
Time-parameterized queries in spatio-temporal databases - Tao, Yufei; Papadias, Dimitris
Time-parameterized queries (TP queries for short) retrieve (i) the actual result at the time that the query is issued, (ii) the validity period of the result given the current motion of the query and the database objects, and (iii) the change that causes the expiration of the result. Due to the highly dynamic nature of several spatio-temporal applications, TP queries are important both as standalone methods, as well as building blocks of more complex operations. However, little work has been done towards their efficient processing. In this paper, we propose a general framework that covers time-parameterized variations of the most...
11.
Cost models for overlapping and multi-version B-trees - 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., banking) and emerging (e.g., spatio-temporal) applications....
12.
Indexing spatio-temporal data warehouses - Papadias, Dimitris; Tao, Yufei; Kalnis, Panagiotis; Zhang, Jun
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...
14.
Mining inter-transaction associations with templates - Feng, Ling; Lu, Hongjun; Yu, Jeffrey Xu; Han, Jiawei
Multi dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. "After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away" is an example of such rules. Since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. In order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction...
15.
Decision tables : scalable classification exploring RDBMS capabilities - Lu, Hongjun; Liu, Hongyan
In this paper, we report our success in building efficient scalable classifiers in the form of decision tables by exploring capabilities of modern relational database management systems. In addition to high classification accuracy, the unique features of the approach include its high training speed, linear scalability, and simplicity in implementation. More importantly, the major computation required in the approach can be implemented using standard functions provided by the modern relational DBMS. This not only makes implementation of the classifier extremely easy, further performance improvement is also expected when better processing strategies for those computations are developed and implemented in RDBMS....
16.
Requirement-based data cube schema design - Cheung, David W.; Zhou, Bo; Kao, Ben; Lu, Hongjun; Lam, Tak Wah; Ting, Hing Fung
On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically. A very important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation...
17.
The MV3R-tree : a spatio-temporal access method for timestamp and interval queries - Tao, Yufei; Papadias, Dimitris
Among the various types of spatio-temporal queries, the most common ones involve window queries in time. In particular, timestamp (or timeslice) queries retrieve all the objects that intersect a window at a specific timestamp. Interval queries include multiple consecutive timestamps. Although several indexes have been developed for either type, currently there does not exist a structure that can efficiently process both query types. This is a significant problem due to the fundamental importance of these queries in any spatio-temporal system that deals with historical information retrieval. Our paper addresses the problem by proposing the MV3R-tree, a structure that utilizes the...
18.
Relation-based similarity - Papadias, Dimitris; Delis, Vasilis
Similarity queries constitute an active area in spatial query processing. The paper addresses the problem of qualitative similarity based on spatial relations. On the one hand spatial similarity entails mechanisms for representing and reasoning on spatial relations, while on the other it introduces a high level of uncertainty. Several spatial queries can be rather fuzzy and user or application dependent. Moreover, relations such as near, northeast etc. lack universally accepted semantics, and as a result their processing in Spatial Databases and GIS has to provide a high level of flexibility in order to satisfy real-life needs. Our work extends the...
19.
Hermes : supporting argumentative discourse in multi-agent decision making - Karacapilidis, Nikos; Papadias, Dimitris
This paper describes Hermes, a system that enhances group decision making by providing an argumentation framework to the agents involved. The system organizes the existing knowledge in a discussion graph , which consists issues, alternatives, positions and preference relations. Argumentation is performed through a set of discourse acts which trigger appropriate procedures for the propagation of information in the graph. Hermes is able to handle incomplete, qualitative and inconsistent information, and provides mechanisms for weighing arguments.
20.
Location-based spatial queries - Zhang, Jun; Zhu, Manli; Papadias, Dimitris; Tao, Yufei; Lee, Dik Lun
In this paper we propose an approach that enables mobile clients to determine the validity of previous queries based on their current locations. In order to make this possible, the server returns in addition to the query result, a validity region around the client's location within which the result remains the same. We focus on two of the most common spatial query types, namely nearest neighbor and window queries, define the validity region in each case and propose the corresponding query processing algorithms. In addition, we provide analytical models for estimating the expected size of the validity region. Our techniques...
1.
