Merge pull request #4390 from ygorshenin/fix-locality-finder

[search] Fixed locality matching code.

20 files changed, 515 insertions, 257 deletions

diff --git a/base/base.pro b/base/base.pro
index d0976ea2f7..803d1b544a 100644
--- a/base/base.pro
+++ b/base/base.pro
@@ -10,9 +10,9 @@ include($$ROOT_DIR/common.pri)
 SOURCES += \
     base.cpp \
     condition.cpp \
-    gmtime.cpp \
     deferred_task.cpp \
     exception.cpp \
+    gmtime.cpp \
     internal/message.cpp \
     logging.cpp \
     lower_case.cpp \
@@ -28,6 +28,7 @@ SOURCES += \
     thread_checker.cpp \
     thread_pool.cpp \
     threaded_container.cpp \
+    time_samples.cpp \
     timegm.cpp \
     timer.cpp \
 
@@ -81,6 +82,7 @@ HEADERS += \
     threaded_container.hpp \
     threaded_list.hpp \
     threaded_priority_queue.hpp \
+    time_samples.hpp \
     timegm.hpp \
     timer.hpp \
     worker_thread.hpp \
diff --git a/base/time_samples.cpp b/base/time_samples.cpp
new file mode 100644
index 0000000000..209385b060
--- /dev/null
+++ b/base/time_samples.cpp
@@ -0,0 +1,24 @@
+#include "base/time_samples.hpp"
+
+#include "std/cmath.hpp"
+
+namespace my
+{
+void TimeSamples::Add(double seconds)
+{
+  m_sum += seconds;
+  m_sum2 += seconds * seconds;
+  ++m_total;
+}
+
+double TimeSamples::GetMean() const { return m_total == 0 ? 0.0 : m_sum / m_total; }
+
+double TimeSamples::GetSD() const
+{
+  if (m_total < 2)
+    return 0.0;
+  return std::max((m_sum2 - m_sum * m_sum / static_cast<double>(m_total)) / (m_total - 1), 0.0);
+}
+
+double TimeSamples::GetVar() const { return sqrt(GetSD()); }
+}  // namespace my
diff --git a/base/time_samples.hpp b/base/time_samples.hpp
new file mode 100644
index 0000000000..c4f1fdf072
--- /dev/null
+++ b/base/time_samples.hpp
@@ -0,0 +1,49 @@
+#pragma once
+
+#include "base/timer.hpp"
+
+#include "std/cstdint.hpp"
+
+namespace my
+{
+// This class can be used in measurements of code blocks performance.
+// It can accumulate time samples, and can calculate mean time and
+// standard deviation.
+//
+// *NOTE* This class is NOT thread-safe.
+class TimeSamples final
+{
+public:
+  void Add(double seconds);
+
+  // Mean of the accumulated time samples.
+  double GetMean() const;
+
+  // Unbiased standard deviation of the accumulated time samples.
+  double GetSD() const;
+
+  // Unbiased variance of the accumulated time samples.
+  double GetVar() const;
+
+private:
+  double m_sum = 0.0;
+  double m_sum2 = 0.0;
+  size_t m_total = 0;
+};
+
+// This class can be used as a single scoped time sample. It
+// automatically adds time sample on destruction.
+//
+// *NOTE* This class is NOT thread-safe.
+class ScopedTimeSample final
+{
+public:
+  ScopedTimeSample(TimeSamples & ts) : m_ts(ts) {}
+  ~ScopedTimeSample() { m_ts.Add(m_t.ElapsedSeconds()); }
+
+private:
+  TimeSamples & m_ts;
+  my::Timer m_t;
+};
+
+}  // namespace my
diff --git a/base/timer.hpp b/base/timer.hpp
index bd793f92c1..d64c66a0ac 100644
--- a/base/timer.hpp
+++ b/base/timer.hpp
@@ -73,4 +73,4 @@ public:
 
 time_t SecondsSinceEpochToTimeT(uint64_t secondsSinceEpoch);
 uint64_t TimeTToSecondsSinceEpoch(time_t time);
-}
+}  // namespace my
diff --git a/indexer/index.hpp b/indexer/index.hpp
index b593e25b2f..3f43d2b707 100644
--- a/indexer/index.hpp
+++ b/indexer/index.hpp
@@ -54,6 +54,9 @@ public:
   inline feature::RegionData const & GetRegionData() const { return m_factory.GetRegionData(); }
   inline version::MwmVersion const & GetMwmVersion() const { return m_factory.GetMwmVersion(); }
   inline string const & GetCountryFileName() const { return m_file.GetCountryFile().GetName(); }
+
+  inline bool HasSearchIndex() { return m_cont.IsExist(SEARCH_INDEX_FILE_TAG); }
+  inline bool HasGeometryIndex() { return m_cont.IsExist(INDEX_FILE_TAG); }
 };
 
 class Index : public MwmSet
diff --git a/search/categories_cache.cpp b/search/categories_cache.cpp
new file mode 100644
index 0000000000..214edb360d
--- /dev/null
+++ b/search/categories_cache.cpp
@@ -0,0 +1,101 @@
+#include "search/categories_cache.hpp"
+
+#include "search/mwm_context.hpp"
+#include "search/query_params.hpp"
+#include "search/retrieval.hpp"
+
+#include "indexer/ftypes_matcher.hpp"
+
+#include "base/assert.hpp"
+
+#include "std/vector.hpp"
+
+namespace search
+{
+namespace
+{
+// Performs pairwise union of adjacent bit vectors
+// until at most one bit vector is left.
+void UniteCBVs(vector<CBV> & cbvs)
+{
+  while (cbvs.size() > 1)
+  {
+    size_t i = 0;
+    size_t j = 0;
+    for (; j + 1 < cbvs.size(); j += 2)
+      cbvs[i++] = cbvs[j].Union(cbvs[j + 1]);
+    for (; j < cbvs.size(); ++j)
+      cbvs[i++] = move(cbvs[j]);
+    cbvs.resize(i);
+  }
+}
+}  // namespace
+
+// CategoriesCache ---------------------------------------------------------------------------------
+CategoriesCache::CategoriesCache(CategoriesSet const & categories,
+                                 my::Cancellable const & cancellable)
+  : m_categories(categories), m_cancellable(cancellable)
+{
+}
+
+CBV CategoriesCache::Get(MwmContext const & context)
+{
+  if (!context.m_handle.IsAlive() || !context.m_value.HasSearchIndex())
+    return CBV();
+
+  auto id = context.m_handle.GetId();
+  auto const it = m_cache.find(id);
+  if (it != m_cache.cend())
+    return it->second;
+
+  auto cbv = Load(context);
+  m_cache[id] = cbv;
+  return cbv;
+}
+
+CBV CategoriesCache::Load(MwmContext const & context)
+{
+  ASSERT(context.m_handle.IsAlive(), ());
+  ASSERT(context.m_value.HasSearchIndex(), ());
+
+  QueryParams params;
+  params.m_tokens.resize(1);
+  params.m_tokens[0].resize(1);
+
+  params.m_types.resize(1);
+  params.m_types[0].resize(1);
+
+  vector<CBV> cbvs;
+
+  m_categories.ForEach([&](strings::UniString const & key, uint32_t const type) {
+    params.m_tokens[0][0] = key;
+    params.m_types[0][0] = type;
+
+    CBV cbv(RetrieveAddressFeatures(context, m_cancellable, params));
+    if (!cbv.IsEmpty())
+      cbvs.push_back(move(cbv));
+  });
+
+  UniteCBVs(cbvs);
+  if (cbvs.empty())
+    cbvs.emplace_back();
+
+  return cbvs[0];
+}
+
+// StreetsCache ------------------------------------------------------------------------------------
+StreetsCache::StreetsCache(my::Cancellable const & cancellable)
+  : m_cache(m_categories, cancellable)
+{
+  ftypes::IsStreetChecker::Instance().ForEachType(
+      [this](uint32_t type) { m_categories.Add(type); });
+}
+
+// VillagesCache -----------------------------------------------------------------------------------
+VillagesCache::VillagesCache(my::Cancellable const & cancellable)
+  : m_cache(m_categories, cancellable)
+{
+  ftypes::IsVillageChecker::Instance().ForEachType(
+      [this](uint32_t type) { m_categories.Add(type); });
+}
+}  // namespace search
diff --git a/search/categories_cache.hpp b/search/categories_cache.hpp
new file mode 100644
index 0000000000..cf2da9297f
--- /dev/null
+++ b/search/categories_cache.hpp
@@ -0,0 +1,61 @@
+#pragma once
+
+#include "search/categories_set.hpp"
+#include "search/cbv.hpp"
+
+#include "indexer/mwm_set.hpp"
+
+#include "base/cancellable.hpp"
+
+#include "std/map.hpp"
+
+namespace search
+{
+class MwmContext;
+
+class CategoriesCache
+{
+public:
+  CategoriesCache(CategoriesSet const & categories, my::Cancellable const & cancellable);
+
+  CBV Get(MwmContext const & context);
+  inline void Clear() { m_cache.clear(); }
+
+private:
+  CBV Load(MwmContext const & context);
+
+  CategoriesSet const & m_categories;
+  my::Cancellable const & m_cancellable;
+  map<MwmSet::MwmId, CBV> m_cache;
+};
+
+class StreetsCache
+{
+ public:
+  StreetsCache(my::Cancellable const & cancellable);
+
+  inline CBV Get(MwmContext const & context) { return m_cache.Get(context); }
+  inline void Clear() { m_cache.Clear(); }
+  inline bool HasCategory(strings::UniString const & category) const
+  {
+    return m_categories.HasKey(category);
+  }
+
+ private:
+  CategoriesSet m_categories;
+  CategoriesCache m_cache;
+};
+
+class VillagesCache
+{
+ public:
+  VillagesCache(my::Cancellable const & cancellable);
+
+  inline CBV Get(MwmContext const & context) { return m_cache.Get(context); }
+  inline void Clear() { m_cache.Clear(); }
+
+private:
+  CategoriesSet m_categories;
+  CategoriesCache m_cache;
+};
+}  // namespace search
diff --git a/search/geocoder.cpp b/search/geocoder.cpp
index 2658e33300..5345d18933 100644
--- a/search/geocoder.cpp
+++ b/search/geocoder.cpp
@@ -205,10 +205,6 @@ WARN_UNUSED_RESULT bool GetAffiliationName(FeatureType const & ft, string & affi
   return false;
 }
 
-bool HasSearchIndex(MwmValue const & value) { return value.m_cont.IsExist(SEARCH_INDEX_FILE_TAG); }
-
-bool HasGeometryIndex(MwmValue & value) { return value.m_cont.IsExist(INDEX_FILE_TAG); }
-
 MwmSet::MwmHandle FindWorld(Index const & index, vector<shared_ptr<MwmInfo>> const & infos)
 {
   MwmSet::MwmHandle handle;
@@ -335,22 +331,6 @@ size_t OrderCountries(m2::RectD const & pivot, vector<shared_ptr<MwmInfo>> & inf
   auto const sep = stable_partition(infos.begin(), infos.end(), intersects);
   return distance(infos.begin(), sep);
 }
-
-// Performs pairwise union of adjacent bit vectors
-// until at most one bit vector is left.
-void UniteCBVs(vector<CBV> & cbvs)
-{
-  while (cbvs.size() > 1)
-  {
-    size_t i = 0;
-    size_t j = 0;
-    for (; j + 1 < cbvs.size(); j += 2)
-      cbvs[i++] = cbvs[j].Union(cbvs[j + 1]);
-    for (; j < cbvs.size(); ++j)
-      cbvs[i++] = move(cbvs[j]);
-    cbvs.resize(i);
-  }
-}
 }  // namespace
 
 // Geocoder::Params --------------------------------------------------------------------------------
@@ -358,9 +338,12 @@ Geocoder::Params::Params() : m_mode(Mode::Everywhere) {}
 
 // Geocoder::Geocoder ------------------------------------------------------------------------------
 Geocoder::Geocoder(Index const & index, storage::CountryInfoGetter const & infoGetter,
-                   PreRanker & preRanker, my::Cancellable const & cancellable)
+                   PreRanker & preRanker, VillagesCache & villagesCache,
+                   my::Cancellable const & cancellable)
   : m_index(index)
   , m_infoGetter(infoGetter)
+  , m_streetsCache(cancellable)
+  , m_villagesCache(villagesCache)
   , m_cancellable(cancellable)
   , m_model(SearchModel::Instance())
   , m_pivotRectsCache(kPivotRectsCacheSize, m_cancellable, Processor::kMaxViewportRadiusM)
@@ -371,8 +354,6 @@ Geocoder::Geocoder(Index const & index, storage::CountryInfoGetter const & infoG
   , m_lastMatchedRegion(nullptr)
   , m_preRanker(preRanker)
 {
-  ftypes::IsStreetChecker::Instance().ForEachType([this](uint32_t type) { m_streets.Add(type); });
-  ftypes::IsVillageChecker::Instance().ForEachType([this](uint32_t type) { m_villages.Add(type); });
 }
 
 Geocoder::~Geocoder() {}
@@ -398,7 +379,7 @@ void Geocoder::SetParams(Params const & params)
   m_retrievalParams = m_params;
 
   // Remove all category synonyms for streets, as they're extracted
-  // individually via LoadStreets.
+  // individually.
   for (size_t i = 0; i < m_params.GetNumTokens(); ++i)
   {
     auto & synonyms = m_params.GetTokens(i);
@@ -410,7 +391,7 @@ void Geocoder::SetParams(Params const & params)
       auto e = synonyms.end();
       synonyms.erase(remove_if(b + 1, e,
                                [this](strings::UniString const & synonym) {
-                                 return m_streets.HasKey(synonym);
+                                 return m_streetsCache.HasCategory(synonym);
                                }),
                      e);
     }
@@ -481,7 +462,7 @@ void Geocoder::GoImpl(vector<shared_ptr<MwmInfo>> & infos, bool inViewport)
         m_worldId = handle.GetId();
         m_context = make_unique<MwmContext>(move(handle));
 
-        if (HasSearchIndex(value))
+        if (value.HasSearchIndex())
         {
           BaseContext ctx;
           InitBaseContext(ctx);
@@ -540,7 +521,7 @@ void Geocoder::GoImpl(vector<shared_ptr<MwmInfo>> & infos, bool inViewport)
           features = features.Intersect(viewportCBV);
       }
 
-      ctx.m_villages = LoadVillages(*m_context);
+      ctx.m_villages = m_villagesCache.Get(*m_context);
 
       auto citiesFromWorld = m_cities;
       FillVillageLocalities(ctx);
@@ -576,7 +557,8 @@ void Geocoder::ClearCaches()
   m_localityRectsCache.Clear();
 
   m_matchersCache.clear();
-  m_streetsCache.clear();
+  m_streetsCache.Clear();
+  m_villagesCache.Clear();
   m_postcodes.Clear();
 }
 
@@ -809,7 +791,7 @@ void Geocoder::ForEachCountry(vector<shared_ptr<MwmInfo>> const & infos, TFn &&
     if (!handle.IsAlive())
       continue;
     auto & value = *handle.GetValue<MwmValue>();
-    if (!HasSearchIndex(value) || !HasGeometryIndex(value))
+    if (!value.HasSearchIndex() || !value.HasGeometryIndex())
       continue;
     fn(i, make_unique<MwmContext>(move(handle)));
   }
@@ -950,7 +932,7 @@ void Geocoder::LimitedSearch(BaseContext & ctx, FeaturesFilter const & filter)
                  });
 
   if (!ctx.m_streets)
-    ctx.m_streets = LoadStreets(*m_context);
+    ctx.m_streets = m_streetsCache.Get(*m_context);
 
   MatchUnclassified(ctx, 0 /* curToken */);
 
@@ -1364,59 +1346,6 @@ void Geocoder::MatchUnclassified(BaseContext & ctx, size_t curToken)
   allFeatures.ForEach(emitUnclassified);
 }
 
-CBV Geocoder::LoadCategories(MwmContext & context, CategoriesSet const & categories)
-{
-  ASSERT(context.m_handle.IsAlive(), ());
-  ASSERT(HasSearchIndex(context.m_value), ());
-
-  m_retrievalParams.m_tokens.resize(1);
-  m_retrievalParams.m_tokens[0].resize(1);
-
-  m_retrievalParams.m_prefixTokens.clear();
-
-  m_retrievalParams.m_types.resize(1);
-  m_retrievalParams.m_types[0].resize(1);
-
-  vector<CBV> cbvs;
-
-  categories.ForEach([&](strings::UniString const & key, uint32_t const type) {
-    m_retrievalParams.m_tokens[0][0] = key;
-    m_retrievalParams.m_types[0][0] = type;
-
-    CBV cbv(RetrieveAddressFeatures(context, m_cancellable, m_retrievalParams));
-    if (!cbv.IsEmpty())
-      cbvs.push_back(move(cbv));
-  });
-
-  UniteCBVs(cbvs);
-  if (cbvs.empty())
-    cbvs.emplace_back();
-
-  return move(cbvs[0]);
-}
-
-CBV Geocoder::LoadStreets(MwmContext & context)
-{
-  if (!context.m_handle.IsAlive() || !HasSearchIndex(context.m_value))
-    return CBV();
-
-  auto mwmId = context.m_handle.GetId();
-  auto const it = m_streetsCache.find(mwmId);
-  if (it != m_streetsCache.cend())
-    return it->second;
-
-  auto streets = LoadCategories(context, m_streets);
-  m_streetsCache[mwmId] = streets;
-  return streets;
-}
-
-CBV Geocoder::LoadVillages(MwmContext & context)
-{
-  if (!context.m_handle.IsAlive() || !HasSearchIndex(context.m_value))
-    return CBV();
-  return LoadCategories(context, m_villages);
-}
-
 CBV Geocoder::RetrievePostcodeFeatures(MwmContext const & context, TokenSlice const & slice)
 {
   return CBV(::search::RetrievePostcodeFeatures(context, m_cancellable, slice));
diff --git a/search/geocoder.hpp b/search/geocoder.hpp
index 715e4250a3..d6b30a1e1d 100644
--- a/search/geocoder.hpp
+++ b/search/geocoder.hpp
@@ -1,7 +1,8 @@
 #pragma once
 
 #include "search/cancel_exception.hpp"
-#include "search/categories_set.hpp"
+#include "search/categories_cache.hpp"
+#include "search/cbv.hpp"
 #include "search/features_layer.hpp"
 #include "search/features_layer_path_finder.hpp"
 #include "search/geocoder_context.hpp"
@@ -136,7 +137,8 @@ public:
   };
 
   Geocoder(Index const & index, storage::CountryInfoGetter const & infoGetter,
-           PreRanker & preRanker, my::Cancellable const & cancellable);
+           PreRanker & preRanker, VillagesCache & villagesCache,
+           my::Cancellable const & cancellable);
 
   ~Geocoder();
 
@@ -257,12 +259,6 @@ private:
   // UNCLASSIFIED objects that match to all currently unused tokens.
   void MatchUnclassified(BaseContext & ctx, size_t curToken);
 
-  CBV LoadCategories(MwmContext & context, CategoriesSet const & categories);
-
-  CBV LoadStreets(MwmContext & context);
-
-  CBV LoadVillages(MwmContext & context);
-
   // A wrapper around RetrievePostcodeFeatures.
   CBV RetrievePostcodeFeatures(MwmContext const & context, TokenSlice const & slice);
 
@@ -278,10 +274,10 @@ private:
 
   storage::CountryInfoGetter const & m_infoGetter;
 
-  my::Cancellable const & m_cancellable;
+  StreetsCache m_streetsCache;
+  VillagesCache & m_villagesCache;
 
-  CategoriesSet m_streets;
-  CategoriesSet m_villages;
+  my::Cancellable const & m_cancellable;
 
   // Geocoder params.
   Params m_params;
@@ -309,9 +305,6 @@ private:
   PivotRectsCache m_pivotRectsCache;
   LocalityRectsCache m_localityRectsCache;
 
-  // Cache of street ids in mwms.
-  map<MwmSet::MwmId, CBV> m_streetsCache;
-
   // Postcodes features in the mwm that is currently being processed.
   Postcodes m_postcodes;
 
diff --git a/search/locality_finder.cpp b/search/locality_finder.cpp
index 92bc5251a5..7621b5f462 100644
--- a/search/locality_finder.cpp
+++ b/search/locality_finder.cpp
@@ -1,5 +1,7 @@
 #include "search/locality_finder.hpp"
 
+#include "search/categories_cache.hpp"
+#include "search/cbv.hpp"
 #include "search/dummy_rank_table.hpp"
 #include "search/mwm_context.hpp"
 
@@ -16,20 +18,58 @@ namespace search
 namespace
 {
 double const kMaxCityRadiusMeters = 30000.0;
-double const kInflateRectMercator = 0.001;
 
-class DoLoader
+struct Filter
 {
 public:
-  DoLoader(MwmContext const & ctx, LocalityFinder::Cache & cache, RankTable const & ranks,
-           int8_t lang)
-    : m_ctx(ctx), m_cache(cache), m_ranks(ranks), m_lang(lang)
+  virtual ~Filter() = default;
+  virtual bool IsGood(uint32_t id) const = 0;
+};
+
+class CityFilter : public Filter
+{
+public:
+  CityFilter(RankTable const & ranks) : m_ranks(ranks) {}
+
+  // Filter overrides:
+  bool IsGood(uint32_t id) const override { return m_ranks.Get(id) != 0; }
+
+private:
+  RankTable const & m_ranks;
+};
+
+class VillageFilter : public Filter
+{
+public:
+  VillageFilter(MwmContext const & ctx, VillagesCache & villages) : m_cbv(villages.Get(ctx)) {}
+
+  // Filter overrides:
+  bool IsGood(uint32_t id) const override { return m_cbv.HasBit(id); }
+
+private:
+  CBV m_cbv;
+};
+
+class LocalitiesLoader
+{
+public:
+  LocalitiesLoader(MwmContext const & ctx, Filter const & filter, int8_t lang,
+                   m4::Tree<LocalityFinder::Item> & localities,
+                   map<MwmSet::MwmId, unordered_set<uint32_t>> & loadedIds)
+    : m_ctx(ctx)
+    , m_filter(filter)
+    , m_lang(lang)
+    , m_localities(localities)
+    , m_loadedIds(loadedIds[m_ctx.GetId()])
   {
   }
 
   void operator()(uint32_t id) const
   {
-    if (m_ranks.Get(id) == 0)
+    if (m_loadedIds.count(id) != 0)
+      return;
+
+    if (!m_filter.IsGood(id))
       return;
 
     FeatureType ft;
@@ -43,77 +83,51 @@ public:
     switch (IsLocalityChecker::Instance().GetType(ft))
     {
     case CITY:
-    case TOWN: break;
-    default:  // cache only cities and towns at this moment
+    case TOWN:
+    case VILLAGE:
+      break;
+    default:
       return;
     }
 
-    if (m_cache.m_loadedIds.count(id) > 0)
-      return;
-
     uint32_t const population = ftypes::GetPopulation(ft);
     if (population == 0)
       return;
 
-    double const radius = ftypes::GetRadiusByPopulation(population);
-    m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(ft.GetCenter(), radius);
-    if (!rect.IsIntersect(m_cache.m_rect))
-      return;
-
     // read item
     string name;
     if (!ft.GetName(m_lang, name) && !ft.GetName(0, name))
       return;
 
-    LocalityItem item(name, population, id);
-    m_cache.m_tree.Add(item, rect);
-    m_cache.m_loadedIds.insert(id);
+    auto const center = ft.GetCenter();
+
+    LocalityFinder::Item item(name, center, population);
+    m_localities.Add(item, m2::RectD(center, center));
+    m_loadedIds.insert(id);
   }
 
 private:
   MwmContext const & m_ctx;
-  LocalityFinder::Cache & m_cache;
-  RankTable const & m_ranks;
+  Filter const & m_filter;
   int8_t const m_lang;
-};
-
-class DoSelectLocality
-{
-public:
-  DoSelectLocality(string & name, m2::PointD const & pt)
-    : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max())
-  {
-  }
-
-  void operator()(m2::RectD const & rect, LocalityItem const & item)
-  {
-    // TODO (@y, @m): replace this naive score by p-values on
-    // multivariate Gaussian.
-    double const distanceMeters = MercatorBounds::DistanceOnEarth(rect.Center(), m_pt);
-    double const score =
-        ftypes::GetPopulationByRadius(distanceMeters) / static_cast<double>(item.m_population);
-    if (score < m_bestScore)
-    {
-      m_bestScore = score;
-      m_name = item.m_name;
-    }
-  }
 
-private:
-  string & m_name;
-  m2::PointD m_pt;
-  double m_bestScore;
+  m4::Tree<LocalityFinder::Item> & m_localities;
+  unordered_set<uint32_t> & m_loadedIds;
 };
 }  // namespace
 
-// LocalityItem ------------------------------------------------------------------------------------
-LocalityItem::LocalityItem(string const & name, uint32_t population, uint32_t id)
-  : m_name(name), m_population(population), m_id(id)
+// LocalityFinder::Item
+// ------------------------------------------------------------------------------------
+LocalityFinder::Item::Item(string const & name, m2::PointD const & center, uint32_t population)
+  : m_name(name), m_center(center), m_population(population)
 {
 }
 
 // LocalityFinder ----------------------------------------------------------------------------------
-LocalityFinder::LocalityFinder(Index const & index) : m_index(index), m_lang(0) {}
+LocalityFinder::LocalityFinder(Index const & index, VillagesCache & villagesCache)
+  : m_index(index), m_villagesCache(villagesCache), m_lang(0)
+{
+}
 
 void LocalityFinder::SetLanguage(int8_t lang)
 {
@@ -124,101 +138,98 @@ void LocalityFinder::SetLanguage(int8_t lang)
   m_lang = lang;
 }
 
-void LocalityFinder::UpdateCache(Cache & cache, m2::PointD const & pt)
+void LocalityFinder::GetLocality(m2::PointD const & pt, string & name)
 {
-  m2::RectD rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters);
-  if (cache.m_rect.IsRectInside(rect))
-    return;
-
-  rect.Add(cache.m_rect);
-  rect.Inflate(kInflateRectMercator, kInflateRectMercator);
+  m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters);
 
-  if (!m_worldId.IsAlive())
-  {
-    m_worldId.Reset();
-    m_ranks.reset();
+  bool covered = false;
+  m_coverage.ForEachInRect(rect, [&covered](bool) { covered = true; });
+  if (!covered)
+    LoadVicinity(pt);
 
-    vector<shared_ptr<MwmInfo>> mwmsInfo;
-    m_index.GetMwmsInfo(mwmsInfo);
-    for (auto const & info : mwmsInfo)
-    {
-      MwmSet::MwmId id(info);
-      Index::MwmHandle handle = m_index.GetMwmHandleById(id);
-      MwmValue const * value = handle.GetValue<MwmValue>();
-      if (handle.IsAlive() && value->GetHeader().GetType() == feature::DataHeader::world)
-      {
-        m_worldId = id;
-        m_ranks = RankTable::Load(value->m_cont);
-        break;
-      }
-    }
-
-    if (!m_ranks)
-      m_ranks = make_unique<DummyRankTable>();
-  }
-
-  ASSERT(m_ranks.get(), ());
-
-  Index::MwmHandle handle = m_index.GetMwmHandleById(m_worldId);
-  if (!handle.IsAlive())
-    return;
+  m_localities.ForEachInRect(rect, LocalitySelector(name, pt));
+}
 
-  cache.m_rect = rect;
-  MwmContext ctx(move(handle));
-  ctx.ForEachIndex(rect, DoLoader(ctx, cache, *m_ranks, m_lang));
+void LocalityFinder::ClearCache()
+{
+  m_ranks.reset();
+  m_coverage.Clear();
+  m_localities.Clear();
+  m_loadedIds.clear();
 }
 
-void LocalityFinder::GetLocality(m2::PointD const & pt, string & name)
+void LocalityFinder::LoadVicinity(m2::PointD const & pt)
 {
-  Cache * working = nullptr;
+  m2::RectD const drect =
+      MercatorBounds::RectByCenterXYAndSizeInMeters(pt, 2 * kMaxCityRadiusMeters);
 
-  // Find suitable cache that includes needed point.
-  for (auto & cache : m_caches)
+  vector<shared_ptr<MwmInfo>> mwmsInfo;
+  m_index.GetMwmsInfo(mwmsInfo);
+  for (auto const & info : mwmsInfo)
   {
-    if (cache.m_rect.IsPointInside(pt))
+    MwmSet::MwmId id(info);
+    Index::MwmHandle handle = m_index.GetMwmHandleById(id);
+
+    if (!handle.IsAlive())
+      continue;
+
+    MwmValue const & value = *handle.GetValue<MwmValue>();
+    auto const & header = value.GetHeader();
+    switch (header.GetType())
     {
-      working = &cache;
+    case feature::DataHeader::world:
+    {
+      if (!m_ranks)
+        m_ranks = RankTable::Load(value.m_cont);
+      if (!m_ranks)
+        m_ranks = make_unique<DummyRankTable>();
+
+      MwmContext ctx(move(handle));
+      ctx.ForEachIndex(
+          drect, LocalitiesLoader(ctx, CityFilter(*m_ranks), m_lang, m_localities, m_loadedIds));
       break;
     }
+    case feature::DataHeader::country:
+      if (header.GetBounds().IsPointInside(pt))
+      {
+        MwmContext ctx(move(handle));
+        ctx.ForEachIndex(drect, LocalitiesLoader(ctx, VillageFilter(ctx, m_villagesCache), m_lang,
+                                                 m_localities, m_loadedIds));
+      }
+      break;
+    case feature::DataHeader::worldcoasts: break;
+    }
   }
 
-  if (working == nullptr)
-  {
-    // Find most unused cache.
-    working =
-        &*min_element(begin(m_caches), end(m_caches), my::LessBy(&LocalityFinder::Cache::m_usage));
-    working->Clear();
-  }
-
-  UpdateCache(*working, pt);
-  working->GetLocality(pt, name);
+  m_coverage.Add(true, m2::RectD(pt, pt));
 }
 
-void LocalityFinder::ClearCache()
+// LocalitySelector --------------------------------------------------------------------------------
+LocalitySelector::LocalitySelector(string & name, m2::PointD const & pt)
+  : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max())
 {
-  for (auto & cache : m_caches)
-    cache.Clear();
 }
 
-// LocalityFinder::Cache ---------------------------------------------------------------------------
-void LocalityFinder::Cache::Clear()
+void LocalitySelector::operator()(LocalityFinder::Item const & item)
 {
-  m_usage = 0;
-  m_tree.Clear();
-  m_loadedIds.clear();
-  m_rect.MakeEmpty();
-}
+  // TODO (@y, @m): replace this naive score by p-values on
+  // multivariate Gaussian.
+  double const distance = MercatorBounds::DistanceOnEarth(item.m_center, m_pt);
 
-void LocalityFinder::Cache::GetLocality(m2::PointD const & pt, string & name)
-{
-  ++m_usage;
-  m_tree.ForEachInRectEx(m2::RectD(pt, pt), DoSelectLocality(name, pt));
+  double const score =
+      ftypes::GetPopulationByRadius(distance) / static_cast<double>(item.m_population);
+  if (score < m_bestScore)
+  {
+    m_bestScore = score;
+    m_name = item.m_name;
+  }
 }
 
-string DebugPrint(LocalityItem const & item)
+string DebugPrint(LocalityFinder::Item const & item)
 {
   stringstream ss;
-  ss << "Name = " << item.m_name << "Population = " << item.m_population << "ID = " << item.m_id;
+  ss << "Name = " << item.m_name << ", Center = " << DebugPrint(item.m_center)
+     << ", Population = " << item.m_population;
   return ss.str();
 }
 }  // namespace search
diff --git a/search/locality_finder.hpp b/search/locality_finder.hpp
index bef8c5b5be..913971ac90 100644
--- a/search/locality_finder.hpp
+++ b/search/locality_finder.hpp
@@ -7,52 +7,59 @@
 #include "geometry/rect2d.hpp"
 #include "geometry/tree4d.hpp"
 
-#include "std/set.hpp"
 #include "std/unique_ptr.hpp"
+#include "std/unordered_set.hpp"
 
 class Index;
 
 namespace search
 {
-struct LocalityItem
-{
-  LocalityItem(string const & name, uint32_t population, uint32_t id);
-
-  string m_name;
-  uint32_t m_population;
-  uint32_t m_id;
-};
+class VillagesCache;
 
 class LocalityFinder
 {
 public:
-  struct Cache
+  struct Item
   {
-    void Clear();
-    void GetLocality(m2::PointD const & pt, string & name);
+    Item(string const & name, m2::PointD const & center, uint32_t population);
 
-    m4::Tree<LocalityItem> m_tree;
-    set<uint32_t> m_loadedIds;
-    size_t m_usage = 0;
-    m2::RectD m_rect;
+    string m_name;
+    m2::PointD m_center;
+    uint32_t m_population;
   };
 
-  LocalityFinder(Index const & index);
+  LocalityFinder(Index const & index, VillagesCache & villagesCache);
 
   void SetLanguage(int8_t lang);
   void GetLocality(m2::PointD const & pt, string & name);
   void ClearCache();
 
 private:
-  void UpdateCache(Cache & cache, m2::PointD const & pt);
+  void LoadVicinity(m2::PointD const & pt);
 
   Index const & m_index;
-  MwmSet::MwmId m_worldId;
+  VillagesCache & m_villagesCache;
   unique_ptr<RankTable> m_ranks;
 
-  Cache m_caches[10];
+  m4::Tree<bool> m_coverage;
+  m4::Tree<Item> m_localities;
+  map<MwmSet::MwmId, unordered_set<uint32_t>> m_loadedIds;
+
   int8_t m_lang;
 };
 
-string DebugPrint(LocalityItem const & item);
+class LocalitySelector
+{
+public:
+  LocalitySelector(string & name, m2::PointD const & pt);
+
+  void operator()(LocalityFinder::Item const & item);
+
+private:
+  string & m_name;
+  m2::PointD m_pt;
+  double m_bestScore;
+};
+
+string DebugPrint(LocalityFinder::Item const & item);
 }  // namespace search
diff --git a/search/processor.cpp b/search/processor.cpp
index 4c96b0c704..e076df2e96 100644
--- a/search/processor.cpp
+++ b/search/processor.cpp
@@ -147,10 +147,14 @@ Processor::Processor(Index const & index, CategoriesHolder const & categories,
   , m_minDistanceOnMapBetweenResults(0.0)
   , m_mode(Mode::Everywhere)
   , m_suggestsEnabled(true)
-  , m_ranker(index, infoGetter, m_emitter, categories, suggests,
+  , m_supportOldFormat(false)
+  , m_viewportSearch(false)
+  , m_villagesCache(static_cast<my::Cancellable const &>(*this))
+  , m_ranker(index, infoGetter, m_emitter, categories, suggests, m_villagesCache,
              static_cast<my::Cancellable const &>(*this))
   , m_preRanker(index, m_ranker, kPreResultsCount)
-  , m_geocoder(index, infoGetter, m_preRanker, static_cast<my::Cancellable const &>(*this))
+  , m_geocoder(index, infoGetter, m_preRanker, m_villagesCache,
+               static_cast<my::Cancellable const &>(*this))
 {
   // Initialize keywords scorer.
   // Note! This order should match the indexes arrays above.
diff --git a/search/processor.hpp b/search/processor.hpp
index 9ce7f8de9c..0aa694a3af 100644
--- a/search/processor.hpp
+++ b/search/processor.hpp
@@ -1,4 +1,6 @@
 #pragma once
+#include "search/categories_cache.hpp"
+#include "search/categories_set.hpp"
 #include "search/emitter.hpp"
 #include "search/geocoder.hpp"
 #include "search/mode.hpp"
@@ -176,6 +178,8 @@ protected:
 protected:
   bool m_viewportSearch;
 
+  VillagesCache m_villagesCache;
+
   Emitter m_emitter;
   Ranker m_ranker;
   PreRanker m_preRanker;
diff --git a/search/ranker.cpp b/search/ranker.cpp
index 1c308b24dc..9c2b5d2c58 100644
--- a/search/ranker.cpp
+++ b/search/ranker.cpp
@@ -279,10 +279,11 @@ size_t const Ranker::kBatchSize = 10;
 
 Ranker::Ranker(Index const & index, storage::CountryInfoGetter const & infoGetter,
                Emitter & emitter, CategoriesHolder const & categories,
-               vector<Suggest> const & suggests, my::Cancellable const & cancellable)
+               vector<Suggest> const & suggests, VillagesCache & villagesCache,
+               my::Cancellable const & cancellable)
   : m_reverseGeocoder(index)
   , m_cancellable(cancellable)
-  , m_locality(index)
+  , m_localities(index, villagesCache)
   , m_index(index)
   , m_infoGetter(infoGetter)
   , m_emitter(emitter)
@@ -342,7 +343,7 @@ Result Ranker::MakeResult(PreResult2 const & r) const
   if (ftypes::IsLocalityChecker::Instance().GetType(r.GetTypes()) == ftypes::NONE)
   {
     string city;
-    m_locality.GetLocality(res.GetFeatureCenter(), city);
+    m_localities.GetLocality(res.GetFeatureCenter(), city);
     res.AppendCity(city);
   }
 
@@ -547,6 +548,6 @@ void Ranker::UpdateResults(bool lastUpdate)
 
 void Ranker::ClearCaches()
 {
-  m_locality.ClearCache();
+  m_localities.ClearCache();
 }
 }  // namespace search
diff --git a/search/ranker.hpp b/search/ranker.hpp
index b4e0687315..0f1950f37b 100644
--- a/search/ranker.hpp
+++ b/search/ranker.hpp
@@ -34,6 +34,7 @@ class CountryInfoGetter;
 
 namespace search
 {
+class VillagesCache;
 class Emitter;
 class PreResult2Maker;
 
@@ -73,7 +74,7 @@ public:
 
   Ranker(Index const & index, storage::CountryInfoGetter const & infoGetter, Emitter & emitter,
          CategoriesHolder const & categories, vector<Suggest> const & suggests,
-         my::Cancellable const & cancellable);
+         VillagesCache & villagesCache, my::Cancellable const & cancellable);
   virtual ~Ranker() = default;
 
   void Init(Params const & params, Geocoder::Params const & geocoderParams);
@@ -97,7 +98,7 @@ public:
 
   void ClearCaches();
 
-  inline void SetLocalityFinderLanguage(int8_t code) { m_locality.SetLanguage(code); }
+  inline void SetLocalityFinderLanguage(int8_t code) { m_localities.SetLanguage(code); }
 
   inline void SetLanguage(pair<int, int> const & ind, int8_t lang)
   {
@@ -131,7 +132,7 @@ private:
   my::Cancellable const & m_cancellable;
   KeywordLangMatcher m_keywordsScorer;
 
-  mutable LocalityFinder m_locality;
+  mutable LocalityFinder m_localities;
 
   Index const & m_index;
   storage::CountryInfoGetter const & m_infoGetter;
diff --git a/search/search.pro b/search/search.pro
index eadec170f1..8d747347aa 100644
--- a/search/search.pro
+++ b/search/search.pro
@@ -12,6 +12,7 @@ HEADERS += \
     algos.hpp \
     approximate_string_match.hpp \
     cancel_exception.hpp \
+    categories_cache.hpp \
     categories_set.hpp \
     cbv.hpp \
     common.hpp \
@@ -81,6 +82,7 @@ HEADERS += \
 
 SOURCES += \
     approximate_string_match.cpp \
+    categories_cache.cpp \
     cbv.cpp \
     displayed_categories.cpp \
     downloader_search_callback.cpp \
diff --git a/search/search_integration_tests/pre_ranker_test.cpp b/search/search_integration_tests/pre_ranker_test.cpp
index 50094d1c4e..b67ce9488c 100644
--- a/search/search_integration_tests/pre_ranker_test.cpp
+++ b/search/search_integration_tests/pre_ranker_test.cpp
@@ -1,5 +1,6 @@
 #include "testing/testing.hpp"
 
+#include "search/categories_cache.hpp"
 #include "search/emitter.hpp"
 #include "search/intermediate_result.hpp"
 #include "search/model.hpp"
@@ -44,9 +45,10 @@ class TestRanker : public Ranker
 {
 public:
   TestRanker(TestSearchEngine & engine, Emitter & emitter, vector<Suggest> const & suggests,
-             my::Cancellable const & cancellable, vector<PreResult1> & results)
+             VillagesCache & villagesCache, my::Cancellable const & cancellable,
+             vector<PreResult1> & results)
     : Ranker(static_cast<Index const &>(engine), engine.GetCountryInfoGetter(), emitter,
-             GetDefaultCategories(), suggests, cancellable)
+             GetDefaultCategories(), suggests, villagesCache, cancellable)
     , m_results(results)
   {
   }
@@ -111,7 +113,8 @@ UNIT_CLASS_TEST(PreRankerTest, Smoke)
 
   vector<PreResult1> results;
   Emitter emitter;
-  TestRanker ranker(m_engine, emitter, m_suggests, m_cancellable, results);
+  VillagesCache villagesCache(m_cancellable);
+  TestRanker ranker(m_engine, emitter, m_suggests, villagesCache, m_cancellable, results);
 
   PreRanker preRanker(m_engine, ranker, pois.size());
   PreRanker::Params params;
diff --git a/search/search_tests/locality_finder_test.cpp b/search/search_tests/locality_finder_test.cpp
index 3a615fe2c4..eb5847b6b5 100644
--- a/search/search_tests/locality_finder_test.cpp
+++ b/search/search_tests/locality_finder_test.cpp
@@ -4,6 +4,7 @@
 #include "indexer/index.hpp"
 #include "indexer/classificator_loader.hpp"
 
+#include "search/categories_cache.hpp"
 #include "search/locality_finder.hpp"
 
 #include "platform/country_file.hpp"
@@ -11,21 +12,30 @@
 #include "platform/local_country_file_utils.hpp"
 #include "platform/platform.hpp"
 
+#include "base/cancellable.hpp"
 
 namespace
 {
+struct TestWithClassificator
+{
+  TestWithClassificator() { classificator::Load(); }
+};
 
-class LocalityFinderTest
+class LocalityFinderTest : public TestWithClassificator
 {
   platform::LocalCountryFile m_worldFile;
+
   Index m_index;
+
+  my::Cancellable m_cancellable;
+  search::VillagesCache m_villagesCache;
+
   search::LocalityFinder m_finder;
   m2::RectD m_worldRect;
 
 public:
-  LocalityFinderTest() : m_finder(m_index)
+  LocalityFinderTest() : m_villagesCache(m_cancellable), m_finder(m_index, m_villagesCache)
   {
-    classificator::Load();
     m_worldFile = platform::LocalCountryFile::MakeForTesting("World");
 
     try
diff --git a/search/search_tests/locality_selector_test.cpp b/search/search_tests/locality_selector_test.cpp
new file mode 100644
index 0000000000..53c7659cf4
--- /dev/null
+++ b/search/search_tests/locality_selector_test.cpp
@@ -0,0 +1,52 @@
+#include "testing/testing.hpp"
+
+#include "search/locality_finder.hpp"
+
+using namespace search;
+
+namespace
+{
+string GetMatchedCity(m2::PointD const & point, vector<LocalityFinder::Item> const & items)
+{
+  string name;
+  LocalitySelector selector(name, point);
+  for (auto const & item : items)
+    selector(item);
+  return name;
+}
+
+// TODO (@y): this test fails for now. Need to uncomment it as soon as
+// locality finder will be fixed.
+//
+// UNIT_TEST(LocalitySelector_Test1)
+// {
+//   auto const name = GetMatchedCity(
+//       m2::PointD(-97.563458662952925238, 26.796728721236661386),
+//       {{"Matamoros", m2::PointD(-97.506656349498797454, 26.797180986068354969), 10000},
+
+//        {"Brownsville", m2::PointD(-97.489103971612919963, 26.845589500139880101), 180663}});
+//   TEST_EQUAL(name, "Matamoros", ());
+// }
+
+UNIT_TEST(LocalitySelector_Test2)
+{
+  vector<LocalityFinder::Item> const localities = {
+      {"Moscow", m2::PointD(37.617513849438893203, 67.45398133444564337), 11971516},
+      {"Krasnogorsk", m2::PointD(37.340409438658895169, 67.58036703829372982), 135735},
+      {"Khimki", m2::PointD(37.444994145035053634, 67.700701677882875629), 240463},
+      {"Mytishchi", m2::PointD(37.733943192236807818, 67.736750571340394345), 180663},
+      {"Dolgoprudny", m2::PointD(37.514259518892714595, 67.780738804428438016), 101979}};
+
+  {
+    auto const name =
+        GetMatchedCity(m2::PointD(37.538269143836714647, 67.535546478148901883), localities);
+    TEST_EQUAL(name, "Moscow", ());
+  }
+
+  {
+    auto const name =
+        GetMatchedCity(m2::PointD(37.469807099326018829, 67.666502652067720192), localities);
+    TEST_EQUAL(name, "Khimki", ());
+  }
+}
+}  // namespace
diff --git a/search/search_tests/search_tests.pro b/search/search_tests/search_tests.pro
index b08d6416e4..2bd4c2eddd 100644
--- a/search/search_tests/search_tests.pro
+++ b/search/search_tests/search_tests.pro
@@ -27,6 +27,7 @@ SOURCES += \
     latlon_match_test.cpp \
     locality_finder_test.cpp \
     locality_scorer_test.cpp \
+    locality_selector_test.cpp \
     nearby_points_sweeper_test.cpp \
     query_saver_tests.cpp \
     ranking_tests.cpp \