分布式数据流上的天际线查询：BOCS算法

122 浏览量更新于2024-07-15 收藏 1.97MB PDF 举报

"分布式数据流；天际线；通信最优处理；逐步优化" 本文主要探讨了在分布式数据流中处理天际线查询的高效方法。天际线查询是一种重要的数据分析技术，它能找出数据集中不受其他任何对象支配的有趣对象集合。在传统的静态数据或集中式数据流中，天际线计算已经得到了一定的研究，但在分布式数据流环境下的处理则更具挑战性，因为数据源可能被水平拆分成多个部分。文章提出了名为BOCS（Block-based Optimal Communication Strategy）的算法，该算法结合了高效的集中式算法GridSky和一套通信协议。BOCS的核心在于其逐步优化策略，将天际线计算分为两个阶段。第一阶段，GridSky在各个远程站点维护本地天际线，并仅将增量更新发送给协调器，降低了通信成本。第二阶段，协调器整合来自各个远程站点的增量，与当前的全局天际线合并，从而得到最新的全局天际线结果。理论分析证明，BOCS在所有采用无共享策略的算法中具有最优的通信效率。通过大量实验，作者展示了BOCS算法不仅在性能上有效，而且具备良好的可扩展性和稳定性。这些实验结果进一步证实了BOCS对于处理分布式数据流中的天际线查询是理想的解决方案。在分布式数据流环境中，有效的数据管理和挖掘对于实时决策和业务分析至关重要。BOCS算法的提出为这一领域提供了新的视角和工具，有助于在分布式环境中更高效地执行天际线查询，为大数据分析提供支持。通过减少通信开销和优化计算过程，BOCS能够处理更大规模、更复杂的分布式数据流，对实时数据挖掘和决策系统有着重要的应用价值。

580 S. Sun et al.

Fig. 3 Dominance and

anti-dominance region

system; p

, p

and p

upgrade from candidate to skyline objects. Besides, p

, p

and p

will

go expired after the 12th, 13th and 16th objects arrive at the system respectively. For each

newly entitled skyline object an expiration event is built and inserted into the event list. So

the ﬁnal event list after p

arrived is: {< 12, p

, EX >, < 13, p

, SK >

,< 14, p

, EX >, < 16, p

, SK >, < 20, p

, EX >, < 20, p

, SK >}.

Another important issue for skyline processing over data streams is to compute the Inﬂu-

ence Time of the new arrival and to eliminate the objects dominated by the new arrival (we

denote them as critical task one and two). The measures adopted no matter by Eager or

Lazy algorithm [2] are less efﬁcient. For the sake of consistency with previous work, in the

rest of the paper, we focus on discussion of data streams under the time-based sliding win-

dow model [31]. Let the width of the sliding window be W, the maximum timestamp of the

objects dwelled into the anti-dominance region (ADR) of the newly arrived p be t

max

, then

the Inﬂuence Time of p is W + t

max

(under count-based data streams, t

max

is the maximum

sequence ID of the objects located in p.ADR). If there is no such object dominating p, the

Inﬂuence Time is then set to current time. In other words, Inﬂuence Time denotes when a new

point begins to join the skyline. Hence, the key is to obtain t

max

efﬁciently. Elimination of

the objects dominated by p is to expunge all objects located in the dominance region (DR)

of p. The 2-dimensional ADR and DR are illustrated by Fig. 3.

Objects are indexed by a R*-tree [27]inI-Eager and I-Lazy or simply preserved in a list

in LL-Eager and LL-Lazy [2], then D-sided search [4] is employed by these algorithms to

implement the two critical tasks mentioned above. A segment of this scenario within I-Eager

(or I-Lazy) is shown below. Proceeding with Example 1 in Sect. 1, p

represents the object

arriving at time i. Figure 4 illustrates how both critical tasks are fulﬁlled when p

arrives

under I-Lazy andI-Eager. Assuming node capacity of the R*-tree is 2, p

and p

dwell at

an intermediate node of the lowest level, so as for p

and p

, p

and p

, p

and p

etc. To

compute the Inﬂuence Time of p

, four dominance tests between p

, p

and p

will

be invoked successively. Among all these objects dominating p

, p

holds the maximum

timestamp, hence the Inﬂuence Time of p

is 13. In order to eliminate the objects dominated

by p

, four dominance tests between p

and p

, p

will be invoked. Among these

objects, p

and p

are dominated by p

, hence they are washed out from the system. Search

on a list theoretically has to traverse the whole list, search on an R*-tree is also inefﬁcient

123

Efﬁcient monitoring of skyline queries over distributed data streams 581

Fig. 4 Example of execution on

R-tree

due to its sensitivity to dimensionality [5]. The overlap ratio of the bounding boxes in the

directory of R*-tree will increase rapidly to about 90% when increasing the dimensionality

to5[26]. This will cause serious efﬁciency deterioration when searching on an R-tree or

R*-tree. The disadvantage of the approach in [3] is similar. To resolve the deﬁciency of the

above algorithms, we propose a more efﬁcient algorithm GridSky in which data objects are

organized in a basic grid. A basic grid is more suitable for the problem concerned in this

paper because cells within the grid are totally disjoint from each other. The proportion of the

objects scanned in GridSky will be much lower than that in Eager or Lazy especially when the

dimensionality is higher. Furthermore, heuristics are developed in GridSky to further speed

up critical tasks. Another disadvantage of R*-trees or other high-dimensional indexes struc-

ture, such as X-tree [26] for example, is that its updating overhead (deletion and insertion) is

much higher than that of a basic grid. By leveraging GridSky as the centralized algorithm,

we ﬁnally design a communication-optimal distributed algorithm BOCS in which a global

skyline is calculated in an incremental and progressive manner.

Concerning research on data streams, there is much attention about query processing and

data mining over it. A good survey on models and issues over data streams can be found

in [31]. The sliding window model is very important in data stream applications as it aims

to provide the latest on-line information. A lot of work based on this model has emerged,

including classiﬁcation of audio data streams [32], frequent itemsets mining [33,35,36]and

clustering analysis [37], etc. A bulk of other algorithms on this model can be referred to [34].

Since the distributed data stream model was ﬁrst proposed in [6], research over distributed

streams has gradually become a hot topic [11,25]. Keralapura et al. address the problem of

threshold counts monitoring [7], it is to return the aggregate frequency count of certain event

that is continuously monitored by distributed nodes with a user-speciﬁc accuracy. Approxi-

mate quantiles computation over distributed streams and sensor networks is studied in [9,23].

Theworkin[8,10] seeks to estimate set expressions and a broad class of complex aggregate

queries just like join sizes, etc. The problem of managing and mining inverse distributions has

been well studied in [12], it is to dynamically maintain the number of items that appear with

speciﬁc times. Besides, heavy hitters, top-K elements monitoring and continuous clustering

analysis over distributed data streams are addressed in [16,17,24], respectively.

123

剩余31页未读，继续阅读

weixin_38543120

粉丝: 6
资源: 932

分布式数据流上的天际线查询：BOCS算法

不确定数据的分布式天际线查询的自适应处理

分布式数据流数据倾斜均衡方法研究.pdf

分布式数据流计算系统的数据缓存技术综述

深度解析分布式数据流系统.docx

无线传感器网络中基于几何的分布式空间天际线查询

分布式数据流分类关键技术研究.pdf

基于分布式数据流的网络处理器数据收集分类平台.pdf

一种面向分布式数据流的闭频繁模式挖掘方法.pdf

分布式流数据加载和查询技术优化.pdf

基于内存的分布式隐私流查询系统

最新资源