# Authenticated Location-Aware Publish/Subscribe Services in Untrusted Outsourced Environments

Authors: Han Yan; Xiang Cheng; Sen Su; Siyao Zhang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Location-aware publish/subscribe is an important location-based service based on server-initiated model. Often times, the owner of massive spatio-textual messages and subscriptions outsources its location-aware publish/subscribe services to a third-party service provider, for example, cloud service provider, who is responsible for delivering messages to their relevant subscribers. The issue arising here is that the messages delivered by the service provider might be tailored for profit purposes, intentionally or not. Therefore, it is essential to develop mechanisms which allow subscribers to verify the correctness of the messages delivered by the service provider. In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. We propose an authenticated framework which not only can deliver the messages efficiently but also can make the subscribers’ authentication available with low cost. Extensive experiments on a real-world dataset demonstrate the effectiveness and efficiency of our proposed authenticated framework.


---

## Body

## 1. Introduction

With the rapid development of mobile Internet and positioning-enabled devices (e.g., smart phones), massive amount of data that contain both text information and geographical location information are being generated at an unprecedented scale on the Web. This enables location-based services (LBS), such as Foursquare (https://foursquare.com) and Yelp (https://www.yelp.com), to be extensively deployed in many systems and widely accepted by Internet users. Location-aware publish/subscribe is an important kind of service based on server-initiated model (relative to user-initiated model, like spatial-keyword query) in LBS. For example, in a Groupon system, subscribers register their spatio-textual subscriptions to capture their interests (e.g., “Adidas shoe discount at Beijing, China”) (for the rest of this paper, we use “subscriber” and “subscription” interchangeably if the context is clear). For each Groupon message with textual description and location (e.g., “Adidas running shoes at cheap prices at Adidas factory store, Beijing, China”), the system delivers the message to relevant subscribers.Since location-aware publish/subscribe is a compute-intensive task, if the data owner of massive spatio-textual messages and subscriptions wants to efficiently deliver each message to relevant subscribers, to strengthen its ability of computing, it needs to build up basic IT infrastructure and hire specialized personnel. However, as such cost might be unaffordable for small-to-medium businesses, outsourcing the data and computations to a third-party service provider (e.g., a cloud service provider) has been an appealing option. Yet, this outsourcing model presents a great challenge that the messages delivered by the service provider might be incomplete or incorrect. There are a variety of reasons for this. First, the service provider might deliver tailored messages to favor its sponsors. Second, the service provider might use some inferior algorithms and deliver the suboptimal messages to the subscribers to save computing resources. Third, with the growing popularity of the cloud, more and more security breaches and attacks on such systems have been reported. In case an attacker takes control of the service provider’s server, it may forge the messages for its own interest.The aforementioned reasons necessitate the development of mechanisms that allow subscribers to authenticate the messages delivered by the service provider. They should be verified in terms of two conditions: (1)soundness and (2)completeness. The former means that the messages are not tampered with, while the latter implies that no valid message is missing.In this paper, to make one step further towards practical deployment of location-aware publish/subscribe in untrusted outsourcing environments, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. To address this problem, we present an authenticated location-aware publish/subscribe framework. We assume that messages are allowed a maximum delayΔt to be delivered to their corresponding subscribers. The data owner organizes the messages within Δt′ (Δt′≤Δt) in an authenticated data structure (ADS) called TMR-tree. Based on the TMR-tree, the service provider first computes the relevant messages for each subscription. During this process, we present an inverted index pruning technique to reduce the times of inverted index (used to index the subscriptions) traversal, thus improving the efficiency of computing the relevant messages for each subscription. Then, the service provider constructs a verification object (VO) for each subscription and the corresponding subscriber can authenticate the messages delivered to it. A thorough experimental study on a real-world dataset is conducted over a wide range of workload settings to evaluate the effectiveness and efficiency of our proposed framework in terms of various performance metrics.Roadmap. The rest of this paper is organized as follows. Section 2 introduces some preliminaries, which include system model, problem definition, and background knowledge. Section 3 presents our proposed authenticated location-aware publish/subscribe framework. In Section 4, we experimentally evaluate the performance of our proposed framework. Related work on the location-aware publish/subscribe and authenticated query processing is surveyed in Section 5. In the end, we conclude the paper in Section 6.


## 2. Preliminaries

In this section, we first describe our system model. Then, we define the problem studied in this paper. At last, we introduce some background knowledge on cryptographic primitives and location-aware publish/subscribe which underlie our proposed framework.


### 2.1. System Model

As shown in Figure1, our system involves four entities: the data owner, the service provider, the subscribers, and the key distribution center (KDC).Figure 1
System model.First, the data owner builds an authenticated data structure (ADS) over the messages within Δt′ (Δt′≤Δt; recall that Δt is a predefined maximum permissible delivery delay) and signs the ADS using the private key distributed by the KDC. Then, the data owner outsources the location-aware publish/subscribe services to the service provider, who provides the storage resources for the messages, the ADS, the signature of the ADS, and algorithms. Based on the ADS, the service provider finds the messages which are relevant to the registered subscriptions and constructs a verification object (VO) for each subscription. After that, the service provider delivers the messages and the VO to corresponding subscribers. The subscribers authenticate thesoundness andcompleteness of these messages using the VO and the public key distributed by the KDC.Throughout this paper, we assume that (1) theKDC and the data owner are trusted but the service provider is the potential adversary and might fabricate the messages (intentionally or not); (2) the KDC or the data owner does not collude with the service provider; (3) the computation and storage capacities of the service provider are polynomially bounded.


### 2.2. Problem Definition

In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. That is, the subscribers register their interests as subscriptions in the system first. Then, the service provider not only needs to efficiently deliver the messages withinΔt′ to the relevant subscribers whose subscriptions have high relevancy to the messages, but also needs to construct a VO for each subscriber to allow them to authenticate thesoundness andcompleteness of the delivered messages. The VO should be constructed as small as possible for minimizing the communication cost between the service provider and subscribers. Meanwhile, the VO should be suitable for subscribers’ authentication for minimizing the computational cost at the subscribers side.


### 2.3. Background Knowledge

#### 2.3.1. Cryptographic Primitives

We present the essential cryptographic primitives on one-way hash function, cryptographic signature, and Merkle hash tree as follows.One-Way Hash Function. A one-way hash function h· maps a message m of arbitrary length to a fixed-length output Hm. It works in one direction. It is easy to compute Hm for a message m. However, it is computationally infeasible to find a message that maps to a given H·.Cryptographic Signature. A cryptographic signature (or simply signature) is a mathematical scheme for demonstrating the authenticity of a digital message. A signer applies for a pair of private key and public key from the KDC. The former is kept by the signer secretly and the latter is publicly distributed. A digital message can be signed using the private key. The authenticity of the message can be verified by anyone who receives this message using the public key.Merkle Hash Tree. The Merkle hash tree (MHT) [1] is an authenticated data structure used for collectively authenticating a set of messages. The MHT is a binary tree and built in a bottom-up manner, by first computing the hash values of the messages in leaf nodes. The hash value of each internal node is derived from its two children nodes. Finally, the hash value of the root is signed by the owner of the messages. The MHT can be used to authenticate any subset of messages, in conjunction with aproof. Theproof consists of the signed root and sibling nodes (auxiliary hash values) on the path from the root down to the messages which need to be authenticated.


#### 2.3.2. Location-Aware Publish/Subscribe

We present the state-of-the-art method [2] for location-aware publish/subscribe as follows.A location-aware publish/subscribe service delivers each message, denoted bym=m.loc,m.text, to its relevant subscribers who register spatio-textual subscriptions (each subscription is denoted by s=s.loc,s.text) to capture their interests. m.loc (s.loc) is a spatial location with the latitude and longitude. m.text (s.text) is a set of keywords t1,t2,…,tm.text (t1,t2,…,ts.text) and each keyword is associated with a weight wti which can be set as the inverted document frequency (IDF) of the keyword. To quantify the relevancy between a subscription and a message, [2] used a spatio-textual similarity function(1)SIMs,m=δ·TSIMs,m+1-δ·SSIMs,m,where(2)TSIMs,m=∑t∈s.text∩m.textwt∑t∈s.textwtis a textual similarity function which is similar to the weighted Jaccard coefficient and(3)SSIMs,m=max⁡0,1-DISTs.loc,m.locmaxDISTis a spatial similarity function, where DISTs.loc,m.loc is the Euclidian distance between s.loc and m.loc, and maxDIST is the maximum user-tolerated Euclidian distance between subscriptions and messages (which can be set as the maximum distance between subscriptions). δ is a preference parameter to tune the weight of textual and spatial similarity. A subscription s and a message m are called relevant if their similarity exceeds a threshold τ. Since subscribers usually have different preferences and requirements on δ and τ (e.g., some subscribers prefer highly relevant results while some subscribers want to get more results), subscribers are allowed to parameterize their parameters δ and τ. Therefore, a parameterized spatio-textual subscription can be redefined as s=s.loc,s.text,s.δ,s.τ. Figure 2 shows an example of 11 parameterized spatio-textual subscriptions and 7 messages.Figure 2
A running example.To deliver messages to relevant subscribers efficiently, [2] proposed aspatial-oriented prefix to prune irrelevant subscriptions and devised a filter-verification framework. In particular, with respect to the textual filter, [2] claimed that if a subscription s is relevant to a message m, they must share at least one common keyword in the so-calledprefix of s, which is computed from the textual similarity threshold. More specifically, based on (1), given a subscription s, since the spatial similarity cannot exceed 1, [2] deduced a textual similarity threshold(4)s.τT=s.τ-1-s.δs.δ.Whens.τT>0, based on s.τT, [2] selected aprefix for each subscription s. The keywords in s.text are sorted by their weights in descending order and a minimum p such that(5)∑i=ps.textwtiws.text<s.τTis computed, where ws.text is the total weight of keywords in s.text. Therefore, theprefix of s can be defined as SIGs=t1,t2,…,tp-1. Since the total weight of keywords after tp is smaller than s.τT, if a subscription s is relevant to a message m (i.e., TSIMs,m≥s.τT), they must share at least one common keyword in SIGs.Whens.τT≤0, a message m may be relevant to s no matter whether they share common keywords. To address this issue, for a subscription s, if s.τ≤1-s.δ, [2] introduced a virtual dummy keyword “∗” with weight of 0 (i.e., w∗=0), and theprefix of s includes its keywords and “∗”.Regarding the spatial filter, based on thefirst match keyword (denoted by ti) between SIGs and m (i.e., m does not contain keywords before ti in SIGs), [2] estimated an upper textual similarity bound of m to s as follows:(6)UTBs∣ti=∑j=is.textwtjws.text≥TSIMs,m.Accordingly, [2] estimated a lower spatial similarity bound between s and m as follows:(7)LSBs∣ti=s.τ-s.δ·UTBs∣ti1-s.δ≤SSIMs,m.For any message, if its spatial similarity to s is smaller than the lower spatial similarity bound LSBs∣ti, the subscription s can be safely pruned.Since given a subscriptions and a message m, we do not know which keyword is theirfirst match keyword (if they have), and thefirst match keywords for different messages to the subscription are different, for each keyword t in SIGs, and [2] computed the lower spatial similarity bound LSBs∣t. Thisprefix of each subscription s with lower spatial similarity bound is calledspatial-oriented prefix. If subscription s is relevant to message m, there must exist a keyword t in SIGs∩m such that SSIMs,m≥LSBs∣t.Based on thespatial-oriented prefix, [2] devised a filter-verification framework. In particular, an inverted index is built on thespatial-oriented prefixes first. Then, in the filter phase, for each message keyword t, the framework retrieves the inverted list Lt of t and for each subscription s in Lt, if SSIMs,m≥LSBs∣t, s is put into the candidate set. In the verification phase, based on (1), the framework verifies whether each candidate s is an answer, and if yes, the message m is delivered to s.


## 2.1. System Model

As shown in Figure1, our system involves four entities: the data owner, the service provider, the subscribers, and the key distribution center (KDC).Figure 1
System model.First, the data owner builds an authenticated data structure (ADS) over the messages within Δt′ (Δt′≤Δt; recall that Δt is a predefined maximum permissible delivery delay) and signs the ADS using the private key distributed by the KDC. Then, the data owner outsources the location-aware publish/subscribe services to the service provider, who provides the storage resources for the messages, the ADS, the signature of the ADS, and algorithms. Based on the ADS, the service provider finds the messages which are relevant to the registered subscriptions and constructs a verification object (VO) for each subscription. After that, the service provider delivers the messages and the VO to corresponding subscribers. The subscribers authenticate thesoundness andcompleteness of these messages using the VO and the public key distributed by the KDC.Throughout this paper, we assume that (1) theKDC and the data owner are trusted but the service provider is the potential adversary and might fabricate the messages (intentionally or not); (2) the KDC or the data owner does not collude with the service provider; (3) the computation and storage capacities of the service provider are polynomially bounded.


## 2.2. Problem Definition

In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. That is, the subscribers register their interests as subscriptions in the system first. Then, the service provider not only needs to efficiently deliver the messages withinΔt′ to the relevant subscribers whose subscriptions have high relevancy to the messages, but also needs to construct a VO for each subscriber to allow them to authenticate thesoundness andcompleteness of the delivered messages. The VO should be constructed as small as possible for minimizing the communication cost between the service provider and subscribers. Meanwhile, the VO should be suitable for subscribers’ authentication for minimizing the computational cost at the subscribers side.


## 2.3. Background Knowledge

### 2.3.1. Cryptographic Primitives

We present the essential cryptographic primitives on one-way hash function, cryptographic signature, and Merkle hash tree as follows.One-Way Hash Function. A one-way hash function h· maps a message m of arbitrary length to a fixed-length output Hm. It works in one direction. It is easy to compute Hm for a message m. However, it is computationally infeasible to find a message that maps to a given H·.Cryptographic Signature. A cryptographic signature (or simply signature) is a mathematical scheme for demonstrating the authenticity of a digital message. A signer applies for a pair of private key and public key from the KDC. The former is kept by the signer secretly and the latter is publicly distributed. A digital message can be signed using the private key. The authenticity of the message can be verified by anyone who receives this message using the public key.Merkle Hash Tree. The Merkle hash tree (MHT) [1] is an authenticated data structure used for collectively authenticating a set of messages. The MHT is a binary tree and built in a bottom-up manner, by first computing the hash values of the messages in leaf nodes. The hash value of each internal node is derived from its two children nodes. Finally, the hash value of the root is signed by the owner of the messages. The MHT can be used to authenticate any subset of messages, in conjunction with aproof. Theproof consists of the signed root and sibling nodes (auxiliary hash values) on the path from the root down to the messages which need to be authenticated.


### 2.3.2. Location-Aware Publish/Subscribe

We present the state-of-the-art method [2] for location-aware publish/subscribe as follows.A location-aware publish/subscribe service delivers each message, denoted bym=m.loc,m.text, to its relevant subscribers who register spatio-textual subscriptions (each subscription is denoted by s=s.loc,s.text) to capture their interests. m.loc (s.loc) is a spatial location with the latitude and longitude. m.text (s.text) is a set of keywords t1,t2,…,tm.text (t1,t2,…,ts.text) and each keyword is associated with a weight wti which can be set as the inverted document frequency (IDF) of the keyword. To quantify the relevancy between a subscription and a message, [2] used a spatio-textual similarity function(1)SIMs,m=δ·TSIMs,m+1-δ·SSIMs,m,where(2)TSIMs,m=∑t∈s.text∩m.textwt∑t∈s.textwtis a textual similarity function which is similar to the weighted Jaccard coefficient and(3)SSIMs,m=max⁡0,1-DISTs.loc,m.locmaxDISTis a spatial similarity function, where DISTs.loc,m.loc is the Euclidian distance between s.loc and m.loc, and maxDIST is the maximum user-tolerated Euclidian distance between subscriptions and messages (which can be set as the maximum distance between subscriptions). δ is a preference parameter to tune the weight of textual and spatial similarity. A subscription s and a message m are called relevant if their similarity exceeds a threshold τ. Since subscribers usually have different preferences and requirements on δ and τ (e.g., some subscribers prefer highly relevant results while some subscribers want to get more results), subscribers are allowed to parameterize their parameters δ and τ. Therefore, a parameterized spatio-textual subscription can be redefined as s=s.loc,s.text,s.δ,s.τ. Figure 2 shows an example of 11 parameterized spatio-textual subscriptions and 7 messages.Figure 2
A running example.To deliver messages to relevant subscribers efficiently, [2] proposed aspatial-oriented prefix to prune irrelevant subscriptions and devised a filter-verification framework. In particular, with respect to the textual filter, [2] claimed that if a subscription s is relevant to a message m, they must share at least one common keyword in the so-calledprefix of s, which is computed from the textual similarity threshold. More specifically, based on (1), given a subscription s, since the spatial similarity cannot exceed 1, [2] deduced a textual similarity threshold(4)s.τT=s.τ-1-s.δs.δ.Whens.τT>0, based on s.τT, [2] selected aprefix for each subscription s. The keywords in s.text are sorted by their weights in descending order and a minimum p such that(5)∑i=ps.textwtiws.text<s.τTis computed, where ws.text is the total weight of keywords in s.text. Therefore, theprefix of s can be defined as SIGs=t1,t2,…,tp-1. Since the total weight of keywords after tp is smaller than s.τT, if a subscription s is relevant to a message m (i.e., TSIMs,m≥s.τT), they must share at least one common keyword in SIGs.Whens.τT≤0, a message m may be relevant to s no matter whether they share common keywords. To address this issue, for a subscription s, if s.τ≤1-s.δ, [2] introduced a virtual dummy keyword “∗” with weight of 0 (i.e., w∗=0), and theprefix of s includes its keywords and “∗”.Regarding the spatial filter, based on thefirst match keyword (denoted by ti) between SIGs and m (i.e., m does not contain keywords before ti in SIGs), [2] estimated an upper textual similarity bound of m to s as follows:(6)UTBs∣ti=∑j=is.textwtjws.text≥TSIMs,m.Accordingly, [2] estimated a lower spatial similarity bound between s and m as follows:(7)LSBs∣ti=s.τ-s.δ·UTBs∣ti1-s.δ≤SSIMs,m.For any message, if its spatial similarity to s is smaller than the lower spatial similarity bound LSBs∣ti, the subscription s can be safely pruned.Since given a subscriptions and a message m, we do not know which keyword is theirfirst match keyword (if they have), and thefirst match keywords for different messages to the subscription are different, for each keyword t in SIGs, and [2] computed the lower spatial similarity bound LSBs∣t. Thisprefix of each subscription s with lower spatial similarity bound is calledspatial-oriented prefix. If subscription s is relevant to message m, there must exist a keyword t in SIGs∩m such that SSIMs,m≥LSBs∣t.Based on thespatial-oriented prefix, [2] devised a filter-verification framework. In particular, an inverted index is built on thespatial-oriented prefixes first. Then, in the filter phase, for each message keyword t, the framework retrieves the inverted list Lt of t and for each subscription s in Lt, if SSIMs,m≥LSBs∣t, s is put into the candidate set. In the verification phase, based on (1), the framework verifies whether each candidate s is an answer, and if yes, the message m is delivered to s.


## 2.3.1. Cryptographic Primitives

We present the essential cryptographic primitives on one-way hash function, cryptographic signature, and Merkle hash tree as follows.One-Way Hash Function. A one-way hash function h· maps a message m of arbitrary length to a fixed-length output Hm. It works in one direction. It is easy to compute Hm for a message m. However, it is computationally infeasible to find a message that maps to a given H·.Cryptographic Signature. A cryptographic signature (or simply signature) is a mathematical scheme for demonstrating the authenticity of a digital message. A signer applies for a pair of private key and public key from the KDC. The former is kept by the signer secretly and the latter is publicly distributed. A digital message can be signed using the private key. The authenticity of the message can be verified by anyone who receives this message using the public key.Merkle Hash Tree. The Merkle hash tree (MHT) [1] is an authenticated data structure used for collectively authenticating a set of messages. The MHT is a binary tree and built in a bottom-up manner, by first computing the hash values of the messages in leaf nodes. The hash value of each internal node is derived from its two children nodes. Finally, the hash value of the root is signed by the owner of the messages. The MHT can be used to authenticate any subset of messages, in conjunction with aproof. Theproof consists of the signed root and sibling nodes (auxiliary hash values) on the path from the root down to the messages which need to be authenticated.


## 2.3.2. Location-Aware Publish/Subscribe

We present the state-of-the-art method [2] for location-aware publish/subscribe as follows.A location-aware publish/subscribe service delivers each message, denoted bym=m.loc,m.text, to its relevant subscribers who register spatio-textual subscriptions (each subscription is denoted by s=s.loc,s.text) to capture their interests. m.loc (s.loc) is a spatial location with the latitude and longitude. m.text (s.text) is a set of keywords t1,t2,…,tm.text (t1,t2,…,ts.text) and each keyword is associated with a weight wti which can be set as the inverted document frequency (IDF) of the keyword. To quantify the relevancy between a subscription and a message, [2] used a spatio-textual similarity function(1)SIMs,m=δ·TSIMs,m+1-δ·SSIMs,m,where(2)TSIMs,m=∑t∈s.text∩m.textwt∑t∈s.textwtis a textual similarity function which is similar to the weighted Jaccard coefficient and(3)SSIMs,m=max⁡0,1-DISTs.loc,m.locmaxDISTis a spatial similarity function, where DISTs.loc,m.loc is the Euclidian distance between s.loc and m.loc, and maxDIST is the maximum user-tolerated Euclidian distance between subscriptions and messages (which can be set as the maximum distance between subscriptions). δ is a preference parameter to tune the weight of textual and spatial similarity. A subscription s and a message m are called relevant if their similarity exceeds a threshold τ. Since subscribers usually have different preferences and requirements on δ and τ (e.g., some subscribers prefer highly relevant results while some subscribers want to get more results), subscribers are allowed to parameterize their parameters δ and τ. Therefore, a parameterized spatio-textual subscription can be redefined as s=s.loc,s.text,s.δ,s.τ. Figure 2 shows an example of 11 parameterized spatio-textual subscriptions and 7 messages.Figure 2
A running example.To deliver messages to relevant subscribers efficiently, [2] proposed aspatial-oriented prefix to prune irrelevant subscriptions and devised a filter-verification framework. In particular, with respect to the textual filter, [2] claimed that if a subscription s is relevant to a message m, they must share at least one common keyword in the so-calledprefix of s, which is computed from the textual similarity threshold. More specifically, based on (1), given a subscription s, since the spatial similarity cannot exceed 1, [2] deduced a textual similarity threshold(4)s.τT=s.τ-1-s.δs.δ.Whens.τT>0, based on s.τT, [2] selected aprefix for each subscription s. The keywords in s.text are sorted by their weights in descending order and a minimum p such that(5)∑i=ps.textwtiws.text<s.τTis computed, where ws.text is the total weight of keywords in s.text. Therefore, theprefix of s can be defined as SIGs=t1,t2,…,tp-1. Since the total weight of keywords after tp is smaller than s.τT, if a subscription s is relevant to a message m (i.e., TSIMs,m≥s.τT), they must share at least one common keyword in SIGs.Whens.τT≤0, a message m may be relevant to s no matter whether they share common keywords. To address this issue, for a subscription s, if s.τ≤1-s.δ, [2] introduced a virtual dummy keyword “∗” with weight of 0 (i.e., w∗=0), and theprefix of s includes its keywords and “∗”.Regarding the spatial filter, based on thefirst match keyword (denoted by ti) between SIGs and m (i.e., m does not contain keywords before ti in SIGs), [2] estimated an upper textual similarity bound of m to s as follows:(6)UTBs∣ti=∑j=is.textwtjws.text≥TSIMs,m.Accordingly, [2] estimated a lower spatial similarity bound between s and m as follows:(7)LSBs∣ti=s.τ-s.δ·UTBs∣ti1-s.δ≤SSIMs,m.For any message, if its spatial similarity to s is smaller than the lower spatial similarity bound LSBs∣ti, the subscription s can be safely pruned.Since given a subscriptions and a message m, we do not know which keyword is theirfirst match keyword (if they have), and thefirst match keywords for different messages to the subscription are different, for each keyword t in SIGs, and [2] computed the lower spatial similarity bound LSBs∣t. Thisprefix of each subscription s with lower spatial similarity bound is calledspatial-oriented prefix. If subscription s is relevant to message m, there must exist a keyword t in SIGs∩m such that SSIMs,m≥LSBs∣t.Based on thespatial-oriented prefix, [2] devised a filter-verification framework. In particular, an inverted index is built on thespatial-oriented prefixes first. Then, in the filter phase, for each message keyword t, the framework retrieves the inverted list Lt of t and for each subscription s in Lt, if SSIMs,m≥LSBs∣t, s is put into the candidate set. In the verification phase, based on (1), the framework verifies whether each candidate s is an answer, and if yes, the message m is delivered to s.


## 3. Authenticated Location-Aware Publish/Subscribe Framework

In this section, we present our proposed authenticated location-aware publish/subscribe framework. In the publish/subscribe scenario, the messages delivered to the subscribers need to be verified as correct or not (i.e.,soundness andcompleteness). However, compared with the subscriptions data, the messages data set is infinite, which can be regarded as the stream data. In such a situation, we (actually the data owner in the practical framework) cannot construct an authenticated data structure (ADS) over the infinite messages data and, based on such a structure, construct the VO for subscribers’ authentication. Therefore, intuitively, we need to sign every coming message and when the signed message is delivered to its corresponding subscribers, they can authenticate this message. However, when many messages need to be delivered to only one subscriber (the subscriber registers many interests in the framework), since every message has a signature, the communication cost between the service provider and this subscriber is high. Moreover, since the decryption of the signature is not a cheap operation, the authentication cost at the subscriber is also high. To tackle this problem, we present an authenticated location-aware publish/subscribe framework, which not only can deliver the messages more efficiently than the framework in the existing work [2], but also can make the subscribers’ authentication available with low communication and authentication cost.The main idea of our framework is to assume that the messages are allowed a maximum delayΔt to be delivered to their corresponding subscribers. Under this circumstance, a batch of messages, rather than only one message, can be computed at a time. We organize these messages in a Merkle hash tree (MHT) like structure (i.e., the ADS). When more than one message is delivered to a subscriber, only one signature is returned, thereby reducing the communication and authentication cost. Moreover, recall that, in [2], an inverted index ofspatial-oriented prefixes of all the subscriptions is constructed and when a message comes, the framework retrieves the inverted index to compute which subscription is relevant to this message. The message needs to be computed with every subscription in Lt of every message keyword t. To reduce the computational cost and improve the efficiency of messages delivery, we present an inverted index pruning technique. By using the constraint of the spatial proximity between these messages (the messages are also organized in an R-tree like structure), we can prune some subscriptions which cannot become the delivery destinations from the inverted index and thus they need not be involved in the further computation.


### 3.1. Text-Aware Merkle R-Tree (TMR-Tree)

We first introduce the method of constructing theADS, called Text-aware Merkle R-tree (TMR-tree), at the data owner side. Consider a predefined maximum permissible delivery delay Δt. The data owner builds one TMR-tree on all the messages within every time interval Δt′ (Δt′≤Δt). Specifically, the TMR-tree has four main features:(i)
The messages inΔt′ are spatially organized in an R-tree.(ii)
Each node has a pseudo-text which includes the union of the keywords in its children’s texts. A nodeu with children v and w has pseudo-text u.text=v.text∪w.text.(iii)
Similar to theMHT, the TMR-tree stores one hash value in each node. Assume the default fanout of the TMR-tree is 2. A leaf node u with children (messages) v and w stores hash value Hu=hv∣w. An internal node u with children v and w stores hash value Hu=hv∣Hv∣w∣Hw, where Hv and Hw are the hash values of v and w. More specifically, the spatial and textual information of v (w) are both involved in the computation, that is, Hu=hv.loc∣v.text∣w.loc∣w.text if u is a leaf node in the TMR-tree and Hu=hv.loc∣v.text∣Hv∣w.loc∣w.text∣Hw if u is an internal node in the TMR-tree.(iv)
The hash value of the root of the TMR-tree is signed by the data owner, producing signatureS.Example 1.
Figure3 shows an example of the TMR-tree constructed over the messages in Figure 2. Here the fanout of the TMR-tree is set as 2. The leaf node R5 has a pseudo-text t5,t4,t3,t2,t1 which is the union of its children’s texts, that is, t5,t4,t3∪t5,t4,t2,t1 (m4.text∪m5.text). Since no matter the leaf or internal node is represented by a rectangle area (the Minimum Bounding Rectangle (MBR) of messages or other MBRs in it), its location is defined by two points which can be the bottom-left and upper-right points. For example, R6 is the MBR of m6 and m7 and its location includes the rectangle’s bottom-left and upper-right points (0.11,0.70 and 0.20,0.79). The leaf node R5 stores a hash value HR5 which summarizes the authentication information about R5 and it is computed through the spatial and textual information of its children (messages); that is, HR5=hm4.loc∣m4.text∣m5.loc∣m5.text. Similarly, the hash value stored in internal node R2 is computed through the spatial and textual information of its children and their hash values; that is, HR2=hR5.loc∣R5.text∣HR5∣R6.loc∣R6.text∣HR6.Figure 3
Illustration of TMR-tree (partial).


### 3.2. Filter-Verification Framework with Inverted Index Pruning

We use the idea of filter-verification framework proposed in [2] and, based on this, present an inverted index pruning technique to reduce the computational cost, thereby improving the efficiency of messages delivery.Since a location and a pseudo-text are associated with a node in the TMR-tree, each node in the TMR-tree can be treated as a dummy message. The main idea of our inverted index pruning technique is based on the following proposition.Proposition 2.
If some subscriptions in the inverted index ofspatial-oriented prefixes (L) are not relevant to a node R (a dummy message) in the TMR-tree, these subscriptions can be safely pruned from L since R’s children (other dummy messages or true messages) cannot be relevant to these subscriptions with certainty.Proof.
If a subscriptions in L is not relevant to a node R, we have ∃s∈L, SSIMs,R<LSBs∣t. According to (3), we have(8)max⁡0,1-DISTs.loc,R.locmaxDIST<LSBs∣t.∀R′∈R, that is, R′ is R’s child, since DISTs.loc,R′.loc≥DISTs.loc,R.loc, we have(9)max⁡0,1-DISTs.loc,R′.locmaxDIST≤max⁡0,1-DISTs.loc,R.locmaxDIST<LSBs∣t.Therefore, s is not relevant to R′ either.Algorithm1 shows the pseudo-code of our framework with the inverted index pruning technique. It takes the TMR-tree and L as input. For each node R and each message m in leaf nodes in the TMR-tree, we use R.Lr (m.Lr) to denote the inverted index where the subscriptions in R.Lr (m.Lr) are likely to be relevant to R (m), which is pruned from Lr of R’s (m’s) parent. We let R.Lp (m.Lp) denote Lr of R’s (m’s) parent. Thus, Lr of each node (or message) is pruned from its Lp, which is its parent’s Lr. In the beginning, we set the root’s Lp (i.e., TMR-tree.Root.Lp) as L, which is the inverted index ofspatial-oriented prefixes of all the subscriptions without any pruning (line (1)). Then, we initialize an empty stack T and push the root into it (lines (2)-(3)). In the filter phase, every element in T is computed until T is empty (lines (4)–(11)). First, we pop an element R from T (line (5)). Then, for each keyword ti in R.text, we retrieve the inverted list R.Lpti of ti and for each subscription sj in R.Lpti, if SSIMsj,R≥LSBsj∣ti, sj is added to R.Lrti (lines (6)–(9)). Other subscriptions which do not satisfy the condition in line (8) are pruned from R.Lp. If R.Lr≠∅ and R is not a message, that is, there exist some subscriptions in R.Lr which might be relevant to R’s children, R’s children are put into stack T (lines (10)-(11)). The subscriptions in each mi.Lr are the candidates which might be relevant to mi. In the verification phase, for each message mi, we verify whether each candidate sj in mi.Lr is the answer of mi and if yes, sj is added to the answer set of mi, that is, Ami (lines (12)–(15)). After computing all the messages in the TMR-tree, all the answer sets (Am1,Am2,…,AmM) are together returned (line (16)). Here we assume that there are M messages that come within Δt′. Each subscription in Ami is the delivery destination of the message mi.Algorithm 1:Filter-verification framework with inverted index pruning.
Input: TMR-tree: the text-aware Merkle R-tree on messages within Δt′; L: the inverted index of spatial-oriented prefixes
Output: Ami: answers of each message mi in the TMR-tree
(1) TMR-tree.Root.Lp=L;
(2) Initialize StackT;
(3)T.Push(TMR-tree.Root);
(4)while  Tis not emptydo
(5)R=T.Pop();
(6)foreach  ti∈R.text  do
(7)foreach  sj∈R.Lp(ti)  do
(8)if  SSIM(sj,R)≥LSBsj∣ti  then
(9)R.Lr(ti).Add(sj);
(10)if  R.Lr≠∅  and  Ris not a message  then
(11)T.Push(R.children);
(12)foreach  mi∈TMR-tree.leafnodesdo
(13)foreach  sj∈mi.Lr  do
(14)if  Verify(sj,mi)  then
(15)Ami.Add(sj);
(16) returnAm1,Am2,…,AmM;Example 3.
Figure4 shows an example of procedures of our proposed inverted index pruning technique in filter-verification framework. In step ①, the root is popped from stack T first. Then, for each keyword in Root.text (t1 to t5 and ∗), we retrieve the corresponding inverted list in Root.Lp to compute the spatial similarity between the root and each subscription in this inverted list. Take subscription s9 as an example, we retrieve Root.Lpt1 and compute the spatial similarity between the root and s9: SSIMs9,Root, which equals 1. Since SSIMs9,Root=1 is greater than LSBs9∣t1=0.60, s9 is added to Root.Lrt1. Notice that the values of spatial similarity between the root and s0, s1, s9 in Root.Lpt4 and s3, s7, s8 in Root.Lpt5 are smaller than the values of these subscriptions’ LSBs∣t; that is, they do not satisfy the condition in line (8) in Algorithm 1. Therefore, they are pruned from Root.Lp and are not added to Root.Lr. Then, since Root.Lr≠∅, its children R1 and R2 are pushed into stack T. Similarly, in step ②, s9 in R2.Lpt1, s9 in R2.Lpt2, s5 in R2.Lpt3, s2, s8 in R2.Lpt4, and s4 in R2.Lpt5 are pruned from R2.Lp. Note that, in step ③, since R6.text does not contain the keywords t3 and t5, we need not compute the spatial similarity between R6 and each subscription in inverted lists R6.Lpt3 and R6.Lpt5 (indicated by “###” in the example), and these subscriptions are also pruned from R6.Lp. At last, in step ④, the candidates which might be relevant to m6 are s0, s4, s5, s6, and s8. Compared with all the subscriptions in the unpruned inverted index L, the computational cost is reduced dramatically.Figure 4
An Example of procedures of filter-verification framework with inverted index pruning (partial).Time Complexity. For the convenience of comparison between the state-of-the-art method for location-aware publish/subscribe and our proposed filter-verification framework with inverted index pruning technique, we first give the time complexity of filter-verification framework proposed in [2] as the following proposition.Proposition 4.
The time complexity of delivering one messagem to its relevant subscriber s in filter-verification framework proposed in [2] is O∑t∈m.textLt+s.text, where L is the inverted index built on thespatial-oriented prefixes.Proof.
In the filter phase, for each keywordt in m.text (including the dummy keyword “∗”), the framework retrieves the inverted list Lt of t and for each subscription s in Lt, if SSIMs,m≥LSBs∣t, s is a candidate to the message m and we add it into the candidate set. Therefore, the time complexity of filtering is O∑t∈m.textLt.
In the verification phase, based on the spatio-textual similarity function (see (1)), s and m are relevant, if and only if(10)ws.text∩m.text=∑t∈s.text∩m.textwt≥s.τ-1-s.δ·SSIMs,ms.δ·ws.text.SSIM(s,m) can be easily computed in O1 time and ws.text can be materialized; thus it is easy to compute s.τ-1-s.δ·SSIMs,m/s.δ·ws.text. To compute ws.text∩m.text, we check whether each keyword t in s.text appears in m.text. If yes, we add the corresponding weight wt into ws.text∩m.text. To facilitate the checking, we build a hash map for keywords in m.text. (We only need to build the hash map for the message once.) Thus the time complexity of verifying a subscription s is Os.text. Therefore, the time complexity of delivering one message m to its relevant subscriber s in filter-verification framework proposed in [2] is O∑t∈m.textLt+s.text‍.The time complexity of our proposed filter-verification framework with inverted index pruning technique is given by the following proposition.Proposition 5.
The time complexity of deliveringM messages that come within Δt′ to their relevant subscribers in our proposed filter-verification framework with inverted index pruning technique is O∑i=11-M/1-f∑t∈Ri.textRi.Lpt+∑i=1Msi.text, where f is the fanout of the TMR-tree, Ri is a node in the TMR-tree (also can be treated as a dummy message), and Lp is the inverted index associated with Ri’s parent in which the subscriptions are likely to be relevant to Ri’s parent.Proof.
A TMR-tree is constructed over theM messages that come within Δt′. If the fanout of the TMR-tree is f, in the worst case, the height of the TMR-tree (excluding the layer of messages) is h=logfM. Thus, the number of internal and leaf nodes in the TMR-tree (assuming the root has depth 1) is(11)f0+⋯+fh-1=1-fh1-f=1-flogfM1-f=1-M1-f.
In the filter phase, when visiting a nodeR (or a message m) in the TMR-tree, we retrieve its Lp, prune R.Lp (or m.Lp), and generate R.Lr (or m.Lr). Therefore, the time complexity of filtering with inverted index pruning is O∑i=11-M/1-f∑t∈Ri.textRi.Lpt.
In the verification phase, suppose each messagem within Δt′ is delivered to only one subscriber. The time complexity of verifying whether M subscriptions are the answers of messages is O∑i=1Msi.text. Therefore, the time complexity of delivering M messages that come within Δt′ to their relevant subscribers in our proposed filter-verification framework with inverted index pruning technique is O∑i=11-M/1-f∑t∈Ri.textRi.Lpt+∑i=1Msi.text.Compared with the filter-verification framework proposed in [2], our proposed filter-verification framework with inverted index pruning technique needs to visit more inverted indexes (the inverted indexes associated with internal and leaf nodes in the TMR-tree). However, since the subscriptions in each node’s inverted index are constantly pruned from the root to the leaf nodes in the TMR-tree, the total times of inverted index traversal are reduced. Therefore, our proposed filter-verification framework with inverted index pruning technique can be considered efficient, which also can be demonstrated from our experimental study (Section 4).


### 3.3.VO Construction and Authentication

After finding the subscribers who are the delivery destinations of messages, that is,Ami, the service provider still needs to construct a VO for each subscriber for their authentication. Algorithm 2 shows the pseudo-code of constructing the VO. It takes the TMR-tree and answers of each message mi (Ami) as input. First, we initialize a VO for each subscription in Am1∪Am2∪⋯∪AmM (VOsi) with the root of the TMR-tree (lines (1)-(2)). Then, we initialize an empty queue Q and put the root into it (lines (3)-(4)). Every element in Q is computed until Q is empty (lines (5)–(12)). When the distance between a message mi and the picked element R (from Q) is smaller than 0, that is, mi is in the subtree rooted at R, for each subscription si in Ami, we replace R in VOsi with three parts: (1) the token “[”; (2) R’s children; and (3) the token “]” (lines (6)–(10)). Note that we use a pair of tokens “[” and “]” to indicate the scope of the entries in R. Then, if R’s children are not in Q and they are not messages, they are put into Q (lines (11)-(12)). At last, the constructed VOsi is delivered to each subscriber si with the corresponding messages (line (13)). Here we assume that there are N subscribers to whom the messages will be delivered.Algorithm 2:
V
O construction.
Input: TMR-tree: a text-aware Merkle R-tree on messages within Δt′; Ami: answers of each message mi in the TMR-tree
Output: VOsi: the VO for each subscription si
(1)foreach  si∈Am1∪Am2∪⋯∪AmM  do
(2)VOsi.Init(TMR-tree.Root);
(3) Initialize QueueQ;
(4)Q.Put(TMR-tree.Root);
(5)whileQis not emptydo
(6)R=Q.Pick();
(7)foreach  mi∈TMR-tree.leafnodesdo
(8)if  Distmi,R≤0  then
(9)foreach  sj∈Ami  do
(10)VOsj.Replace(R, “[” + R.children + “]”);
(11)if  R.childrenarenotinQ  andtheyarenotmessages  then
(12)Q.Put(R.children);
(13) returnVOs1,VOs2,…,VOsN;Example 6.
Following the example in Figure2, after computing the delivery destinations of messages m1 to m7, we obtain their answer sets as follows: Am1:s6, Am2:s5,s6, Am3:s5, Am4:s2,s3,s7,s10, Am5:s0,s3,s4,s7,s8, Am6:s6, and Am7:s6. Here we take the construction of the VO of s6 (VOs6) as an example (shown in Figure 5) and messages m1, m2, m6, and m7 will be delivered to s6. In step ①, the root is picked from the queue Q. Obviously, DISTm1.loc,root.loc, DISTm2.loc,root.loc, DISTm6.loc,root.loc, and DISTm7.loc,root.loc are all smaller than 0. Therefore, we replace “root” in VOs6 with “R1R2”. Since R1 and R2 are not in Q and they are not messages, they are put into Q. The steps ②, ③, and ④ are similar to ①. In step ⑤, since m1, m2, m6, and m7 are not in the subtree root at R4, that is, DISTm1.loc,R4.loc, DISTm2.loc,R4.loc, DISTm6.loc,R4.loc, and DISTm7.loc,R4.loc are all greater than 0, “R4” in VOs6 is not replaced and thus VOs6 remains unchanged. Due to the similar reason, in step ⑥, VOs6 still remains unchanged. At last, in step ⑦, after computing the last element R6 in Q, VOs6 is “m1m2R4R5m6m7”.Figure 5
An example of procedures ofVO construction (VOs6).To authenticate thesoundness of delivered messages, each subscriber si needs to scan their VOsi to recompute the hash value of the root of the TMR-tree and compare it against the root signature using the data owner’s public key distributed by the KDC. Since each VOsi includes the entries which have been visited during messages delivery, the subscriber can simulate the procedure of the TMR-tree traversal and recursively reconstruct each MBR and compute its hash value in a bottom-up manner. Specifically, each MBR and its hash value can be computed from the entries in its child node which are indicated by “[” and “]”.To authenticate thecompleteness of delivered messages, the subscriber si needs to check that each message in results is indeed present in VOsi and whether they satisfy the parameters δ and τ. What is more, the subscriber still needs to check that the other entries returned in the VOsi do not satisfy δ and τ.Example 7.
Still takings6 as an example, the subscriber can recursively reconstruct R3 from m1 and m2, R1 from R3 and R4, R6 from m6 and m7, R2 from R5 and R6, and at last the root from R1 and R2 and compute its hash value to compare it against the root signature to authenticate thesoundness of delivered messages m1, m2, m6, and m7. As for authenticating thecompleteness of m1, m2, m6, and m7, the subscriber needs to recompute whether they satisfy s6.δ=0.2 and s6.τ=0.7, while R4 and R5 do not.From the example we can see that when more than one message is delivered to a subscriber, only one signature is returned, thus reducing the communication and authentication cost.Space and Time Complexity. We first give a baseline method for the problem of authenticating messages in outsourced location-aware publish/subscribe services. Then, we give the space complexity of its VO and compare it with our proposed authenticated location-aware publish/subscribe framework. We also compare the authentication’s time complexity of baseline method and our framework.Baseline: the data owner signs every message within Δt′ and when the signed messages are delivered to their corresponding subscribers, each VOsi consists of the messages (to si) and their signatures. Then, the subscriber si can verify thesoundness by computing the hash value of each message in VOsi and comparing it against the message’s signature. Recomputing the spatio-textual similarity between each message in VOsi and the subscription si enables the subscriber to verify thecompleteness.The space complexity of theVO of baseline method is given by following proposition.Proposition 8.
If there arep messages which are delivered to a subscriber s at one time, the VO size for s, that is, the space complexity of VOs, is O∑i=1pmi+pS, where S is the size of the signature and each mi includes the size of its spatial and textual information.Compared with the baseline method, the space complexity ofVO of our proposed authenticated location-aware publish/subscribe framework is given by the following proposition.Proposition 9.
If there arep messages which are delivered to a subscriber s at one time, the space complexity of VOs is O∑i=1pmi+∑i=1qRi+S, where S is the size of the signature. Ri is a dummy message and we assume there are q dummy messages that are included in VOs.From the above propositions we can see that, in our proposed filter-verification framework with inverted index pruning technique, if more than one message is delivered to a subscriber, only one signature is returned. Although our framework hasq dummy messages in its VO, its VO size is still smaller than that of the baseline method when p is large since the signatures are space consuming.Since the authentication time is co-related to the size ofVO, the time complexity of authentication of our proposed filter-verification framework with inverted index pruning technique is also smaller than that of the baseline method.


## 3.1. Text-Aware Merkle R-Tree (TMR-Tree)

We first introduce the method of constructing theADS, called Text-aware Merkle R-tree (TMR-tree), at the data owner side. Consider a predefined maximum permissible delivery delay Δt. The data owner builds one TMR-tree on all the messages within every time interval Δt′ (Δt′≤Δt). Specifically, the TMR-tree has four main features:(i)
The messages inΔt′ are spatially organized in an R-tree.(ii)
Each node has a pseudo-text which includes the union of the keywords in its children’s texts. A nodeu with children v and w has pseudo-text u.text=v.text∪w.text.(iii)
Similar to theMHT, the TMR-tree stores one hash value in each node. Assume the default fanout of the TMR-tree is 2. A leaf node u with children (messages) v and w stores hash value Hu=hv∣w. An internal node u with children v and w stores hash value Hu=hv∣Hv∣w∣Hw, where Hv and Hw are the hash values of v and w. More specifically, the spatial and textual information of v (w) are both involved in the computation, that is, Hu=hv.loc∣v.text∣w.loc∣w.text if u is a leaf node in the TMR-tree and Hu=hv.loc∣v.text∣Hv∣w.loc∣w.text∣Hw if u is an internal node in the TMR-tree.(iv)
The hash value of the root of the TMR-tree is signed by the data owner, producing signatureS.Example 1.
Figure3 shows an example of the TMR-tree constructed over the messages in Figure 2. Here the fanout of the TMR-tree is set as 2. The leaf node R5 has a pseudo-text t5,t4,t3,t2,t1 which is the union of its children’s texts, that is, t5,t4,t3∪t5,t4,t2,t1 (m4.text∪m5.text). Since no matter the leaf or internal node is represented by a rectangle area (the Minimum Bounding Rectangle (MBR) of messages or other MBRs in it), its location is defined by two points which can be the bottom-left and upper-right points. For example, R6 is the MBR of m6 and m7 and its location includes the rectangle’s bottom-left and upper-right points (0.11,0.70 and 0.20,0.79). The leaf node R5 stores a hash value HR5 which summarizes the authentication information about R5 and it is computed through the spatial and textual information of its children (messages); that is, HR5=hm4.loc∣m4.text∣m5.loc∣m5.text. Similarly, the hash value stored in internal node R2 is computed through the spatial and textual information of its children and their hash values; that is, HR2=hR5.loc∣R5.text∣HR5∣R6.loc∣R6.text∣HR6.Figure 3
Illustration of TMR-tree (partial).


## 3.2. Filter-Verification Framework with Inverted Index Pruning

We use the idea of filter-verification framework proposed in [2] and, based on this, present an inverted index pruning technique to reduce the computational cost, thereby improving the efficiency of messages delivery.Since a location and a pseudo-text are associated with a node in the TMR-tree, each node in the TMR-tree can be treated as a dummy message. The main idea of our inverted index pruning technique is based on the following proposition.Proposition 2.
If some subscriptions in the inverted index ofspatial-oriented prefixes (L) are not relevant to a node R (a dummy message) in the TMR-tree, these subscriptions can be safely pruned from L since R’s children (other dummy messages or true messages) cannot be relevant to these subscriptions with certainty.Proof.
If a subscriptions in L is not relevant to a node R, we have ∃s∈L, SSIMs,R<LSBs∣t. According to (3), we have(8)max⁡0,1-DISTs.loc,R.locmaxDIST<LSBs∣t.∀R′∈R, that is, R′ is R’s child, since DISTs.loc,R′.loc≥DISTs.loc,R.loc, we have(9)max⁡0,1-DISTs.loc,R′.locmaxDIST≤max⁡0,1-DISTs.loc,R.locmaxDIST<LSBs∣t.Therefore, s is not relevant to R′ either.Algorithm1 shows the pseudo-code of our framework with the inverted index pruning technique. It takes the TMR-tree and L as input. For each node R and each message m in leaf nodes in the TMR-tree, we use R.Lr (m.Lr) to denote the inverted index where the subscriptions in R.Lr (m.Lr) are likely to be relevant to R (m), which is pruned from Lr of R’s (m’s) parent. We let R.Lp (m.Lp) denote Lr of R’s (m’s) parent. Thus, Lr of each node (or message) is pruned from its Lp, which is its parent’s Lr. In the beginning, we set the root’s Lp (i.e., TMR-tree.Root.Lp) as L, which is the inverted index ofspatial-oriented prefixes of all the subscriptions without any pruning (line (1)). Then, we initialize an empty stack T and push the root into it (lines (2)-(3)). In the filter phase, every element in T is computed until T is empty (lines (4)–(11)). First, we pop an element R from T (line (5)). Then, for each keyword ti in R.text, we retrieve the inverted list R.Lpti of ti and for each subscription sj in R.Lpti, if SSIMsj,R≥LSBsj∣ti, sj is added to R.Lrti (lines (6)–(9)). Other subscriptions which do not satisfy the condition in line (8) are pruned from R.Lp. If R.Lr≠∅ and R is not a message, that is, there exist some subscriptions in R.Lr which might be relevant to R’s children, R’s children are put into stack T (lines (10)-(11)). The subscriptions in each mi.Lr are the candidates which might be relevant to mi. In the verification phase, for each message mi, we verify whether each candidate sj in mi.Lr is the answer of mi and if yes, sj is added to the answer set of mi, that is, Ami (lines (12)–(15)). After computing all the messages in the TMR-tree, all the answer sets (Am1,Am2,…,AmM) are together returned (line (16)). Here we assume that there are M messages that come within Δt′. Each subscription in Ami is the delivery destination of the message mi.Algorithm 1:Filter-verification framework with inverted index pruning.
Input: TMR-tree: the text-aware Merkle R-tree on messages within Δt′; L: the inverted index of spatial-oriented prefixes
Output: Ami: answers of each message mi in the TMR-tree
(1) TMR-tree.Root.Lp=L;
(2) Initialize StackT;
(3)T.Push(TMR-tree.Root);
(4)while  Tis not emptydo
(5)R=T.Pop();
(6)foreach  ti∈R.text  do
(7)foreach  sj∈R.Lp(ti)  do
(8)if  SSIM(sj,R)≥LSBsj∣ti  then
(9)R.Lr(ti).Add(sj);
(10)if  R.Lr≠∅  and  Ris not a message  then
(11)T.Push(R.children);
(12)foreach  mi∈TMR-tree.leafnodesdo
(13)foreach  sj∈mi.Lr  do
(14)if  Verify(sj,mi)  then
(15)Ami.Add(sj);
(16) returnAm1,Am2,…,AmM;Example 3.
Figure4 shows an example of procedures of our proposed inverted index pruning technique in filter-verification framework. In step ①, the root is popped from stack T first. Then, for each keyword in Root.text (t1 to t5 and ∗), we retrieve the corresponding inverted list in Root.Lp to compute the spatial similarity between the root and each subscription in this inverted list. Take subscription s9 as an example, we retrieve Root.Lpt1 and compute the spatial similarity between the root and s9: SSIMs9,Root, which equals 1. Since SSIMs9,Root=1 is greater than LSBs9∣t1=0.60, s9 is added to Root.Lrt1. Notice that the values of spatial similarity between the root and s0, s1, s9 in Root.Lpt4 and s3, s7, s8 in Root.Lpt5 are smaller than the values of these subscriptions’ LSBs∣t; that is, they do not satisfy the condition in line (8) in Algorithm 1. Therefore, they are pruned from Root.Lp and are not added to Root.Lr. Then, since Root.Lr≠∅, its children R1 and R2 are pushed into stack T. Similarly, in step ②, s9 in R2.Lpt1, s9 in R2.Lpt2, s5 in R2.Lpt3, s2, s8 in R2.Lpt4, and s4 in R2.Lpt5 are pruned from R2.Lp. Note that, in step ③, since R6.text does not contain the keywords t3 and t5, we need not compute the spatial similarity between R6 and each subscription in inverted lists R6.Lpt3 and R6.Lpt5 (indicated by “###” in the example), and these subscriptions are also pruned from R6.Lp. At last, in step ④, the candidates which might be relevant to m6 are s0, s4, s5, s6, and s8. Compared with all the subscriptions in the unpruned inverted index L, the computational cost is reduced dramatically.Figure 4
An Example of procedures of filter-verification framework with inverted index pruning (partial).Time Complexity. For the convenience of comparison between the state-of-the-art method for location-aware publish/subscribe and our proposed filter-verification framework with inverted index pruning technique, we first give the time complexity of filter-verification framework proposed in [2] as the following proposition.Proposition 4.
The time complexity of delivering one messagem to its relevant subscriber s in filter-verification framework proposed in [2] is O∑t∈m.textLt+s.text, where L is the inverted index built on thespatial-oriented prefixes.Proof.
In the filter phase, for each keywordt in m.text (including the dummy keyword “∗”), the framework retrieves the inverted list Lt of t and for each subscription s in Lt, if SSIMs,m≥LSBs∣t, s is a candidate to the message m and we add it into the candidate set. Therefore, the time complexity of filtering is O∑t∈m.textLt.
In the verification phase, based on the spatio-textual similarity function (see (1)), s and m are relevant, if and only if(10)ws.text∩m.text=∑t∈s.text∩m.textwt≥s.τ-1-s.δ·SSIMs,ms.δ·ws.text.SSIM(s,m) can be easily computed in O1 time and ws.text can be materialized; thus it is easy to compute s.τ-1-s.δ·SSIMs,m/s.δ·ws.text. To compute ws.text∩m.text, we check whether each keyword t in s.text appears in m.text. If yes, we add the corresponding weight wt into ws.text∩m.text. To facilitate the checking, we build a hash map for keywords in m.text. (We only need to build the hash map for the message once.) Thus the time complexity of verifying a subscription s is Os.text. Therefore, the time complexity of delivering one message m to its relevant subscriber s in filter-verification framework proposed in [2] is O∑t∈m.textLt+s.text‍.The time complexity of our proposed filter-verification framework with inverted index pruning technique is given by the following proposition.Proposition 5.
The time complexity of deliveringM messages that come within Δt′ to their relevant subscribers in our proposed filter-verification framework with inverted index pruning technique is O∑i=11-M/1-f∑t∈Ri.textRi.Lpt+∑i=1Msi.text, where f is the fanout of the TMR-tree, Ri is a node in the TMR-tree (also can be treated as a dummy message), and Lp is the inverted index associated with Ri’s parent in which the subscriptions are likely to be relevant to Ri’s parent.Proof.
A TMR-tree is constructed over theM messages that come within Δt′. If the fanout of the TMR-tree is f, in the worst case, the height of the TMR-tree (excluding the layer of messages) is h=logfM. Thus, the number of internal and leaf nodes in the TMR-tree (assuming the root has depth 1) is(11)f0+⋯+fh-1=1-fh1-f=1-flogfM1-f=1-M1-f.
In the filter phase, when visiting a nodeR (or a message m) in the TMR-tree, we retrieve its Lp, prune R.Lp (or m.Lp), and generate R.Lr (or m.Lr). Therefore, the time complexity of filtering with inverted index pruning is O∑i=11-M/1-f∑t∈Ri.textRi.Lpt.
In the verification phase, suppose each messagem within Δt′ is delivered to only one subscriber. The time complexity of verifying whether M subscriptions are the answers of messages is O∑i=1Msi.text. Therefore, the time complexity of delivering M messages that come within Δt′ to their relevant subscribers in our proposed filter-verification framework with inverted index pruning technique is O∑i=11-M/1-f∑t∈Ri.textRi.Lpt+∑i=1Msi.text.Compared with the filter-verification framework proposed in [2], our proposed filter-verification framework with inverted index pruning technique needs to visit more inverted indexes (the inverted indexes associated with internal and leaf nodes in the TMR-tree). However, since the subscriptions in each node’s inverted index are constantly pruned from the root to the leaf nodes in the TMR-tree, the total times of inverted index traversal are reduced. Therefore, our proposed filter-verification framework with inverted index pruning technique can be considered efficient, which also can be demonstrated from our experimental study (Section 4).


## 3.3.VO Construction and Authentication

After finding the subscribers who are the delivery destinations of messages, that is,Ami, the service provider still needs to construct a VO for each subscriber for their authentication. Algorithm 2 shows the pseudo-code of constructing the VO. It takes the TMR-tree and answers of each message mi (Ami) as input. First, we initialize a VO for each subscription in Am1∪Am2∪⋯∪AmM (VOsi) with the root of the TMR-tree (lines (1)-(2)). Then, we initialize an empty queue Q and put the root into it (lines (3)-(4)). Every element in Q is computed until Q is empty (lines (5)–(12)). When the distance between a message mi and the picked element R (from Q) is smaller than 0, that is, mi is in the subtree rooted at R, for each subscription si in Ami, we replace R in VOsi with three parts: (1) the token “[”; (2) R’s children; and (3) the token “]” (lines (6)–(10)). Note that we use a pair of tokens “[” and “]” to indicate the scope of the entries in R. Then, if R’s children are not in Q and they are not messages, they are put into Q (lines (11)-(12)). At last, the constructed VOsi is delivered to each subscriber si with the corresponding messages (line (13)). Here we assume that there are N subscribers to whom the messages will be delivered.Algorithm 2:
V
O construction.
Input: TMR-tree: a text-aware Merkle R-tree on messages within Δt′; Ami: answers of each message mi in the TMR-tree
Output: VOsi: the VO for each subscription si
(1)foreach  si∈Am1∪Am2∪⋯∪AmM  do
(2)VOsi.Init(TMR-tree.Root);
(3) Initialize QueueQ;
(4)Q.Put(TMR-tree.Root);
(5)whileQis not emptydo
(6)R=Q.Pick();
(7)foreach  mi∈TMR-tree.leafnodesdo
(8)if  Distmi,R≤0  then
(9)foreach  sj∈Ami  do
(10)VOsj.Replace(R, “[” + R.children + “]”);
(11)if  R.childrenarenotinQ  andtheyarenotmessages  then
(12)Q.Put(R.children);
(13) returnVOs1,VOs2,…,VOsN;Example 6.
Following the example in Figure2, after computing the delivery destinations of messages m1 to m7, we obtain their answer sets as follows: Am1:s6, Am2:s5,s6, Am3:s5, Am4:s2,s3,s7,s10, Am5:s0,s3,s4,s7,s8, Am6:s6, and Am7:s6. Here we take the construction of the VO of s6 (VOs6) as an example (shown in Figure 5) and messages m1, m2, m6, and m7 will be delivered to s6. In step ①, the root is picked from the queue Q. Obviously, DISTm1.loc,root.loc, DISTm2.loc,root.loc, DISTm6.loc,root.loc, and DISTm7.loc,root.loc are all smaller than 0. Therefore, we replace “root” in VOs6 with “R1R2”. Since R1 and R2 are not in Q and they are not messages, they are put into Q. The steps ②, ③, and ④ are similar to ①. In step ⑤, since m1, m2, m6, and m7 are not in the subtree root at R4, that is, DISTm1.loc,R4.loc, DISTm2.loc,R4.loc, DISTm6.loc,R4.loc, and DISTm7.loc,R4.loc are all greater than 0, “R4” in VOs6 is not replaced and thus VOs6 remains unchanged. Due to the similar reason, in step ⑥, VOs6 still remains unchanged. At last, in step ⑦, after computing the last element R6 in Q, VOs6 is “m1m2R4R5m6m7”.Figure 5
An example of procedures ofVO construction (VOs6).To authenticate thesoundness of delivered messages, each subscriber si needs to scan their VOsi to recompute the hash value of the root of the TMR-tree and compare it against the root signature using the data owner’s public key distributed by the KDC. Since each VOsi includes the entries which have been visited during messages delivery, the subscriber can simulate the procedure of the TMR-tree traversal and recursively reconstruct each MBR and compute its hash value in a bottom-up manner. Specifically, each MBR and its hash value can be computed from the entries in its child node which are indicated by “[” and “]”.To authenticate thecompleteness of delivered messages, the subscriber si needs to check that each message in results is indeed present in VOsi and whether they satisfy the parameters δ and τ. What is more, the subscriber still needs to check that the other entries returned in the VOsi do not satisfy δ and τ.Example 7.
Still takings6 as an example, the subscriber can recursively reconstruct R3 from m1 and m2, R1 from R3 and R4, R6 from m6 and m7, R2 from R5 and R6, and at last the root from R1 and R2 and compute its hash value to compare it against the root signature to authenticate thesoundness of delivered messages m1, m2, m6, and m7. As for authenticating thecompleteness of m1, m2, m6, and m7, the subscriber needs to recompute whether they satisfy s6.δ=0.2 and s6.τ=0.7, while R4 and R5 do not.From the example we can see that when more than one message is delivered to a subscriber, only one signature is returned, thus reducing the communication and authentication cost.Space and Time Complexity. We first give a baseline method for the problem of authenticating messages in outsourced location-aware publish/subscribe services. Then, we give the space complexity of its VO and compare it with our proposed authenticated location-aware publish/subscribe framework. We also compare the authentication’s time complexity of baseline method and our framework.Baseline: the data owner signs every message within Δt′ and when the signed messages are delivered to their corresponding subscribers, each VOsi consists of the messages (to si) and their signatures. Then, the subscriber si can verify thesoundness by computing the hash value of each message in VOsi and comparing it against the message’s signature. Recomputing the spatio-textual similarity between each message in VOsi and the subscription si enables the subscriber to verify thecompleteness.The space complexity of theVO of baseline method is given by following proposition.Proposition 8.
If there arep messages which are delivered to a subscriber s at one time, the VO size for s, that is, the space complexity of VOs, is O∑i=1pmi+pS, where S is the size of the signature and each mi includes the size of its spatial and textual information.Compared with the baseline method, the space complexity ofVO of our proposed authenticated location-aware publish/subscribe framework is given by the following proposition.Proposition 9.
If there arep messages which are delivered to a subscriber s at one time, the space complexity of VOs is O∑i=1pmi+∑i=1qRi+S, where S is the size of the signature. Ri is a dummy message and we assume there are q dummy messages that are included in VOs.From the above propositions we can see that, in our proposed filter-verification framework with inverted index pruning technique, if more than one message is delivered to a subscriber, only one signature is returned. Although our framework hasq dummy messages in its VO, its VO size is still smaller than that of the baseline method when p is large since the signatures are space consuming.Since the authentication time is co-related to the size ofVO, the time complexity of authentication of our proposed filter-verification framework with inverted index pruning technique is also smaller than that of the baseline method.


## 4. Experimental Study

In this section, we proceed to conduct extensive experiments to evaluate the performance of our proposed authenticated location-aware publish/subscribe framework.


### 4.1. Experiment Setup

#### 4.1.1. Datasets

Similar to [2], we use a real-world dataset POI which contains 10 million points of interests in USA. We randomly select 1–5 keywords from each POI to generate subscriptions. Thus the average keyword number in each subscription is 3. The maximum permissible response delay Δt and the messages delivery interval Δt′ (Δt′≤Δt) are both set as 5 mins. During this interval, we randomly select 2000 POIs as messages. To generate long messages, we combine 10 POIs as a single message. The average keyword number in each message is 41.


#### 4.1.2. Parameters

The performance of our proposed framework is evaluated by varying the preferences.δ (0.1, 0.3, 0.5, 0.7, and 0.9) and threshold s.τ (0.5, 0.6, 0.7, 0.8, and 0.9). We set s.δ as 0.5 and s.τ as 0.7 in the default setting. When we vary a parameter, the other parameter will be in the default setting. We use inverted document frequency (IDF) to generate keywords weights.


#### 4.1.3. System Configuration

All the experiments are run on a server with Intel(R) Xeon(R) CPU E5-2609 v2 @2.5 GHz (Quad Core) and 64 GB RAM, running Linux Ubuntu. We use in-memory setting and the programs are implemented in C++.


#### 4.1.4. Performance Metrics

The metrics for performance evaluation include(i)
PAS and PC: percentage of accessed subscriptions and candidates, which indicate the ratios of accessed subscriptions in the inverted index ofspatial-oriented prefixes and candidates to the number of total subscriptions(ii)
FS: time of finding the relevant subscriptions for each message withinΔt′(iii)
CVO: time of constructing theVO(iv)
VOS:VO size, which affects the communication cost between the service provider and subscribers(v)
AM: time of authenticating the messages at the subscribers sideNote that, in our framework, we process a batch of messages at one time; thus each time we first get a total value of each metric. Then, for the metrics PAS, PC, and FS, we report the average value corresponding to each message and, for the metrics CVO, VOS, and AM, we report the average value corresponding to each subscriber.


#### 4.1.5. Algorithms

For metrics (i), (ii), and (iii), algorithms to be evaluated in our experiments include (1) SP (the method of finding the relevant subscriptions for each message using thespatial-oriented prefixes, which is proposed in [2]); (2) SP + IIP (our filter-verification framework with inverted index pruning technique); (3) VOC (our method of constructing the VO).For metrics (iv) and (v), algorithms to be evaluated include (1) ALPF (our authenticated location-aware publish/subscribe framework) and (2) BL (the baseline method).Note that, to the best of our knowledge, this is the first attempt to define and solve the problem of authenticating messages in outsourced location-aware publish/subscribe services. Therefore, no existing algorithm is included in our experiments as comparative analysis.


### 4.2. Performance Study

#### 4.2.1. Cost at the Service Provider

The cost at the service provider is evaluated from two aspects. First, in Figure6, we evaluate the ratios of accessed subscriptions and candidates (as a function of s.δ and s.τ) to the number of total subscriptions (PAS and PC), where the accessed subscriptions refer to subscriptions that are accessed in the inverted index and candidates refer to subscriptions that are verified using the Verify function in Algorithm 1. Second, as shown in Figure 7, we evaluate the running time (as a function of s.δ and s.τ), which includes the time of finding the relevant subscriptions for each message (FS) and constructing the VO (CVO).Figure 6
Evaluation of PAS and PC.
(a)
Varyingsδ
(b)
VaryingsτFigure 7
Evaluation of FS and CVO.
(a)
Varyingsδ
(b)
VaryingsτAccording to Figures6 and 7, we make the following observations. First, SP + IIP outperforms SP; that is, the PAS and PC of SP + IIP are both smaller than those of SP (shown in Figure 6). Besides, FS of SP + IIP is smaller than that of SP (shown in Figure 7). The reason lies in that SP + IIP uses the inverted index pruning technique to prune the subscriptions from the inverted index ofspatial-oriented prefixes. These pruned subscriptions are not relevant to the messages and thus they need not be involved in the computation. Second, with the increase of s.τ, the performance of SP and SP + IIP increases, because for larger s.τ there are smaller number of subscriptions required to be visited and verified, and we have greater opportunity to prune more irrelevant subscriptions. Third, with the decrease of s.δ, SP and SP + IIP take much longer time, because for smaller s.δ, the spatial similarity is more important and they cannot estimate accurate prefix bounds. Fourth, as s.δ (s.τ) increases, CVO increases (decreases) slightly since we use the answers of each message to construct the VO and CVO depending on the number of answers. With the increase of s.δ (s.τ), we get more (less) answers and thus CVO increases (decreases). Fifth, although in our framework it costs extra time to construct VO for subscribers’ authentication, the total running time (FS + CVO) is still better than SP. For example, in Figure 7, when s.δ=0.3, SP + IIP costs around 60 ms and VOC costs about 20 ms, thus the total running time is about 80 ms, which is still less than the cost of SP, 90 ms.


#### 4.2.2. Cost between the Service Provider and Subscribers

We evaluate the metric VOS, that is,VO size, which affects the communication overhead between the service provider and subscribers. Figure 8 shows VOS under the experimental settings by varying s.δ and s.τ.Figure 8
Evaluation of VOS.
(a)
Varyingsδ
(b)
VaryingsτFrom Figure8, we make the following observations. First, ALPF outperforms BL since we process a batch of messages rather than only one message at a time and when many messages are delivered to a subscriber si, the VOsi consists of only one signature, which is computed using the root hash value of the TMR-tree. However, in BL, the VOsi would include the signatures of every message. Second, with the increase of s.δ (s.τ), VOS increases (decreases) in a near linear manner. The reason lies in that VOS depends on the number of messages delivered to each subscriber. When s.δ (s.τ) increases, the number of answers of each message increases (decreases) and, conversely, the number of messages delivered to each subscriber increases (decreases). Third, the biggest value of VOS is about 240 KB when s.τ=0.5. This value is acceptable especially when more than one message needs to be verified by a subscriber.


#### 4.2.3. Cost at the Subscribers

The last metric AM, that is, the time of authenticating the messages at the subscribers side, is evaluated. AM is crucial since the subscribers may have limited computing resources. Figure9 shows AM as a function of s.δ and s.τ.Figure 9
Evaluation of AM.
(a)
Varyingsδ
(b)
VaryingsτAccording to Figure9, we first find that, in ALPF, it always costs subscribers less time to authenticate the messages delivered to them than that in BL. This is because in ALPF when thesoundness is verified, subscribers just need to decrypt one signature and recompute the root hash value of the TMR-tree to compare against it. However, in BL, the number of decryption operations equals the number of messages delivered to the subscribers but decryption is not a cheap operation comparing with the hashing operation. Thus, ALPF outperforms BL. Second, we find that, with the increase of s.δ (s.τ), AM increases (decreases) in a near linear manner since AM is always related to VOS and they have the same changing situation. Third, the worst case of authenticating the messages costs subscribers about 1.2 s, which is reasonable and would not have too many bad effects on the subscribers experience.


#### 4.2.4. Security Analysis

In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. Therefore, our goal of security analysis is to prove that our proposed authenticated location-aware publish/subscribe framework can guarantee the verification ofsoundness andcompleteness of messages by their corresponding subscribers.Proof of Soundness.
Assume that a messagem delivered to a subscriber s is bogus or modified. In this paper, we adopt the commonly used hash function SHA1 [3]. Because SHA1 is collision-resistant and the hash value of the root of the TMR-tree is computed recursively from the messages that come within Δt′, which must include m, the recomputed root hash value of the TMR-tree cannot be verified against the signature, which can be detected by the subscriber s. Therefore, through our framework, subscribers can receivesound messages from the service provider.Proof of Completeness.
Letm be a message satisfying the parameters δ and τ which is delivered to a subscriber s. For the recomputed hash value of the root of the TMR-tree to match the signature (i.e., thesoundness is satisfied), there are the following two cases: (i)
The messagem is included in the corresponding VOs. In this case, the subscriber s can confirm whether this message is the result of using the returned spatial and textual information of m.(ii)
The messagem is not included in the corresponding VOs. In this case, it must be in the subtree rooted at R which is included in VOs. However, the subscriber s cannot make sure that R does not satisfy δ and τ since if m is the result, R must satisfy δ and τ, which alarms the subscriber about potential violation of thecompleteness.
Therefore, through our framework, subscribers can receivecomplete messages from the service provider.


## 4.1. Experiment Setup

### 4.1.1. Datasets

Similar to [2], we use a real-world dataset POI which contains 10 million points of interests in USA. We randomly select 1–5 keywords from each POI to generate subscriptions. Thus the average keyword number in each subscription is 3. The maximum permissible response delay Δt and the messages delivery interval Δt′ (Δt′≤Δt) are both set as 5 mins. During this interval, we randomly select 2000 POIs as messages. To generate long messages, we combine 10 POIs as a single message. The average keyword number in each message is 41.


### 4.1.2. Parameters

The performance of our proposed framework is evaluated by varying the preferences.δ (0.1, 0.3, 0.5, 0.7, and 0.9) and threshold s.τ (0.5, 0.6, 0.7, 0.8, and 0.9). We set s.δ as 0.5 and s.τ as 0.7 in the default setting. When we vary a parameter, the other parameter will be in the default setting. We use inverted document frequency (IDF) to generate keywords weights.


### 4.1.3. System Configuration

All the experiments are run on a server with Intel(R) Xeon(R) CPU E5-2609 v2 @2.5 GHz (Quad Core) and 64 GB RAM, running Linux Ubuntu. We use in-memory setting and the programs are implemented in C++.


### 4.1.4. Performance Metrics

The metrics for performance evaluation include(i)
PAS and PC: percentage of accessed subscriptions and candidates, which indicate the ratios of accessed subscriptions in the inverted index ofspatial-oriented prefixes and candidates to the number of total subscriptions(ii)
FS: time of finding the relevant subscriptions for each message withinΔt′(iii)
CVO: time of constructing theVO(iv)
VOS:VO size, which affects the communication cost between the service provider and subscribers(v)
AM: time of authenticating the messages at the subscribers sideNote that, in our framework, we process a batch of messages at one time; thus each time we first get a total value of each metric. Then, for the metrics PAS, PC, and FS, we report the average value corresponding to each message and, for the metrics CVO, VOS, and AM, we report the average value corresponding to each subscriber.


### 4.1.5. Algorithms

For metrics (i), (ii), and (iii), algorithms to be evaluated in our experiments include (1) SP (the method of finding the relevant subscriptions for each message using thespatial-oriented prefixes, which is proposed in [2]); (2) SP + IIP (our filter-verification framework with inverted index pruning technique); (3) VOC (our method of constructing the VO).For metrics (iv) and (v), algorithms to be evaluated include (1) ALPF (our authenticated location-aware publish/subscribe framework) and (2) BL (the baseline method).Note that, to the best of our knowledge, this is the first attempt to define and solve the problem of authenticating messages in outsourced location-aware publish/subscribe services. Therefore, no existing algorithm is included in our experiments as comparative analysis.


## 4.1.1. Datasets

Similar to [2], we use a real-world dataset POI which contains 10 million points of interests in USA. We randomly select 1–5 keywords from each POI to generate subscriptions. Thus the average keyword number in each subscription is 3. The maximum permissible response delay Δt and the messages delivery interval Δt′ (Δt′≤Δt) are both set as 5 mins. During this interval, we randomly select 2000 POIs as messages. To generate long messages, we combine 10 POIs as a single message. The average keyword number in each message is 41.


## 4.1.2. Parameters

The performance of our proposed framework is evaluated by varying the preferences.δ (0.1, 0.3, 0.5, 0.7, and 0.9) and threshold s.τ (0.5, 0.6, 0.7, 0.8, and 0.9). We set s.δ as 0.5 and s.τ as 0.7 in the default setting. When we vary a parameter, the other parameter will be in the default setting. We use inverted document frequency (IDF) to generate keywords weights.


## 4.1.3. System Configuration

All the experiments are run on a server with Intel(R) Xeon(R) CPU E5-2609 v2 @2.5 GHz (Quad Core) and 64 GB RAM, running Linux Ubuntu. We use in-memory setting and the programs are implemented in C++.


## 4.1.4. Performance Metrics

The metrics for performance evaluation include(i)
PAS and PC: percentage of accessed subscriptions and candidates, which indicate the ratios of accessed subscriptions in the inverted index ofspatial-oriented prefixes and candidates to the number of total subscriptions(ii)
FS: time of finding the relevant subscriptions for each message withinΔt′(iii)
CVO: time of constructing theVO(iv)
VOS:VO size, which affects the communication cost between the service provider and subscribers(v)
AM: time of authenticating the messages at the subscribers sideNote that, in our framework, we process a batch of messages at one time; thus each time we first get a total value of each metric. Then, for the metrics PAS, PC, and FS, we report the average value corresponding to each message and, for the metrics CVO, VOS, and AM, we report the average value corresponding to each subscriber.


## 4.1.5. Algorithms

For metrics (i), (ii), and (iii), algorithms to be evaluated in our experiments include (1) SP (the method of finding the relevant subscriptions for each message using thespatial-oriented prefixes, which is proposed in [2]); (2) SP + IIP (our filter-verification framework with inverted index pruning technique); (3) VOC (our method of constructing the VO).For metrics (iv) and (v), algorithms to be evaluated include (1) ALPF (our authenticated location-aware publish/subscribe framework) and (2) BL (the baseline method).Note that, to the best of our knowledge, this is the first attempt to define and solve the problem of authenticating messages in outsourced location-aware publish/subscribe services. Therefore, no existing algorithm is included in our experiments as comparative analysis.


## 4.2. Performance Study

### 4.2.1. Cost at the Service Provider

The cost at the service provider is evaluated from two aspects. First, in Figure6, we evaluate the ratios of accessed subscriptions and candidates (as a function of s.δ and s.τ) to the number of total subscriptions (PAS and PC), where the accessed subscriptions refer to subscriptions that are accessed in the inverted index and candidates refer to subscriptions that are verified using the Verify function in Algorithm 1. Second, as shown in Figure 7, we evaluate the running time (as a function of s.δ and s.τ), which includes the time of finding the relevant subscriptions for each message (FS) and constructing the VO (CVO).Figure 6
Evaluation of PAS and PC.
(a)
Varyingsδ
(b)
VaryingsτFigure 7
Evaluation of FS and CVO.
(a)
Varyingsδ
(b)
VaryingsτAccording to Figures6 and 7, we make the following observations. First, SP + IIP outperforms SP; that is, the PAS and PC of SP + IIP are both smaller than those of SP (shown in Figure 6). Besides, FS of SP + IIP is smaller than that of SP (shown in Figure 7). The reason lies in that SP + IIP uses the inverted index pruning technique to prune the subscriptions from the inverted index ofspatial-oriented prefixes. These pruned subscriptions are not relevant to the messages and thus they need not be involved in the computation. Second, with the increase of s.τ, the performance of SP and SP + IIP increases, because for larger s.τ there are smaller number of subscriptions required to be visited and verified, and we have greater opportunity to prune more irrelevant subscriptions. Third, with the decrease of s.δ, SP and SP + IIP take much longer time, because for smaller s.δ, the spatial similarity is more important and they cannot estimate accurate prefix bounds. Fourth, as s.δ (s.τ) increases, CVO increases (decreases) slightly since we use the answers of each message to construct the VO and CVO depending on the number of answers. With the increase of s.δ (s.τ), we get more (less) answers and thus CVO increases (decreases). Fifth, although in our framework it costs extra time to construct VO for subscribers’ authentication, the total running time (FS + CVO) is still better than SP. For example, in Figure 7, when s.δ=0.3, SP + IIP costs around 60 ms and VOC costs about 20 ms, thus the total running time is about 80 ms, which is still less than the cost of SP, 90 ms.


### 4.2.2. Cost between the Service Provider and Subscribers

We evaluate the metric VOS, that is,VO size, which affects the communication overhead between the service provider and subscribers. Figure 8 shows VOS under the experimental settings by varying s.δ and s.τ.Figure 8
Evaluation of VOS.
(a)
Varyingsδ
(b)
VaryingsτFrom Figure8, we make the following observations. First, ALPF outperforms BL since we process a batch of messages rather than only one message at a time and when many messages are delivered to a subscriber si, the VOsi consists of only one signature, which is computed using the root hash value of the TMR-tree. However, in BL, the VOsi would include the signatures of every message. Second, with the increase of s.δ (s.τ), VOS increases (decreases) in a near linear manner. The reason lies in that VOS depends on the number of messages delivered to each subscriber. When s.δ (s.τ) increases, the number of answers of each message increases (decreases) and, conversely, the number of messages delivered to each subscriber increases (decreases). Third, the biggest value of VOS is about 240 KB when s.τ=0.5. This value is acceptable especially when more than one message needs to be verified by a subscriber.


### 4.2.3. Cost at the Subscribers

The last metric AM, that is, the time of authenticating the messages at the subscribers side, is evaluated. AM is crucial since the subscribers may have limited computing resources. Figure9 shows AM as a function of s.δ and s.τ.Figure 9
Evaluation of AM.
(a)
Varyingsδ
(b)
VaryingsτAccording to Figure9, we first find that, in ALPF, it always costs subscribers less time to authenticate the messages delivered to them than that in BL. This is because in ALPF when thesoundness is verified, subscribers just need to decrypt one signature and recompute the root hash value of the TMR-tree to compare against it. However, in BL, the number of decryption operations equals the number of messages delivered to the subscribers but decryption is not a cheap operation comparing with the hashing operation. Thus, ALPF outperforms BL. Second, we find that, with the increase of s.δ (s.τ), AM increases (decreases) in a near linear manner since AM is always related to VOS and they have the same changing situation. Third, the worst case of authenticating the messages costs subscribers about 1.2 s, which is reasonable and would not have too many bad effects on the subscribers experience.


### 4.2.4. Security Analysis

In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. Therefore, our goal of security analysis is to prove that our proposed authenticated location-aware publish/subscribe framework can guarantee the verification ofsoundness andcompleteness of messages by their corresponding subscribers.Proof of Soundness.
Assume that a messagem delivered to a subscriber s is bogus or modified. In this paper, we adopt the commonly used hash function SHA1 [3]. Because SHA1 is collision-resistant and the hash value of the root of the TMR-tree is computed recursively from the messages that come within Δt′, which must include m, the recomputed root hash value of the TMR-tree cannot be verified against the signature, which can be detected by the subscriber s. Therefore, through our framework, subscribers can receivesound messages from the service provider.Proof of Completeness.
Letm be a message satisfying the parameters δ and τ which is delivered to a subscriber s. For the recomputed hash value of the root of the TMR-tree to match the signature (i.e., thesoundness is satisfied), there are the following two cases: (i)
The messagem is included in the corresponding VOs. In this case, the subscriber s can confirm whether this message is the result of using the returned spatial and textual information of m.(ii)
The messagem is not included in the corresponding VOs. In this case, it must be in the subtree rooted at R which is included in VOs. However, the subscriber s cannot make sure that R does not satisfy δ and τ since if m is the result, R must satisfy δ and τ, which alarms the subscriber about potential violation of thecompleteness.
Therefore, through our framework, subscribers can receivecomplete messages from the service provider.


## 4.2.1. Cost at the Service Provider

The cost at the service provider is evaluated from two aspects. First, in Figure6, we evaluate the ratios of accessed subscriptions and candidates (as a function of s.δ and s.τ) to the number of total subscriptions (PAS and PC), where the accessed subscriptions refer to subscriptions that are accessed in the inverted index and candidates refer to subscriptions that are verified using the Verify function in Algorithm 1. Second, as shown in Figure 7, we evaluate the running time (as a function of s.δ and s.τ), which includes the time of finding the relevant subscriptions for each message (FS) and constructing the VO (CVO).Figure 6
Evaluation of PAS and PC.
(a)
Varyingsδ
(b)
VaryingsτFigure 7
Evaluation of FS and CVO.
(a)
Varyingsδ
(b)
VaryingsτAccording to Figures6 and 7, we make the following observations. First, SP + IIP outperforms SP; that is, the PAS and PC of SP + IIP are both smaller than those of SP (shown in Figure 6). Besides, FS of SP + IIP is smaller than that of SP (shown in Figure 7). The reason lies in that SP + IIP uses the inverted index pruning technique to prune the subscriptions from the inverted index ofspatial-oriented prefixes. These pruned subscriptions are not relevant to the messages and thus they need not be involved in the computation. Second, with the increase of s.τ, the performance of SP and SP + IIP increases, because for larger s.τ there are smaller number of subscriptions required to be visited and verified, and we have greater opportunity to prune more irrelevant subscriptions. Third, with the decrease of s.δ, SP and SP + IIP take much longer time, because for smaller s.δ, the spatial similarity is more important and they cannot estimate accurate prefix bounds. Fourth, as s.δ (s.τ) increases, CVO increases (decreases) slightly since we use the answers of each message to construct the VO and CVO depending on the number of answers. With the increase of s.δ (s.τ), we get more (less) answers and thus CVO increases (decreases). Fifth, although in our framework it costs extra time to construct VO for subscribers’ authentication, the total running time (FS + CVO) is still better than SP. For example, in Figure 7, when s.δ=0.3, SP + IIP costs around 60 ms and VOC costs about 20 ms, thus the total running time is about 80 ms, which is still less than the cost of SP, 90 ms.


## 4.2.2. Cost between the Service Provider and Subscribers

We evaluate the metric VOS, that is,VO size, which affects the communication overhead between the service provider and subscribers. Figure 8 shows VOS under the experimental settings by varying s.δ and s.τ.Figure 8
Evaluation of VOS.
(a)
Varyingsδ
(b)
VaryingsτFrom Figure8, we make the following observations. First, ALPF outperforms BL since we process a batch of messages rather than only one message at a time and when many messages are delivered to a subscriber si, the VOsi consists of only one signature, which is computed using the root hash value of the TMR-tree. However, in BL, the VOsi would include the signatures of every message. Second, with the increase of s.δ (s.τ), VOS increases (decreases) in a near linear manner. The reason lies in that VOS depends on the number of messages delivered to each subscriber. When s.δ (s.τ) increases, the number of answers of each message increases (decreases) and, conversely, the number of messages delivered to each subscriber increases (decreases). Third, the biggest value of VOS is about 240 KB when s.τ=0.5. This value is acceptable especially when more than one message needs to be verified by a subscriber.


## 4.2.3. Cost at the Subscribers

The last metric AM, that is, the time of authenticating the messages at the subscribers side, is evaluated. AM is crucial since the subscribers may have limited computing resources. Figure9 shows AM as a function of s.δ and s.τ.Figure 9
Evaluation of AM.
(a)
Varyingsδ
(b)
VaryingsτAccording to Figure9, we first find that, in ALPF, it always costs subscribers less time to authenticate the messages delivered to them than that in BL. This is because in ALPF when thesoundness is verified, subscribers just need to decrypt one signature and recompute the root hash value of the TMR-tree to compare against it. However, in BL, the number of decryption operations equals the number of messages delivered to the subscribers but decryption is not a cheap operation comparing with the hashing operation. Thus, ALPF outperforms BL. Second, we find that, with the increase of s.δ (s.τ), AM increases (decreases) in a near linear manner since AM is always related to VOS and they have the same changing situation. Third, the worst case of authenticating the messages costs subscribers about 1.2 s, which is reasonable and would not have too many bad effects on the subscribers experience.


## 4.2.4. Security Analysis

In this paper, we study the problem of authenticating messages in outsourced location-aware publish/subscribe services. Therefore, our goal of security analysis is to prove that our proposed authenticated location-aware publish/subscribe framework can guarantee the verification ofsoundness andcompleteness of messages by their corresponding subscribers.Proof of Soundness.
Assume that a messagem delivered to a subscriber s is bogus or modified. In this paper, we adopt the commonly used hash function SHA1 [3]. Because SHA1 is collision-resistant and the hash value of the root of the TMR-tree is computed recursively from the messages that come within Δt′, which must include m, the recomputed root hash value of the TMR-tree cannot be verified against the signature, which can be detected by the subscriber s. Therefore, through our framework, subscribers can receivesound messages from the service provider.Proof of Completeness.
Letm be a message satisfying the parameters δ and τ which is delivered to a subscriber s. For the recomputed hash value of the root of the TMR-tree to match the signature (i.e., thesoundness is satisfied), there are the following two cases: (i)
The messagem is included in the corresponding VOs. In this case, the subscriber s can confirm whether this message is the result of using the returned spatial and textual information of m.(ii)
The messagem is not included in the corresponding VOs. In this case, it must be in the subtree rooted at R which is included in VOs. However, the subscriber s cannot make sure that R does not satisfy δ and τ since if m is the result, R must satisfy δ and τ, which alarms the subscriber about potential violation of thecompleteness.
Therefore, through our framework, subscribers can receivecomplete messages from the service provider.


## 5. Related Work

Our work is related to the location-aware publish/subscribe and authenticated query processing. Sections5.1 and 5.2 retrospect the related work done in these areas.


### 5.1. Location-Aware Publish/Subscribe

Recently, location-aware publish/subscribe has attracted considerable attention. Most studies in this field can be categorized according to different evaluation methods of relevancy between subscriptions and messages [2, 4–8]. In particular, [4–7] use a spatial region to indicate the spatial information of each subscription and spatial overlap to evaluate spatial similarity and “AND”, “OR” semantics or Boolean expressions to evaluate textual relevancy, while [2, 8] combine the textual relevancy and spatial similarity into a ranking function to quantify the relevancy between subscriptions and messages.More specifically, regarding the first category, Chen et al. [4] study the problem of matching Boolean range continuous queries over a stream of incoming spatio-textual messages in real time. A Boolean range continuous query is to continually retrieve the spatio-textual messages arriving before the user-specified expiration time such that the retrieved spatio-textual messages satisfy the user’s keywords which are connected by “AND” or “OR” semantics and are located in the query range. The authors present IQ-Tree, which is a hybrid index based on Quad-tree and inverted files. In [5], Li et al. study the location-aware publish/subscribe, which delivers a message to its corresponding subscribers having spatial overlap with the message and all the keywords in the subscriptions are contained in the message (“AND” semantic). They propose the Rt-tree, which extends the R-tree by selecting some representative keywords from subscriptions and adding them into R-tree nodes to enable textual pruning. Both matching algorithms of [4, 5] follow the filtering-and-refinement paradigm. More recently, although they study the same problem, Wang et al. [6] find that, in [4, 5], the spatial factor is always prioritized during the index construction regardless of the keyword distribution of the query set and the inverted indexing technique is not well-suited to textual filtering. Therefore, they utilize the keyword partition and space partition in one tree structure when constructing the index for queries based on expected matching cost. They compute the cost based on the number of queries associated with each partition and the probability of whether the partition is explored during message matching, instead of the complexity of filter and verification steps. Guo et al. [7] study filtering dynamic streams for continuous moving Boolean subscriptions. Different from previous works, it continuously monitors users’ locations and sends nearby messages in real time and it allows users to specify their interests with Boolean expressions, which provides better flexibility and expressiveness in shaping an interest.With respect to the second category, as introduced in Section2.3, Hu et al. [2] study the parameterized location-aware publish/subscribe, which requires subscribers to specify parameters to enable personalized filtering. In [8], Chen et al. study top-k spatial-keyword publish/subscribe, which aims to continuously feed the user with new spatio-textual messages whose temporal spatial-keyword scores are ranked within the top-k. They use a Quad-tree to partition the whole space. Each subscription is assigned to a number of covering cells, forming a disjoint partition of the entire space and an inverted file ordered by subscription id is built to organize the subscriptions assigned to each cell.


### 5.2. Authenticated Query Processing

Authenticated query processing has been studied extensively. Most studies on query authentication are based on anADS, Merkle hash tree (MHT) [1], as introduced in Section 2.3. The notion of the MHT is generalized to multiway trees and widely adapted to various index structures. Typical examples include the Merkle B-tree and its variant Embedded Merkle B-tree [9]. Following the concept of the MHT, the authenticated query processing problem has also been studied for the relational data [9, 10], data streams [11–15], and textual search engines [16].In the spatial databases domain, based on theMHT, there are also many query authentication applications. Yang et al. [17] first introduce the query authentication problem to the domain of spatial data and study the authentication of spatial range queries. They propose an ADS called MR-tree, which combines the ideas of MB-tree [9] and R∗-tree [18]. Yiu et al. investigate how to efficiently authenticate moving kNN queries [19], moving range queries [20], and shortest-path queries [21]. More recently, Hu et al. [22] and Chen et al. [23] develop new schemes for range and top-k query authentication that preserve the location privacy of queried objects. Besides, Lin et al. [24] investigate the authentication of location-based skyline queries. A new ADS called MR-Sky-tree is proposed. Authentication of reverse k nearest neighbor query is studied by Li et al. in [25]. For the mixed data types, such as spatio-textual data, Su et al. [26] and Wu et al. [27] study the authentication problem for snapshot and moving top-k spatial-keyword queries, respectively. Yan et al. [28] explore the authentication problem in the area of spatio-textual similarity joins. Instead of only supporting the relational data as [10] does, the proposed authentication schemes in [28] can support spatial data. Zhang et al. [29] study the authentication of location-based top-k queries which ask for the POIs in a certain region and with the highest k ratings for an interested POI attribute.Besides theMHT, there are some other index structures which can be used to construct the ADS, such as Voronoi diagram and prefix-tree. Hu et al. [30] propose a novel approach that authenticates spatial queries based on the neighborhood information derived from the Voronoi diagram. The problem of authenticating query results in data integration services is studied by Chen et al. in [31], which addresses multisource data authentication that can simultaneously support a wide range of query types. Based on the prefix-tree, they propose Homomorphic Secret Sharing Seal, which is to merge the authentication codes of nonresult values with a common prefix, thus allowing them to be verified as a whole.


## 5.1. Location-Aware Publish/Subscribe

Recently, location-aware publish/subscribe has attracted considerable attention. Most studies in this field can be categorized according to different evaluation methods of relevancy between subscriptions and messages [2, 4–8]. In particular, [4–7] use a spatial region to indicate the spatial information of each subscription and spatial overlap to evaluate spatial similarity and “AND”, “OR” semantics or Boolean expressions to evaluate textual relevancy, while [2, 8] combine the textual relevancy and spatial similarity into a ranking function to quantify the relevancy between subscriptions and messages.More specifically, regarding the first category, Chen et al. [4] study the problem of matching Boolean range continuous queries over a stream of incoming spatio-textual messages in real time. A Boolean range continuous query is to continually retrieve the spatio-textual messages arriving before the user-specified expiration time such that the retrieved spatio-textual messages satisfy the user’s keywords which are connected by “AND” or “OR” semantics and are located in the query range. The authors present IQ-Tree, which is a hybrid index based on Quad-tree and inverted files. In [5], Li et al. study the location-aware publish/subscribe, which delivers a message to its corresponding subscribers having spatial overlap with the message and all the keywords in the subscriptions are contained in the message (“AND” semantic). They propose the Rt-tree, which extends the R-tree by selecting some representative keywords from subscriptions and adding them into R-tree nodes to enable textual pruning. Both matching algorithms of [4, 5] follow the filtering-and-refinement paradigm. More recently, although they study the same problem, Wang et al. [6] find that, in [4, 5], the spatial factor is always prioritized during the index construction regardless of the keyword distribution of the query set and the inverted indexing technique is not well-suited to textual filtering. Therefore, they utilize the keyword partition and space partition in one tree structure when constructing the index for queries based on expected matching cost. They compute the cost based on the number of queries associated with each partition and the probability of whether the partition is explored during message matching, instead of the complexity of filter and verification steps. Guo et al. [7] study filtering dynamic streams for continuous moving Boolean subscriptions. Different from previous works, it continuously monitors users’ locations and sends nearby messages in real time and it allows users to specify their interests with Boolean expressions, which provides better flexibility and expressiveness in shaping an interest.With respect to the second category, as introduced in Section2.3, Hu et al. [2] study the parameterized location-aware publish/subscribe, which requires subscribers to specify parameters to enable personalized filtering. In [8], Chen et al. study top-k spatial-keyword publish/subscribe, which aims to continuously feed the user with new spatio-textual messages whose temporal spatial-keyword scores are ranked within the top-k. They use a Quad-tree to partition the whole space. Each subscription is assigned to a number of covering cells, forming a disjoint partition of the entire space and an inverted file ordered by subscription id is built to organize the subscriptions assigned to each cell.


## 5.2. Authenticated Query Processing

Authenticated query processing has been studied extensively. Most studies on query authentication are based on anADS, Merkle hash tree (MHT) [1], as introduced in Section 2.3. The notion of the MHT is generalized to multiway trees and widely adapted to various index structures. Typical examples include the Merkle B-tree and its variant Embedded Merkle B-tree [9]. Following the concept of the MHT, the authenticated query processing problem has also been studied for the relational data [9, 10], data streams [11–15], and textual search engines [16].In the spatial databases domain, based on theMHT, there are also many query authentication applications. Yang et al. [17] first introduce the query authentication problem to the domain of spatial data and study the authentication of spatial range queries. They propose an ADS called MR-tree, which combines the ideas of MB-tree [9] and R∗-tree [18]. Yiu et al. investigate how to efficiently authenticate moving kNN queries [19], moving range queries [20], and shortest-path queries [21]. More recently, Hu et al. [22] and Chen et al. [23] develop new schemes for range and top-k query authentication that preserve the location privacy of queried objects. Besides, Lin et al. [24] investigate the authentication of location-based skyline queries. A new ADS called MR-Sky-tree is proposed. Authentication of reverse k nearest neighbor query is studied by Li et al. in [25]. For the mixed data types, such as spatio-textual data, Su et al. [26] and Wu et al. [27] study the authentication problem for snapshot and moving top-k spatial-keyword queries, respectively. Yan et al. [28] explore the authentication problem in the area of spatio-textual similarity joins. Instead of only supporting the relational data as [10] does, the proposed authentication schemes in [28] can support spatial data. Zhang et al. [29] study the authentication of location-based top-k queries which ask for the POIs in a certain region and with the highest k ratings for an interested POI attribute.Besides theMHT, there are some other index structures which can be used to construct the ADS, such as Voronoi diagram and prefix-tree. Hu et al. [30] propose a novel approach that authenticates spatial queries based on the neighborhood information derived from the Voronoi diagram. The problem of authenticating query results in data integration services is studied by Chen et al. in [31], which addresses multisource data authentication that can simultaneously support a wide range of query types. Based on the prefix-tree, they propose Homomorphic Secret Sharing Seal, which is to merge the authentication codes of nonresult values with a common prefix, thus allowing them to be verified as a whole.


## 6. Conclusion

In this paper we have studied the problem of authenticating messages in outsourced location-aware publish/subscribe services. We propose an authenticated location-aware publish/subscribe framework, including anADS TMR-tree to organize the messages that come within Δt′, a filter-verification framework with inverted index pruning technique to efficiently deliver the messages to their relevant subscribers, and the methods of constructing the VO and authenticating the delivered messages at the subscribers side. Experimental results on a real-world dataset show that our framework achieves high performance.



---

*Source: 4215425-2017-09-25.xml*