Toward Efficient Navigation of Massive-Scale Geo-Textual Streams
Toward Efficient Navigation of Massive-Scale Geo-Textual Streams
复制标题
DOI：
10.24963/ijcai.2019/672
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Chengcheng Yang;Lisi Chen;Shuo Shang;Fan Zhu;Li Liu;Ling Shao
中科院分区：
文献类型：
--
作者：
Chengcheng Yang;Lisi Chen;Shuo Shang;Fan Zhu;Li Liu;Ling Shao
随着便携设备的普及，大量的应用不断地产生大量的地理标记文本数据流，从而对地理文本流数据的高效索引提出了挑战，这在数据管理和人工智能应用中都是一项重要的任务，例如实时数据流挖掘和定向广告。然而，使用最先进的索引方法是不可能的，因为它们专注于静态数据集的搜索优化，并且具有较高的索引维护成本。在本文中，我们提出了NQ-树，它结合了新的结构设计和自调整方法来在更新和搜索效率之间导航。我们的贡献包括：(1)设计了不同侧重点的多个存储，每个存储侧重于写友好和读友好；(2)利用数据压缩技术来降低I/O开销；(3)利用空间和关键字信息来提高剪枝效率；(4)提出了分析代价模型，并使用在线自调整方法来实现对不同负载的高效访问。在两个真实数据集上的实验表明，NQ-树的性能比两个精心设计的基线高出10倍。
With the popularization of portable devices, numerous applications continuously produce huge streams of geo-tagged textual data, thus posing challenges to index geo-textual streaming data efficiently, which is an important task in both data management and AI applications, e.g., real-time data streams mining and targeted advertising. This, however, is not possible with the state-of-the-art indexing methods as they focus on search optimizations of static datasets, and have high index maintenance cost. In this paper, we present NQ-tree, which combines new structure designs and self-tuning methods to navigate between update and search efficiency. Our contributions include: (1) the design of multiple stores each with a different emphasis on write-friendness and read-friendness; (2) utilizing data compression techniques to reduce the I/O cost; (3) exploiting both spatial and keyword information to improve the pruning efficiency; (4) proposing an analytical cost model, and using an online self-tuning method to achieve efficient accesses to different workloads. Experiments on two real-world datasets show that NQ-tree outperforms two well designed baselines by up to 10×.