数据流管理系统TelegraphCQ的研究

数据流是近年来出现的一种新的数据形式,这类数据的特点是以连续的、实时的、无限的形式出现.针对传统的数据库的查询处理技术已经不适合数据流的问题,研究了数据流管理系统TelegraphCQ的开放源码,在此基础上详细阐述了TelegraphCQ的系统结构、TelegraphCQ的数据管理方案和查询处理技术,同时给出了建立TelegraphCQ的详细步骤及其使用方法.     

数据仓库系统中一种高效的多维层次聚集算法

如何减少联机分析处理中多表连接和压缩维属性连接关键字,对查询数据进行有效地分组聚集操作,成为联机分析处理查询处理的关键问题.为此,提出了一种基于多维层次编码的新型预聚集算法MDHEPA.该算法充分利用编码长度较小的多维层次编码及其前缀,对事实表中的数据进行快速地分组聚集计算,大大减少和简化了多表连接操作,提高了联机分析处理查询效率.理论分析和实验结果表明,该算法是有效的.     

Exploratory product search using top-k join queries

Given a relation that contains main products and a set of relations corresponding to accessory products that can be combined with a main product, the Exploratory Top-k Join query retrieves the k best combinations of main and accessory products based on user preferences. As a result, the user is presented with a set of k combinations of distinct main products, where a main product is combined with accessory products only if the combination has a better score than the single main product. We model this problem as a rank-join problem, where each combination is represented by a tuple from the main relation and a set of tuples from (some of) the accessory relations. The nature of the problem is challenging because the inclusion of accessory products is not predefined by the user, but instead all potential combinations (joins) are explored during query processing in order to identify the highest scoring combinations. Existing approaches cannot be directly applied to this problem, as they are designed for joining a predefined set of relations. In this paper, we present algorithms for processing exploratory top-k joins that adopt the pull-bound framework for rank-join processing. We introduce a novel algorithm (XRJN) which employs a more efficient bounding scheme and allows earlier termination of query processing. We also provide theoretical guarantees on the performance of this algorithm, by proving that XRJN is instance-optimal. In addition, we consider a pulling strategy that boosts the performance of query processing even further. Finally, we conduct a detailed experimental study that demonstrates the efficiency of the proposed algorithms in various setups.     

Nearest and reverse nearest neighbor queries for moving objects

With the continued proliferation of wireless communications and advances in positioning technologies, algorithms for efficiently answering queries about large populations of moving objects are gaining interest. This paper proposes algorithms for k nearest and reverse k nearest neighbor queries on the current and anticipated future positions of points moving continuously in the plane. The former type of query returns k objects nearest to a query object for each time point during a time interval, while the latter returns the objects that have a specified query object as one of their k closest neighbors, again for each time point during a time interval. In addition, algorithms for so-called persistent and continuous variants of these queries are provided. The algorithms are based on the indexing of object positions represented as linear functions of time. The results of empirical performance experiments are reported.     

Regular path queries under approximate semantics

We give a general framework for approximate query processing in semistructured databases. We focus on regular path queries, which are the integral part of most of the query languages for semistructured databases. To enable approximations, we allow the regular path queries to be distorted. The distortions are expressed in the system by using weighted regular expressions, which correspond to weighted regular transducers. After defining the notion of weighted approximate answers we show how to compute them in order of their proximity to the query. In the new approximate setting, query containment has to be redefined in order to take into account the quantitative proximity information in the query answers. For this, we define the approximate containment, and its variants k-containment and reliable contain-ment. Then, we give an optimal algorithm for deciding the k-containment. Regarding the reliable approximate containment, we show that it is polynomial time equivalent to the notorious limitedness problem in distance automata.     

Query indexing with containment-encoded intervals for efficient stream processing

Many continual range queries can be issued against data streams. To efficiently evaluate continual queries against a stream, a main memory-based query index with a small storage cost and a fast search time is needed, especially if the stream is rapid. In this paper, we study a CEI-based query index that meets both criteria for efficient processing of continual interval queries. This new query index is an indirect indexing approach. It centres around a set of predefined virtual containment-encoded intervals, or CEIs. The CEIs are used to first decompose query intervals and then perform efficient search operations. The CEIs are defined and labeled such that containment relationships among them are encoded in their IDs. The containment encoding makes decomposition and search operations efficient; from the encoding of the smallest CEI containing a data point, the encodings of other containing CEIs can be easily derived. Closed-form formulae for the bounds of the average index storage cost are derived. Simulations are conducted to evaluate the effectiveness of the CEI-based query index and to compare it with alternative approaches. The results show that the CEI-based query index significantly outperforms existing approaches in terms of both storage cost and search time. Kun-Lung Wu received the B.S. degree in electrical engineering from the National Taiwan University, Taipei, Taiwan, the M.S. and Ph.D. degrees in computer science from the University of Illinois at Urbana–Champaign. He is with the IBM Thomas J. Watson Research Center, currently a member of the Software Tools and Techniques Group. His current research interests include data streams, continual queries, mobile computing, Internet technologies and applications, database systems and distributed and parallel computing. He has published extensively and holds various patents in these areas. Dr. Wu is a Senior Member of the IEEE Computer Society and a member of the ACM. He was an Associate Editor for the IEEE Transactions on Knowledge and Data Engineering, 2000–2004. He was the general chair for the 3rd International Workshop on e-Commerce and Web-Based Information Systems (WECWIS 2001). He has served as an organising and program committee member on various conferences. He has received various IBM awards, including IBM Corporate Environmental Affair Excellence Award, Research Division Award and Invention Achievement Awards. He received a best paper award from IEEE EEE 2004. He is an IBM Master Inventor. Shyh-Kwei Chen received the B.S. degree in computer science and information engineering from National Taiwan University, Taipei, Taiwan, in 1983, the M.S. degree in computer science from the University of Minnesota, Minneapolis, in 1987, and the Ph.D. degree in computer science from University of Illinois at Urbana–Champaign, in 1994. Dr. Chen has been with the IBM Thomas J. Watson Research Center, Yorktown Heights, New York since October 1994, where he is currently a research staff member. His current research interests include XML, electronic commerce, business performance management, data engineering and compilers. He is a member of the ACM, the IEEE and the IEEE Computer Society. Philip S. Yu received the B.S. degree in electrical engineering from National Taiwan University, the M.S. and Ph.D. degrees in electrical engineering from Stanford University, and the M.B.A. degree from New York University. He is with the IBM Thomas J. Watson Research Center and is currently manager of the Software Tools and Techniques group. His research interests include data mining, Internet applications and technologies, database systems, multimedia systems, parallel and distributed processing and performance modelling. Dr. Yu has published more than 400 papers in refereed journals and conferences. He holds or has applied for more than 250 US patents. Dr. Yu is a Fellow of the ACM and a Fellow of the IEEE. He is an associate editor of ACM Transactions on Internet Technology. He is a member of the IEEE Data Engineering steering committee and is also on the steering committee of IEEE Conference on Data Mining. He was the Editor-in-Chief of IEEE Transactions on Knowledge and Data Engineering (2001–2004), an editor and advisory board member of IEEE Transactions on Knowledge and Data Engineering and also a guest coeditor of the special issue on mining of databases. He had also served as an associate editor of Knowledge and Information Systems. In addition to serving as program committee member on various conferences, he was the program cochair of the 11th International Conference on Data Engineering, the 6th Pacific Area Conference on Knowledge Discovery and Data Mining, and the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, and the program chair of the 2nd International Workshop on Research Issues on Data Engineering: Transaction and Query Processing, the PAKDD Workshop on Knowledge Discovery from Advanced Databases and the 2nd International Workshop on Advanced Issues of E-Commerce and Web-based Information Systems. He served as the general chair of the 14th International Conference on Data Engineering and the general cochair of the 2nd IEEE International Conference on Data Mining. He has received several IBM honours, including two IBM Outstanding Innovation Awards, an Outstanding Technical Achievement Award, two Research Division Awards and the 81st Plateau of Invention Achievement Awards. He received an Outstanding Contributions Award from IEEE International Conference on Data Mining in 2003 and also an IEEE Region 1 Award for “promoting and perpetuating numerous new electrical engineering concepts” in 1999. Dr. Yu is an IBM Master Inventor and was recognised as one of the IBM's 10 top leading inventors in 1999.     

A Theoretical Analysis of Query Selection for Collaborative Filtering

We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple algorithm for generating queries for a theoretical model of this problem. We show that the algorithm requires at most opt(F)(ln(|F|/opt(F)) + 1) + 1 queries to find the correct expert, where opt(F) is the optimal worst-case bound on the number of queries for learning arbitrary elements of the set of experts F. The algorithm runs in time polynomial in |F| and |X| (where X is the domain) and we prove that no polynomial-time algorithm can have a significantly better bound on the number of queries unless all problems in NP have n ^{O(log log n)} time algorithms. We also study a more general case where the user ratings come from a finite set Y and there is an integer-valued loss function on Y that is used to measure the distance between the ratings. Assuming that the loss function is a metric and that there is an expert within a distance from the user, we give a polynomial-time algorithm that is guaranteed to find such an expert after at most 2opt(F, ) ln + 2( + 1)(1 + deg(F, )) queries, where deg(F, ) is the largest number of experts in F that are within a distance 2 of any f F.     

Aurora: a new model and architecture for data stream management

This paper describes the basic processing model and architecture of Aurora, a new system to manage data streams for monitoring applications. Monitoring applications differ substantially from conventional business data processing. The fact that a software system must process and react to continual inputs from many sources (e.g., sensors) rather than from human operators requires one to rethink the fundamental architecture of a DBMS for this application area. In this paper, we present Aurora, a new DBMS currently under construction at Brandeis University, Brown University, and M.I.T. We first provide an overview of the basic Aurora model and architecture and then describe in detail a stream-oriented set of operators.Received: 12 September 2002, Accepted: 26 March 2003, Published online: 21 July 2003Edited by Y. Ioannidis     

Semantic optimization techniques for preference queries

Preference queries are relational algebra or SQL queries that contain occurrences of the winnow operator (find the most preferred tuples in a given relation). Such queries are parameterized by specific preference relations. Semantic optimization techniques make use of integrity constraints holding in the database. In the context of semantic optimization of preference queries, we identify two fundamental properties: containment of preference relations relative to integrity constraints and satisfaction of order axioms relative to integrity constraints. We show numerous applications of those notions to preference query evaluation and optimization. As integrity constraints, we consider constraint-generating dependencies, a class generalizing functional dependencies. We demonstrate that the problems of containment and satisfaction of order axioms can be captured as specific instances of constraint-generating dependency entailment. This makes it possible to formulate necessary and sufficient conditions for the applicability of our techniques as constraint validity problems. We characterize the computational complexity of such problems.     

Optimizing XML queries: Bitmapped materialized views vs. indexes

Optimizing queries using materialized views has not been addressed adequately in the context of XML due to the many limitations associated with the definition and usability of materialized views in traditional XML query evaluation models.