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.
2. The Challenge of Verifiable 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.
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