Verifiable Keyword-Based Semantic Similarity Search on Social Data Outsourcing

Yizhu Zou, Xin Yao, Zhigang Chen, Ming Zhao

Abstract

In the modern data economy, social data holds immense business value for market research and sentiment analysis. However, outsourcing this data to third-party providers introduces significant trust issues regarding the authenticity and completeness of query results. This paper proposes two verification schemes—basic and enhanced—to ensure the integrity of semantic similarity search results. Using a real-world Twitter dataset of 41.6 million tweets, we demonstrate that these schemes effectively detect dishonest behavior by providers with minimal computational and storage overhead.

1. Introduction

Social media platforms are goldmines for business intelligence. Organizations often acquire this data through third-party Social Data Providers (SDPs) who aggregate and resell platform data. This outsourcing model creates a "trust gap": a dishonest SDP might manipulate query results—by adding fake posts, deleting negative sentiment, or providing incomplete sets—to serve their own interests or those of a specific client. This paper addresses these risks by introducing a framework for verifiable keyword-based semantic similarity search.

The core problem lies in verifying semantic similarity searches. When a consumer queries for keywords and their semantic neighbors (e.g., "smartphone" and related brands), they must be certain that the results are both authentic (not tampered with) and complete (no relevant data omitted). While public APIs offer a window into the data, their rate limits and sampling (often 1%) make them insufficient for full-scale verification of the "firehose" data purchased from SDPs. Proving that something does not exist (completeness) is significantly more challenging than proving that a returned item is authentic.

3. Proposed Verification Methodologies

To address these vulnerabilities, the researchers propose two distinct solutions to keep SDPs honest:

3.1 The Basic Scheme (Probabilistic)

This leverages the OSN’s public APIs. Since these APIs usually return a random 1% sample of data, the consumer can collect this sample independently and check if it exists within the larger dataset provided by the SDP. If the SDP is deleting data, there is a high statistical probability that they will eventually delete one of the tweets the consumer found via the API, "tripping the alarm." This method is clever because it turns a platform limitation into a verification tool without requiring extra work from the OSN.

3.2 The Enhanced Scheme (Deterministic)

To move from "probably correct" to "guaranteed correct," the authors introduce a cryptographic approach:

  • NameNet: A hierarchical database that organizes keywords by "is-a" relationships (e.g., "iPhone 7" is a "Cell Phone"). This allows for precise semantic similarity measurements.
  • Merkle Hash Trees (MHTs): The OSN operator generates auxiliary information in the form of MHTs. One tree verifies the social content, while another verifies keyword relationships, ensuring the SDP traversed every possible similar keyword.
  • Verification Objects (VO): The SDP provides a cryptographic VO alongside query results. The consumer uses this to reconstruct the MHT root and compare it against a signature from the original OSN.

4. Experimental Evaluation and Results

The schemes were evaluated using a massive Twitter dataset containing 41.6 million tweets. The results confirm that the proposed methods are both effective and highly efficient.

Detection probability $p(\%)$ of the Basic Scheme as a function of the number of query results $\eta$ for various modification ratios $\gamma$.

As illustrated in the figure above, the detection probability in the Basic Scheme hits 100% once the query result size exceeds $10^4$ to $10^5$ tweets, depending on the fraction of data modified by the SDP. Furthermore, verification is extremely fast; even for large queries, a data consumer can verify the results in under one second on a standard server. The storage cost for the Enhanced Scheme scales linearly with the number of unique keywords, making it highly suitable for massive social networks.

5. Conclusion

This research provides a vital stepping stone toward a more transparent and trustworthy social data marketplace. By combining statistical sampling with cryptographic proofs, the proposed framework ensures that when companies buy data for business intelligence, they are receiving an authentic and complete representation of the social conversation.

Summary updated

Abstract

In the data-driven economy era, social data have tremendous business and potential values. Obtaining authentic social data is the first step in mining the business value of social data. In this paper, we consider an emerging social data outsourcing paradigm. Therein, different online social network (OSN) operators outsource their social data to a third-party social data provider (SDP), who resells them to data consumers who can be any individual or entities. However, a dishonest SDP may return untrusted query results to data consumers through various activities, such as adding fake data and deleting/modifying correct data. To deal with these dishonesties, we propose a basic scheme and an enhanced scheme to allow data consumers to verify the correctness and completeness of their received social data from the SDP. Data consumers in the basic scheme utilize the public APIs to collect the sampled social data and compare them with their received social data. This scheme is a probabilistic verification method as the data consumers only having a tiny proportion of the social data. To permit data consumers to verify the query results trustworthiness deterministically, we proposed an enhanced scheme, in which the OSN operator generates some cryptographic auxiliary information. The SDP can construct a verification object for the data consumer based on these information. Extensive experiments ran on a real Twitter dataset confirm that our schemes are effective and efficient.
BibTeX
@inproceedings{zou2018verifiable,
  author = {Yizhu Zou and Xin Yao and Zhigang Chen and Ming Zhao},
  title = {{Verifiable Keyword-Based Semantic Similarity Search on Social Data Outsourcing}},
  booktitle = {IEEE Access},
  year = {2018},
  doi = {10.1109/access.2018.2888685},
}
Figure