增量精炼的GIS交互查询的空间连接技术-

1、摘要:越来越多的新兴网络数据库应用程序处理大型地标数据集。然而,通过空间查询探索这些大型数据集十分耗费时间和资源。互动空间查询的需要出现在多项领域上,例如地理信息系统(GIS进行有效的决策支持。在本文中,我们提出一个新的GIS互动空间查询处理技术。我们提出一系列的增量精炼空间连接算法,到目前为止可以用来报告增量精炼运行集合查询同时显示元数据集采样的实际查询结果。我们的目标是最小化时间直到通过置信区间(congfidence interval衡量查询结果对于用户来说是可接受的精确的估计。我们的方法能够让更多的交互式数据探索和分析。在关系数据库中相似的已做了工作,据我们所知,这是第一次在GIS中使

2、用这个方法。我们通过大量的实验性能比较,调查和评估不同的抽样方法。基于真实和综合数据的实验显示当使用完全R树连接时,一个数量级(order of magnitude响应时间改善和最后获取的结果有关。我们也显示了不同索引结构对我们算法的性能影响通过使用三种有名的抽样方法。关键字:交互式查询,抽样,估计,置信区间,空间连接,窗口查询,R-树,人口比例,GIS1.介绍在很多领域和应用程序中使用GIS来探索大型地标数据集,为了获取直觉知识和洞察存储的信息。在GIS中为了不同的目的经常使用数据分析,比如,科学搜索和决策支持。这个数据分析与集合查询有直接关系比如空间连接。集合查询要求存取大容量的数据集并且

3、经常计算精确的数字查询结果。然而,计算精确的大数据集的查询结果会耗费很多时间由于完整的数据集大小和空间的地理相关数据比例。GIS和空间数据集提供了一些算法用来计算精确的空间数据的查询结果,其中一些算法对于探索大型空间数据集在时间上是不允许。在一些GIS应用程序中查询响应时间是挑剔的,因此,在合理的短时间内获取近似的查询结果远远比花费很长时间评估精确的结果要重要的多。比如,预先警告系统如洪水和火灾探测系统需要尽快的获取查询结果。这些系统将对是否疏散危险中的人们做出及时的决定。因为,它们需要在在查询数据处理的早期阶段检测出异常情况。在合理的错误范围内获取一个快速的查询结果比花费很长时间得到精确的结

4、果更好。图表1的例子显示了我们实验中使用的部分真实数据集的,这个实验是美国的煤矿资源,其参杂了地球化学松散的沉淀物(geochemical unconsolidated sediments。这个查询结果对分析如湖泊和河流这些沉淀物如何影响煤矿资源如盐石是很有帮助的。假设一些数据集需要相互关联,获取二个数据集的交集的准确数量要花费数天。一个近似的结果是足够的并且避免浪费计算时间,因此允许更有效率的数据挖掘。我们的目标就是加速GIS数据的挖掘处理同时提供一个估计结果的统计置信(statistical confidence。在这篇文章中,对于GIS的空间连接我们提出一个新的交互查询处理技术,它将返回

5、有界置信区间内的最终结果的增量精细运行估计,同时展示相连接的数据集的部分结果,一个近似的结果,界于say bounded by 5% of the exact answer with 95% probability (confidence level。这个近似结果通过使用数据集的子集计算所用时间是计算精确结果所用时间的十分之一。同时,目前用户能够看到真实的连接索引。为了使系统更加具有交互性,用户可以停止查询结果是当结果是足够好或者指定想得到的精度。在传统的GIS中,空间查询以模块化的形式生成,用户必须控制查询处理(query processing。用户只能提交他们的查询,等待很长时间看不到任何

6、结果直到最后一个结果返回。交互式查询处理(Interactive query processing方式能够为更有效率的数据挖掘和更有效率的决策支持提供灵活的方法。这个方法允许快速的获取查询结果是否有用的消息,因此能够更改查询处理或者相应的停止它。由于GIS查询主要用来获取大型数据集和他们之间的联系,这个交互式查询处理技术对GIS最终用户(GIS end users更加具有吸引力。用户经常希望形象化查询结果,在交互模式下实现将大大增加了GIS的实用性。有时仅仅一个集合查询结果(aggregate query result价值是足够的,我们的目的是最小化需求的时间提供部分结果以及任一想得到的集合价

7、值的一个有界置信区间估计。如果获取一个精确的结果的查询仅仅需要30s相比较而言使用我们方法获取一个估计值需要5s,这个方法是无意义的。另一方面,如果我们花费15min计算一个置信区间的有界估计与花费3h 计算一个精确结果相对比,我们的方法是很有吸引力的。当我们处理的GIS数据是字节或者系统大小时这种情景是可能的。因此,一些GIS应用程序会从我们的方法中获益。这篇文章是我们早期工作的拓展(4文献。在那篇文章中,我们提出IRSJ算法,提供了GIS数据挖掘的交互空间查询处理。通过使用增量随机的抽样方法:(索引水平和页水平样本获取合理精确的置信区间的查询估计,IRSJ算法实现降低执行时间。在这篇文章中

8、,我们扩展了用于GIS交互空间查询处理的抽样方法(sampling methods的综合研究。我们也研究了索引结构如何影响我们基于算法的抽样性能。这篇文章的主要结构如下:我们介绍一个新的交互查询处理技术应用于GIS空间连接,允许更有用的数据挖掘和更有效的决策支持。我们提供一系列的IRSJ算法通过一般化之前提出的(IRSJt and IRSJp算法并且通过提出一个新的称为分层增量精确的空间连接的IRSJ算法(IRSJs。(第三部分 我们的工作提供了处理空间连接的增量抽样方法的正式的分析。对于处理建立R树和变体索引的空间数据集的三个抽样方法,我们提供了一个综合研究。我们为样本方法提供公式以及提供了

9、他们准确性的统计证据。(第四部分大量的研究工作讨论了索引结构如果影响空间查询算法的性能。目的就是评估我们提出的算法的适用性和效率,我们把提出的算法应用在不同的索引结构上:R-树,R*树和STR 压缩R树.我们展示出IRSJ算法实现期望的性能无论哪种索引数据结构。(第五部分 我们为IRSJ算法提出一个分析消耗模型,与满树连接消耗模型做比较。而且,在进一步的实验评估中,我们展示了所提出的算法实验确认性。在我们的实验中,我们使用了合成数据和实际数据集,不用的数据分布在我们的实验。我们也做了我们方法的相比较的研究,对于基于R树全连接和变体的全连接,然后总结出我们的方法优于满树连接。这篇文章的其余结构如

10、下:第二部分我们提供了R-树索引结构和相关工作。第三部分展示了三个普通抽样方法基于统计和IRSJ算法的三个变体(IRSJt, IRSJs and IRSJp。第四部分,我们讨论了对于空间连接的一般统计和提供了获取估计的公式以及每个IRSJ算法的置信区间。第五部分,展示了IRSJ的分析消耗模型和三个ISRSJ算法的实验估计。第六部分总结这篇文章。2.相关工作GIS支持对于地理数据的数据管理(选择和存储以及修复操作(查询和显示。地理数据用来描述各种类型的几何形状和地理环境的各种类型位置。地理空间实体通过他们的特定的属性(比如密度以及他们与其他实体的空间关系(比如距离来描述。(29文献。地理或者空间

11、查询大多形成在一个空间索引数据库,为了获取基于数据实体之间空间关系的结果。(24文献一些空间关系的例子包括相交,包含,毗邻。同时我们的方法能使用在这些空间关系中的任意一个。在这片文章中,我们主要研究二个数据集之间的交集。R-树(13文献和R的变体是空间数据库最为广泛的索引结构。R*-树和使用不同的压缩算法的压缩R-树是R树变体的例子。R树是一个高度平衡的树结构改编于B-树来支持空间数据。一个R树存储了一个实体的最小外包络矩形(MBRs.R*-树和R-树之间最主要的不同是在R*-树(5文献种强制复插入的概念这将会生成一个更好的树结构。STR树使用了分类瓦片-递归算法(26文献。STR-树最主要的

12、思想是充分压缩叶子节点通过瓦片数据。与R树或者其他R-树变体比较,压缩R-树的数据结构更加平衡,更好的被利用。当我们对一个R-树索引数据集执行一个区域查询,在R-树上查询区域相交的所有外包络矩形会被取回。这是一个递归方式,从根节点开始顺其路径知道叶子节点。在空间数据库和GIS中,空间连接是最重要和消耗资源的查询之一。空间连接找出所有的实体,满足来自2个或更多关系的空间判断(如相交。一些基于R-树基础上的的空间连接算法(文献7,21,28,33提出了优化查询性能。在本文,我们的研究工作建立在先前从事的空间数据库和空间连接的相当可观的工作基础上。我们使用R树和它的变体作为索引结构并且展示了索引结构

13、如何影响我们算法的性能。我们提出的算法延续了一种相似得方法(由Papadias et a提出的文献33,提出多元空间连接算法,窗口降低算法被用于连接或者两个以上的R-树。一个数据集的数据项通过执行一个窗口查询与其他数据集连接。例如,如果我们连接城市和河流,一个城市的外包络矩形提供外包络矩形查询来执行河流数据集。这个窗口查询(文献33作为我们算法的一部分来使用。我们的工作不同于过去的工作,过去的工作仅仅只对通过取样的外部数据集的子集执行相交查询。我们增量地精简查询结果直到我们获取想得到的置信区间精度。先前设计的空间查询算法最小化查询完成时间。然而,我们设计的算法最小化时间直到通过置信区间衡量是一

14、个可接受的准确的查询结果估计是有效的。此外,我们的算法不仅仅返回一个集合查询值的估计而且还有真正连接的部分结果。(文献18-20在线查询处理工作被提出。作者提出了一个在线集合的接口。目的就是形成在线集合使用户能够看到他们的查询进程(比如GPA的平均水平处理了14%并且能够控制执行(加速特殊关系的修复。他们为计算运行置信区间(running confidence intervals和每一个运行集合(running aggregate接近相应的最后结果的估计值提供方法。(Hellerstein et al提出的(文献19初始的动机,统计和算法为支持在线集合(online aggregation提出

15、了连接算法(文献20,这个算法是为了满足在线查询进程系统的性能需求。他们的工作与相关数据库的在线集合相关。(Their work was geared towards online aggregation in relational databases.他们原始的信息返回方法用来控制地理相关数据,这个方法实际性能经常很差,因为他们忽略了空间数据的地理方面(文献25。因此,要进一步做很多工作来有效率的完成空间查询返回并考虑空间数据方面。在这篇文章中,我们采用了在(18-20文献提出的在线集合的想法,但是需要进一步完善算法使其能够高效率的操作地理相关数据的空间信息。空间连接选择性估计在(文献1,6

16、,9,10,22,38,39研究。最佳查询是为了找到好的查询计划,其中,精确的查询估计是决定性作用的重要方面。选择性查询被用来集合查询的快速估计,比如使用连接选择估计找出两个数据集之间关系的查询。统计技术也用在空间连接选择估计,其3个最普遍的算法是参数方法,柱状图方法,抽样方法。参数方法使用数据比例的分布来展示估计的规则(文献6,8,10。然而参数方法做了一些关于数据集的假设:均匀分布数据集(文献8,分形行为(文献6,服从强度规则(文献10。这些方法(文献6,10被证明仅仅处理点数据集。由于这些有局限的假设(数据独立分布,在GIS中参数方法不适用于真实数据集,因为真实数据不可能有如此的比例。我

17、们的增量抽样方法和参数方法主要的不同是我们的方法返回一个估计的连接结果和一个实际结果的增量累加集(estimated join result and an incrementally accumulating set of actual result tuples。相反参数方法仅仅返回一个集合值。由于柱状和抽样方法与参数方法比较起来限制小,在GIS中对大范围的数据集更适用。柱状方法将空间范围不同区域的某些信息保存在一个附加的数据结构(柱状图,当给出一个查询时这个结构用来估计连接选择性(join selectivity。目前的工作已发经已经显示了对于大范围查询柱状方法优于抽样方式。然而柱状方式需

18、要已知的数据分布的广泛实验估计来获取一个错误的边界。虽然(文献1,38实验结果显示低错误率,但是由于缺少错误保障,很难衡量存储和精确率二者的比重。Das et al.(文献9介绍一个方法,这个方法允许对于空间连接高质量的选择估计。这个方法返回了具有可查明的概率性质量的保障相似结果。说到参数方法,柱状方法也仅仅返回集合值并且不是真正的结果元组。因此,柱状方法也不能解决在这篇文章里讨论的问题。抽样方法使用了数据集(样本的子集,通过对样本应用连接来计算最后结果的估计值。同时抽样技术也使用在关系数据库估计,对于空间数据集的抽样方法的可用性和准确率,先前也很少的尝试。Olken(文献30提出了不同的方法

19、使用于通过R-树和四叉树的查询结果选择随机样本。在(文献43,作者讨论了4个不同的应用在四叉树随机抽样方法并且展示了这些算法的分析消耗结果。(文献1使用三个抽样方法来估计空间连接选择性(selectivity of spatial joins。以低开销选择出一个代表性的样本这个困难使抽样方法不可行。然而增量的随机抽样方法克服了这个问题另外提供了一个非模块化和交互性查询处理。GIS系统经常用来形象化终端客户的结果来协助对于处理过程做出决定。一个快速的伴随当前可视化结果的近似结果对于在GIS中用户操作的数据挖掘是是十分重要的。在GIS 在线查询处理(online query processing的

20、环境中我们研究了抽样技术用来获取空间连接选择估计。我们的方法提供了对于连接的错误置信区间以及(the ability to incrementally tighten the intervals.每种抽样方式用来生成实际连接结果(实际连接区域的子集而不是大量连接(相交部分的估计。3.IRSJ我们研究了三个普遍抽样技术:简单随机抽样(元组水平抽样,分层随机抽样,聚集抽样(页水平抽样。这些抽样技术用作为我们的GIS交互空间连接所有方法的一部分。我们发展了IRSJ算法的三个变体:IRSJt, IRSJs and IRSJp。表1是这篇文章的注记3.1随机抽样和随机数据在抽样中,被抽取的数据子集作为样

21、本来获取查询估计。抽样方法最普遍的应用就是为了集合查询(aggregate queries比如平均值,和统计合理准确的集合结果能够能数据样本中获得。样本用来获取一个随机与真实元组(actual tuples相关的子集来加速数据采集和分析。选择的样本应该能够准确表达整个数据集;置信区间能够用来反映估计的准确性(文献35, 36。查询估计和置信区间是统计地有意义的除非样本被随机取回。Olken(文献30提出多种索引的随机抽样技术生成有意义的置信区间。我们假定任一随机技术是可用的。在我们的实验中使用的加重随机抽样方法是接受/拒绝方法(文献30,34,包含可能性是与抽样列参数成比例的。简单随机抽样。分

22、层随机抽样。聚合抽样。第五部分在我们的实验中,我们比较了对于不同的需求的置信区间聚合抽样和简单随机抽样,分层随机抽样的精度和所需时间。分层和聚合抽样二者最主要的不同是分层和聚合的结构为了得到最佳的结果。3.2 IRSJ 概貌IRSJ过程由3部分组成:1抽样2空间连接3使用统计的查询结果精简估计。图2显示IRSJ概貌,2个连接的R和S关系数据库。1抽样步骤:样本基于抽样方法从外界关系R数据库中抽取出来。我们的抽样方式无法以增量模式来替换。2空间连接步骤:每个元组的外包络矩形被用作为对内部S关系数据库的窗口查询的外包络矩形。每个窗口查询返回0(假或1(真对于连接自身和找到的交集数量。它也返回R和S

23、实际连接区域。在这篇文章中,我只对交集的数量感兴趣。交集的数量以及被标注为中间结果的实际相交对(R和S实体3精简步骤:连接的实体数量和在每一步发现的总共的交集数量用来计算一个运行估计和置信区间。最后,这个计算的运行估计和置信区间与中间结果结合通过可视化过程加入到查询结果中。然后查询结果报告给用户。如果提供的置信区间是充分的或者能看到来自可视的实际的连接区域(中间结果的趋势,用户可以停止查询过程,否则过程继续。过程的每一步在增量的模式下是重复的来计算新的统计知道获取到想要的置信区间。3.3 IRSJ算法我们提出了3个IRSJ算法这些算法都是给予普遍的框架(在3.2部分:IRSJt, IRSJs

24、and IRSJp.在IRSJ算法中我们假定外部和内部关系数据库是编入了R-树或者R-树变体的索引,因为我们比较的度量标准是获取连接估计的时间与满树连接相反。建立R-树同时,我们保存叶子水平页的记录用来生成每个IRSJ算法的样本。另外,我们生成之前步骤的层,之后用在IRSJs算法中。IRSJt相当与3.1部分描述的简单随机抽样方法。IRSJs 相当与3.1部分描述的分层随机抽样方法。IRSJp相当与3.1部分描述的聚合抽样方法。4.IRSJ统计在这部分,我们讨论了空间连接统计并且提供了人口比例和三种算法每一个的置信区间。也提供了增量分层随机抽样的证明。4.1人口比例和置信区间为了提供准确结果的

25、界限,我们增量的计算和返回给用户当前带有置信区间的估计。我们为IRSJ的统计使用二项式分布。4.2 IRSJt统计4.3 IRSJs统计4.4 IRSJp统计5.性能评估5.1期望的消耗估计在这部分,我们为IRSJ算法提出一个消耗模型并且把它与满R-树连接算法做了比较,在探究详细的实验估计之前更直观看到IRSJ的性能。空间查询分析消耗模型为空间选择(文献11和23和27和32和空间连接(文献3, 21,39-41已经被提出。为了对于性能估计是具有实用性的,我们考虑一个LRU缓冲系统计算期望的I/O对于IRSJ算法。为了提供IRSJ的分析性能估计,我们首先展示了存在的R-树消耗模型:对于窗口查询

26、的消耗模型(23,32和满R-树连接的拓展消耗模型。我们我们使用这些消耗模型来分析我们算法的性能。我们估计了IRSJt的期望消耗和(21文献提出的对于两个真正数据集,矿物资源外部R关系数据库和地理化学非凝结的沉淀物内部S关系数据库实现满R-树连接的期望消耗。我们使用了二次方程算法构建了R和S的R树。表二显示了IRSJt和满R-树对于真正数据集连接的消耗模型的参数。5.2 实验的估计在这部分,我们提出了IRSJt, IRSJs, and IRSJp算法对于人工合成和真正GIS数据集的实验结果。算法之间相互比较并且和满R-树连接算法(文献7做了比较。我们展示结果证明使用不同索引结构包括R-树,R*

27、-树和STR-树性能影响。我们也展示了对于不同的缓冲面积I/Os数量和节点(页存取数量。由于所有展示的结果,估计和相应的置信区间在90%或者95%置信水平上展示出来。这部分,我们展示了IRSJt, IRSJs, and IRSJp算法的精度。图8,我们展示了人工合成数据的结果,数据中外界关系含有800,000均匀分布的元组和内部关系含有800,00不规则分布的元组。在这个实验中,二个数据集都是建立的R-树索引。图9,展示了真正数据集的结果。由于集合抽样方法与简单随机抽样和分层随机抽样(如3.1部分提到的相比较一般获得更好的结果,可能认为IRSJp与IRSJt和IRSJs比较要求更少的I/Os。

28、然而,IRSJp在I/Os 方面反应的优势与在数据大。小上需要获取一个给定的置信区间的劣势上相比就没那么重要了。实验结果显示IRSJt和IRSJs与IRSJp.比较需要更少I/Os。图10,我们展示了结果受选择索引结构选择的影响。我们绘制置信区间相对时间来衡量缓冲I/Os的数量对于分别建立R-tree, R*-tree and STR-tree结构的合成数据集和真正数据集。图11(a我们绘制了不同置信区间IRSJt需要的相对数据集范围的I/Os数量和满R-树连接的I/Os数量。图11(b我们绘制了R-tree join I/O ratio to IRSJt?图12 展示了相对数据集范围的节点存

29、取数量和node access ratio of the full R-tree join to IRSJt。表5 对于建立了R树索引的真正数据集,IRSJt和满R-树连接的I/Os和节点存取在这部分,我们展示了实验结果来看下索引结构如何影响三种IRSJ变体的结果。图15,在5%的置信区间分别对建立STR-tree, R*-tree, and R-tree索引结构使用IRSJt, IRSJs, and IRSJp方法获取估计结果所需的I/Os数量。(a展示合成数据集的结果。(b展示了真正数据集的结果。图16 展示在5%置信区间使用不同索引结构IRSJs一个估计所需的I/Os数量图17 不同置信

30、区间使用合成和真正数据集分别对应不同索引结构的所需I/Os的数量图18我们比较了IRSJt and IRSJs.6总结在这篇文章中,我们拓展了IRSJ算法为GIS交互查询处理进程有效地估计空间连接结果。我们实施了IRSJ三个变体:IRSJt使用简单随即抽样方式(元组水平,IRSJs使用分层随机抽样,IRSJp使用集合抽样(页水平。算法提供置信区间估计。我们为提出的算法提供统计可靠的证据以及它们的性能估计。实验的结果表明,需要获取一个合理准确估计的时间(I/Os相对于为了获取准确而结果使用满R-树连接算法在合成和真正数据集之间所需的时间相比有较小的数量级。我们也观察到IRSJt与满R-树连接相比

31、较在连接增加的数据集范围时查询时间有所减少。因此我们的方法对于大GIS数据集优势更显著。或许令人吃惊的是,我们的简单随机采样和分层随机抽样的业绩优于集合抽样。这是因为只有一个基准/页可以用,当计算置信区间由于数据的相关页面违反页水平独立。在所有的实验结果中,IRSJs性能至少与IRSJt一样。实验中使用了3个不同的索引结构,R-树, R*-树, 和STRtree,来观察索引结构如何影响IRSJ的性能。索引结构的选择不会影响三种IRSJ算法的相对性能。然而,正如所料,当使用STR树和R*树时算法更快的达到指定的置信区间的收敛。以下问题最为本文的研究成果,并且我们在考虑未来的一些问题:1.定义好的

32、层可以提高IRSJs 算法的性能。在实验中比较了IRSJs创造地层的不同方法,是非常有用和有兴趣看到的。2.扩展对于多元式空间连接增量抽样技术。从所有连接数据集中抽样从而获取更好的随机值和在紧缩置信区间具有相同查询处理时间的结果。3.动态空间连接不能决定先验查询计划。当查询在处理时,动态空间连接方法可以决定连接顺序。处理数据集(一个可能的连接顺序子集的信息可以用来优化其余的查询处理。改变连接顺序对查询优化是有益的。我们考虑的问题是如何决定连接顺序,什么因素影响查询处理和什么时候改变连接顺序。4.窗口查询是用来作为我们IRSJ算法的一部分。通过研究缓冲影响来改善对于R-树连接IRSJ算法的窗口查

33、询是我们对我们工作合理的扩展。References1. An N, Yang Z, SivasubramaniamA(2001 Selectivity estimation for spatial joins. In: Proceedingsof international conf. on data engineering (ICDE, pp 3683752. Anselin L (1992 Spatial data analysis with GIS: an introduction to application in the social sciences. In: Technical

34、report 92-10, National Center for Geographic Information and Analysis, University of California at Santa Barbara3. Aref WG, Samet H (1994 A cost model for query optimization using R-trees. In: Proceedings of workship advances in GIS4. Bae WD, Alkobaisi S, Leutenegger ST (2006 An incremental refinini

35、ng spatial join algorithm for estimating qeury results in GIS. In: Proceedings of international conf. on database and expert systems applications (DEXA, pp 9359445. Beckmann N, Kriegel H-P, Schneider R (1990 The R*-tree: an efficient and robust access methods for points and rectangles. In: Proceedin

36、gs of ACM SIGMOD, pp 322331 6. Belussi A, Faloutsos C (1998 Self-spacial join selectivity estimation using fractal concepts. ACM Trans Inf Sys 16(2:161201 7. Brinkhoff T, Kriegel H, Seeger B (1993 Efficient processing of spatial joins using R-trees. In: Proceedings of ACM SIGMOD, pp 127246 8. Chen C

37、M, Roussopoulos N (1994 Adaptive selectivity estimation using query feedback. In: Proceedings of ACM SIGMOD, pp 161172 9. Das A, Gehrke J, Riedewald M (2004 Approximation techniques for spatial data. In: Proceedings of ACM SIGMOD, pp 695706 10. Faloutsos C, Seeger B, Graina A, Traina C (2000 Spatial

38、 join selectivity using power laws. In: Proceedings of ACM SIGMOD, pp 177188 11. Faloutsos C, Sellis T, Roussopoulos N (1987 Analysis of object oriented spatial access methods. In: Proceedings of ACM SIGMOD, pp 426439 12. Ghilani CD, Wolf PR (2006 Adjustment computations: spatial data analysis. Wile

39、y, New York 13. Guttman A (1984 R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM SIGMOD, pp 4557 14. Haas PJ, Swami AN (1995 Sampling-based selectivity estimation for joins using augmented frequent value statistics. In: Proceedings of international conf. on data engineering (ICDE, pp 522531 Geoinfor