大数据与计算智能：信息粒度研究与应用

需积分: 10 18 浏览量更新于2024-07-20 收藏 8.58MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

《信息粒度、大数据与计算智能：研究系列第8卷》是一本深度探讨大数据处理、分析与计算智能领域的专著，由Witold Pedrycz和Shyi-Ming Chen共同编辑。随着商业、工业和政府组织对大数据的需求增长，传统的数据处理方法已无法满足海量、多样性和高速变化（3V挑战）的数据集。本书针对这一挑战，提供了关于新兴原则、概念基础、算法和实践的深入研究，尤其关注计算智能在大数据架构实现、分析与解读中的应用。内容涵盖了多个关键主题，包括： 1. **近邻查询在大数据中的应用**，处理海量数据中的高效搜索。 2. **信息挖掘技术**，探索如何从大量信息中提取有价值的知识。 3. **实时模糊回归分析中的信息粒度问题**，解决复杂数据处理中的效率问题。 4. **基于大数据的连接理解**，从社区到灵活粒度，揭示数据之间的关系。 5. **图论框架**，评估向维护优化转变的可行性。 6. **增量式频繁模式挖掘**，处理大型数据库中的频繁模式发现。 7. **改进的隐语义索引方法**，在客户关系管理等实际场景中提升数据挖掘效果。 8. **基于商空间的不同粒度和粒计算方法特性**，探讨粒度对数据处理的影响。 9. **任务驱动的信息粒化优化**，寻找最优的数据组织策略。 10. **规则基分类系统的统一框架**，建立基于规则的学习系统。 11. **模糊随机回归支持的多粒度评价模型**，提升信息粒度的理解和利用。 12. **基于粒度和可能性分布的模糊稳健回归模型**，强化数据建模。 13. **云计算架构在大数据中的角色**，讨论云计算如何支撑大数据处理。 14. **大数据存储对空间数据库的影响**，关注大数据对空间查询处理的挑战。 15. **Web KnowARR框架**，结合图数据库的计算智能集成。 16. **CRM和大数据挖掘**，融合客户关系管理和数据洞察。 17. **ISCIFCM和DPEI模型性能竞赛**，在特定条件下的模型比较。 18. **粗糙集理论在经济数据分析中的市场运动知识获取**，应用计算智能进行复杂数据理解。 19. **深度神经网络在天气预报中的应用**，利用大数据进行精确预测。 20. **计算智能在空气质量监测大数据分析中的当前知识与未来挑战**，展示其潜力和未来发展方向。本书不仅提供了理论知识，还通过详细的算法设计和代表性应用实例，帮助读者理解和掌握如何利用计算智能工具处理大数据，使之更具可操作性。该系列书籍旨在为研究人员和实践者提供一个全面的平台，探讨大数据及其在各领域中的应用和发展趋势。

资源详情

资源推荐

2 Background

Big data refers to data sets whose size and structure strains the ability of com-

monly used relational DBMSs to capture, manage, and process the data within a

tolerable elapsed time [22]. The volume–velocity-variety of information in this

kind of datasets give rise to the big data challenge, which is also known as the 3V

challenge.

The volume of such datasets is in the order of few terabytes (TB) to petabytes

(PB) that are often of high information granularity. Examples of such volumes are

the U.S. Library of Congress that in April 2011 had more than 235 TB of data

stored and the World of Warcraft online game using 1.3 PB of storage to maintain

its game, the German Climate Computing Center (DKRZ) storing 60 PB of

climate data.

The velocity of information in social media applications (such as photovoltaic,

trafﬁc and other monitoring apps) can grow exponentially as users join the com-

munity. Such growth can produce unprecedented volumes of data streams. For

example, Ontario’s Meter Data Management and Repository (MDM/R) [23]

stores, processes and manages data from 4.6 million smart meters in Ontario,

Canada and provides hourly billing quantity and extensive reports counting

110 million meter reads per day on an annual basis that exceeds the number of

debit card transactions processed in Canada.

QueryProcessor

(a)

(b)

Fig. 1 a A snapshot of a cellular network instance, where the 2-nearest neighbors for u

are {u

}. Similarly for the other users: u

!fu

; u

g; u

!fu

; u

g; u

!fu

; u

g; u

; u

g; u

!fu

; u

g. b Rayzit [20], an example application of a proximity-based micro-

blogging chat

6 G. Chatzimilioudis et al.

Furthermore, the variety of data can be anything from structured (relational or

tabular) to semi-structured (XML or JSON) or even unstructured (Web text and

log ﬁles) data and combination thereof. For example, Google’s experimental robot

cars [24], which have navigated thousands of miles of California roads, use an

artiﬁcial-intelligence technique tackling big data challenges, parsing vast quanti-

ties of data and making decisions instantaneously.

Due to the high demand for big-data management, the literature witnessed an

emergence of new techniques and tools for taming big data. For example, new data

management related mechanisms are proposed [25, 26] that exploit the MapReduce

framework [27] for analyzing data on racks of servers and NoSQL databases.

Computational Intelligence techniques [28–30] such as fuzzy logic, evolu-

tionary computation, neurocomputing and other machine learning techniques

provide us with searching and reasoning means to bring forward solutions to the

big data challenges. Information Granularity [31] is a research ﬁeld that sheds light

into processing complex information entities that can be abstracted or detailed in

different levels. Information granularity techniques are ﬁrst-class candidates for

breaking volume barriers when it comes to processing big data, focusing the

computational power directly to the various levels of abstraction needed. In

addition, Evolutionary Computation (EC) techniques are mainly used for opti-

mization tasks, such as ﬁnding the parameters/models that optimize some pre-

speciﬁed evaluation criteria given some observed data and can be utilized for

dealing with both single and Multi-objective Optimization Problems (MOPs) [13].

As we enter the age of big data, many different evolutionary computation and

machine learning techniques have been modiﬁed, combined, extended and

investigated for their ability to extract insights in an actionable manner. In [32],

Stanford and Google researchers developed a deep learning based approach to

build an online face detector by training a model on a large dataset of Youtube

images (a model with 1 billion connections and a dataset with 10 million

200 9 200 pixel images downloaded from the Internet). The network is trained

using model parallelism and asynchronous SGD on a cluster with 1,000 machines

(16,000 crores) for 3 days. Furthermore, Hall et al. [33] introduced a Decision tree

approach for analyzing big data, which was extended in [34] by combining the

Decision Trees with GAs for further improving their performance. Moreover in

[35], Lu and Fahn proposed a hierarchical artiﬁcial neural network for recognizing

high similar large data sets.

3 System Model and Problem Formulation

This section formalizes our system model and deﬁnes the problem. The main

symbols are summarized in Table 1.

Let U denote a set of smartphone users moving in the plane of a geographic

region. Let such an area be covered by a set of Network Connectivity Points (NCP)

(e.g., cellular towers found in cellular networks, WiFi access points found in

Nearest Neighbor Queries on Big Data 7

wireless networks etc.) Each NCP inherently creates the notion of a cell, deﬁned as

. Without loss of generality, let the cell be represented by a circular area with

radius radius

. The number of users k serviced by an NCP is a network parameter

(cell capacity). A mobile user u is serviced at any given time point by one NCP,

but is also aware of the other NCPs that are in its vicinity and whose communi-

cation range cover it (e.g., cell-ids of different providers in an area, or MAC

addresses of WiFi hot-spots in an area, etc).

Assume that there is some centralized (or cloud-like) service, denoted as QP

(Query Processor), which is accessible by all users in user set U. Allow each user

u to report its positional information to QP regularly. These updates have the form

¼fu; locðuÞ; ncpðuÞ; ncp

vic

ðuÞg, where loc(u) is the location of user u,

ncp(u) is the NCP user u is registered to and ncp

vic

(u) is a list of NCPs in the

vicinity of u.

The problem we consider in this work is how to efﬁciently compute the k-nearest

neighbors of all smartphones that are connected to the network, at all times. We

consider a timestep that deﬁnes rounds where we need to recompute the kNNsof

the users. Depending on the application, this can take place either at a preset time

interval or whenever we have a number of new user location updates arriving at

the server. Formally, we aim to solve a problem we coin the CAkNN problem.

Deﬁnition 1 (CAkNN problem) Given a set U of n points in space and their

location reports r

i;t

2 R at timestep t 2 T, then for each object u

2 U and timestep

t 2 T, the CAkNN problem is to ﬁnd the k objects U

sol

 U  u

such that for all

other objects u

2 U  U

sol

 u

; distðu

; u

Þdistðu

; u

Þ holds.

Table 1 Notation used throughout this work

Notation Description

NCP Network connectivity point

c, C Single NCP, set of all NCPs

radius

Range of NCP c

k The maximum number of users an NCP can serve

u, U A single user, set of all users in the network

n Number of users in the network ðjUjÞ

Set of users of NCP c

r, R A single user report, all user reports for a single timestep

loc(u) Location of user u

ncp(u) The NCP that a user is registered to

ncp

vic

(u) List of NCPs whose range cover user u

The search space of NCP c

Distance of kth nearest user to the border of NCP c

kNN(u) The set of k-nearest neighbors of user u

kth

The kth nearest outside user to the boundary of cell c

The location of a user can be determined either by ﬁne-grain means (e.g., AGPS) or by coarse-

grain means (e.g., ﬁngerprint-based geo-location [36]).

8 G. Chatzimilioudis et al.

In order to better illustrate our deﬁnition, consider Fig. 2, where we plot a

timestep snapshot of 7 users u

- u

moving in an arbitrary geographic region. The

result for this timestep to a k = 2 query would be kNN(u

) = {u

, u

kNN(u

) = {u

, u

}, kNN(u

) = {u

, u

}, kNN(u

) = {u

, u

}, kNN(u

) = {u

}, kNN(u

) = {u

, u

Obviously, the solution for a user u will not always reside inside the same NCP

cell c, but might reside in neighboring cells or even further (e.g., if neighboring cells

do not have any users). Computing a separate search space for every user is very

expensive. On the other hand, search space sharing is achieved when the same

search space is used by multiple users and it guarantees the correct kNN solution for

all of them. If we apply this reasoning for all users U

in c, then the common search

space S

for U

would be deﬁned as the union of the individual search spaces of

every user in U

. We efﬁciently build S

with the assistance of complementary data

structures we devise in this work and explain next. In Fig. 2, the search space

constructed by our framework for users u

and u

is the largest dotted circle.

4 Related Work

In this section we provide an extensive coverage of the k nearest neighbor related

work tackling static data, continuous data and distributed data.

4.1 KNN Queries on Static Data

For applications where data is represented by a linear array, constant time algo-

rithms have been proposed to solve the All Nearest Neighbor (ANN) and All k-

Nearest Neighbor (AkNN) problems. There has been extensive work in the ﬁeld of

image processing and computational geometry (e.g., [9, 10]).

In Euclidean space (and general metric spaces), there has been also extensive

work on solving the ANN and AkNN problems. For large datasets residing on disk

(external memory), works like Zhang et al. [12] and Chen et al. [11] exploit

possible indices on the datasets and propose algorithms for R-tree based nearest

neighbor search.

For small ANN and AkNN problems in Euclidean space, where data ﬁts inside

main memory, early work in the domain of computational geometry has proposed

solutions. Clarkson et al. [7] was the ﬁrst to solve the ANN problem followed by

Gabow et al. [8], Vaidya [37] and Callahan [6]. Given a set of points [7, 8] use a

special quad-tree and [37] use a hierarchy of boxes to divide the data and compute

the ANN. The worst case running time, for both building the needed data struc-

tures and searching in these techniques, is O(nlogn), where n is the number of

points in the system. For the AkNN problem works [7] propose an algorithm with

O(kn + nlogn) and [37] an algorithm with O(knlogn) time complexity.

Nearest Neighbor Queries on Big Data 9

For multi-dimensional disk-resident data kNN Joins have been optimized in

[11, 12, 28, 38–40]. Zhang et al. [12] index the disk-resident data using an R-tree

and develop an efﬁcient depth-ﬁrst traversal algorithm and a hash based algorithm.

In [11] the authors propose the minimum bounding rectangle enhanced quad-tree

as well as a new distance measure for pruning as many distance comparisons as

possible. In [28], a specialized index together with an optimal page loading

strategy were proposed to reduce both CPU and I/O cost for disk-resident data. Xia

et al. [38] optimizes kNN Joins for high dimensional data by hashing points into

blocks and sorting the blocks for a nested loop join. Xia and Yao [39, 40] similarly

propose efﬁcient indexing techniques for avoiding scanning the whole dataset

repeatedly and for pruning as many distance computations as possible.

4.2 Continuous KNN Queries

When it comes to streaming updates of object attributes, main memory processing

is usually mandatory for spatio-temporal applications, where objects are highly

mobile.

Yu et al. [41] followed by Mouratidis et al. [42] optimize Continuous kNN

queries. Objects are indexed by a grid in main memory given a system-deﬁned

parameter value for the grid size. For each query they both use a form of iteratively

enlarging a range search to ﬁnd the kNN. For small object speeds and/or low

object agility, both propose a stateful technique to incrementally compute the

result of a query of the current timestep using the result of the previous timestep.

They deﬁne an inﬂuence region for the query inside the grid and depending on

what happens in this region, the new result is computed using the previous result,

minimizing the search space. Whenever the query object moves or the agility and

speed of the objects is high, both fall back to their slower stateless version where at

each timestep the result of the query is computed from scratch.

Fig. 2 The search space of

cell c is the big circle with

the dotted outline. Any user

inside this circle is a kNN

candidate for any user

inside c

10 G. Chatzimilioudis et al.

剩余443页未读，继续阅读

ramissue

粉丝: 354
资源: 1487

大数据与计算智能：信息粒度研究与应用

cesium 填挖方

基于scala 怎么使用druid

Semantic Segmentation vs. Instance Segmentation

CREATE TABLE db1.test_local ( `id` UInt8, `EventDate` Date, `userID` UInt32 ) ENGINE = MergeTree PARTITION BY toYYYYMM(EventDate) ORDER BY id SETTINGS index_granularity = 8192将这张表分区改为天

写一个cesium 卫星覆盖范围

Linux 内核优化参数

如果去除cesium 穿过地球的polyline

clickhouse的casewhen

clickhouse case

cesium 用entity画半个圆

Basler相机MFC实例

r语言 以30min为时间粒度统计每个粒度之中的数据量

Cesium 给我画一个长两公里宽50米弧形的隧道模型

cesium用entity绘制圆

具体判断cesium polyline是否与地球有交点

linux性能调优的参数配置

最新资源

r语言以30min为时间粒度统计每个粒度之中的数据量