Explicitly add some folks who might know about chrome://predictors.

(By the way, is there a component I should be using here?)

Am I right that you're talking about the "Autocomplete Action Predictor" tab in chrome://predictors? I believe that the "Resource Prefetch Predictor" db correctly deletes entries that were deleted from the history.
I'll take a look at the autocomplete predictor.

We don't have a special bug component for predictors.

Yes, this only affects autocomplete predictors and not resource prefetch predictors.

Okay, I know what's going on. 

The AutocompleteActionPredictor actually implements HistoryServiceObserver::OnURLsDeleted() but the predictor deletes only the rows that fully match URLs that were removed from the history. However, the autocomplete predictor's database is also populated by autocomplete results that are related to the page the user just visited but don't match any entry in the history.

So, for example, when I type "facebook.com" in the omnibox, the database gets the following URLs:
http://www.facebook.com/
https://www.google.fr/search?q=facebook.com&oq=facebook.com&aqs=chrome..5j61i53j1l4&sourceid=chrome&ie=UTF-8
http://facebook.com/device
http://facebook.com/help/delete_account
http://www.facebook.com/recover.php

Later when I'm deleting the http://www.facebook.com/ entry from the history this URL will be also deleted from the autocomplete database, but all other URLs that I've never visited will stay.

I agree this is a problem because this way we reveal what the user has typed in the omnibox.

The AutocompletePredictor already has a function that deletes all entries that aren't present in the history. But this function is currently called only during the startup. I think we should just call it every time after the user deletes something in the history.

I'll go ahead and send a CL.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c2a4bcefb464c1e9b1885a442b7017b1e87afc6b

commit c2a4bcefb464c1e9b1885a442b7017b1e87afc6b
Author: Alexandr Ilin <alexilin@chromium.org>
Date: Mon May 14 15:56:55 2018

predictors: Clean up the predictor db after deleting individual urls

The autocomplete predictor database contains entries related to a page the user
has visited even after this page was removed from the history. These entries
are cleaned up after only the startup. This CL adds this clean up after every
removal from history.

Bug:  838897 
Change-Id: Ia56de868cddf8bb0a28d288265b884c0e67458d5
Reviewed-on: https://chromium-review.googlesource.com/1043868
Commit-Queue: Alexandr Ilin <alexilin@chromium.org>
Reviewed-by: Benoit L <lizeb@chromium.org>
Reviewed-by: Christian Dullweber <dullweber@chromium.org>
Cr-Commit-Position: refs/heads/master@{#558326}
[modify] https://crrev.com/c2a4bcefb464c1e9b1885a442b7017b1e87afc6b/chrome/browser/predictors/autocomplete_action_predictor.cc
[modify] https://crrev.com/c2a4bcefb464c1e9b1885a442b7017b1e87afc6b/chrome/browser/predictors/autocomplete_action_predictor.h
[modify] https://crrev.com/c2a4bcefb464c1e9b1885a442b7017b1e87afc6b/chrome/browser/predictors/autocomplete_action_predictor_unittest.cc