Graph Search, Why Bother?
Graph Search, Why Bother?
Social Networks are the New Media G HNO 粤g Individual Social networks are graphs The nodes are the people and groups The links/edges show relationships or flows between the nodes
Social Networks are the New Media 12 Social networks are graphs • The nodes are the people and groups • The links/edges show relationships or flows between the nodes
Social Networks are the New Media 基于出租车的城市计算案例 最快行车路线设计 反映出租车轨迹 数据分布的热度图 事件检测和预算 验证和发现城市规划可能存在的问题 打车推荐系统 端盐 金庸“被逝世” Social networks are becoming an im portant way to get information in every day life
Social Networks are the New Media 13 Social networks are becoming an important way to get information in everyday life！
The need for a Social Search Engine Graph Searching rch YOon File systems Databases World wide web Social Networks File systems-1960's: very simple search functionalities Databases-mid 1960S: SQL language World wide Web-1990'S: keyword search engines Social networks- late 1990s. Facebook launched"graph search"on 16th January, 2013 Assault on Google, Yelp, and LinkedIn with new graph search Yelp was down more than 7% Graph search is a new paradigm for social computing
The need for a Social Search Engine 14 • File systems - 1960’s： very simple search functionalities • Databases - mid 1960’s：SQL language • World Wide Web - 1990’s：keyword search engines • Social networks - late 1990’s: File systems Databases World Wide Web Graph search is a new paradigm for social computing! Social Networks Facebook launched “graph search” on 16th January, 2013 Assault on Google, Yelp, and LinkedIn with new graph search; Yelp was down more than 7%
Graph Search Vs RDBMS [13 person identifier index person name index friend. person_a index Query: Find the name of all of identifier name erson_a person_b Alberto Pepe's friends Alberto Pepe 1234 111 234 …1 Step 1: The person name index-> the identifier of Alberto Pepe. [o(log2n) Step 2: The friend. person index - k friend identifiers [O(og2×):X<m Step 3: The k friend identifiers - k friend names [o(k log2n
Graph Search vs. RDBMS [13] 15 Query： Find the name of all of Alberto Pepe's friends. Step 1: The person.name index -> the identifier of Alberto Pepe. [O(log2n)] Step 2: The friend.person index -> k friend identifiers. [O(log2x) : x<<m] Step 3: The k friend identifiers -> k friend names. [O(k log2n)]