Self-driving cars typically depend on high-definition (HD) maps for computing a driving strategy at areas inside and outside their field of view. Data in HD maps, however, can be outdated and erroneous. It is therefore of critical importance to validate this information before its use. We propose two complementary approaches for online map validation which promise sufficient performance for being effectively used on board in series production cars. The first approach builds a model-based framework. The second utilizes deep similarity learning.