• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of experimental algorithmics >Reverse-Safe Text Indexing
【24h】

Reverse-Safe Text Indexing

机译：反向安全文本索引

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We introduce the notion of reverse-safe data structures. These are data structures that prevent the reconstructionof the data they encode (i.e., they cannot be easily reversed). A data structure D is called z-reverse-safewhen there exist at least z datasets with the same set of answers as the ones stored by D. The main challengeis to ensure that D stores as many answers to useful queries as possible, is constructed efficiently, and hassize close to the size of the original dataset it encodes. Given a text of length n and an integer z, we proposean algorithm that constructs a z-reverse-safe data structure (z-RSDS) that has size O(n) and answers decisionand counting pattern matching queries of length at most d optimally, where d is maximal for any suchz-RSDS. The construction algorithm takes O(n~ω logd) time, where ω is the matrix multiplication exponent.We show that, despite the n~ω factor, our engineered implementation takes only a few minutes to finish formillion-letter texts. We also show that plugging our method in data analysis applications gives insignificantor no data utility loss. Furthermore, we show how our technique can be extended to support applicationsunder realistic adversary models. Finally, we show a z-RSDS for decision pattern matching queries, whosesize can be sublinear in n. A preliminary version of this article appeared in ALENEX 2020.
机译：我们介绍了反向安全数据结构的概念。这些是防止重建的数据结构他们编码的数据（即，它们不能轻易逆转）。数据结构D被称为Z反向安全当存在至少具有相同答案的数据集时作为D的相同答案。主要挑战是为了确保D存储尽可能多的答案，以有效地构建，并且具有大小接近它编码的原始数据集的大小。给定长度n和整数z的文本，我们提出一种构造具有大小O（n）和答案决定的z反向安全数据结构（z-rsds）的算法并在最佳地上计算长度的匹配的模式，其中d是最大的Z-RSD。施工算法需要O（n〜ωlogd）时间，其中ω是矩阵乘法指数。我们展示了，尽管是N〜ω因素，但我们的工程实施只需几分钟即可完成百万字母文本。我们还显示在数据分析应用中插入我们的方法提供了微不足道的或者没有数据实用丢失。此外，我们展示了如何扩展我们的技术以支持应用程序在现实的反对模型下。最后，我们为决策模式匹配查询显示一个Z-RSD，其大小可以在n中载入。 Alenex 2020中出现了本文的初步版本。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号