(物聯(lián)網(wǎng)搜索)(共68張PPT)

物聯(lián)網(wǎng)搜索2022/11/71日期INTRODUCTIONTOTHEReal-TimeSearchfor

Real-WorldEntities2022/11/72日期ubiquitouscomputingMarkWeiser(1991)提出了普適運算thefatherofubiquitouscomputing(1988)achiefscientistatXeroxPARC

(施樂帕克研究中心)intheUnitedStates2022/11/73日期ubiquitouscomputing

普適運算并非將基礎(chǔ)技術(shù)全盤翻新，普適運算技術(shù)運用了無線電網(wǎng)絡(luò)的科技，讓人們在不受時空限制的環(huán)境下享用資訊透過整合式無縫科技技術(shù)，讓人們使用起來更便利，省時。2022/11/74日期1面向物聯(lián)網(wǎng)的搜索服務(wù)描述2022/11/75日期基本要素及實現(xiàn)過程特點及面臨的挑戰(zhàn)2022/11/76日期物理世界實體2022/11/77日期物理世界實體與實體相連感知其狀態(tài)的傳感器用戶提出的對實體狀態(tài)或指定狀態(tài)實體的查詢接收查詢、處理并返回查詢狀態(tài)或與查詢相符實體的搜索引擎基本要素及實現(xiàn)過程2022/11/78日期面向物聯(lián)網(wǎng)的搜索示意圖2022/11/79日期特點及面臨的挑戰(zhàn)VS2022/11/710日期搜索對象的比較由傳感器自動生成的快速變化的結(jié)構(gòu)化內(nèi)容2022/11/711日期搜索對象的比較主要指因特網(wǎng)上的網(wǎng)頁及PDF、DOC等由人工輸入、靜態(tài)或緩慢變化的非結(jié)構(gòu)化內(nèi)容2022/11/712日期面向物聯(lián)網(wǎng)的搜索特點及

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

基本策略22022/11/723日期主動發(fā)送與被動索取信息發(fā)布/訂閱使用中介節(jié)點倒排索引壓縮技術(shù)建立模型實體評分與排名Top-k查詢2022/11/724日期主動發(fā)送與被動索取

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

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

pullandpushPull：實體本地存儲數(shù)據(jù)，查詢時用戶向?qū)嶓w發(fā)送查詢語句后將數(shù)據(jù)取回2022/11/727日期主動發(fā)送與被動索取

pullandpushPush和Pull混合的方法：數(shù)據(jù)被發(fā)送到某一位置，用戶從該位置取回數(shù)據(jù)(mediators)，并且有一些頻繁被查詢到的數(shù)據(jù)直接被Push到用戶端，而另一些很少被查詢到的數(shù)據(jù)則留在實體一端等待用戶Pull出。2022/11/728日期信息發(fā)布/訂閱

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

Publish/Subscribe2022/11/730日期使用中介節(jié)點

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

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

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

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

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

ScoringandRanking2022/11/736日期實體評分與排名

ScoringandRankingScoring是根據(jù)實體與查詢的相關(guān)度對實體評分，ranking根據(jù)該分數(shù)對實體進行排名。使用scoring和ranking有兩個目的。2022/11/737日期實體評分與排名

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

top-kquerytop-k查詢是指返回查詢結(jié)果返回集中K個最相關(guān)的實體，因為一般的查詢無須將所有匹配實體都返回。有時可以不考慮所有實體而直接找到Top-k實體，這與找到所有實體然后返回其子集的蠻力方法相比可以大大提高查詢效率。2022/11/739日期2022/11/740日期現(xiàn)有主要系統(tǒng)分析32022/11/741日期SnoogleDyser2022/11/742日期snoogle基本思想：把對實體的文本描述以關(guān)鍵詞的形式存儲到傳感器節(jié)點中以待用戶查詢，如一本書的附屬節(jié)點中含有關(guān)鍵詞”書“。用戶提出由一組關(guān)鍵詞組成的Adhoc查詢后，系統(tǒng)經(jīng)過對比返回匹配列表的前K項，其中列表中內(nèi)容匹配度依次遞減，K由用戶指定。2022/11/743日期snoogle系統(tǒng)架構(gòu)示意圖2022/11/744日期兩級mediator結(jié)構(gòu)下層稱為索引點（indexpoints），每個IP維護一個一定地理范圍內(nèi)所有傳感器節(jié)點的聚合視圖。上層的mediator稱為關(guān)鍵索引點（KeyIP），它負責維護整個網(wǎng)絡(luò)的聚合視圖。2022/11/745日期搜索過程移動節(jié)點的搜索由IPs間的移交協(xié)議實現(xiàn)。一般地，由IP周期性地發(fā)送信標信息來檢測節(jié)點是否在其范圍內(nèi)，當有節(jié)點移入或移出時更新其索引并通知KeyIP。也可以使用計時器方法，由節(jié)點發(fā)送保持活動消息，同時IP維護一個計時器。若一段時間內(nèi)沒有收到節(jié)點的消息，IP將其從索引表中刪除，其他檢測到節(jié)點消息的IP將節(jié)點加入到索引表中。2022/11/746日期通信壓縮系統(tǒng)采用Bloomfilter方法實現(xiàn)通信壓縮，將一組關(guān)鍵詞由nbit向量表示。該方法是一種空間效率很高的隨機數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。2022/11/747日期如何排序局域搜索時，查詢消息直接發(fā)到IP，IP根據(jù)其倒排索引計算出匹配傳感器的排序列表并將前K個結(jié)果返回。2022/11/748日期如何排序查詢時，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對傳感器進行排序，為統(tǒng)一不同IP的排序，需要把關(guān)鍵詞在一個IP包含的所有節(jié)點中出現(xiàn)的總頻率納入到排序算法中。2022/11/749日期如何排序查詢時，系統(tǒng)根據(jù)匹配關(guān)鍵詞的數(shù)量對傳感器進行排序，為統(tǒng)一不同IP的排序，需要把關(guān)鍵詞在一個IP包含的所有節(jié)點中出現(xiàn)的總頻率納入到排序算法中。2022/11/750日期如何排序全局搜索時：KeyIP收到查詢請求后，采取如下方法：向所有IPs查詢并返回當?shù)丶墑e最高的傳感器節(jié)點，將這一列表存儲在全局排序表中。為獲得級別第二的節(jié)點，KeyIP向所有IPs發(fā)送查詢請求，要求僅返回分數(shù)高于全局排序中級別第二的節(jié)點。將其插入到全局排序表中第二的位置，依此類推，直至獲得用戶要求的K個節(jié)點。最后將結(jié)果返回2022/11/751日期總結(jié)snoogle系統(tǒng)是第一個基于傳感器網(wǎng)絡(luò)的物理世界信息檢索系統(tǒng)，Bloomfilter壓縮算法，分布式Top-k查詢算法的使用減少了通信開銷，安全隱私管理保障了用戶的信息安全。2022/11/752日期總結(jié)但是，該系統(tǒng)僅支持偽靜態(tài)元數(shù)據(jù)的搜索，KeyIP的集中性質(zhì)不適于全球搜索，而且Bloomfilter的使用會導(dǎo)致查詢結(jié)果不準確，Top-k算法在減少通信開銷的同時也會產(chǎn)生大量的中間數(shù)據(jù)。2022/11/753日期DyserDyser是一個針對物聯(lián)網(wǎng)的實體實時搜索引擎，它充分利用現(xiàn)有的Internet網(wǎng)絡(luò)設(shè)施，實現(xiàn)了對快速變化內(nèi)容的可伸縮式搜索。系統(tǒng)可以根據(jù)用戶指定的當前狀態(tài)搜索實體，如可搜索一棟大廈里現(xiàn)在空閑的房間，某區(qū)域目前較安靜的地方等。2022/11/754日期Dyser系統(tǒng)架構(gòu)示意圖2022/11/755日期系統(tǒng)架構(gòu)介紹傳感器sensor和實體entity時模型中的兩個關(guān)鍵元素，每個傳感器和實體都與一個由網(wǎng)頁地址URL確定、通過HTTP協(xié)議訪問的Web資源對應(yīng)。所有這些Web資源又有一個HTML表示，通常稱其為傳感器頁（sensorpage）和實體頁（entitypage）。2022/11/756日期系統(tǒng)架構(gòu)介紹除了非結(jié)構(gòu)化文本，頁面中還包含一些如傳感器類型、可能讀數(shù)等結(jié)構(gòu)化信息。傳感器與實體之間是多對多的關(guān)系。圖中解析器用來處理用戶查詢、索引存儲傳感器和實體的索引元數(shù)據(jù)。索引器類似網(wǎng)絡(luò)蜘蛛抓取傳感器和實體網(wǎng)頁。2022/11/757日期2022/11/758日期建模及排序系統(tǒng)采用傳感器排名sensorranking方法對傳感器排序，以便進行選擇性的搜索。排序基于預(yù)測模型實現(xiàn)，由模型返回在一特定時間傳感器讀數(shù)為指定值的概率值，該模型由傳感器或傳感器網(wǎng)關(guān)創(chuàng)建，并發(fā)布在相應(yīng)的傳感器頁上。2022/11/759日期建模及排序可以根據(jù)不同場合選擇不同的預(yù)測模型，Dyser系統(tǒng)中提出匯總預(yù)測模型（APM）、單周期預(yù)測模型（SPPM）、多周期預(yù)測模型（MPPM）三種模型。2022/11/760日期搜索過程搜索時，搜索引擎首先從索引表中獲得含有請求類型傳感器的實體，根據(jù)實體與搜索的匹配度計算出實體的匹配概率（該值為與實體相