Building All k Nearest Neighbor Social Communities
Paris Descartes University, Seminar Series on Data Analytics,
Paris, France, April 12, 2017
Building All k Nearest Neighbor
Social Communities
D
e
m
e
t
r
i
s
Z
e
i
n
a
l
i
p
o
u
r
A
s
s
i
s
t
a
n
t
P
r
o
f
e
s
s
o
r
Max Planck Institute for Informatics, Germany & Department of
Computer Science, University of Cyprus, Cyprus
http://www.cs.ucy.ac.cy/~dzeina/
dzeina@cs.ucy.ac.cy
undefined
Acknowledgements
Joint work with:
•
"
D
i
s
t
r
i
b
u
t
e
d
I
n
-
M
e
m
o
r
y
P
r
o
c
e
s
s
i
n
g
o
f
A
l
l
k
N
e
a
r
e
s
t
N
e
i
g
h
b
o
r
Q
u
e
r
i
e
s
"
,
G
e
o
r
g
i
o
s
C
h
a
t
z
i
m
i
l
i
o
u
d
i
s
,
C
o
n
s
t
a
n
t
i
n
o
s
C
o
s
t
a
,
D
e
m
e
t
r
i
o
s
Z
e
i
n
a
l
i
p
o
u
r
-
Y
a
z
t
i
,
W
a
n
g
-
C
h
i
e
n
L
e
e
a
n
d
E
v
a
g
g
e
l
i
a
P
i
t
o
u
r
a
,
I
E
E
E
T
r
a
n
s
a
c
t
i
o
n
s
o
n
K
n
o
w
l
e
d
g
e
a
n
d
D
a
t
a
E
n
g
i
n
e
e
r
i
n
g
(
T
K
D
E
'
1
6
)
,
I
E
E
E
C
o
m
p
u
t
e
r
S
o
c
i
e
t
y
,
V
o
l
.
2
8
,
I
s
s
.
4
,
p
p
.
9
2
5
-
9
3
8
,
2
0
1
6
.
–
Sources (GPL):
https://github.com/dmsl/rayzit/tree/master/spitfire
•
"
R
a
y
z
i
t
:
A
n
A
n
o
n
y
m
o
u
s
a
n
d
D
y
n
a
m
i
c
C
r
o
w
d
M
e
s
s
a
g
i
n
g
A
r
c
h
i
t
e
c
t
u
r
e
"
,
C
o
n
s
t
a
n
t
i
n
o
s
C
o
s
t
a
,
C
h
r
y
s
o
v
a
l
a
n
t
i
s
A
n
a
s
t
a
s
i
o
u
,
G
e
o
r
g
i
o
s
C
h
a
t
z
i
m
i
l
i
o
u
d
i
s
a
n
d
D
e
m
e
t
r
i
o
s
Z
e
i
n
a
l
i
p
o
u
r
-
Y
a
z
t
i
,
i
n
I
E
E
E
M
o
b
i
s
o
c
i
a
l
'
1
5
,
V
o
l
.
2
,
p
p
.
9
8
-
1
0
3
,
P
i
t
t
s
b
u
r
g
h
,
P
A
,
U
S
A
,
2
0
1
5
.
–
Sources (MIT):
https://github.com/dmsl/rayzit/
Online Social Communities
•
W
i
t
h
t
h
e
a
d
v
e
n
t
t
h
e
I
n
t
e
r
n
e
t
,
m
i
c
r
o
b
l
o
g
g
i
n
g
c
h
a
t
t
o
o
l
s
h
a
v
e
e
s
t
a
b
l
i
s
h
e
d
n
e
w
m
e
a
n
s
f
o
r
O
n
l
i
n
e
S
o
c
i
a
l
N
e
t
w
o
r
k
s
:
–
C
o
n
t
e
n
t
:
M
i
c
r
o
b
l
o
g
g
i
n
g
d
a
t
a
(
s
m
a
l
l
e
l
e
m
e
n
t
s
o
f
c
o
n
t
e
n
t
s
u
c
h
a
s
s
h
o
r
t
t
e
x
t
,
i
m
a
g
e
s
,
v
i
d
e
o
.
)
–
S
t
r
u
c
t
u
r
e
:
I
m
p
l
i
c
i
t
G
r
a
p
h
(
a
d
d
r
e
s
s
b
o
o
k
)
o
r
E
x
p
l
i
c
i
t
G
r
a
p
h
(
f
o
l
l
o
w
e
r
s
,
f
r
i
e
n
d
s
)
U
N
I
X
t
a
l
k
‘
8
0
‘
9
0
‘
7
0
‘
0
0
‘
1
0
‘
1
5
I
R
C
‘88
M
S
N
‘99
S
k
y
p
e
‘03
C
h
a
t
M
e
s
s
a
g
i
n
g
F
a
c
e
b
o
o
k
‘04
T
w
i
t
t
e
r
‘06
S
o
c
i
a
l
F
o
u
r
s
q
u
a
r
e
‘08
L
o
c
a
t
i
o
n
F
o
r
g
e
t
S
n
a
p
c
h
a
t
‘11
A
n
o
n
.
L
B
S
R
a
y
z
i
t
‘13
S
M
S
Online Social Communities
•
B
e
n
e
f
i
t
s
:
a
v
o
i
d
c
e
n
s
o
r
s
h
i
p
a
n
d
r
e
t
a
i
n
p
r
i
v
a
c
y
–
“huge value for individuals
…
especially when they are working
in far more difficult parts of the world.” J. Bartlett, dw.com,
25.7.2016.
–
Apps: Games (MMOG), Education(MOOC), Crowdsourcing.
•
D
r
a
w
b
a
c
k
s
:
a
c
c
o
u
n
t
a
b
i
l
i
t
y
a
n
d
t
r
a
c
e
a
b
i
l
i
t
y
–
t
h
r
e
a
t
s
,
r
u
m
o
r
s
p
r
e
a
d
i
n
g
a
n
d
n
e
g
a
t
i
v
e
d
i
s
c
o
u
r
s
e
(
e
.
g
.
,
i
n
t
i
m
i
d
a
t
e
,
c
o
n
t
r
o
l
,
m
a
n
i
p
u
l
a
t
e
,
f
a
l
s
e
l
y
d
i
s
c
r
e
d
i
t
,
o
r
h
u
m
i
l
i
a
t
e
)
l
e
a
d
i
n
g
t
o
t
h
e
s
h
u
t
d
o
w
n
o
f
s
e
r
v
i
c
e
s
(
e
.
g
.
,
S
e
c
r
e
t
)
–
i
l
l
e
g
a
l
c
o
n
t
e
n
t
d
i
s
s
e
m
i
n
a
t
i
o
n
l
e
a
d
i
n
g
a
n
A
S
N
t
o
a
d
a
r
k
n
e
t
w
o
r
k
(
e
.
g
.
,
t
r
a
d
e
d
r
u
g
s
,
s
e
x
,
c
y
b
e
r
-
a
r
m
s
,
w
e
a
p
o
n
s
,
c
o
u
n
t
e
r
f
e
i
t
c
u
r
r
e
n
c
y
)
.
–
Topic to be revisited at the end of this talk.
T
h
e
t
r
e
n
d
s
s
h
o
w
t
h
a
t
s
o
c
i
a
l
i
z
a
t
i
o
n
w
i
l
l
N
O
T
b
e
c
o
n
f
i
n
e
d
w
i
t
h
i
n
s
p
e
c
i
f
i
c
s
o
c
i
a
l
c
i
r
c
l
e
s
:
•
Smart-homes, smart cars, smart anything
…
•
Personal assistants (e.g., siri, cortana) and
Chatbots (skype) for Commerce and Q/A
Socializing with People (and Bots)
Problem 1: Lack of Proximity
•
Current Microblogging apps are unable to
realize proximity-based applications, e.g., for:
–
V2V communication scenarios
–
Adhoc events
–
Emergency response scenarios
•
Crowd around is not in your Social graph
–
#Hashtags not useful either (difficult to be discovered)
Problem 2: Location Privacy
•
L
B
a
p
p
s
c
a
n
c
o
n
t
i
n
u
o
u
s
l
y
“
k
n
o
w
”
(
s
u
r
v
e
i
l
,
t
r
a
c
k
o
r
m
o
n
i
t
o
r
)
t
h
e
l
o
c
a
t
i
o
n
o
f
a
u
s
e
r
w
h
i
l
e
s
e
r
v
i
n
g
t
h
e
m
.
–
W
h
i
c
h
L
o
c
a
t
i
o
n
s
e
t
t
i
n
g
s
t
o
k
e
e
p
o
n
?
•
“
P
l
e
a
s
e
r
o
b
m
e
”
a
w
a
r
e
n
e
s
s
p
r
o
j
e
c
t
s
h
o
w
s
t
h
e
i
m
p
a
c
t
o
f
l
o
c
a
t
i
o
n
r
e
l
e
a
s
e
.
–
S
h
o
w
s
w
h
e
n
u
s
e
r
s
c
h
e
c
k
-
i
n
s
o
m
e
w
h
e
r
e
t
h
a
t
i
s
n
o
t
t
h
e
i
r
h
o
m
e
(
F
o
u
r
s
q
u
a
r
e
l
o
c
a
t
i
o
n
u
p
d
a
t
e
s
)
.
Problem 3: Boostrapping
•
L
B
a
p
p
s
s
u
f
f
e
r
f
r
o
m
b
o
o
t
s
t
r
a
p
p
i
n
g
i
s
s
u
e
s
–
“Bootstrapping refers to the starting of a self-
sustaining community that is supposed to proceed
without external input”
wikipedia
•
M
o
s
t
L
B
a
p
p
s
d
o
n
’
t
h
a
v
e
e
n
o
u
g
h
u
s
e
r
s
o
n
l
i
n
e
u
p
f
r
o
n
t
.
•
T
h
i
s
g
i
v
e
s
t
h
e
i
m
p
r
e
s
s
i
o
n
t
o
n
e
w
u
s
e
r
s
t
h
a
t
t
h
e
a
p
p
i
s
d
e
s
e
r
t
e
d
.
•
C
o
n
s
e
q
u
e
n
t
l
y
,
m
a
n
y
p
e
o
p
l
e
d
o
n
’
t
u
s
e
i
t
a
n
d
t
h
e
a
p
p
g
r
a
d
u
a
l
l
y
d
i
e
s
.
Rayzit Concept
•
R
a
y
z
i
t
:
a
c
r
o
w
d
m
e
s
s
a
g
i
n
g
s
y
s
t
e
m
t
h
a
t
i
n
s
t
a
n
t
l
y
f
o
r
m
s
a
d
y
n
a
m
i
c
s
o
c
i
a
l
n
e
t
w
o
r
k
b
a
s
e
d
o
n
u
s
e
r
p
r
o
x
i
m
i
t
y
–
Not location-based app but kNN-based! (explained next)
•
Rayzit was funded by the Appcampus Program
(Microsoft, Nokia & Aalto, Finland) in 2013.
–
Ranked among 5 best apps of the program from 3500 apps.
–
O
v
e
r
4
5
,
0
0
0
u
s
e
r
i
n
t
e
r
a
c
t
i
o
n
s
f
r
o
m
o
v
e
r
1
0
,
0
0
0
u
s
e
r
s
!
•
R
e
s
e
a
r
c
h
P
r
o
b
l
e
m
:
B
i
g
D
a
t
a
A
k
N
N
Q
u
e
r
y
P
r
o
c
e
s
s
i
n
g
http://rayzit.com/
AkNN Networks
E
x
a
m
p
l
e
P
r
o
b
l
e
m
:
F
i
n
d
2
C
l
o
s
e
s
t
N
e
i
g
h
b
o
r
s
f
o
r
A
L
L
U
s
e
r
"Continuous all k-nearest neighbor querying in smartphone networks", Georgios Chatzimilioudis,
Demetrios Zeinalipour-Yazti, Wang-Chien Lee, Marios D. Dikaiakos, In IEEE MDM'12.
•
Rayzit User Map
Large-scale
AkNN Networks
H
o
w
t
o
c
o
m
p
u
t
e
t
h
e
k
N
N
f
o
r
m
i
l
l
i
o
n
s
o
f
m
o
b
i
l
e
u
s
e
r
s
e
v
e
r
y
f
e
w
m
i
n
u
t
e
s
?
…
f
r
o
m
s
c
r
a
t
c
h
,
w
i
t
h
o
u
t
t
r
a
c
k
i
n
g
(
r
e
c
o
r
d
i
n
g
)
t
h
e
l
o
c
a
t
i
o
n
o
f
u
s
e
r
s
Presentation Outline
•
Introduction
•
A
k
N
N
Q
u
e
r
y
P
r
o
c
e
s
s
i
n
g
–
I
E
E
E
T
K
D
E
’
1
6
•
Rayzit Crowd Messenger
–
Mobisocial @ IEEE MDM’15
•
Future Challenges
System Model
•
|
O
|
=
n
o
b
j
e
c
t
s
r
e
p
o
r
t
l
o
c
a
t
i
o
n
t
o
Q
P
•
Q
P
c
o
m
p
u
t
e
s
A
k
N
N
q
u
e
r
y
e
v
e
r
y
f
e
w
m
i
n
u
t
e
s
.
Q
P
kNN Query Definition
•
k
N
N
(
q
,
O
)
:
G
i
v
e
n
a
m
u
l
t
i
-
d
i
m
e
n
s
i
o
n
a
l
q
u
e
r
y
p
o
i
n
t
q
,
f
i
n
d
t
h
e
k
o
b
j
e
c
t
s
i
n
O
t
h
a
t
h
a
v
e
t
h
e
s
m
a
l
l
e
s
t
d
i
s
t
a
n
c
e
*
t
o
q
.
–
*
e
.
g
.
M
a
n
h
a
t
t
a
n
(
L
1
)
,
E
u
c
l
i
d
e
a
n
(
L
2
)
,
G
e
o
g
r
a
p
h
i
c
a
l
d
i
s
t
a
n
c
e
(
e
a
r
t
h
s
u
r
f
a
c
e
d
i
s
t
a
n
c
e
)
o
3
q
o
2
o
5
o
4
O
o
1
2
N
N
(
q
,
O
)
=
{o
1
,
o
2
}
AkNN Query Definition
•
F
i
n
d
k
N
N
f
o
r
a
l
l
o
b
j
e
c
t
s
i
n
O
!
•
A
k
N
N
(
O
)
:
G
i
v
e
n
o
b
j
e
c
t
s
o
a
≠
o
b
≠
o
c
,
∀
o
b
∈
k
N
N
(
o
a
,
O
)
a
n
d
∀
o
c
∈
O
-
k
N
N
(
o
a
,
O
)
,
i
t
h
o
l
d
s
t
h
a
t
d
i
s
t
(
o
a
,
o
b
)
≤
d
i
s
t
(
o
a
,
o
c
)
A
k
N
N
=
k
N
N
S
e
l
f
-
J
o
i
n
k
N
N
S
e
l
f
-
J
o
i
n
D
e
f
i
n
i
t
i
o
n
O
⋈
k
N
N
O
=
{(
o
a
,
o
b
)
|
o
a
,
o
b
∈
O
a
n
d
o
b
∈
k
N
N
(
o
a
,
O
)
}
O
(
n
2
)
-
t
i
m
e
s
e
a
r
c
h
c
o
s
t
k
N
N
s
o
f
o
a
n
o
t
k
N
N
s
o
f
o
a
Centralized AkNN
•
Classical problem with many centralized
algorithms
•
A
p
p
l
i
c
a
t
i
o
n
s
:
c
o
m
p
u
t
a
t
i
o
n
a
l
g
e
o
m
e
t
r
y
,
i
m
a
g
e
p
r
o
c
e
s
s
i
n
g
,
d
a
t
a
c
o
m
p
r
e
s
s
i
o
n
,
c
l
u
s
t
e
r
i
n
g
a
n
d
s
p
a
t
i
a
l
d
a
t
a
b
a
s
e
s
.
•
B
a
s
i
c
T
y
p
e
s
o
f
A
l
g
o
r
i
t
h
m
s
:
–
Memory-resident structures & algorithms (theory)
–
Disk-resident structures & algorithms (databases)
–
Parallel algorithms (Graphics)
•
C
o
m
m
o
n
P
r
o
b
l
e
m
:
–
Not designed for distributed Big Data Architectures
(shared-nothing cloud infrastructure)
Distributed AkNN: Issues
o
8
o
1
o
2
o
3
o
4
o
5
o
1
0
o
9
o
1
1
o
6
o
7
L
e
t
u
s
p
a
r
t
i
t
i
o
n
t
h
e
1
1
o
b
j
e
c
t
s
o
v
e
r
4
s
e
r
v
e
r
s
{s
1
,
…
,
s
4
}
P
r
o
b
l
e
m
s
:
A) Communication Overhead
•
O
1
:
2
N
N
(
o
1
)
a
r
e
l
o
c
a
t
e
d
o
n
a
d
j
a
c
e
n
t
n
o
d
e
s
s
1
a
n
d
s
2
=
>
W
e
n
e
e
d
t
o
m
i
n
i
m
i
z
e
t
h
e
r
e
p
l
i
c
a
t
i
o
n
(
f
)
a
m
o
n
g
n
o
d
e
s
!
B) Load Balancing
•
s
4
:
1
5
d
i
s
t
a
n
c
e
s
a
m
o
n
g
6
o
b
j
e
c
t
s
(
i
.
e
.
,
n
(
n
-
1
)
/
2
)
•
s
3
:
o
n
l
y
3
d
i
s
t
a
n
c
e
s
!
=
>
W
e
n
e
e
d
t
o
y
i
e
l
d
a
f
a
i
r
s
p
a
c
e
p
a
r
t
i
t
i
o
n
i
n
g
!
2
N
N
Other Hadoop AkNN
•
B
i
b
l
i
o
g
r
a
p
h
y
i
n
c
l
u
d
e
d
a
f
e
w
n
e
w
d
i
s
t
r
i
b
u
t
e
d
a
l
g
o
r
i
t
h
m
s
f
o
u
n
d
e
d
o
n
t
h
e
M
a
p
-
R
e
d
u
c
e
m
o
d
e
l
.
–
n: number of nodes
–
m: number of servers
–
f: replication factor of an algorithm
H-NJ Algorithm
•
Hadoop Naïve kNN Join Algorithm [1]:
–
M
1
:
T
r
a
n
s
f
e
r
O
(
|
O
|
=
n
)
t
o
a
l
l
m
s
e
r
v
e
r
s
–
R
1
:
O
n
e
a
c
h
s
e
r
v
e
r
,
e
x
e
c
u
t
e
O
i
⋈
k
N
N
O
•
O
i
c
o
n
t
a
i
n
s
n
/
m
o
b
j
e
c
t
s
–
C
o
m
m
u
n
i
c
a
t
i
o
n
C
o
s
t
:
O
(
m
n
)
–
C
P
U
C
o
s
t
:
O
(
n
2
/
m
)
m
n
n
n
n
[1] Lu et. al VLDB’12
R
e
p
l
i
c
a
t
i
o
n
F
a
c
t
o
r
f
H
-
N
J
=
m
O
i
⋈
k
N
N
O
H-BNLJ Algorithm
•
H. Block Nested Loop kNN Join Algorithm [2]:
–
M
1
(
P
a
r
t
i
t
i
o
n
)
:
P
a
r
t
i
t
i
o
n
O
t
o
√
m
s
e
t
s
,
y
i
e
l
d
i
n
g
m
(
O
i
,
O
j
)
-
p
a
i
r
s
,
w
h
e
r
e
i
,
j
≤
√
m
–
R
1
(
L
o
c
a
l
k
N
N
)
:
E
a
c
h
u
n
i
q
u
e
p
a
i
r
(
O
x
,
O
y
)
i
s
m
a
p
p
e
d
t
o
s
a
m
e
s
e
r
v
e
r
,
w
h
i
c
h
c
o
m
p
u
t
e
s
a
d
i
s
t
r
i
b
u
t
e
d
O
x
⋈
k
N
N
O
y
–
M
2
(
M
e
r
g
e
L
o
c
a
l
k
N
N
)
:
H
a
s
h
√
m
l
o
c
a
l
r
e
s
u
l
t
s
o
f
a
n
o
b
j
e
c
t
o
a
t
o
t
h
e
s
a
m
e
s
e
r
v
e
r
(
f
o
r
a
l
l
o
b
j
e
c
t
s
)
–
R
2
(
G
l
o
b
a
l
k
N
N
)
:
C
o
m
p
u
t
e
t
o
p
-
k
f
o
r
e
a
c
h
o
b
j
e
c
t
l
o
c
a
l
l
y
.
m
[2] Zhang et. al EDBT’12
(
O
x
,
O
y
)
o
a
=
{…
}
…
M
R
1
:
o
a
=
{…
}
…
o
a
=
{…
}
o
a
=
{…
}
H-BRJ Optimization
•
H
.
B
l
o
c
k
R
-
t
r
e
e
N
e
s
t
e
d
L
o
o
p
k
N
N
J
o
i
n
[
2
]
:
–
O
p
t
i
m
i
z
e
s
L
o
c
a
l
k
N
N
c
o
m
p
u
t
a
t
i
o
n
(
R
e
d
u
c
e
-
j
o
b
1
)
i
n
p
r
e
v
i
o
u
s
a
l
g
o
r
i
t
h
m
(
H
-
B
N
L
J
)
b
y
b
u
i
l
d
i
n
g
a
n
R
-
t
r
e
e
o
n
O
i
–
D
i
s
t
r
i
b
u
t
e
d
R
-
t
r
e
e
k
N
N
(
n
/
√
m
l
o
g
(
n
/
√
m
)
)
–
Optimal Load Balancing = 1
R
e
p
l
i
c
a
t
i
o
n
F
a
c
t
o
r
r
e
m
a
i
n
s
f
H
-
B
R
J
=
2
√
m
[2] Zhang et. al EDBT’12
(
O
y
,
O
x
)
o
a
=
{…
}
…
M
R
1
o
a
=
{…
}
…
M
R
2
o
a
=
{…
}
o
a
=
{…
}
(
O
y
,
O
y
)
(
O
x
,
O
x
)
(
O
x
,
O
y
)
O
O
x
O
y
all
combos
√
m
m
PGBJ Algorithm
•
P
a
r
t
i
t
i
o
n
G
r
o
u
p
B
l
o
c
k
k
N
N
J
o
i
n
[
1
]
:
–
P
r
e
p
r
o
c
e
s
s
i
n
g
:
S
c
a
t
t
e
r
√
n
p
i
v
o
t
p
o
i
n
t
s
i
n
s
p
a
c
e
(
p
a
r
t
.
)
–
M
a
p
1
:
M
a
p
e
a
c
h
o
b
j
e
c
t
t
o
i
t
s
n
e
a
r
e
s
t
“
p
i
v
o
t
”
a
n
d
s
t
o
r
e
m
i
n
a
n
d
m
a
x
d
i
s
t
a
n
c
e
s
o
f
m
a
p
p
i
n
g
s
t
o
p
i
v
o
t
s
(
f
o
r
p
r
u
n
i
n
g
)
–
M
i
d
s
t
e
p
:
B
a
l
a
n
c
e
√
n
g
r
o
u
p
s
i
n
t
o
m
c
l
u
s
t
e
r
s
O
i
(
b
a
l
a
n
c
i
n
g
)
–
M
a
p
2
:
C
o
m
p
u
t
e
c
a
n
d
i
d
a
t
e
s
F
i
f
o
r
O
i
(
c
o
r
r
e
c
t
n
e
s
s
)
–
R
e
d
u
c
e
2
:
O
i
⋈
k
N
N
F
i
l
o
c
a
l
l
y
m
[1] Lu et al. VLDB’12
O
O
’
1
O
’
2
O
’
3
O
’
m
pivots &
statistics
only
geo-clustering
(voronoi partiotioning)
√
n
O
1
O
2
O
3
O
m
W
o
r
k
e
r
s
W
o
r
k
e
r
s
The Spitfire Algorithm
•
S
p
i
t
f
i
r
e
E
x
e
c
u
t
i
o
n
P
h
a
s
e
s
–
1) Quick Partitioning (each cell at least k)
–
2) Replication border cases minimally
–
3) Perform local AkNN computation efficiently
D
i
s
t
r
i
b
u
t
e
d
A
l
g
o
r
i
t
h
m
i
m
p
l
e
m
e
n
t
e
d
i
n
M
P
I
Spitfire - Partitioning
1.
P
a
r
t
i
t
i
o
n
i
n
g
(
G
e
o
g
r
a
p
h
i
c
a
l
)
–
O
(
n
)
–
m
d
i
s
j
o
i
n
t
,
a
p
p
r
.
e
q
u
a
l
l
y
p
o
p
u
l
a
t
e
d
s
u
b
a
r
e
a
s
(
b
a
l
a
n
c
i
n
g
)
–
Using equi-width and equi-depth histograms
Steps:
1.
H
a
s
h
i
n
t
o
e
q
u
i
-
w
i
d
t
h
b
u
c
k
e
t
s
o
n
x
-
a
x
i
s
2.
G
r
o
u
p
x
-
b
u
c
k
e
t
s
i
n
t
o
√
m
a
p
p
r
o
x
.
e
q
u
i
-
d
e
p
t
h
g
r
o
u
p
s
3.
F
o
r
e
a
c
h
x
-
g
r
o
u
p
d
o
s
t
e
p
1
a
n
d
2
o
n
y
-
a
x
i
s
Result:
•
m
a
p
p
r
.
e
q
u
i
-
d
e
p
t
h
g
r
o
u
p
s
.
•
E
a
c
h
c
e
l
l
h
a
s
a
t
l
e
a
s
t
k
i
t
e
m
s
•
O
(
n
)
a
s
s
u
m
i
n
g
t
h
a
t
n
u
m
b
e
r
o
f
b
u
c
k
e
t
s
i
s
l
e
s
s
t
h
a
n
√
n
Spitfire - Replication
2.
R
e
p
l
i
c
a
t
i
o
n
S
t
e
p
–
I
n
t
h
e
p
a
r
t
i
t
i
o
n
i
n
g
s
t
e
p
,
w
e
m
a
d
e
s
u
r
e
t
h
a
t
e
a
c
h
n
e
i
g
h
b
o
r
i
n
g
c
e
l
l
t
o
O
i
c
o
n
t
a
i
n
s
k
e
n
t
r
i
e
s
.
–
P
r
o
b
l
e
m
:
O
i
c
a
n
’
t
c
o
m
p
l
e
t
e
t
h
e
A
k
N
N
c
o
m
p
u
t
a
t
i
o
n
f
o
r
i
t
s
i
n
t
e
r
n
a
l
o
b
j
e
c
t
s
a
s
t
h
e
r
e
a
r
e
o
b
j
e
c
t
s
(
e
.
g
.
,
t
h
e
r
e
d
b
u
l
l
e
t
)
l
y
i
n
g
c
l
o
s
e
t
o
n
e
i
g
h
b
o
r
s
.
–
S
o
l
u
t
i
o
n
:
•
R
e
c
e
i
v
e
E
x
t
e
r
n
a
l
C
a
n
d
i
d
a
t
e
s
(
E
C
)
f
r
o
m
n
e
i
g
h
b
o
r
s
.
•
I
f
a
l
l
n
o
d
e
s
d
o
t
h
i
s
,
e
a
c
h
O
i
c
a
n
n
e
x
t
p
e
r
f
o
r
m
a
l
o
c
a
l
A
k
N
N
c
o
m
p
u
t
a
t
i
o
n
!
–
N
e
x
t
P
r
o
b
l
e
m
:
H
o
w
t
o
f
i
n
d
E
C
?
O
i
Spitfire - Replication
2.
R
e
p
l
i
c
a
t
i
o
n
:
H
o
w
t
o
d
e
r
i
v
e
E
C
?
–
A
)
S
e
g
m
e
n
t
i
n
g
B
o
r
d
e
r
i
n
t
o
s
m
a
l
l
e
r
“
b
”
s
e
g
m
e
n
t
s
–
B
)
A
p
p
l
y
T
o
p
-
k
“
h
i
d
i
n
g
”
r
u
l
e
f
o
r
e
a
c
h
“
b
”
t
o
f
i
n
d
w
h
i
c
h
l
o
c
a
l
o
b
j
e
c
t
s
a
r
e
n
e
c
e
s
s
a
r
y
f
o
r
n
e
i
g
h
b
o
r
O
j
.
–
C
)
S
h
i
p
t
h
o
s
e
c
a
n
d
i
d
a
t
e
s
o
v
e
r
t
o
O
j
i
n
b
a
t
c
h
m
o
d
e
I
f
k
o
b
j
e
c
t
s
a
r
e
c
l
o
s
e
r
t
o
b
t
h
a
n
o
1
a
n
d
o
3
,
t
h
e
n
o
1
i
s
g
u
a
r
a
n
t
e
e
d
N
O
T
t
o
b
e
a
k
N
N
o
f
o
3
a
n
d
v
i
c
e
v
e
r
s
a
.
(
B
)
:
T
o
p
-
k
“
h
i
d
i
n
g
”
r
u
l
e
(
A
)
:
S
e
g
m
e
n
t
i
n
g
B
o
r
d
e
r
b
Spitfire - Refinement
3.
L
o
c
a
l
R
e
f
i
n
e
m
e
n
t
-
-
O
(
f
S
p
i
t
f
i
r
e
n
2
/
m
2
)
–
e
x
e
c
u
t
e
l
o
c
a
l
l
y
O
i
⋈
k
N
N
(
O
i
∪
E
C
i
)
u
s
i
n
g
a
n
y
A
k
N
N
a
l
g
o
r
i
t
h
m
(
w
e
u
s
e
a
v
a
r
i
a
n
t
o
f
P
r
o
x
i
m
i
t
y
I
E
E
E
M
D
M
1
2
)
s
i
E
C
i
Same intuition:
1.
Partition using a grid
2.
Find candidates per cell
3.
Refinement per cell
⋈
kNN
Evaluation Testbed
•
9 computing nodes
•
8 GB RAM
•
2
CPUs@2.40GHz
•
MapReduce over
Tachyon
(memory-centric file system)
•
Datasets:
–
R
a
n
d
o
m
(
s
y
n
t
h
e
t
i
c
)
–
u
n
i
f
o
r
m
d
i
s
t
r
i
b
u
t
i
o
n
–
O
l
d
e
n
b
u
r
g
(
r
e
a
l
i
s
t
i
c
)
–
s
k
e
w
e
d
d
i
s
t
r
i
b
u
t
i
o
n
–
G
e
o
l
i
f
e
(
r
e
a
l
i
s
t
i
c
)
–
v
e
r
y
s
k
e
w
e
d
d
i
s
t
r
i
b
u
t
i
o
n
–
R
a
y
z
i
t
(
r
e
a
l
)
–
s
k
e
w
e
d
d
i
s
t
r
i
b
u
t
i
o
n
u
p
t
o
2
x
1
0
0
0
0
u
s
e
r
s
Response Time
•
Spitfire
and
PGBJ
scale better than block algorithms H-BNLJ and H-BRJ
that run out of memory!
•
Spitfire
outperforms all other algorithms in all cases.
•
Spitfire better than PGBJ on all datasets:
(67%, 75%, 14% on
Random, Oldenburg, Geolife).
Re-computation
possible every
100 sec (~every
few min)
Partitioning and Replication
•
Spitfire
partitioning is much
faster
than
PGBJ
•
PGBJ
is growing exponentially
•
H-BNLJ
and
H-BRJ
do not partition geographically
suffer in refinement
•
Same response times for all datasets
partitioning independent of dataset
Replication Factor (f)
•
Plot for most skewed dataset. Others have similar results
•
f
Spitfire
outperforms
(optimal value for f is 1)
•
f
S
p
i
t
f
i
r
e
d
r
o
p
s
a
s
n
i
n
c
r
e
a
s
e
s
(
s
c
a
l
a
b
i
l
i
t
y
)
•
f
H-BNLJ
and
f
H-BRJ
=
2m
0.5
, independent of
n
•
Replication factor offers clear comparison independent of implementation
Presentation Outline
•
Introduction
•
AkNN Query Processing
–
IEEE TKDE’16
•
R
a
y
z
i
t
C
r
o
w
d
M
e
s
s
e
n
g
e
r
–
M
o
b
i
s
o
c
i
a
l
@
I
E
E
E
M
D
M
’
1
5
•
Future Challenges
Rayzit Application
•
A
u
s
e
r
c
a
n
p
o
s
t
a
n
e
w
R
a
y
z
(
t
e
x
t
,
a
u
d
i
o
,
v
i
d
e
o
–
s
h
o
w
n
a
s
a
t
t
a
c
h
m
e
n
t
)
.
•
T
o
m
i
n
i
m
i
z
e
s
p
a
m
m
i
n
g
,
e
a
c
h
u
s
e
r
h
a
s
a
p
o
w
e
r
b
a
r
t
h
a
t
d
e
c
r
e
a
s
e
s
o
n
e
v
e
r
y
a
c
t
i
o
n
:
•
R
a
y
z
,
r
e
p
l
y
,
r
e
-
r
a
y
z
,
p
o
w
e
r
+
/
-
•
W
h
e
n
e
m
p
t
y
n
o
m
o
r
e
a
c
t
i
o
n
s
a
r
e
p
o
s
s
i
b
l
e
u
n
t
i
l
i
t
g
r
a
d
u
a
l
l
y
r
e
l
o
a
d
s
.
•
T
o
r
e
l
o
a
d
f
a
s
t
e
r
,
w
e
p
r
o
v
i
d
e
t
h
e
i
n
c
e
n
t
i
v
e
t
o
p
r
o
v
i
d
e
u
s
e
f
u
l
a
n
s
w
e
r
s
t
h
a
t
w
i
l
l
b
e
s
t
a
r
r
e
d
b
y
o
t
h
e
r
s
.
•
A message can be bounded to a
certain distance (kNN is default)
•
0.5, 5, 50, 500, 5000 km
Example Conversations
G
e
n
e
r
a
l
A
d
v
i
c
e
&
C
r
o
w
d
C
a
s
t
i
n
g
Example Conversations
P
h
i
l
o
s
o
p
h
i
c
a
l
&
L
o
c
a
t
i
o
n
-
b
a
s
e
d
Q
u
e
s
t
i
o
n
s
Example Conversations
F
e
e
l
i
n
g
s
E
x
p
r
e
s
s
i
o
n
&
T
a
b
o
o
Q
u
e
s
t
i
o
n
s
Example Conversations
I
n
a
p
p
r
o
p
r
i
a
t
e
M
e
s
s
a
g
e
s
(
b
e
f
o
r
e
i
n
s
t
a
l
l
a
t
i
o
n
o
f
r
e
p
o
r
t
f
i
l
t
e
r
)
More Topics on Rayzit
•
Topics:
Location, Surveys, Thoughs, Feelings
•
Most answered rayz (responses)
–
“Rain! Lovely.”
(228)
–
“Any good PGs near Avanshi RoadCBE?”
(142)
–
“Which windows phone do you have?”
(119)
–
“anyone around..???”
(94)
–
“Share a secret ..”
(90)
–
“Rayzit: What is the next feature you would like to see?”
(81)
–
“I love.... (continue)” (58)
–
“Where are you from? I want to test Rayzit location.”
(52)
–
“Where to dine in Coimbatore if you want to have a dinner
peacefully and by yourself?”
(40)
Analyzing the Rayzit Network
•
We used both Flurry App Analytics and Analytic
queries on our NoSQL database
•
I
n
t
e
r
v
a
l
o
f
A
n
a
l
y
s
i
s
:
O
c
t
.
1
3
–
M
a
r
.
1
5
–
32,762 Sessions
–
5,062 New Users
–
1.7 mins Median
Session Length
•
C
o
n
c
l
u
s
i
o
n
:
–
App more popular in Asia, India particularly because
of large Microsoft community and Microsoft
Promotion)
Average Reply Time
2
8
%
2
8
%
o
f
r
e
p
l
i
e
s
w
e
r
e
r
e
c
o
r
d
e
d
w
i
t
h
i
n
1
m
i
n
u
t
e
.
C
r
o
w
d
V
o
l
u
m
e
c
r
e
a
t
e
s
q
u
i
c
k
r
e
s
p
o
n
s
e
p
o
s
s
i
b
i
l
i
t
i
e
s
N
e
a
r
b
y
u
s
e
r
s
r
e
s
p
o
n
d
q
u
i
c
k
l
y
(
m
o
r
e
i
n
t
e
r
e
s
t
e
d
i
n
t
h
e
d
i
s
c
u
s
s
i
o
n
)
.
O
n
l
i
n
e
u
s
e
r
s
O
f
f
l
i
n
e
u
s
e
r
s
S
p
o
r
a
d
i
c
u
s
e
r
s
R
e
s
t
Average and Maximum
Distance (Rayz, Reply)
•
H
y
p
o
t
h
e
s
i
s
:
C
l
o
s
e
r
G
e
o
g
r
a
p
h
i
c
U
s
e
r
s
m
e
a
n
s
M
o
r
e
R
e
p
l
i
e
s
People in classroom, event?
d
i
s
t
a
n
c
e
o
f
r
a
y
z
t
o
r
e
p
l
i
e
s
(
[
1
-
5
0
]
r
e
p
l
i
e
s
)
=
1
5
k
m
(
m
a
x
)
>
5
0
r
e
p
l
i
e
s
A
t
1
0
k
m
(
m
a
x
)
>
1
0
0
r
e
p
l
i
e
s
a
t
8
m
e
t
e
r
s
!
Presentation Outline
•
Introduction
•
AkNN Query Processing
–
IEEE TKDE’16
•
Rayzit Crowd Messenger
–
Mobisocial @ IEEE MDM’15
•
F
u
t
u
r
e
C
h
a
l
l
e
n
g
e
s
Future Challenges
•
T
o
o
l
s
t
o
h
a
n
d
l
e
l
a
c
k
o
f
a
c
c
o
u
n
t
a
b
i
l
i
t
y
h
a
v
e
s
h
o
w
n
t
o
e
n
c
o
u
r
a
g
e
n
e
g
a
t
i
v
e
d
i
s
c
o
u
r
s
e
,
i
n
c
l
u
d
i
n
g
p
e
r
s
o
n
a
l
a
t
t
a
c
k
s
,
t
h
r
e
a
t
s
o
r
r
u
m
o
r
s
p
r
e
a
d
i
n
g
.
•
I
n
t
r
o
d
u
c
e
m
o
r
e
a
u
t
o
m
a
t
e
d
a
n
d
c
r
o
w
d
m
a
n
a
g
e
m
e
n
t
t
e
c
h
n
i
q
u
e
s
(
c
o
l
l
a
b
o
r
a
t
i
v
e
f
i
l
t
e
r
i
n
g
)
:
–
M
o
r
e
i
n
t
e
l
l
i
g
e
n
t
R
e
p
o
r
t
M
a
n
a
g
e
m
e
n
t
–
C
l
a
s
s
i
f
y
r
a
y
z
t
h
r
e
a
d
s
t
o
c
a
t
e
g
o
r
i
e
s
–
M
o
r
e
d
e
t
a
i
l
e
d
d
a
t
a
a
n
a
l
y
s
i
s
(
i
n
t
e
r
a
c
t
i
o
n
g
r
a
p
h
s
,
r
e
r
a
y
z
p
a
t
h
l
e
n
g
t
h
,
c
o
m
m
u
n
i
t
y
d
e
t
e
c
t
i
o
n
,
c
h
a
t
g
r
o
u
p
s
v
s
.
l
o
c
a
t
i
o
n
,
n
e
w
v
s
.
o
l
d
u
s
e
r
s
,
…
.
Future Challenges
•
Shallow syntax in messages:
2m, 2morrow,
tmw, tomoz, tomz,
all refer to tomorrow.
•
O
f
f
-
t
h
e
-
s
h
e
l
f
P
a
r
t
-
o
f
-
S
p
e
e
c
h
(
P
O
S
)
t
a
g
g
e
r
s
(
e
.
g
.
,
S
t
a
n
f
o
r
d
N
L
P
o
r
M
P
I
A
I
D
A
)
d
o
n
’
t
w
o
r
k
a
d
e
q
u
a
t
e
l
y
o
n
t
h
e
s
e
m
e
s
s
a
g
e
s
.
•
D
a
t
a
c
o
n
t
a
i
n
s
m
a
n
y
i
n
f
r
e
q
u
e
n
t
e
n
t
i
t
y
t
y
p
e
s
(
e
.
g
.
,
p
h
y
s
i
c
i
s
t
)
a
n
d
c
a
p
i
t
a
l
i
z
a
t
i
o
n
(
u
s
e
d
f
o
r
r
e
c
o
g
n
i
z
i
n
g
n
a
m
e
d
e
n
t
i
t
i
e
s
,
e
.
g
.
,
A
l
b
e
r
t
E
i
n
s
t
e
i
n
)
i
s
n
o
t
t
h
e
r
e
.
•
M
i
g
h
t
n
e
e
d
t
o
e
x
p
l
o
i
t
s
p
a
t
i
a
l
a
n
d
t
e
m
p
o
r
a
l
d
i
m
e
n
s
i
o
n
s
i
n
d
a
t
a
t
o
u
n
d
e
r
s
t
a
n
d
w
h
a
t
s
o
m
e
t
h
i
n
g
r
e
f
e
r
s
t
o
.
Future Challenges
Paris Descartes University Seminar Series on Data Analytics
in collaboration with the diNo group, April 12, 2017
Building All k Nearest Neigbhor
Social Communities
D
e
m
e
t
r
i
s
Z
e
i
n
a
l
i
p
o
u
r
T
h
a
n
k
Y
o
u
!
Q
u
e
s
t
i
o
n
s
?
Max Planck Institute for Informatics, Germany & Department of
Computer Science, University of Cyprus, Cyprus
http://www.cs.ucy.ac.cy/~dzeina/
dzeina@cs.ucy.ac.cy
This content discusses the development of online social communities facilitated by microblogging tools on the Internet. It explores the structure and content of these communities and highlights both their benefits and drawbacks, emphasizing privacy, censorship, and the risks of negative discourse. The content also touches on the implications of the spread of illegal content within these communities.
Uploaded on Feb 28, 2025 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Building All k Nearest Neighbor Social Communities Demetris Zeinalipour Assistant Professor Max Planck Institute for Informatics, Germany & Department of Computer Science, University of Cyprus, Cyprus http://www.cs.ucy.ac.cy/~dzeina/ dzeina@cs.ucy.ac.cy Paris Descartes University, Seminar Series on Data Analytics, Paris, France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Acknowledgements Joint work with: "Distributed In-Memory Processing of All k Nearest Neighbor Queries", Georgios Chatzimilioudis, Constantinos Costa, Demetrios Zeinalipour-Yazti, Wang-Chien Lee and Evaggelia Pitoura, IEEE Transactions on Knowledge and Data Engineering (TKDE'16), IEEE Computer Society, Vol. 28, Iss. 4, pp. 925-938, 2016. Sources (GPL): https://github.com/dmsl/rayzit/tree/master/spitfire "Rayzit: An Anonymous and Dynamic Crowd Messaging Architecture", Constantinos Costa, Chrysovalantis Anastasiou, Georgios Chatzimilioudis and Demetrios Zeinalipour-Yazti, in IEEE Mobisocial '15, Vol. 2, pp. 98-103, Pittsburgh, PA, USA, 2015. Sources (MIT): https://github.com/dmsl/rayzit/ 2 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Online Social Communities With the advent the Internet, microblogging chat tools have established new means for Online Social Networks: Content: Microblogging data (small elements of content such as short text, images, video.) Structure: Implicit Graph (address book) or Explicit Graph (followers, friends) UNIX talk 88 99 03 IRC MSN Skype Facebook 04 Twitter 06 Foursquare 08 Snapchat 11 Rayzit 13 SMS 70 80 90 00 10 15 Chat Messaging Social Location Forget Anon. LBS 3 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Online Social Communities Benefits: avoid censorship and retain privacy huge value for individuals especially when they are working in far more difficult parts of the world. J. Bartlett, dw.com, 25.7.2016. Apps: Games (MMOG), Education(MOOC), Crowdsourcing. Drawbacks: accountability and traceability threats, rumor spreading and negative discourse (e.g., intimidate, control, manipulate, falsely discredit, or humiliate) leading to the shutdown of services (e.g., Secret) illegal content dissemination leading an ASN to a dark network (e.g., trade drugs, sex, cyber-arms, weapons, counterfeit currency). Topic to be revisited at the end of this talk. 4 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Socializing with People (and Bots) The trends show that socialization will NOT be confined within specific social circles: Smart-homes, smart cars, smart anything Personal assistants (e.g., siri, cortana) and Chatbots (skype) for Commerce and Q/A 5 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Problem 1: Lack of Proximity Current Microblogging apps are unable to realize proximity-based applications, e.g., for: V2V communication scenarios Adhoc events Emergency response scenarios Crowd around is not in your Social graph #Hashtags not useful either (difficult to be discovered) 6 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Problem 2: Location Privacy LB apps can continuously know (surveil, track or monitor) the location of a user while serving them. Which Location settings to keep on? Please rob me awareness project shows the impact of location release. Shows when users check-in somewhere that is not their home (Foursquare location updates). 7 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Problem 3: Boostrapping LB apps suffer from bootstrapping issues Bootstrapping refers to the starting of a self- sustaining community that is supposed to proceed without external input wikipedia Most LB apps don t have enough users online upfront. This gives the impression to new users that the app is deserted. Consequently, many people don t use it and the app gradually dies. 8 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Rayzit Concept Rayzit: a crowd messaging system that instantly forms a dynamic social network based on user proximity Not location-based app but kNN-based! (explained next) Rayzit was funded by the Appcampus Program (Microsoft, Nokia & Aalto, Finland) in 2013. Ranked among 5 best apps of the program from 3500 apps. Over 45,000 user interactions from over 10,000 users! Research Problem: Big Data AkNN Query Processing http://rayzit.com/ 9 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 AkNN Networks Example Problem: Find 2 Closest Neighbors for ALL User "Continuous all k-nearest neighbor querying in smartphone networks", Georgios Chatzimilioudis, Demetrios Zeinalipour-Yazti, Wang-Chien Lee, Marios D. Dikaiakos, In IEEE MDM'12. 10 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Large-scale AkNN Networks Rayzit User Map How to compute the kNN for millions of mobile users every few minutes? from scratch, without tracking (recording) the location of users 11 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Presentation Outline Introduction AkNN Query Processing IEEE TKDE 16 Rayzit Crowd Messenger Mobisocial @ IEEE MDM 15 Future Challenges 12 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 System Model |O| = n objects report location to QP QP computes AkNN query every few minutes. o2 QP O o1 o8 o3 o7 o5 o9 o4 o6 o11 o10 13 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 kNN Query Definition kNN(q, O): Given a multi-dimensional query point q, find the k objects in O that have the smallest distance* to q. *e.g. Manhattan (L1), Euclidean (L2), Geographical distance (earth surface distance) q O o1 o2 2NN(q,O) = {o1,o2} o3 o4 o5 14 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 AkNN Query Definition kNNs of oa not kNNs of oa Find kNN for all objects in O! AkNN(O): Given objects oa ob oc, ob kNN(oa,O) and oc O - kNN(oa,O), it holds that dist(oa,ob) dist(oa,oc) o2 o1 O AkNN = kNN Self-Join o8 o3 kNN Self-Join Definition O kNN O = {(oa, ob) | oa, ob O and ob kNN(oa, O)} o7 o5 o9 o4 o6 o11 o10 O(n2)-time search cost 15 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Centralized AkNN Classical problem with many centralized algorithms Applications: computational geometry, image processing, data compression, clustering and spatial databases. Basic Types of Algorithms: Memory-resident structures & algorithms (theory) Disk-resident structures & algorithms (databases) Parallel algorithms (Graphics) Common Problem: Not designed for distributed Big Data Architectures (shared-nothing cloud infrastructure) 16 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Distributed AkNN: Issues s1 2NN Let us partition the 11 objects over 4 servers {s1, ,s4} Problems: A) Communication Overhead O1: 2NN(o1) are located on adjacent nodes s1 and s2 => We need to minimize the replication (f) among nodes! B) Load Balancing s4: 15 distances among 6 objects (i.e., n(n-1)/2) s3:only 3 distances! => We need to yield a fair space partitioning! s2 o2 o1 o3 o8 o5 o7 o4 o9 o6 o10 o11 s3 s4 17 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Other Hadoop AkNN Bibliography included a few new distributed algorithms founded on the Map-Reduce model. n: number of nodes m: number of servers f: replication factor of an algorithm 18 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 PGBJ Algorithm Partition Group Block kNN Join [1]: Preprocessing: Scatter n pivot points in space (part.) Map1: Map each object to its nearest pivot and store min and max distances of mappings to pivots (for pruning) Midstep: Balance ngroups into m clusters Oi(balancing) Map2: Compute candidates Fifor Oi(correctness) Reduce2: Oi kNNFilocally [1] Lu et al. VLDB 12 pivots & statistics only n O1 O2 O m O 1 O 2 O 3 O m O3 Om geo-clustering (voronoi partiotioning) Workers Workers 22 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 The Spitfire Algorithm Spitfire Execution Phases 1) Quick Partitioning (each cell at least k) 2) Replication border cases minimally 3) Perform local AkNN computation efficiently Distributed Algorithm implemented in MPI 23 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Spitfire - Partitioning 1. Partitioning (Geographical) O(n) m disjoint, appr. equally populated subareas (balancing) Using equi-width and equi-depth histograms Steps: 1.Hash into equi-width buckets on x-axis 2.Group x-buckets into m approx. equi-depth groups 3.For each x-group do step 1 and 2 on y-axis Result: m appr. equi-depth groups. Each cell has at least k items O(n) assuming that number of buckets is less than n 24 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Spitfire - Replication 2. Replication Step In the partitioning step, we made sure that each neighboring cell to Oicontains k entries. Problem: Oican t complete the AkNN computation for its internal objects as there are objects (e.g., the red bullet) lying close to neighbors. Solution: Receive External Candidates (EC) from neighbors. If all nodes do this, each Oi can next perform a local AkNN computation! Next Problem: How to find EC? Oi 25 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Spitfire - Replication 7 2. Replication: How to derive EC? A) Segmenting Border into smaller b segments B) Apply Top-k hiding rule for each b to find which local objects are necessary for neighbor Oj. C) Ship those candidates over to Ojin batch mode e O4 O6 O8 and the condition mindist(o,b) < b is checked for each segment b. If this condition holds then object o is part of ECb. In our example, ECbe= {o1,o2}, ECe= {o1,o2} and ECed= {o2,o4}. Now s1sends ECbeto s2, ECeto s3, and ECedto s4, based on the adjacency described earlier. Similarly, the above steps take place in parallel on each server. Therefore, s1 receives from s2 the ECbeof set O2, from s3 the ECe of set O3, and from s4 the ECedof set O4. Hence, server s1 will be able to construct its EC1 = b BiECb= {o5,o6,o7,o8}. The External Candidate compu- tation completes and the local kNN refinement phase initiates computing kNN(o,Oi ECi), o Oi on each server si. s1 s2 a b c O1 O2 O3 O3 O1 O13 O5 O2 O12 f d (A): Segmenting Border (B): Top-k hiding rule O1 O3 O7 b O9 O10 O11 g h i b s4 s3 If k objects are closer to b than o1and o3, then o1is guaranteed NOT to be Fig. 4. (Top) o2 hides o1 from o3, (Bottom) Segment b hides o1 a kNN of o3and vice versa. Fig. 3. Server s1sends {o1,o2} to s2, {o1,o2} to s3, and {o2,o4} to s4. Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017 from o3. 4 In this section we first show that our algorithm leads to a cor- rect AkNN result, i.e., based on the External Candidates determined by computeECB. Then, we analyze its computational and communication cost. CORRECTNESS AND ANALYSIS 26 m ikNN(o,ECi Oi) = kNN(o,O), In Spitfire, we partition sub-area Ai of server si into a grid of equi-width cells Ci. Each cell c Ci contains a disjoint subset Oc Oi of objects. Next, we compute locally a correct external candidate set ECcfor each cell c Ci (similarly to the replication step). Finally, we find the kNNs for each object o Oi by computing kNN(o,Oc ECc). In Algorithm 4, objects o Oi are scanned once to build a k-min heap Hc for each cell c Ci based on the minimum distance mindist(o,c) between o and the cell-border (Line 3). The first k objects are then popped from Hc to determine threshold c, based on Equation (2) (Lines 4-5). Objects o Oi are scanned once again to determine the External Candidates ECcthat satisfy the threshold as in Equation (3) (Lines 6-10). Finally, si computes kNN(o,Oc ECc), o Oc(Line 11). Given optimal load balancing, the building phase (heap construction and External Candidates) completes in O(n time, whereas finding the kNN within Oc ECc completes in O(fSpitfiren 4.1 To prove correctness, we show that it suffices to compute the External Candidates ECBito border Bi in order to find the External Candidates ECi of the whole area Ai, given area Ai, its border Bi, and the necessary objects around Bi. In the following, we first define the notion of point hiding. Correctness of the computeECB function Definition 1 (Point Hiding). Given three points o1,o2,o3on a line, which holds the following relationship dist(o1,o3) = dist(o1,o2)+ dist(o2,o3), we say that o2hides o1and o3from each other. In Figure 4 (top) point o2hides o1and o3from each other. m) Lemma 1. Given three points o1, o2, o3 where o2 hides o1 from o3and the fact that o1is not a kNN of o2, it holds that o1is not a kNN of o3, and vice versa. n m= |Oi|. m) time, where 3.5 Given an object set O, assume that a set of servers {s1,s2,s3,s4} have been assigned to sub-areas {abde, bcfe, efih, dehg}, respectively (see Figure 3). In the following, we discuss the processing steps of server s1. The objects of s1are O1={o1,o2,o3,o4}, its adjacent servers are Adji={s2,s3,s4}, and its border segments are B1 = {a,ab,b,be,e,ed,d,da}. For simplicity we have defined the border segments to be a one-to-one mapping to the corresponding adjacent servers. As shown, border segment be is adjacent to server s2, corner e is adjacent to server s3, and segment ed is adjacent to server s4. Server s1locally computes ECbfor each b Bi. It does so by scanning all objects o O1and building a heap Hbfor each border segment bbased on mindist(o,b). The k closest objects to each b are popped from Hb as a result. In our example, {o1,o2} are the k closest objects to segment be, {o1,o2} are the k closest objects to e, and {o2,o4} are the k closest objects to segment ed. For each segment b, its pruning threshold b is deter- mined by the largest maxdist of its closest objects computed in the previous step. For instance, for segment be this is b= maxdist(o1,be), since maxdist(o1,be) > maxdist(o2,be). Given the thresholds b, all objects o O1are scanned again Running Example Proof: To prove that o1 is not a kNN of o3 it suffices to prove that there are k points closer than o1 is to o3. The fact that o1 is not a kNN of o2means that there are k other points, {p1,p2,...,pk}, in space that are closer to o2 than is o1, dist(pi,o2) dist(o1,o2). It holds that dist(pi,o3) dist(o1,o2)+ dist(o1,o3) dist(o2,o1) based on trigonometry, which gives dist(pi,o3) dist(o1,o3). Therefore there are k points, namely {p1,p2,...,pk}, that are closer to o3than is o1 Similarly, we can extend the notion of hiding from a point to a line segment, i.e., border. In Figure 4 (bottom) segment b hides o1and o3from each other. Definition 2 (Segment Hiding). Given two points o1, o3, and a segment b, we say that b hides o1 and o3 from each other, when there is always a point o b that hides o1and o3from each other. Lemma 2. Given two points o1and o3, a segment bthat hides o1from o3, and the fact that o1is not a kNN of any point on b, it holds that o1is not a kNN of o3, and vice versa. Proof: It suffices if it holds that dist(ki,o3) dist(o1,o3) for 1 i k. Given that o1is not a kNN of any point p b,
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Spitfire - Refinement 3. Local Refinement -- O( fSpitfiren2/m2 ) execute locally Oi kNN(Oi ECi) using any AkNN algorithm (we use a variant of Proximity IEEE MDM12) si Same intuition: 1.Partition using a grid kNN 2.Find candidates per cell 3.Refinement per cell ECi 27 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Evaluation Testbed 9 computing nodes 8 GB RAM 2 CPUs@2.40GHz MapReduce over Tachyon (memory-centric file system) Datasets: Random (synthetic) uniform distribution Oldenburg (realistic) skewed distribution Geolife (realistic) very skewed distribution Rayzit (real) skewed distribution up to 2x10000 users 28 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Response Time Re-computation possible every 100 sec (~every few min) Spitfire and PGBJ scale better than block algorithms H-BNLJ and H-BRJ that run out of memory! Spitfire outperforms all other algorithms in all cases. Spitfire better than PGBJ on all datasets: (67%, 75%, 14% on Random, Oldenburg, Geolife). 29 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
11 RANDOM: Total Computation for varying number of users (k=64, m=9) OLDENBURG: Total Computation for varying number of users (k=64, m=9) GEOLIFE: Total Computation for varying number of users (k=64, m=9) RAYZIT: Total Computation for varying number of users (k=64, m=9) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) 100000 100000 100000 100000 Proximity H-BNLJ H-BRJ PGBJ Spitfire Proximity H-BNLJ H-BRJ PGBJ Spitfire Proximity H-BNLJ H-BRJ PGBJ Spitfire Proximity H-BNLJ H-BRJ PGBJ Spitfire 10000 10000 10000 10000 1000 1000 1000 1000 Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory 100 100 100 100 10 10 10 10 1 1 1 1 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 2*104 Number of online users (n) Fig. 8. AkNN query response time with increasing number of users. We compare the proposed Spitfire algorithm against the three state-of-the-art AkNN algorithms and a centralized algorithm on four datasets. Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Partitioning and Replication GEOLIFE: Partitioning and Replication for varying number of users (k=64, m=9) RANDOM: Partitioning and Replication for varying number of users (k=64, m=9) OLDENBURG: Partitioning and Replication for varying number of users (k=64, m=9) RAYZIT: Partitioning and Replication for varying number of users (k=64, m=9) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) 1000 1000 1000 1000 H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire 100 100 100 100 10 10 10 10 1 1 1 1 0.1 0.1 0.1 0.1 0.01 0.01 0.01 0.01 104 105 106 104 105 106 104 105 106 2*104 Number of online users (n) Number of online users (n) Number of online users (n) Number of online users (n) Spitfire partitioning is much faster than PGBJ PGBJ is growing exponentially H-BNLJ and H-BRJ do not partition geographically suffer in refinement Same response times for all datasets partitioning independent of dataset Fig. 9. Partitioning and Replication step response time with increasing number of users. 30 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017 RANDOM: Refinement for varying number of users (k=64, m=9) OLDENBURG: Refinement for varying number of users (k=64, m=9) GEOLIFE: Refinement for varying number of users (k=64, m=9) RAYZIT: Refinement for varying number of users (k=64, m=9) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) 10000 10000 10000 10000 H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire 1000 1000 1000 1000 100 100 100 100 Out Of Memory Out Of Memory Out Of Memory 10 10 10 10 1 1 1 1 0.1 0.1 0.1 0.1 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 2*104 Number of online users (n) Fig. 10. Refinement step response time with increasing number of users and for each available dataset. RANDOM: Replication factor for varying number of users (k=64, m=9) OLDENBURG: Replication factor for varying number of users (k=64, m=9) GEOLIFE: Replication factor for varying number of users (k=64, m=9) RAYZIT: Replication factor for varying number of users (k=64, m=9) 11 11 11 11 H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire Replication factor (f) Replication factor (f) Replication factor (f) Replication factor (f) 9 9 9 9 7 7 7 7 5 5 5 5 3 3 3 3 1 1 1 1 104 105 106 104 105 106 104 105 106 2*104 Number of Users (n) Number of Users (n) Number of Users (n) Number of Users (n) Fig. 11. Replication factor f with increasing number of users. The optimal value for f is 1, signifying no replication. TABLE 3 up the values shown in Figures 9 and 10 and comparing to the total response time in Figure 8, it becomes obvious that most of H-BRJ s response time is spent in communication, which is indicated theoretically by its communication complexity of O( mn) shown in Table 2. We focus on comparing only Spitfire and PGBJ for the rest of our evaluation. For 104online users, Spitfire outperforms all algorithms by at least 85% for all dataset, whereas for 105Spitfire outperforms PGBJ, by 75%, 75% and 53% for the Random, Oldenburg and Geolife datasets, respectively. Values used in our experiments Section 5.5 5.6 5.7 5.8 5.9 Dataset ALL Random ALL Random, Rayzit Random n k 64 64 64 m 9 9 9 9 [104, 105, 106] 106 106(104Rayzit) 106(104Rayzit) 106 4i, 1 i 5 64 [3, 6, 9] 5.5 Varying Number of Users (n) In this experimental series, we increase the workload of the system by growing the number of online users (n) exponen- tially and measure the response time and replication factor of the algorithms under evaluation. Total Computation: In Figure 8, we measure the total re- sponse time for all algorithms, datasets and workloads. We can clearly see that Spitfire outperforms all other algorithms in every case. It is also evident that H-BNLJ and H-BRJ do not scale. H-BRJ achieves the worst time for 106users. Adding Spitfire and PGBJ are the only algorithms that scale. For a million online users (n=106), Spitfire and PGBJ are the fastest algorithms, but Spitfire still outperforms PGBJ by 67%, 75%, 14% for the Random, Oldenburg and Geolife datasets, respec- tively. The small percentage noted for the Geolife dataset is attributed to the fact that this dataset is highly skewed (as observed in Figure 7), and that PGBJ achieves better load balancing (as shown later in Section 5.7), which in turn leads to a faster refinement step.
11 RANDOM: Total Computation for varying number of users (k=64, m=9) OLDENBURG: Total Computation for varying number of users (k=64, m=9) GEOLIFE: Total Computation for varying number of users (k=64, m=9) RAYZIT: Total Computation for varying number of users (k=64, m=9) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) 100000 100000 100000 100000 Proximity H-BNLJ H-BRJ PGBJ Spitfire Proximity H-BNLJ H-BRJ PGBJ Spitfire Proximity H-BNLJ H-BRJ PGBJ Spitfire Proximity H-BNLJ H-BRJ PGBJ Spitfire 10000 10000 10000 10000 1000 1000 1000 1000 Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory Out Of Memory 100 100 100 100 10 10 10 10 1 1 1 1 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 2*104 Number of online users (n) Fig. 8. AkNN query response time with increasing number of users. We compare the proposed Spitfire algorithm against the three state-of-the-art AkNN algorithms and a centralized algorithm on four datasets. RANDOM: Partitioning and Replication for varying number of users (k=64, m=9) OLDENBURG: Partitioning and Replication for varying number of users (k=64, m=9) GEOLIFE: Partitioning and Replication for varying number of users (k=64, m=9) RAYZIT: Partitioning and Replication for varying number of users (k=64, m=9) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) 1000 1000 1000 1000 H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire 100 100 100 100 10 10 10 10 1 1 1 1 0.1 0.1 0.1 0.1 0.01 0.01 0.01 0.01 104 105 106 104 105 106 104 105 106 2*104 Number of online users (n) Number of online users (n) Number of online users (n) Number of online users (n) Fig. 9. Partitioning and Replication step response time with increasing number of users. RANDOM: Refinement for varying number of users (k=64, m=9) OLDENBURG: Refinement for varying number of users (k=64, m=9) GEOLIFE: Refinement for varying number of users (k=64, m=9) RAYZIT: Refinement for varying number of users (k=64, m=9) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) Response time in log-scale (sec) 10000 10000 10000 10000 H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire 1000 1000 1000 1000 100 100 100 100 Out Of Memory Out Of Memory Out Of Memory 10 10 10 10 1 1 1 1 0.1 0.1 0.1 0.1 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 104 Number of online users (n) 105 106 2*104 Number of online users (n) Fig. 10. Refinement step response time with increasing number of users and for each available dataset. Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Replication Factor (f) GEOLIFE: Replication factor for varying number of users (k=64, m=9) RANDOM: Replication factor for varying number of users (k=64, m=9) OLDENBURG: Replication factor for varying number of users (k=64, m=9) RAYZIT: Replication factor for varying number of users (k=64, m=9) 11 11 11 11 H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire H-BNLJ H-BRJ PGBJ Spitfire Replication factor (f) Replication factor (f) Replication factor (f) Replication factor (f) 9 9 9 9 7 7 7 7 5 5 5 5 3 3 3 3 1 1 1 1 104 105 106 104 105 106 104 105 106 2*104 Number of Users (n) Number of Users (n) Number of Users (n) Number of Users (n) Plot for most skewed dataset. Others have similar results fSpitfire outperforms (optimal value for f is 1) Fig. 11. Replication factor f with increasing number of users. The optimal value for f is 1, signifying no replication. fSpitfiredrops as n increases (scalability) fH-BNLJand fH-BRJ= 2m0.5, independent of n Replication factor offers clear comparison independent of implementation 31 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017 TABLE 3 up the values shown in Figures 9 and 10 and comparing to the total response time in Figure 8, it becomes obvious that most of H-BRJ s response time is spent in communication, which is indicated theoretically by its communication complexity of O( mn) shown in Table 2. We focus on comparing only Spitfire and PGBJ for the rest of our evaluation. For 104online users, Spitfire outperforms all algorithms by at least 85% for all dataset, whereas for 105Spitfire outperforms PGBJ, by 75%, 75% and 53% for the Random, Oldenburg and Geolife datasets, respectively. Values used in our experiments Section 5.5 5.6 5.7 5.8 5.9 Dataset ALL Random ALL Random, Rayzit Random n k 64 64 64 m 9 9 9 9 [104, 105, 106] 106 106(104Rayzit) 106(104Rayzit) 106 4i, 1 i 5 64 [3, 6, 9] 5.5 Varying Number of Users (n) In this experimental series, we increase the workload of the system by growing the number of online users (n) exponen- tially and measure the response time and replication factor of the algorithms under evaluation. Total Computation: In Figure 8, we measure the total re- sponse time for all algorithms, datasets and workloads. We can clearly see that Spitfire outperforms all other algorithms in every case. It is also evident that H-BNLJ and H-BRJ do not scale. H-BRJ achieves the worst time for 106users. Adding Spitfire and PGBJ are the only algorithms that scale. For a million online users (n=106), Spitfire and PGBJ are the fastest algorithms, but Spitfire still outperforms PGBJ by 67%, 75%, 14% for the Random, Oldenburg and Geolife datasets, respec- tively. The small percentage noted for the Geolife dataset is attributed to the fact that this dataset is highly skewed (as observed in Figure 7), and that PGBJ achieves better load balancing (as shown later in Section 5.7), which in turn leads to a faster refinement step.
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Presentation Outline Introduction AkNN Query Processing IEEE TKDE 16 Rayzit Crowd Messenger Mobisocial @ IEEE MDM 15 Future Challenges 32 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Rayzit Application A user can post a new Rayz (text, audio, video shown as attachment). To minimize spamming, each user has a powerbar that decreases on every action: Rayz, reply, re-rayz, power+/- When empty no more actions are possible until it gradually reloads. To reload faster, we provide the incentive to provide useful answers that will be starred by others. A message can be bounded to a certain distance (kNN is default) 0.5, 5, 50, 500, 5000 km 33 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Example Conversations General Advice & Crowd Casting 34 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Example Conversations Philosophical & Location-based Questions 35 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Example Conversations Feelings Expression & Taboo Questions 36 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Example Conversations Inappropriate Messages (before installation of report filter) 37 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 More Topics on Rayzit Topics: Location, Surveys, Thoughs, Feelings Most answered rayz (responses) Rain! Lovely. (228) Any good PGs near Avanshi RoadCBE? (142) Which windows phone do you have? (119) anyone around..??? (94) Share a secret .. (90) Rayzit: What is the next feature you would like to see? (81) I love.... (continue) (58) Where are you from? I want to test Rayzit location. (52) Where to dine in Coimbatore if you want to have a dinner peacefully and by yourself? (40) 38 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Analyzing the Rayzit Network We used both Flurry App Analytics and Analytic queries on our NoSQL database Interval of Analysis: Oct. 13 Mar. 15 32,762 Sessions 5,062 New Users 1.7 mins Median Session Length Conclusion: App more popular in Asia, India particularly because of large Microsoft community and Microsoft Promotion) 39 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Average Reply Time Online users 28% Offline users Sporadic users Rest 28% of replies were recorded within 1 minute. Crowd Volume creates quick response possibilities Nearby users respond quickly (more interested in the discussion). 40 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Average and Maximum Distance (Rayz, Reply) Hypothesis: Closer Geographic Users means More Replies distance of rayz to replies ([1-50] replies) = 15km (max) >50 replies At 10km (max) >100 replies at 8 meters! Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017 People in classroom, event? 41
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Presentation Outline Introduction AkNN Query Processing IEEE TKDE 16 Rayzit Crowd Messenger Mobisocial @ IEEE MDM 15 Future Challenges 42 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Future Challenges Tools to handle lack of accountability have shown to encourage negative discourse, including personal attacks, threats or rumor spreading. Introduce more automated and crowd management techniques (collaborative filtering): More intelligent Report Management Classify rayz threads to categories More detailed data analysis (interaction graphs, rerayz path length, community detection, chat groups vs. location, new vs. old users, . 43 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Future Challenges Shallow syntax in messages: 2m, 2morrow, tmw, tomoz, tomz,all refer to tomorrow. Off-the-shelf Part-of-Speech (POS) taggers (e.g., Stanford NLP or MPI AIDA) don t work adequately on these messages. Data contains many infrequent entity types (e.g., physicist) and capitalization (used for recognizing named entities, e.g., AlbertEinstein) is not there. Might need to exploit spatial and temporal dimensions in data to understand what something refers to. 44 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Future Challenges Microblog NER (T-POS, T-NER) Temporal Tagging (Heideltime) Quantity Tagging (QKB) Knowledge Base (YAGO, Freebase) { RQ1, RQ2, RQ3} 45 Demetris Zeinalipour, Paris Descartes Univ., France, April 12, 2017
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010 Building All k Nearest Neigbhor Social Communities Demetris Zeinalipour Thank You! Questions? Max Planck Institute for Informatics, Germany & Department of Computer Science, University of Cyprus, Cyprus http://www.cs.ucy.ac.cy/~dzeina/ dzeina@cs.ucy.ac.cy Paris Descartes University Seminar Series on Data Analytics in collaboration with the diNo group, April 12, 2017
