基于网格和队列触发的多维空间Skyline查询算法

在流数据环境下,多维空间的Skyline计算会随着维度的增高影响滑动窗口上Skyline点集的计算效率.针对以上问题,提出SQTS算法,采用网格索引结构,对元组进行标记,排除部分非Skyline点集;引入SD队列触发Skyline维护,避免过期数据点的频繁排查,提高多维空间下的Skyline计算效率.仿真实验结果表明,SQTS算法在多维流数据环境下,提高了Skyline点集的计算效率,验证了算法有效性.     

Flexible integration of multimedia sub-queries with qualitative preferences

Complex multimedia queries, aiming to retrieve from large databases those objects that best match the query specification, are usually processed by splitting them into a set of m simpler sub-queries, each dealing with only some of the query features. To determine which are the overall best-matching objects, a rule is then needed to integrate the results of such sub-queries, i.e., how to globally rank the m-dimensional vectors of matching degrees, or partial scores, that objects obtain on the m sub-queries. It is a fact that state-of-the-art approaches all adopt as integration rule a scoring function, such as weighted average, that aggregates the m partial scores into an overall (numerical) similarity score, so that objects can be linearly ordered and only the highest scored ones returned to the user. This choice however forces the system to compromise between the different sub-queries and can easily lead to miss relevant results. In this paper we explore the potentialities of a more general approach, based on the use of qualitative preferences, able to define arbitrary partial (rather than only linear) orders on database objects, so that a larger flexibility is gained in shaping what the user is looking for. For the purpose of efficient evaluation, we propose two integration algorithms able to work with any (monotone) partial order (thus also with scoring functions): MPO, which delivers objects one layer of the partial order at a time, and iMPO, which can incrementally return one object at a time, thus also suitable for processing top k queries. Our analysis demonstrates that using qualitative preferences pays off. In particular, using Skyline and Region-prioritized Skyline preferences for queries on a real image database, we show that the results we get have a precision comparable to that obtainable using scoring functions, yet they are obtained much faster, saving up to about 70% database accesses.     

欣赏和保护城市轮廓线——旧金山城市设计调查

本文通过作者对旧金山市的实地调查,介绍了其城市轮廓线的层次与建筑布局特点,同时指出,良好的城市规划与设计是保证城市的特色的基础。     

一种高效的分布式Skyline查询算法

本文提出了一种新的分布环境中的Skyline查询算法--一种新的四阶段Skyline算法FDSL。现有的算法，如Distributed Skylining算法，在节点数m较大时会消耗大量的网络带宽。FDSL算法在任意数据集上只需要四次交互就能完成，并且通过剪除不必要的对象来减少网络带宽的消耗。本文通过模拟数据验证了FDSL算法的效率。实验表明，当节点点数m大于4时，FDSL算法的性能比现有算法提高了15％～30％。     

基于Skyline的态势拖放中一种减少轨迹变化延时方法研究

利用Skyline提供的3D控件技术，容易实现战场态势的三维显示和回放，在回放过程中，用户希望能够进行任意时刻的拖放，以便能够快速查看到用户关心的态势，但在实现拖放时，不仅需要对目标的位置和状态进行更新，而且还需要对划过的轨迹进行快速增补或者擦除，拖动的范围增大，因增补或擦除目标轨迹的延时增加。本文提出一种轨迹分段预处理的方法，将大大减少拖放延时。     

Faster output-sensitive skyline computation algorithm

We present the second output-sensitive skyline computation algorithm which is faster than the only existing output-sensitive skyline computation algorithm [1] in worst case because our algorithm does not rely on the existence of a linear time procedure for finding medians.     

On efficient reverse skyline query processing

Given a D-dimensional data set P and a query point q, a reverse skyline query (RSQ) returns all the data objects in P whose dynamic skyline contains q. It is important for many real life applications such as business planning and environmental monitoring. Currently, the state-of-the-art algorithm for answering the RSQ is the reverse skyline using skyline approximations (RSSA) algorithm, which is based on the precomputed approximations of the skylines. Although RSSA has some desirable features, e.g., applicability to arbitrary data distributions and dimensions, it needs for multiple accesses of the same nodes, incurring redundant I/O and CPU costs. In this paper, we propose several efficient algorithms for exact RSQ processing over multidimensional datasets. Our methods utilize a conventional data-partitioning index (e.g., R-tree) on the dataset P, and employ precomputation, reuse, and pruning techniques to boost the query performance. In addition, we extend our techniques to tackle a natural variant of the RSQ, i.e., constrained reverse skyline query (CRSQ), which retrieves the reverse skyline inside a specified constrained region. Extensive experimental evaluation using both real and synthetic datasets demonstrates that our proposed algorithms outperform RSSA by several orders of magnitude under all experimental settings.     

Efficient distributed skyline computation using dependency-based data partitioning

Skyline queries, together with other advanced query operators, are essential in order to help identify sets of interesting data points buried within huge amount of data readily available these days. A skyline query retrieves sets of non-dominated data points in a multi-dimensional dataset. As computing infrastructures become increasingly pervasive, connected by readily available network services, data storage and management have become inevitably more distributed. Under these distributed environments, designing efficient skyline querying with desirable quick response time and progressive returning of answers faces new challenges. To address this, in this paper, we propose a novel skyline query scheme termed MpSky. MpSky is based on a novel space partitioning scheme, employing the dependency relationships among data points on different servers. By grouping points of each server using dependencies, we are able to qualify a skyline point by only comparing it with data on dependent servers, and parallelize the skyline computation among non-dependent partitions that are from different servers or individual servers. By controlling the query propagation among partitions, we are able to generate skyline results progressively and prune partitions and points efficiently. Analytical and extensive simulation results show the effectiveness of the proposed scheme.     

CBD天际线之新视野

随着城市化进程的推进,高品质CBD的天际线正极大地改变着城市的面貌,天际线越来越被看做是一个城市的象征性符号,起着展现城市形象的关键性作用。该文通过树立天际线外郭,天际线立面与天际线层次的三个属性概念,同时结合目前国内天际线发展的最新进展,由此来剖析天际线特征,得出相关规律与结论。     

基于Skyline的三维数字校园

校园景观三维可视化是实现数字校园的第一步,利用三维建模软件和Skyline系列软件,基于大比例尺地形图及校园航空数字影像图进行数字校园三维景观的建模及其可视化,以北京建筑工程学院为例证实了该方法的可行性．