什麼數據結構用於在大型數據集上近實時查找？

我有一個2000萬人的數據集，其位置已知。在接近實時的情況下，我想知道我收到的查詢是否在這個集合中，如果是，則是實際位置。基本上，我想要一個大型的哈希表。由於數量巨大（每秒數千次查詢），因此支付Redis/Memcached網絡往返費用是不成問題的。什麼數據結構用於在大型數據集上近實時查找？

是否有數據結構可以提供非常快速的成員資格測試和數據檢索？少量的錯誤是可以接受的。

一些位置比其他位置更受歡迎。例如，「美國，紐約，紐約」比「美國，阿拉斯加，安克雷奇」更頻繁地出現。

來源

2013-05-22 François Beausoleil

使用排序後的數組和做二進制搜索是另一種選擇：

val ids: Array[Long] = new Array(30000000) 
val values: Array[Int] = new Array(30000000) 
var lookups = Map.empty[String, Int] 

// populate ids with sorted array read from disk 
Source.fromFile("sorted.csv").map(_.split("\t")).zipWithIndex.foreach { 
    case (Array(id, value), index) => 
     ids[index] = id.toLong 
     values[index] = lookups.get(value) match { 
      case Some(valueIndex) => valueIndex 
      case None => 
       val valueIndex = values.size + 1 
       lookups = lookups.updated(value, valueIndex) 
       valueIndex 
     } 
} 

// Flip lookups around: value becomes key, key becomes value 
val realLookup = lookups.foldLeft(Map.empty[Int, String]) { 
    case (memo, (value, index)) => memo.updated(index, value) 
} 

// Usage: 
Source.fromFile("ids.csv").foreach { 
    idStr => 
     val id = idStr.toLong 
     val index = java.util.Arrays.binarySearch(ids, id) 
     if (index < 0) { 
      // Unknown -- check javadoc 
      println(idStr) 
     } else { 
      // Known 
      println(id + "\t" + realLookup(values(index)) 
     } 
}

來源

2013-05-31 15:33:38

這使用最少量的內存：每個條目一個long和一個int。對於50M條目，我消耗大約3.5吉比特的RAM。使用HashMap，我會消耗超過6個GiB和龍骨。運行時間非常好，非常穩定：第99百分位非常穩定。 –

一種選擇是使用簡單明瞭的地圖：

// Scala 
val locations: Map[String, Geo] = Map.empty 
def location(id: String): Option[Geo] = locations.get(id)

，雖然花費了大量的內存。

來源

2013-05-22 02:00:21

「2000萬」 - 「我想要一個大的散列表」 - 聽起來你已經有了答案。包含2000萬個項目的哈希映射將很容易適應單個機器上單個進程使用的內存。

C++：std::unordered_map<Key, Value>
C＃：System.Collections.Generic.Dictionary<Key, Value>
的Java：java.util.HashMap<Key, Value>
斯卡拉：HashMap[Key, Value]

如果你告訴我們你所使用的語言，我們可以指出你的該語言的確切類型。（關鍵字）的情況下，可以使用輔助Bloom filter（rampion的想法 - 不是我的 - 只是爲了完整性而將其包括在內）加速成員資格測試，在散列映射中是而不是。

來源

2013-05-22 02:03:39

'的std :: map'不是由一個哈希表，而是由一個平衡的二叉搜索樹的支持。在C++ 11中，你有散列表支持'std :: unordered_map'。 –

@EugenConstantinDinca哈哈wooops - 這是漫長的一天。 :) –

我目前的實現目標是Scala/Java，但是任何可以與RabbitMQ交談的東西都可以。 –

你可以使用一個Bloomier filter：

布隆過濾器[...]是用來測試一個元素是否是一組的成員的空間效率的概率數據結構。假陽性檢索結果是可能的，但是假陰性不是;即查詢返回「內部集合（可能是錯誤的）」或「絕對不在集合中」。元素可以添加到集合中，但不能刪除（儘管這可以通過計數過濾器來解決）。添加到集合中的元素越多，誤報的概率就越大。

[...]

Chazelle等。（2004）設計了一個Bloom過濾器的泛化，可以將一個值與已插入的每個元素相關聯，實現一個關聯數組。像布盧姆過濾器一樣，這些結構通過接受小的誤報概率來實現小空間開銷。在「Bloomier過濾器」的情況下，假陽性定義爲當鍵不在地圖中時返回結果。地圖永遠不會爲地圖中的鍵返回錯誤的值。

來源

2013-05-22 02:03:57 rampion

甲Judy Array

是一種數據結構，具有高性能，低內存使用和實施的關聯數組。

朱迪陣列顯然壓縮得非常好，非常快。

來源

2013-05-22 15:39:29

什麼數據結構用於在大型數據集上近實時查找？

回答

相關問題