Optimally Leveraging Density and Locality for Exploratory Browsing and Sampling
Optimally Leveraging Density and Locality for Exploratory Browsing and Sampling
复制标题
最佳地利用密度和位置进行探索性浏览和采样
DOI：
10.1145/3209900.3209903
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Parameswaran, Aditya
中科院分区：
文献类型：
--
作者：
Kim, Albert;Xu, Liqi;Siddiqui, Tarique;Huang, Silu;Madden, Samuel;Parameswaran, Aditya
探索性数据分析通常涉及重复浏览满足某些谓词的少量记录样本。我们提出了一个快速的查询评估引擎，称为NeedleTail，旨在让分析师尽快浏览大型数据集上的查询结果的子集，独立于结果的整体大小。NeedleTail引入了DensityMaps，这是一种轻量级的内存索引结构，以及一组高效且理论上合理的算法，可以快速定位有希望的块，权衡局部性和密度。在使用样本计算总量的设置中，我们扩展了调查抽样的技术，以减轻样本中的偏差。我们的实验结果表明，NeedleTail在HDD上返回结果的速度平均快7倍，而占用的内存比现有技术少23倍。
Exploratory data analysis often involves repeatedly browsing a small sample of records that satisfy certain predicates. We propose a fast query evaluation engine, called NeedleTail, aimed at letting analysts browse a subset of the query result on large datasets as quickly as possible, independent of the overall size of the result. NeedleTail introduces DensityMaps, a lightweight in-memory indexing structure, and a set of efficient and theoretically sound algorithms to quickly locate promising blocks, trading off locality and density. In settings where the samples are used to compute aggregates, we extend techniques from survey sampling to mitigate the bias in our samples. Our experimental results demonstrate that NeedleTail returns results 7× faster on average on HDDs while occupying up to 23× less memory than existing techniques.
登录
查看更多内容
估计 Oracle 中时间受限的近似查询中的聚合
DOI：
--
发表时间：
2009
期刊：
International Conference on Extending Database Technology
影响因子：
--
作者：
Ying Hu;S. Sundara;Jagannathan Srinivasan
通讯作者：
Jagannathan Srinivasan
最佳地利用密度和位置来支持 LIMIT 查询
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Albert Kim;Liqi Xu;Tarique Siddiqui;Silu Huang;S. Madden;Aditya G. Parameswaran
通讯作者：
Aditya G. Parameswaran
面向新型用户的分析数据库技术：数据爱好者
DOI：
10.1145/2213836.2213902
发表时间：
2012
期刊：
Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data
影响因子：
--
作者：
P. Hanrahan
通讯作者：
P. Hanrahan
位图索引是数据仓库设计的合适方法
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
K. Sarika
通讯作者：
K. Sarika
位图索引
DOI：
--
发表时间：
2009
期刊：
Encyclopedia of Database Systems
影响因子：
--
作者：
C. Chan
通讯作者：
C. Chan