The PvS-Index: An Indexing Method for Local Image Descriptors

Abstract

In the last twenty years the problem of finding near neighbours to a specified data point in high dimensional space has become of increasing interest to the database community, especially in the context of Time series and Multimedia data. First approaches, published in the 1980s and the early 90s have shown to work very well for up to 12 and in selected cases up to 20 dimensions. In higher dimensional spaces, the performance of these indexing structures degraded drastically, making a sequential scan still the best choice in respect of performance.In this thesis I present the PvS-Index, a new approximate indexing technique for this kind of high dimensional data. Due to its low calculation-cost and a fixed amount of I/O operations it provides a good evaluation time independent from the actual size of the collection. When applying this PvS-Index to the problem of image copyright protection using local descriptors, my measurements showed a performance gain of several orders of magnitude in comparison with a sequential scan through the whole data set.

Á síðustu tveimur áratugum hefur áhuginn á því að finna næstu nágranna fyrirspurnapunkta í margvíðu rúmi vakið áhuga rannsakenda í gagnasafnsfræði, sér í lagi í tengslum við tímaraðir og margmiðlunargögn. Fyrstu aðferðirnar, sem birtust á níunda og snemma á tíunda áratug síðustu aldar, hafa virkað vel upp að 12 víddum, og jafnvel 20 víddum í sérstökum tilfellum. Með fleiri víddum versna afköst þessarra aðferða hins vegar hratt, þannig að runuleit gegnum allt gagnasafnið verður hraðvirkasta leitaraðferðin.Í þessari meistararitgerð kynni ég PvS-vísinn, sem er nýr vísir fyrir nálgunarfyrirspurnir í margvíð gögn. Vegna lítils reiknikostnaðar og fasts diskakostnaðar gefur PvS-vísirinn góðan svartíma, sem er óháður stærð gagnasafnsins. Niðurstöður mínar sýna að þegar PvS-vísinum er beitt við höfundarréttarvörn fyrir stafrænar myndir, með því að nota staðværa lýsinga, þá eru afköst nokkrum stærðargráðum betri en með runuleit gegnum allt gagnasafnið.