（物聯(lián)網(wǎng)搜索）課件

物聯(lián)網(wǎng)搜索2022/12/101物聯(lián)網(wǎng)搜索2022/12/81INTRODUCTIONTOTHEReal-TimeSearchfor

Real-WorldEntities2022/12/102INTRODUCTIONTOTHEReal-TimeSubiquitouscomputingMarkWeiser(1991)提出了普適運(yùn)算thefatherofubiquitouscomputing(1988)achiefscientistatXeroxPARC

(施樂帕克研究中心)intheUnitedStates2022/12/103ubiquitouscomputingMarkWeiseubiquitouscomputing

普適運(yùn)算并非將基礎(chǔ)技術(shù)全盤翻新，普適運(yùn)算技術(shù)運(yùn)用了無線電網(wǎng)絡(luò)的科技，讓人們?cè)诓皇軙r(shí)空限制的環(huán)境下享用資訊透過整合式無縫科技技術(shù)，讓人們使用起來更便利，省時(shí)。2022/12/104ubiquitouscomputing普適運(yùn)1面向物聯(lián)網(wǎng)的搜索服務(wù)描述2022/12/1051面向物聯(lián)網(wǎng)的2022/12/85基本要素及實(shí)現(xiàn)過程特點(diǎn)及面臨的挑戰(zhàn)2022/12/106基本要素及實(shí)現(xiàn)過程2022/12/86物理世界實(shí)體2022/12/107物理世界實(shí)體2022/12/87物理世界實(shí)體與實(shí)體相連感知其狀態(tài)的傳感器用戶提出的對(duì)實(shí)體狀態(tài)或指定狀態(tài)實(shí)體的查詢接收查詢、處理并返回查詢狀態(tài)或與查詢相符實(shí)體的搜索引擎基本要素及實(shí)現(xiàn)過程2022/12/108物理世界實(shí)體基本要素及實(shí)現(xiàn)過程2022/12/88面向物聯(lián)網(wǎng)的搜索示意圖2022/12/109面向物聯(lián)網(wǎng)的搜索示意圖2022/12/89特點(diǎn)及面臨的挑戰(zhàn)VS2022/12/1010特點(diǎn)及面臨的挑戰(zhàn)VS2022/12/810搜索對(duì)象的比較由傳感器自動(dòng)生成的快速變化的結(jié)構(gòu)化內(nèi)容2022/12/1011搜索對(duì)象的比較由傳感器自動(dòng)生成的快速變化2022/12/81搜索對(duì)象的比較主要指因特網(wǎng)上的網(wǎng)頁(yè)及PDF、DOC等由人工輸入、靜態(tài)或緩慢變化的非結(jié)構(gòu)化內(nèi)容2022/12/1012搜索對(duì)象的比較主要指因特網(wǎng)上的網(wǎng)頁(yè)及PDF、2022/12/面向物聯(lián)網(wǎng)的搜索特點(diǎn)及

面臨的挑戰(zhàn)2022/12/1013面向物聯(lián)網(wǎng)的搜索特點(diǎn)及

面臨的挑戰(zhàn)2022/12/813搜索內(nèi)容的時(shí)空性強(qiáng)龐大的數(shù)據(jù)量數(shù)據(jù)的高度動(dòng)態(tài)性傳感器節(jié)點(diǎn)的資源受限傳感器節(jié)點(diǎn)的移動(dòng)性安全和隱私問題2022/12/1014搜索內(nèi)容的時(shí)空性強(qiáng)2022/12/814搜索內(nèi)容的時(shí)空性強(qiáng)只需在指定區(qū)域查找實(shí)體需要檢索的信息具有高度的時(shí)效性，只有實(shí)時(shí)或預(yù)測(cè)將來的數(shù)據(jù)才有意義安靜的餐廳不擁塞的道路2022/12/1015搜索內(nèi)容的時(shí)空性強(qiáng)只需在指定區(qū)域查找實(shí)體安靜的餐廳不擁塞的道龐大的數(shù)據(jù)量隨著物聯(lián)網(wǎng)的廣泛推廣，物聯(lián)網(wǎng)搜索信息量與現(xiàn)有的網(wǎng)頁(yè)數(shù)量相比，將會(huì)發(fā)生數(shù)量級(jí)的飛躍。2022/12/1016龐大的數(shù)據(jù)量隨著物聯(lián)網(wǎng)的廣泛推廣，物聯(lián)網(wǎng)搜索信息量與現(xiàn)有的網(wǎng)數(shù)據(jù)的高度動(dòng)態(tài)性實(shí)體特征數(shù)據(jù)每分每秒都在變化，傳感器實(shí)時(shí)對(duì)這些高度動(dòng)態(tài)變化的信息進(jìn)行檢測(cè)存儲(chǔ)，針對(duì)網(wǎng)頁(yè)設(shè)計(jì)的索引方法，幾乎無法適用，因此，創(chuàng)建一種對(duì)實(shí)時(shí)信息創(chuàng)建索引的方法很重要2022/12/1017數(shù)據(jù)的高度動(dòng)態(tài)性實(shí)體特征數(shù)據(jù)每分每秒都在變化，傳感器實(shí)時(shí)對(duì)這數(shù)據(jù)的高度動(dòng)態(tài)性2022/12/1018數(shù)據(jù)的高度動(dòng)態(tài)性2022/12/818傳感器節(jié)點(diǎn)的資源受限傳統(tǒng)的網(wǎng)頁(yè)搜索內(nèi)容均是由資源豐富的PC終端等輸入，內(nèi)容生成及發(fā)送次數(shù)一般不受限制，而傳感器終端因?yàn)槟芰渴芟?，?jié)點(diǎn)的頻繁通信是不允許的。2022/12/1019傳感器節(jié)點(diǎn)的資源受限傳統(tǒng)的網(wǎng)頁(yè)搜索內(nèi)容均是由資源豐富的PC終傳感器移動(dòng)性受限附著在實(shí)體之上的傳感器，會(huì)隨著實(shí)體的移動(dòng)而移動(dòng)，這使在網(wǎng)絡(luò)中始終維持注冊(cè)最新信息成為一個(gè)很大的挑戰(zhàn)。2022/12/1020傳感器移動(dòng)性受限附著在實(shí)體之上的傳感器，會(huì)隨著實(shí)體的移動(dòng)而移安全和隱私問題人們可以不選擇使用網(wǎng)頁(yè)、或不頻繁更新網(wǎng)頁(yè)或設(shè)置網(wǎng)頁(yè)不可搜索，但是，當(dāng)傳感器成為每個(gè)實(shí)物如一雙鞋的附屬物時(shí)，用戶可能都不知道它們的存在。2022/12/1021安全和隱私問題人們可以不選擇使用網(wǎng)頁(yè)、或不頻繁更新網(wǎng)頁(yè)或設(shè)置安全和隱私問題2022/12/1022安全和隱私問題2022/12/822面向物聯(lián)網(wǎng)搜索的

基本策略22022/12/1023面向物聯(lián)網(wǎng)搜索的

基本策略22022/12/823主動(dòng)發(fā)送與被動(dòng)索取信息發(fā)布/訂閱使用中介節(jié)點(diǎn)倒排索引壓縮技術(shù)建立模型實(shí)體評(píng)分與排名Top-k查詢2022/12/1024主動(dòng)發(fā)送與被動(dòng)索取2022/12/824主動(dòng)發(fā)送與被動(dòng)索取

pullandpush在分布式環(huán)境中，實(shí)體搜索功能的實(shí)現(xiàn)需要描述實(shí)體狀態(tài)的數(shù)據(jù)存儲(chǔ)在某位置等待用戶的查詢。有如下三種方式2022/12/1025主動(dòng)發(fā)送與被動(dòng)索取

pullandpush在分布式環(huán)境主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush：實(shí)體主動(dòng)將數(shù)據(jù)發(fā)送到用戶方，將數(shù)據(jù)存儲(chǔ)在用戶系統(tǒng)中，查詢功能在用戶本地實(shí)現(xiàn)。2022/12/1026主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush：實(shí)主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPull：實(shí)體本地存儲(chǔ)數(shù)據(jù)，查詢時(shí)用戶向?qū)嶓w發(fā)送查詢語(yǔ)句后將數(shù)據(jù)取回2022/12/1027主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPull：實(shí)主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush和Pull混合的方法：數(shù)據(jù)被發(fā)送到某一位置，用戶從該位置取回?cái)?shù)據(jù)(mediators)，并且有一些頻繁被查詢到的數(shù)據(jù)直接被Push到用戶端，而另一些很少被查詢到的數(shù)據(jù)則留在實(shí)體一端等待用戶Pull出。2022/12/1028主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush和P信息發(fā)布/訂閱

Publish/Subscribe建立實(shí)體與用戶間的明確關(guān)系對(duì)連續(xù)查詢時(shí)很有用的。例如實(shí)體數(shù)據(jù)可以僅被Push到滿足潛在匹配查詢的用戶處，或用戶查詢只對(duì)潛在匹配實(shí)體進(jìn)行Pull操作。Publish/Subscribe是當(dāng)用戶只對(duì)某些實(shí)體或數(shù)據(jù)感興趣時(shí)的常用技術(shù)，它可以只將與訂閱內(nèi)容相匹配的數(shù)據(jù)交付給用戶。2022/12/1029信息發(fā)布/訂閱

Publish/Subscribe建立實(shí)體與信息發(fā)布/訂閱

Publish/Subscribe2022/12/1030信息發(fā)布/訂閱

Publish/Subscribe2022/使用中介節(jié)點(diǎn)

(mediators)Mediators是一個(gè)邏輯上處于實(shí)體與用戶之間的概念成分，通常用來維護(hù)一個(gè)實(shí)體的聚合視圖(aggressiveview)。例如，發(fā)送到一個(gè)mediator的查詢無須Pull所有實(shí)體的數(shù)據(jù)即可實(shí)現(xiàn)。Mediator可以在集中或分散（如一個(gè)Mediator層次結(jié)構(gòu)，上級(jí)中介super-mediator具有子中介sub-mediator的聚合視圖）下實(shí)現(xiàn)。2022/12/1031使用中介節(jié)點(diǎn)

(mediators)Mediators是一個(gè)倒排索引

invertedindex維持一個(gè)實(shí)體集聚合視圖的mediator要能有效地根據(jù)查詢要求指定的某種狀態(tài)查找出對(duì)應(yīng)實(shí)體。invertedindex就是滿足這樣要求的一種數(shù)據(jù)結(jié)構(gòu)，它可以高效地從實(shí)體集中查找出生成某種數(shù)據(jù)的實(shí)體。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的存儲(chǔ)位置。2022/12/1032倒排索引

invertedindex維持一個(gè)實(shí)體集聚合視圖壓縮技術(shù)

Compression用來減少數(shù)據(jù)和查詢所需的存儲(chǔ)和通信量，如mediators通常存儲(chǔ)經(jīng)過壓縮的實(shí)體數(shù)據(jù)聚合視圖。使用無損壓縮不會(huì)對(duì)系統(tǒng)的基本操作造成影響。而使用有損壓縮則只能維持一個(gè)近似的視圖，在這種情況下，查詢結(jié)果或者為啟發(fā)式的，或者將近似視圖用在確定實(shí)體或用戶子集，以便隨后執(zhí)行Push或Pull操作獲得準(zhǔn)確結(jié)果。2022/12/1033壓縮技術(shù)

Compression用來減少數(shù)據(jù)和查詢所需的存儲(chǔ)建立模型

Models使用模型可以在沒有實(shí)際交流的情況下，推斷與用戶或?qū)嶓w有關(guān)的信息。實(shí)體集可以通過用戶模型來決定該用戶是否對(duì)某個(gè)實(shí)體感興趣，從而將數(shù)據(jù)只Push到對(duì)其感興趣的用戶處。2022/12/1034建立模型

Models使用模型可以在沒有實(shí)際交流的情況下，推建立模型

Models通常依據(jù)過去的信息來構(gòu)建模型，如關(guān)于一個(gè)實(shí)體狀態(tài)的統(tǒng)計(jì)模型可以由該實(shí)體以前的狀態(tài)來構(gòu)建。與壓縮技術(shù)一樣，基于模型的技術(shù)或?qū)е聠l(fā)式查詢剖析，或用來確定實(shí)體或用戶集，以便Push或Pull操作，最終獲得準(zhǔn)確結(jié)果。2022/12/1035建立模型

Models通常依據(jù)過去的信息來構(gòu)建模型，如關(guān)于一實(shí)體評(píng)分與排名

ScoringandRanking2022/12/1036實(shí)體評(píng)分與排名

ScoringandRanking202實(shí)體評(píng)分與排名

ScoringandRankingScoring是根據(jù)實(shí)體與查詢的相關(guān)度對(duì)實(shí)體評(píng)分，ranking根據(jù)該分?jǐn)?shù)對(duì)實(shí)體進(jìn)行排名。使用scoring和ranking有兩個(gè)目的。2022/12/1037實(shí)體評(píng)分與排名

ScoringandRankingSco實(shí)體評(píng)分與排名

ScoringandRanking給用戶提供與查詢需求最相關(guān)的實(shí)體可以據(jù)此首先對(duì)排名靠前的實(shí)體進(jìn)行Push、Pull操作等操作以提到效率。一個(gè)統(tǒng)一的評(píng)分方式是實(shí)現(xiàn)實(shí)體間直接比較的重要前提。例如，在基于關(guān)鍵詞的搜索中一般考慮關(guān)鍵詞的總頻率，高頻詞會(huì)較低頻詞給予更高的權(quán)重。2022/12/1038實(shí)體評(píng)分與排名

ScoringandRanking給用戶Top-k查詢

top-kquerytop-k查詢是指返回查詢結(jié)果返回集中K個(gè)最相關(guān)的實(shí)體，因?yàn)橐话愕牟樵儫o須將所有匹配實(shí)體都返回。有時(shí)可以不考慮所有實(shí)體而直接找到Top-k實(shí)體，這與找到所有實(shí)體然后返回其子集的蠻力方法相比可以大大提高查詢效率。2022/12/1039Top-k查詢

top-kquerytop-k查詢是指返回2022/12/10402022/12/840現(xiàn)有主要系統(tǒng)分析32022/12/1041現(xiàn)有主要系統(tǒng)分析32022/12/841SnoogleDyser2022/12/1042Snoogle2022/12/842snoogle基本思想：把對(duì)實(shí)體的文本描述以關(guān)鍵詞的形式存儲(chǔ)到傳感器節(jié)點(diǎn)中以待用戶查詢，如一本書的附屬節(jié)點(diǎn)中含有關(guān)鍵詞”書“。用戶提出由一組關(guān)鍵詞組成的Adhoc查詢后，系統(tǒng)經(jīng)過對(duì)比返回匹配列表的前K項(xiàng)，其中列表中內(nèi)容匹配度依次遞減，K由用戶指定。2022/12/1043snoogle基本思想：把對(duì)實(shí)體的文本描述以關(guān)鍵詞的形式存儲(chǔ)snoogle系統(tǒng)架構(gòu)示意圖2022/12/1044snoogle系統(tǒng)架構(gòu)示意圖2022/12/844兩級(jí)mediator結(jié)構(gòu)下層稱為索引點(diǎn)（indexpoints），每個(gè)IP維護(hù)一個(gè)一定地理范圍內(nèi)所有傳感器節(jié)點(diǎn)的聚合視圖。上層的mediator稱為關(guān)鍵索引點(diǎn)（KeyIP），它負(fù)責(zé)維護(hù)整個(gè)網(wǎng)絡(luò)的聚合視圖。2022/12/1045兩級(jí)mediator結(jié)構(gòu)下層稱為索引點(diǎn)（indexpoin搜索過程移動(dòng)節(jié)點(diǎn)的搜索由IPs間的移交協(xié)議實(shí)現(xiàn)。一般地，由IP周期性地發(fā)送信標(biāo)信息來檢測(cè)節(jié)點(diǎn)是否在其范圍內(nèi)，當(dāng)有節(jié)點(diǎn)移入或移出時(shí)更新其索引并通知KeyIP。也可以使用計(jì)時(shí)器方法，由節(jié)點(diǎn)發(fā)送保持活動(dòng)消息，同時(shí)IP維護(hù)一個(gè)計(jì)時(shí)器。若一段時(shí)間內(nèi)沒有收到節(jié)點(diǎn)的消息，IP將其從索引表中刪除，其他檢測(cè)到節(jié)點(diǎn)消息的IP將節(jié)點(diǎn)加入到索引表中。2022/12/1046搜索過程移動(dòng)節(jié)點(diǎn)的搜索由IPs間的移交協(xié)議實(shí)現(xiàn)。一般地，由I通信壓縮系統(tǒng)采用Bloomfilter方法實(shí)現(xiàn)通信壓縮，將一組關(guān)鍵詞由nbit向量表示。該方法是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。2022/12/1047通信壓縮系統(tǒng)采用Bloomfilter方法實(shí)現(xiàn)通信壓縮，將如何排序局域搜索時(shí)，查詢消息直接發(fā)到IP，IP根據(jù)其倒排索引計(jì)算出匹配傳感器的排序列表并將前K個(gè)結(jié)果返回。2022/12/1048如何排序局域搜索時(shí)，查詢消息直接發(fā)到IP，IP根據(jù)其倒排索引如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為統(tǒng)一不同IP的排序，需要把關(guān)鍵詞在一個(gè)IP包含的所有節(jié)點(diǎn)中出現(xiàn)的總頻率納入到排序算法中。2022/12/1049如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為統(tǒng)一不同IP的排序，需要把關(guān)鍵詞在一個(gè)IP包含的所有節(jié)點(diǎn)中出現(xiàn)的總頻率納入到排序算法中。2022/12/1050如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為如何排序全局搜索時(shí)：KeyIP收到查詢請(qǐng)求后，采取如下方法：向所有IPs查詢并返回當(dāng)?shù)丶?jí)別最高的傳感器節(jié)點(diǎn)，將這一列表存儲(chǔ)在全局排序表中。為獲得級(jí)別第二的節(jié)點(diǎn)，KeyIP向所有IPs發(fā)送查詢請(qǐng)求，要求僅返回分?jǐn)?shù)高于全局排序中級(jí)別第二的節(jié)點(diǎn)。將其插入到全局排序表中第二的位置，依此類推，直至獲得用戶要求的K個(gè)節(jié)點(diǎn)。最后將結(jié)果返回2022/12/1051如何排序全局搜索時(shí)：KeyIP收到查詢請(qǐng)求后，采取如下方法總結(jié)snoogle系統(tǒng)是第一個(gè)基于傳感器網(wǎng)絡(luò)的物理世界信息檢索系統(tǒng)，Bloomfilter壓縮算法，分布式Top-k查詢算法的使用減少了通信開銷，安全隱私管理保障了用戶的信息安全。2022/12/1052總結(jié)snoogle系統(tǒng)是第一個(gè)基于傳感器網(wǎng)絡(luò)的物理世界信息檢總結(jié)但是，該系統(tǒng)僅支持偽靜態(tài)元數(shù)據(jù)的搜索，KeyIP的集中性質(zhì)不適于全球搜索，而且Bloomfilter的使用會(huì)導(dǎo)致查詢結(jié)果不準(zhǔn)確，Top-k算法在減少通信開銷的同時(shí)也會(huì)產(chǎn)生大量的中間數(shù)據(jù)。2022/12/1053總結(jié)但是，該系統(tǒng)僅支持偽靜態(tài)元數(shù)據(jù)的搜索，KeyIP的集中性DyserDyser是一個(gè)針對(duì)物聯(lián)網(wǎng)的實(shí)體實(shí)時(shí)搜索引擎，它充分利用現(xiàn)有的Internet網(wǎng)絡(luò)設(shè)施，實(shí)現(xiàn)了對(duì)快速變化內(nèi)容的可伸縮式搜索。系統(tǒng)可以根據(jù)用戶指定的當(dāng)前狀態(tài)搜索實(shí)體，如可搜索一棟大廈里現(xiàn)在空閑的房間，某區(qū)域目前較安靜的地方等。2022/12/1054DyserDyser是一個(gè)針對(duì)物聯(lián)網(wǎng)的實(shí)體實(shí)時(shí)搜索引擎，它充Dyser系統(tǒng)架構(gòu)示意圖2022/12/1055Dyser系統(tǒng)架構(gòu)示意圖2022/12/855系統(tǒng)架構(gòu)介紹傳感器sensor和實(shí)體entity時(shí)模型中的兩個(gè)關(guān)鍵元素，每個(gè)傳感器和實(shí)體都與一個(gè)由網(wǎng)頁(yè)地址URL確定、通過HTTP協(xié)議訪問的Web資源對(duì)應(yīng)。所有這些Web資源又有一個(gè)HTML表示，通常稱其為傳感器頁(yè)（sensorpage）和實(shí)體頁(yè)（entitypage）。2022/12/1056系統(tǒng)架構(gòu)介紹傳感器sensor和實(shí)體entity時(shí)模型中的兩系統(tǒng)架構(gòu)介紹除了非結(jié)構(gòu)化文本，頁(yè)面中還包含一些如傳感器類型、可能讀數(shù)等結(jié)構(gòu)化信息。傳感器與實(shí)體之間是多對(duì)多的關(guān)系。圖中解析器用來處理用戶查詢、索引存儲(chǔ)傳感器和實(shí)體的索引元數(shù)據(jù)。索引器類似網(wǎng)絡(luò)蜘蛛抓取傳感器和實(shí)體網(wǎng)頁(yè)。2022/12/1057系統(tǒng)架構(gòu)介紹除了非結(jié)構(gòu)化文本，頁(yè)面中還包含一些如傳感器類型、2022/12/10582022/12/858建模及排序系統(tǒng)采用傳感器排名sensorranking方法對(duì)傳感器排序，以便進(jìn)行選擇性的搜索。排序基于預(yù)測(cè)模型實(shí)現(xiàn)，由模型返回在一特定時(shí)間傳感器讀數(shù)為指定值的概率值，該模型由傳感器或傳感器網(wǎng)關(guān)創(chuàng)建，并發(fā)布在相應(yīng)的傳感器頁(yè)上。2022/12/1059建模及排序系統(tǒng)采用傳感器排名sensorranking方法建模及排序可以根據(jù)不同場(chǎng)合選擇不同的預(yù)測(cè)模型，Dyser系統(tǒng)中提出匯總預(yù)測(cè)模型（APM）、單周期預(yù)測(cè)模型（SPPM）、多周期預(yù)測(cè)模型（MPPM）三種模型。2022/12/1060建模及排序可以根據(jù)不同場(chǎng)合選擇不同的預(yù)測(cè)模型，Dyser系統(tǒng)搜索過程搜索時(shí)，搜索引擎首先從索引表中獲得含有請(qǐng)求類型傳感器的實(shí)體，根據(jù)實(shí)體與搜索的匹配度計(jì)算出實(shí)體的匹配概率（該值為與實(shí)體相關(guān)符合匹配的傳感器的概率值和）；根據(jù)概率值由大到小對(duì)實(shí)體進(jìn)行進(jìn)行排序后從頭開始核對(duì)實(shí)體的狀態(tài)與要求值是否相同。當(dāng)一個(gè)實(shí)體所有狀態(tài)都相符時(shí)，輸出實(shí)體并繼續(xù)審閱下一個(gè)實(shí)體，重復(fù)操作，直至返回足夠的匹配實(shí)體。2022/12/1061搜索過程搜索時(shí)，搜索引擎首先從索引表中獲得含有請(qǐng)求類型傳感器總結(jié)Dyser系統(tǒng)將優(yōu)化搜索引擎性能的傳感器排名與優(yōu)化用戶滿意度的相關(guān)性排名相結(jié)合，在內(nèi)部搜索過程中使用傳感器排名，顯示結(jié)果給用戶時(shí)使用相關(guān)性排名。2022/12/1062總結(jié)Dyser系統(tǒng)將優(yōu)化搜索引擎性能的傳感器排名與優(yōu)化用戶滿總結(jié)系統(tǒng)的不足在于，當(dāng)傳感器的數(shù)量很龐大時(shí)，建立模型需要較大的開銷，預(yù)測(cè)模型的使用在提高效率的同時(shí)可能使結(jié)果準(zhǔn)確率下降。系統(tǒng)沒有考慮安全隱私問題，傳感器數(shù)據(jù)及對(duì)應(yīng)網(wǎng)頁(yè)可被任何人檢索。2022/12/1063總結(jié)系統(tǒng)的不足在于，當(dāng)傳感器的數(shù)量很龐大時(shí)，建立模型需要較大2022/12/10642022/12/864物聯(lián)網(wǎng)搜索期待你的加入2022/12/1065物聯(lián)網(wǎng)搜索期待你的加入2022/12/865謝謝大家2022/12/1066謝謝大家2022/12/866物聯(lián)網(wǎng)搜索2022/12/1067物聯(lián)網(wǎng)搜索2022/12/81INTRODUCTIONTOTHEReal-TimeSearchfor

Real-WorldEntities2022/12/1068INTRODUCTIONTOTHEReal-TimeSubiquitouscomputingMarkWeiser(1991)提出了普適運(yùn)算thefatherofubiquitouscomputing(1988)achiefscientistatXeroxPARC

(施樂帕克研究中心)intheUnitedStates2022/12/1069ubiquitouscomputingMarkWeiseubiquitouscomputing

普適運(yùn)算并非將基礎(chǔ)技術(shù)全盤翻新，普適運(yùn)算技術(shù)運(yùn)用了無線電網(wǎng)絡(luò)的科技，讓人們?cè)诓皇軙r(shí)空限制的環(huán)境下享用資訊透過整合式無縫科技技術(shù)，讓人們使用起來更便利，省時(shí)。2022/12/1070ubiquitouscomputing普適運(yùn)1面向物聯(lián)網(wǎng)的搜索服務(wù)描述2022/12/10711面向物聯(lián)網(wǎng)的2022/12/85基本要素及實(shí)現(xiàn)過程特點(diǎn)及面臨的挑戰(zhàn)2022/12/1072基本要素及實(shí)現(xiàn)過程2022/12/86物理世界實(shí)體2022/12/1073物理世界實(shí)體2022/12/87物理世界實(shí)體與實(shí)體相連感知其狀態(tài)的傳感器用戶提出的對(duì)實(shí)體狀態(tài)或指定狀態(tài)實(shí)體的查詢接收查詢、處理并返回查詢狀態(tài)或與查詢相符實(shí)體的搜索引擎基本要素及實(shí)現(xiàn)過程2022/12/1074物理世界實(shí)體基本要素及實(shí)現(xiàn)過程2022/12/88面向物聯(lián)網(wǎng)的搜索示意圖2022/12/1075面向物聯(lián)網(wǎng)的搜索示意圖2022/12/89特點(diǎn)及面臨的挑戰(zhàn)VS2022/12/1076特點(diǎn)及面臨的挑戰(zhàn)VS2022/12/810搜索對(duì)象的比較由傳感器自動(dòng)生成的快速變化的結(jié)構(gòu)化內(nèi)容2022/12/1077搜索對(duì)象的比較由傳感器自動(dòng)生成的快速變化2022/12/81搜索對(duì)象的比較主要指因特網(wǎng)上的網(wǎng)頁(yè)及PDF、DOC等由人工輸入、靜態(tài)或緩慢變化的非結(jié)構(gòu)化內(nèi)容2022/12/1078搜索對(duì)象的比較主要指因特網(wǎng)上的網(wǎng)頁(yè)及PDF、2022/12/面向物聯(lián)網(wǎng)的搜索特點(diǎn)及

面臨的挑戰(zhàn)2022/12/1079面向物聯(lián)網(wǎng)的搜索特點(diǎn)及

面臨的挑戰(zhàn)2022/12/813搜索內(nèi)容的時(shí)空性強(qiáng)龐大的數(shù)據(jù)量數(shù)據(jù)的高度動(dòng)態(tài)性傳感器節(jié)點(diǎn)的資源受限傳感器節(jié)點(diǎn)的移動(dòng)性安全和隱私問題2022/12/1080搜索內(nèi)容的時(shí)空性強(qiáng)2022/12/814搜索內(nèi)容的時(shí)空性強(qiáng)只需在指定區(qū)域查找實(shí)體需要檢索的信息具有高度的時(shí)效性，只有實(shí)時(shí)或預(yù)測(cè)將來的數(shù)據(jù)才有意義安靜的餐廳不擁塞的道路2022/12/1081搜索內(nèi)容的時(shí)空性強(qiáng)只需在指定區(qū)域查找實(shí)體安靜的餐廳不擁塞的道龐大的數(shù)據(jù)量隨著物聯(lián)網(wǎng)的廣泛推廣，物聯(lián)網(wǎng)搜索信息量與現(xiàn)有的網(wǎng)頁(yè)數(shù)量相比，將會(huì)發(fā)生數(shù)量級(jí)的飛躍。2022/12/1082龐大的數(shù)據(jù)量隨著物聯(lián)網(wǎng)的廣泛推廣，物聯(lián)網(wǎng)搜索信息量與現(xiàn)有的網(wǎng)數(shù)據(jù)的高度動(dòng)態(tài)性實(shí)體特征數(shù)據(jù)每分每秒都在變化，傳感器實(shí)時(shí)對(duì)這些高度動(dòng)態(tài)變化的信息進(jìn)行檢測(cè)存儲(chǔ)，針對(duì)網(wǎng)頁(yè)設(shè)計(jì)的索引方法，幾乎無法適用，因此，創(chuàng)建一種對(duì)實(shí)時(shí)信息創(chuàng)建索引的方法很重要2022/12/1083數(shù)據(jù)的高度動(dòng)態(tài)性實(shí)體特征數(shù)據(jù)每分每秒都在變化，傳感器實(shí)時(shí)對(duì)這數(shù)據(jù)的高度動(dòng)態(tài)性2022/12/1084數(shù)據(jù)的高度動(dòng)態(tài)性2022/12/818傳感器節(jié)點(diǎn)的資源受限傳統(tǒng)的網(wǎng)頁(yè)搜索內(nèi)容均是由資源豐富的PC終端等輸入，內(nèi)容生成及發(fā)送次數(shù)一般不受限制，而傳感器終端因?yàn)槟芰渴芟蓿?jié)點(diǎn)的頻繁通信是不允許的。2022/12/1085傳感器節(jié)點(diǎn)的資源受限傳統(tǒng)的網(wǎng)頁(yè)搜索內(nèi)容均是由資源豐富的PC終傳感器移動(dòng)性受限附著在實(shí)體之上的傳感器，會(huì)隨著實(shí)體的移動(dòng)而移動(dòng)，這使在網(wǎng)絡(luò)中始終維持注冊(cè)最新信息成為一個(gè)很大的挑戰(zhàn)。2022/12/1086傳感器移動(dòng)性受限附著在實(shí)體之上的傳感器，會(huì)隨著實(shí)體的移動(dòng)而移安全和隱私問題人們可以不選擇使用網(wǎng)頁(yè)、或不頻繁更新網(wǎng)頁(yè)或設(shè)置網(wǎng)頁(yè)不可搜索，但是，當(dāng)傳感器成為每個(gè)實(shí)物如一雙鞋的附屬物時(shí)，用戶可能都不知道它們的存在。2022/12/1087安全和隱私問題人們可以不選擇使用網(wǎng)頁(yè)、或不頻繁更新網(wǎng)頁(yè)或設(shè)置安全和隱私問題2022/12/1088安全和隱私問題2022/12/822面向物聯(lián)網(wǎng)搜索的

基本策略22022/12/1089面向物聯(lián)網(wǎng)搜索的

基本策略22022/12/823主動(dòng)發(fā)送與被動(dòng)索取信息發(fā)布/訂閱使用中介節(jié)點(diǎn)倒排索引壓縮技術(shù)建立模型實(shí)體評(píng)分與排名Top-k查詢2022/12/1090主動(dòng)發(fā)送與被動(dòng)索取2022/12/824主動(dòng)發(fā)送與被動(dòng)索取

pullandpush在分布式環(huán)境中，實(shí)體搜索功能的實(shí)現(xiàn)需要描述實(shí)體狀態(tài)的數(shù)據(jù)存儲(chǔ)在某位置等待用戶的查詢。有如下三種方式2022/12/1091主動(dòng)發(fā)送與被動(dòng)索取

pullandpush在分布式環(huán)境主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush：實(shí)體主動(dòng)將數(shù)據(jù)發(fā)送到用戶方，將數(shù)據(jù)存儲(chǔ)在用戶系統(tǒng)中，查詢功能在用戶本地實(shí)現(xiàn)。2022/12/1092主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush：實(shí)主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPull：實(shí)體本地存儲(chǔ)數(shù)據(jù)，查詢時(shí)用戶向?qū)嶓w發(fā)送查詢語(yǔ)句后將數(shù)據(jù)取回2022/12/1093主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPull：實(shí)主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush和Pull混合的方法：數(shù)據(jù)被發(fā)送到某一位置，用戶從該位置取回?cái)?shù)據(jù)(mediators)，并且有一些頻繁被查詢到的數(shù)據(jù)直接被Push到用戶端，而另一些很少被查詢到的數(shù)據(jù)則留在實(shí)體一端等待用戶Pull出。2022/12/1094主動(dòng)發(fā)送與被動(dòng)索取

pullandpushPush和P信息發(fā)布/訂閱

Publish/Subscribe建立實(shí)體與用戶間的明確關(guān)系對(duì)連續(xù)查詢時(shí)很有用的。例如實(shí)體數(shù)據(jù)可以僅被Push到滿足潛在匹配查詢的用戶處，或用戶查詢只對(duì)潛在匹配實(shí)體進(jìn)行Pull操作。Publish/Subscribe是當(dāng)用戶只對(duì)某些實(shí)體或數(shù)據(jù)感興趣時(shí)的常用技術(shù)，它可以只將與訂閱內(nèi)容相匹配的數(shù)據(jù)交付給用戶。2022/12/1095信息發(fā)布/訂閱

Publish/Subscribe建立實(shí)體與信息發(fā)布/訂閱

Publish/Subscribe2022/12/1096信息發(fā)布/訂閱

Publish/Subscribe2022/使用中介節(jié)點(diǎn)

(mediators)Mediators是一個(gè)邏輯上處于實(shí)體與用戶之間的概念成分，通常用來維護(hù)一個(gè)實(shí)體的聚合視圖(aggressiveview)。例如，發(fā)送到一個(gè)mediator的查詢無須Pull所有實(shí)體的數(shù)據(jù)即可實(shí)現(xiàn)。Mediator可以在集中或分散（如一個(gè)Mediator層次結(jié)構(gòu)，上級(jí)中介super-mediator具有子中介sub-mediator的聚合視圖）下實(shí)現(xiàn)。2022/12/1097使用中介節(jié)點(diǎn)

(mediators)Mediators是一個(gè)倒排索引

invertedindex維持一個(gè)實(shí)體集聚合視圖的mediator要能有效地根據(jù)查詢要求指定的某種狀態(tài)查找出對(duì)應(yīng)實(shí)體。invertedindex就是滿足這樣要求的一種數(shù)據(jù)結(jié)構(gòu)，它可以高效地從實(shí)體集中查找出生成某種數(shù)據(jù)的實(shí)體。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的存儲(chǔ)位置。2022/12/1098倒排索引

invertedindex維持一個(gè)實(shí)體集聚合視圖壓縮技術(shù)

Compression用來減少數(shù)據(jù)和查詢所需的存儲(chǔ)和通信量，如mediators通常存儲(chǔ)經(jīng)過壓縮的實(shí)體數(shù)據(jù)聚合視圖。使用無損壓縮不會(huì)對(duì)系統(tǒng)的基本操作造成影響。而使用有損壓縮則只能維持一個(gè)近似的視圖，在這種情況下，查詢結(jié)果或者為啟發(fā)式的，或者將近似視圖用在確定實(shí)體或用戶子集，以便隨后執(zhí)行Push或Pull操作獲得準(zhǔn)確結(jié)果。2022/12/1099壓縮技術(shù)

Compression用來減少數(shù)據(jù)和查詢所需的存儲(chǔ)建立模型

Models使用模型可以在沒有實(shí)際交流的情況下，推斷與用戶或?qū)嶓w有關(guān)的信息。實(shí)體集可以通過用戶模型來決定該用戶是否對(duì)某個(gè)實(shí)體感興趣，從而將數(shù)據(jù)只Push到對(duì)其感興趣的用戶處。2022/12/10100建立模型

Models使用模型可以在沒有實(shí)際交流的情況下，推建立模型

Models通常依據(jù)過去的信息來構(gòu)建模型，如關(guān)于一個(gè)實(shí)體狀態(tài)的統(tǒng)計(jì)模型可以由該實(shí)體以前的狀態(tài)來構(gòu)建。與壓縮技術(shù)一樣，基于模型的技術(shù)或?qū)е聠l(fā)式查詢剖析，或用來確定實(shí)體或用戶集，以便Push或Pull操作，最終獲得準(zhǔn)確結(jié)果。2022/12/10101建立模型

Models通常依據(jù)過去的信息來構(gòu)建模型，如關(guān)于一實(shí)體評(píng)分與排名

ScoringandRanking2022/12/10102實(shí)體評(píng)分與排名

ScoringandRanking202實(shí)體評(píng)分與排名

ScoringandRankingScoring是根據(jù)實(shí)體與查詢的相關(guān)度對(duì)實(shí)體評(píng)分，ranking根據(jù)該分?jǐn)?shù)對(duì)實(shí)體進(jìn)行排名。使用scoring和ranking有兩個(gè)目的。2022/12/10103實(shí)體評(píng)分與排名

ScoringandRankingSco實(shí)體評(píng)分與排名

ScoringandRanking給用戶提供與查詢需求最相關(guān)的實(shí)體可以據(jù)此首先對(duì)排名靠前的實(shí)體進(jìn)行Push、Pull操作等操作以提到效率。一個(gè)統(tǒng)一的評(píng)分方式是實(shí)現(xiàn)實(shí)體間直接比較的重要前提。例如，在基于關(guān)鍵詞的搜索中一般考慮關(guān)鍵詞的總頻率，高頻詞會(huì)較低頻詞給予更高的權(quán)重。2022/12/10104實(shí)體評(píng)分與排名

ScoringandRanking給用戶Top-k查詢

top-kquerytop-k查詢是指返回查詢結(jié)果返回集中K個(gè)最相關(guān)的實(shí)體，因?yàn)橐话愕牟樵儫o須將所有匹配實(shí)體都返回。有時(shí)可以不考慮所有實(shí)體而直接找到Top-k實(shí)體，這與找到所有實(shí)體然后返回其子集的蠻力方法相比可以大大提高查詢效率。2022/12/10105Top-k查詢

top-kquerytop-k查詢是指返回2022/12/101062022/12/840現(xiàn)有主要系統(tǒng)分析32022/12/10107現(xiàn)有主要系統(tǒng)分析32022/12/841SnoogleDyser2022/12/10108Snoogle2022/12/842snoogle基本思想：把對(duì)實(shí)體的文本描述以關(guān)鍵詞的形式存儲(chǔ)到傳感器節(jié)點(diǎn)中以待用戶查詢，如一本書的附屬節(jié)點(diǎn)中含有關(guān)鍵詞”書“。用戶提出由一組關(guān)鍵詞組成的Adhoc查詢后，系統(tǒng)經(jīng)過對(duì)比返回匹配列表的前K項(xiàng)，其中列表中內(nèi)容匹配度依次遞減，K由用戶指定。2022/12/10109snoogle基本思想：把對(duì)實(shí)體的文本描述以關(guān)鍵詞的形式存儲(chǔ)snoogle系統(tǒng)架構(gòu)示意圖2022/12/10110snoogle系統(tǒng)架構(gòu)示意圖2022/12/844兩級(jí)mediator結(jié)構(gòu)下層稱為索引點(diǎn)（indexpoints），每個(gè)IP維護(hù)一個(gè)一定地理范圍內(nèi)所有傳感器節(jié)點(diǎn)的聚合視圖。上層的mediator稱為關(guān)鍵索引點(diǎn)（KeyIP），它負(fù)責(zé)維護(hù)整個(gè)網(wǎng)絡(luò)的聚合視圖。2022/12/10111兩級(jí)mediator結(jié)構(gòu)下層稱為索引點(diǎn)（indexpoin搜索過程移動(dòng)節(jié)點(diǎn)的搜索由IPs間的移交協(xié)議實(shí)現(xiàn)。一般地，由IP周期性地發(fā)送信標(biāo)信息來檢測(cè)節(jié)點(diǎn)是否在其范圍內(nèi)，當(dāng)有節(jié)點(diǎn)移入或移出時(shí)更新其索引并通知KeyIP。也可以使用計(jì)時(shí)器方法，由節(jié)點(diǎn)發(fā)送保持活動(dòng)消息，同時(shí)IP維護(hù)一個(gè)計(jì)時(shí)器。若一段時(shí)間內(nèi)沒有收到節(jié)點(diǎn)的消息，IP將其從索引表中刪除，其他檢測(cè)到節(jié)點(diǎn)消息的IP將節(jié)點(diǎn)加入到索引表中。2022/12/10112搜索過程移動(dòng)節(jié)點(diǎn)的搜索由IPs間的移交協(xié)議實(shí)現(xiàn)。一般地，由I通信壓縮系統(tǒng)采用Bloomfilter方法實(shí)現(xiàn)通信壓縮，將一組關(guān)鍵詞由nbit向量表示。該方法是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。2022/12/10113通信壓縮系統(tǒng)采用Bloomfilter方法實(shí)現(xiàn)通信壓縮，將如何排序局域搜索時(shí)，查詢消息直接發(fā)到IP，IP根據(jù)其倒排索引計(jì)算出匹配傳感器的排序列表并將前K個(gè)結(jié)果返回。2022/12/10114如何排序局域搜索時(shí)，查詢消息直接發(fā)到IP，IP根據(jù)其倒排索引如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為統(tǒng)一不同IP的排序，需要把關(guān)鍵詞在一個(gè)IP包含的所有節(jié)點(diǎn)中出現(xiàn)的總頻率納入到排序算法中。2022/12/10115如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為統(tǒng)一不同IP的排序，需要把關(guān)鍵詞在一個(gè)IP包含的所有節(jié)點(diǎn)中出現(xiàn)的總頻率納入到排序算法中。2022/12/10116如何排序查詢時(shí)，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對(duì)傳感器進(jìn)行排序，為如何排序全局搜索時(shí)：KeyIP收到查詢請(qǐng)求后，采取如下方法：向所有IPs查詢并返回當(dāng)?shù)丶?jí)別最高的傳感器節(jié)點(diǎn)，將這一列表存儲(chǔ)在全局排序表中。為獲得級(jí)別第二的節(jié)點(diǎn)，KeyIP向所有IPs發(fā)送查詢請(qǐng)求，要求僅返回分?jǐn)?shù)高于全局排序中級(jí)別第二的節(jié)點(diǎn)。將其插入到全局排序表中第二的位置，依此類推，直至獲得用戶要求的K個(gè)節(jié)點(diǎn)。最后將結(jié)果返回2022/12/10117如何排序全局搜索時(shí)：KeyIP收到查詢請(qǐng)求后，采取如下方法總結(jié)snoogle系統(tǒng)是第一個(gè)基于傳感器網(wǎng)絡(luò)的物理世界信息檢索系統(tǒng)，Bloomfilter壓縮算法，分布式Top-k查詢算法的使用減少了通信開銷，安全隱私管理保障了用戶的信息安全。2022/12/10118總結(jié)snoogle系統(tǒng)是第一個(gè)基于傳感器網(wǎng)絡(luò)的物理世界信息檢總結(jié)但是，該系統(tǒng)僅支持偽靜態(tài)元數(shù)據(jù)的搜索，KeyIP的集中性質(zhì)不適于全球搜索，而且Bloomfilter的使用會(huì)導(dǎo)致查詢結(jié)果不準(zhǔn)確，Top-k算法在減少通信開銷的同