XQuery最大分割断层

Question

我试图在mondial数据库的XML版本中使用XQuery/XPath来查找两个彼此相距最远的城市，只考虑到人口超过50万的城市。为了计算距离，我假设是一个墨卡托投影。

这是我的代码：

let $db := doc("mondial.xml")

(: Cities with 500,000+ population :)
let $cities := (for $city in $db/mondial/country//city
(: Compare using latest population data :)
where $city/population[@year = max($city/population/@year)] > 500000
return $city)

(: City pairs and the distances between them (not
not square-rooted as all we care about is order) :)
let $distancesSquared := (for $city1 in $cities
for $city2 in $cities
    where $city1 != $city2
    return <distancesquared city1="{ data($city1/name) }" city2="{ data($city2/name) }">{ (
        let $diffLong := number($city1/longitude) - number($city2/longitude)
        let $diffLat := number($city1/latitude) - number($city2/latitude)
        return $diffLong * $diffLong + $diffLat * $diffLat
    ) }</distancesquared>)

let $max := max($distancesSquared)

return $distancesSquared[data(.) = $max]

但出于某种原因，我在这条线上遇到了一个分割错误：

let $max := max($distancesSquared)

我使用xqilla来运行这样的查询：

xqilla -o query.xml query.xq

有什么想法吗?我的代码有什么问题？

Answer 1

这是一个非常糟糕的查询，因为中间数据的数量随输入数据量的平方变化。

因为变量$distancesSquared被引用了两次，所以它几乎肯定会在内存中实现，而且很可能是巨大的。

首先，检查故障是否仍然发生在较少的数据量上。如果这种情况发生在小数据集上，那么您的代码就没有什么问题，这是XQuilla中的一个bug。

如果这只发生在大型数据集中，那么您可能超过了某种类型的系统限制(可能是内存)；检查是否有任何配置参数可以调整。

更好的是:找到一个改进的算法。

作为第一步，尝试一种在时间上仍然是二次型，但在记忆中不再是二次型的算法:具体地说，对于每个城市，找到最遥远的城市；在表单中建立一个列表。

<city name="London" furthest="Christchurch" distance="8000"/>

然后在这个城市对列表中找到最大值。

更聪明的是，有办法解决这个问题，而不检查所有对城市。恐怕我已经有一段时间没有研究过这样的算法了，所以我不记得细节了。但是总的想法是把每个城市分配到一个区域，计算出每一对区域中的点之间的极限距离，然后当找到离给定城市最远的城市时，只处理足够远的区域。